 |
DSA711S - DATA STRUCTURES and ALGORITHMS 2 - 2ND OPP - JULY 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: JULY 2022
DURATION: 2 HOURS
PAPER: THEORY
MARKS: 60
SECOND OPPORTUNITY /SUPPLEMENTARY 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 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.4
8. 12
C. 8
D. None of the above
1.2 Given a list of elements; 3, 12, 6,16,9 inserted into a data structure in that order. An element is
deleted using a basic data structure operation. If the deleted element is 9, the data structure
cannot be a
?
A. Queue
8. Tree
C. Graph
D. None of the above
1.3 Given the following tree. Give the Preorder traversal?
A. A8DHIECGFJ
8. HDl8EAFCJG
C. HIDEBFJFCA
D. A8DHIECFGJ
1.4 If the node to be deleted has
node's parent.
A. Only a left subtree
8. Only a right subtree
C. No children
D. Has no children
we delete the node and attach the left subtree to the deleted
2
|
|
3 Page 3 |
▲back to top |
Question 2: [Stack/Queue/Linked-list -11 Marks]
2.1 Define a Queue, mention various operations on Queue [3]
2.2 Define a graph. How is it different from a Tree ?[3]
2.3 Explain the concept of singly-linked list with example [3]
2.4 The following Five Soccer Players 'names3: Pogba, Messi, Mane, Ronalda and Salah 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 are names of players left in the
stack? [2]
Question 3: [BST-15 Marks]
3.1 Construct a Binary Search Tree (BST)for the following elements: 12, 76, 51, 96, 200, 100 82. Using
POSTORDERTraversal technique [7]
3.2 Mention any two operations on BST[2]
3.3 Use Insertion sort algorithm to sort the array below: 4,3,2,10,12,1,5,6. Show content for each step
[6]
Question 4: [AVLTrees -14 Marks]
1.1 Study the AVL tree below and write down any two possible insertions sequence that produce
the following result: [2]
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 [2]
1.4 Name and briefly explain the two types of AVL tree rotations [4]
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 13 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