 |
DSA711S - DATA STRUCTURES and ALGORITHMS 2 - 1ST OPP - JUNE 2022 |
|
|
1 Page 1 |
▲back to top |
n Am I BI A u n IVER s ITY
OF SCIEnCE Ano TECHnOLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENTOF COMPUTERSCIENCE
QUALIFICATION: BACHELOROF COMPUTERSCIENCE,BACHELOROF INFORMATICS
QUALIFICATION CODE: 07BCMS, 07BAIT
LEVEL: 7
COURSE: DATA STRUCTURESAND ALGORITHMS 2
COURSE CODE: DSA711S
DATE: JUNE 2022
PAPER: THEORY
DURATION: 2 HOURS
MARKS: 60
FIRST OPPORTUNITY EXAMINATION QUESTION PAPER
EXAMINER(S)
MODERATOR:
Mr. S TJIRASO
Mr. R MUSUTUA
Mr. L HAINGURA
INSTRUCTIONS
1. Answer ALLthe questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly
THIS QUESTION PAPER CONSISTS OF 4 PAGES
(Including this front page)
1
|
|
2 Page 2 |
▲back to top |
Question 1: [Multiple choice Questions -8 Marks]
1.1 Which of the following tree traversal technique visits root node first?
A. lnOrder Traversal
B. PostOrder Traversal
C. PreOrder Traversal
D. Level Order Traversal
1.2 A binary tree has n levels where level zero is the level of the root. And n denotes the last level.
Given that the root has only one child, what is the minimum number of leaves of level n of the
tree
A. 0
B. 1
C. -1
D. 4
1.3 Given a list of elements; 12, 16, 20, 27, 19 inserted into a data structure in that order. An
element is deleted using a basic data structure operation. If the deleted element is a 19 the
data structure can be a ?
A. Queue
B. Tree
C. Array
D. Stack
1.4 The following operations performed on a stack of size 5:
Push(DSA),pop(),push(ICG),push(DBF),pop(),push(OPS),pop,pop(),push(PRG)W. hich of the
following statement is correct?
A. Performed smoothly
B. Underflow
C. Overflow
D. Repeated operation
Question 2: [Stack/Queue/Linked-list -10 Marks]
2.1 Explain the difference between Queue and Stack? [4]
2.2 What do we call a condition that's occurs when a user try to remove an element from an
empty stack? [2]
2.3 Which of the following permutations can be obtained in the same order using a stack.
Assuming that input is the sequence. 5, 6, 7, 8, 9. In that order? [2]
i. 7, 8, 9, 5, 6
ii. 5, 9, 6, 7, 8
iii. 9, 8, 7, 5, 6
iv. 7, 8, 9, 6, 5
2.4 The following Five Namibian artist's names: The_Dogg, Gazza, TopCheri, Tate_Buti and
BigBen were pushed into a stack in that order. The stack is then popped out four names and
each name is inserted in a queue. The two names are deleted from the queue and pushed
back on the stack. Now one name is then popped from the stack. What is the popped name
of the artist? [2]
2
|
|
3 Page 3 |
▲back to top |
Question 3: [BST-12 Marks]
3. Study the Binary Search Tree below
3.1 Write down all the BSTtraversals below:
i. Preorder traversal [2]
ii. lnorder traversal [2]
iii. Postorder traversal [2]
3.2 Construct a BSTfor the elements: 9 8 12 16 10. Using post order traversal [6]
Question 4: [AVL Trees-18 Marks]
1.1 Study the AVL tree below and write down all possible insertions sequence that produce the
following result: [4]
1.2 To an empty AVL tree. Which of the insertions in a) achieve the balance without any
rotation?[2]
1.3 Is the AVL in a) is balance? state your reason with support the balancing factors involved [4]
1.4 Name and briefly explain any three types of AVL tree rotations [6]
1.5 Differentiate between BSTand AVL tree (2)
3
|
|
4 Page 4 |
▲back to top |
Question 5: [SPLAYTREE-12 Marks]
2. Study the Splay Tree below and answer the questions that follows:
2.1 You are tasked to search for the element 9 in picture above and reconstruct the new Splay Tree
after the search operation completed.[10]
2.2 State the type of Splay Tree rotation performed on the above search operation. Hint: [Zig, Zag,
Zig-Zag or Zag-Zig] [2]
******** ** *** ** *** ****** **** End of Exam***********************************
4