 |
DSA711S - DATA STRUCTURES AND ALGORITHMS 2 - 1ST OPP - JUNE 2025 |
|
|
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 SOFTWAREENGINEERING
QUALIFICATION: BACHELOROF COMPUTERSCIENCE
QUALIFICATIONCODE:07BCHS
LEVEL: 7
COURSE:DATA STRUCTURESAND ALGORITHMS2
COURSECODE:DSA711S
DATE:MAY 2025
PAPER:THEORY
DURATION: 2 HOURS
MARKS: 100
FIRSTOPPORTUNITYEXAMINATION QUESTIONPAPER
EXAMINER
PROF AMBROSE AZETA
MODERATOR:
MRS P. DOLIAN
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly.
THIS QUESTION PAPERCONSISTSOF 4 PAGES
(Including this front page)
PERMISSIBLEMATERIALS
1. NON-PROGRAMMABLECALCULATOR
1
|
|
2 Page 2 |
▲back to top |
SECTIONA: TRUE OR FALSE
This section consists of 15 questions. Answer all the questions
Each correct answer is allocated 2 Marks
Write True or False for Questions 1 to 15.
Al: The worst-case running time for deletion in a balanced search Tree is O{log n).[2 Marks]
A2: An AVL tree is a binary search tree in which the heights of the left and right subtrees of
every node differs by at most 2
[2 Marks]
A3: Insertion in an AVL tree starts with a regular binary search tree insertion, followed by
rebalancing.
[2 Marks]
A4: BSTscan be used to implement priority queues.
[2 Marks]
AS: AVL tree is a self-balancing Binary Search Tree (BST)where the difference between the
heights of left and right subtrees cannot be more than 1 for all the nodes. This difference is
called the Balance Factor {BF).
[2 Marks)
A6: The time complexity of KMP algorithm for pattern matching is O(m+n)
[2 Marks)
A7: Deletion in an AVL tree starts with a regular binary search tree deletion, followed by
rebalancing.
[2 Marks]
A8: in a binary tree, every node will always have O or 1 children/sons.
[2 Marks]
A9: B-tree and AVL tree have the same worst case time complexity for insertion and deletion.
[2 Marks]
AlO: In pattern matching, the output of the input statement:
txt[] = "AAAAAAAAAAAAAAAAABp"a,t[]= "AAAAB"is: 14
[2 Marks]
All: One of the methods of resolving collision in hashing is linear probing
[2 Marks]
A12: One of the examples of probabilistic data structures is bloom filters
[2 Marks]
A13: Operations of binary search trees does not include: Insert
[2 Marks]
A14: The binary search algorithm finds an item on a sorted list by repeatedly discarding half
of the list.
[2 Marks]
AlS: 2-8° Search Trees is a type of tree in Data Structures
[2 Marks]
SECTION8: MULTIPLECHOICEQUESTIONS(MCQs)
This section consists of 20 MCQs. Answer all the questions
Select only one option, each correct answer is allocated 2 Marks
Bl: The best-case time complexity for search, insertion, and deletion in an AVL tree is:
A. O{log n)
B. O(n)
C. Log (n)
D. Log {On)
Study Figure 1, Algorithm a and b, and use them to answer questions from 82 to 813
3
11
Figure 1-Binary Search Tree
...
public static void main(String[] args) {
II Creating the object of Tree class
Tree bt = new Tree();
bt.root= new Node(l00);
bt.root.left= new Node(90);
bt.root.right= new Node(110);
bt.root.left.left= new Node(80);
bt.root.left.right= new Node(95);
bt.root.right.left= new Node(89);
}
Algorithm a
If total Nodes=3 and Nodel = Imbalance
Right Rotate Nodes 2 and 3;
If total Nodes=3 and Nodel = Imbalance:
For Node j = 1 to 3
Left Rotate Node j
End
Endif
Endif
Algorithm b
|
|
3 Page 3 |
▲back to top |
82: In Figure 1 above, when the root node 8 is deleted, the new root node will be either:
A. 9 or 3
B. 4 or 10 C. 3 or 12
D. 9 or 5
83: In Figure 1 above, what is the height of the tree?
A. 1
B. 6
C.3
D.4
84: In Figure 1 above, the successor of Node 12 is
A. 3
B. 4
C. 11
D. 9
BS: In Figure 1 above, is the tree a balanced BST?
Yes or No
86: If node 9 is deleted, will the BSTin Figure 1 be an AVL Tree? Yes or No
87: If node 3 and 5 are deleted, will the BSTin Figure 1 above be an AVL Tree? Yes or No
88. Figure 1 is a valid 2-3 Tree?
Yes or No
89. The height of Node 10 in Figure 1 is A. 2
B. 0
C. 1
D. -1
810. The sibling of 9 in Figure 1 is
A. 10
B5
C. 12
D. 11
811. Postorder of the Tree in Figure 1 gives:
A. 8,4,3,5,10,9,12,11 _B. 3,5,4,9,11,12,10,8 C. 3,4,5,8,9,10,11,12 D. 8,4,10,3,5,9,12,11
812. The implementation of Algorithm a, gives:
A. Binary Search Tree B. Binary Tree
C. AVL Tree
D. Namty Tree
813. The AVL deletion in Algorithm b, handles:
A. RIGHT-LEFTRotation B. LEFT-Rotation RIGHT-Rotation D. None
814: If at anytime a BSTis not balanced, to restore the properties of 2-3 B Trees, re-balancing is
done using
A. Rotation
B. Rotation and/or Exchange of colour red/black
C. Upward Promotion and/or Splitting D. None
815: If at any time a BSTis not balanced, to restore the properties of AVL Trees, re-balancing is
done using
A. Rotation
B. Rotation and/or Exchange of colour red/black
C. Upward Promotion and/or Splitting D. None
816: If at anytime a BSTis not balanced, to restore the properties of Red-Black Trees, re-balancing is
done using
A. Rotation
B. Rotation and/or Exchange of colour red/black
C. Upward Promotion and/or Splitting D. None
817: A function is called recursion
A. If it accepts a variable in high-level language
B. If it calls itself
C. If it translates assembly language into machine language D. None of the mentioned
818: The property that "The root and leaves (nil) are black" applies to
A. BST
B. Binary tree
C. AVL
D. red-black trees
819: In a 2-3 tree, what is the maximum number of keys/elements a node can have?
A. 2
B. 1
C.3
D.4
820: One of the following is the result of factorial (n) or n ! where n = 3
A. 2
B. 24
C. 6
D. 120
3
|
|
4 Page 4 |
▲back to top |
SECTION C: STRUCTURED/THEORY QUESTIONS
This section consists of 3 questions. Answer ALLthe questions
Each correct answer is allocated 10 Marks
Question One [10 Marks]
(A} Show how Hashing can be used to store the following elements: 74, 77, 65, using a
Hash table of size 7.
(S Marks)
(i} Describe what happens when you want to insert a new element 44.
(ii} Use two methods - chaining and linear probing to resolve any collision in (i} above.
(B} Using dynamic programming approach, write a function in Java that will print the
first 10 numbers of Fibonacci series as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
(S Marks)
Question Two [10 Marks]
(A} Show the steps in inserting the following elements in a Red-Black Tree: 10, 18, 7 (5 Marks)
(B} Show the insertion of the following elements in a 2-3 Tree: 50 60 70 40 30 (5 Marks)
Question Three [10 Marks]
(A) (i} In pattern matching, give the output of the below statements and explain how
naive search algorithm was used to derive the output
(2 Marks)
Input: text= "aabaacaadaabaaba",
pattern = "aaba"
(ii} Create by inserting the elements: 5, 7, 3, 70, 40, 83, in a 2-3 B Tree one after the another.
The final tree should look like the figure below.
(3 Marks)
{B} (i}Briefly explain the KMP Algorithm for Pattern Matching with example(s) (1 Mark)
(ii) Briefly define Dynamic Programming
(1 Mark)
(iii} Create and insert the elements below in a BST: 28, 22, 8
Is the BSTan AVL? If yes, then stop and do nothing.
If No, then do re-balancing using ROTATION
(3 Mark)
--THE
END
4
|
|
5 Page 5 |
▲back to top |
n Am I BI A u n IVER s ITY
OF SCIEnCE Ano TECHnOLOGY
FACULTYOF COMPUTING AND INFORMATICS
DEPARTMENTOF SOFTWAREENGINEERING'·
QUALIFICATION: BACHELOROF COMPUTERSCIENCE
QUALIFICATIONCODE:07BCMS
LEVEL~7
COURSE:DATA STRUCTURESAND ALGORITHMS,2
di I' .
I
'·1
DATE:MAY 2025
COURSECbDE: DSA711S
I'
DURATION: 2 HOURS
MARl<S:100
FIRSTOPPORTUNITYEXAMINATION QUESTION PAPERMEMORANDUM
q
EXAMINER
1 PROFAMBROSEAZETA
I,
MODERAJ©R:
l
MRS P. DOLIAN
,I ,
' 'I I •
·,
. 11,
THIS MEMO' RANl, DUM PAPERCONSISTSOF 10 PAGES
(Including this front page)
INSTRUCTIONSTO MODERATOR/FIRSTEXAMINER
1. Please use the memorandum or sample solutions to guide your marking.
2. When marking questions you should be guided by the allocation of marks.
3. Sample answers or solutions appear in bold.
4. Reasonable, in depth or innovative correct solutions provided by the students should be
allocated marks even though not provided in this memorandum
5. All things that should not be marked, e.g. any "rough work", have to be crossed out
unambiguously
1