 |
DSA711S - DATA STRUCTURES AND ALGORITHMS 2 - 2ND OPP - JULY 2024 |
|
|
1 Page 1 |
▲back to top |
nAmlBIA unlVERSITY
OF SCIEnCE Ano TECHn
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENTOF SOFTWAREENGINEERING
QUALIFICATION:BACHELOROF COMPUTERSCIENCE
QUALIFICATIONCODE:07BCMS
COURSE:DATASTRUCTURESAND ALGORITHMS2
DATE:JULY2024
DURATION: 2 HOURS
LEVEL:7
COURSECODE:DSA711S
PAPER:THEORY
MARKS: 90
SECONDOPPORTUNITY/ SUPPLEMENTARYEXAMINATION QUESTION PAPER
EXAMINER(S)
Mr S. TJIRASO
MODERATOR:
MRS P. DOLIAN
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly
THIS QUESTIONPAPERCONSISTSOF 9 PAGES
(Including this front page)
PERMISSIBLE MATERIALS
1. NON-PRGRAMMABLE CALCULATOR
|
|
2 Page 2 |
▲back to top |
SECTIONA: Multiple Choice Questions
• Answer all the questions in the provided booklet.
• The section consists of 10 problems.
[20 Marks]
Problem Al
What is a hash table?
A. A structure that maps values to keys
B. A structure used for storage
c.structure that maps keys to values
D. None of the above
[2 Marks]
Problem A2
Which of the following statements is true?
[2 Marks]
Statement A: Dynamic programming is an optimization technique.
Statement B: NOT all recursive problems can be implemented iteratively.
A. Statement A is true, and Statement B is false.
B. Statement A is false, and statement B is true.
C. Both Statement A and Statement Bare true.
D. Both Statement A and Statement Bare false.
Problem A3
When several elements/values are competing for the same bucket in the hash
table, what is it called?
[2 Marks]
A. Tabulation
B. Replication
C. Duplication
D. None of the above
Problem A4
Study the code snippet below and answer the questions that follows.
int countDown(int number)
if(number== O)
return O;
return (number% 10 + countDown(number / 10));
}
1
|
|
3 Page 3 |
▲back to top |
What is the output of the function countDown if the input; number=2945?
A. Function will generate an error
B. 2945
C. 2
D.9
E.20
F.5
G. None of the above
[2 Marks]
Problem AS
Which of the following algorithm can be designed using recursion?
A. Factorial of a number n
B. Tower of Hanoi
C. Fibonacci Series
D. All of the above
[2 Marks]
Problem A6
A binary search tree is constructed by inserting the following elements in order:
60 25 72 15 30 68 100 13 18 47 70. How many number of left subtree nodes?
[2 Marks]
A. 3
B.5
C. 7
D.6
Problem A7
What would be the worst case complexities of inserting the name Abel, deleting the
name: Abel and searching for the name: Abel in the Binary Search tree below?
[2 Marks]
2
|
|
4 Page 4 |
▲back to top |
A. O(log n) for all operation; insertion, Searching and deletion
B. 0( n ) for insertion and searching, O(log n) deletion
C. 0( n ) for all operation; insertion, Searching and deletion
D. 0( n ) for insertion and deletion, O(log n) searching
Problem AB
Study the BSTbelow and answer the question that follow;
If we compute; zh- 1: where h is "height",what are we computing or trying to find out? (2
Marks]
A. 3
B. Minimum number of nodes in tree
C. 2
D. Minimum number of internal nodes in tree
E. Maximum number of nodes in tree
F. 4
G. Minimum height
3
|
|
5 Page 5 |
▲back to top |
H. Invalid computation
I. Maximum number of leaf nodes in tree
J. Maximum number of internal nodes in tree
K. Maximum height
L. Minimum number of leaf nodes in tree
Problem A9
The operation for visiting each node in the data structure is known as......
A. inserting
B. Merging
C. Sorting
D. Traversal
Problem AlO
Which traversal algorithm is satisfying the following order?
1 - Go left and perform x
2 - Perform an action on current node
3 - Go right and perform x
HINT: xis the name of the traversal being performed
A. PostOrder
B. PreOrder
C. lnOrder
D. None of the above
(2 Marks]
(2 Marks)
4
|
|
6 Page 6 |
▲back to top |
SECTION 8: True and FalseQuestions
• Answer all the questions in the provided booklet.
• The section consists of 10 problems.
(20 Marks]
Problem 131
A recursive function without a base case will not result in an infinite loop.
(2 Marks]
Problem 82
The head of a singly-linked always points to the first node.
[2 Marks]
Problem B3
The postorder traversal processes the left subtree first, then the root, and finally the right
subtree.
(2 Marks]
Problem B4
Hashing is aimed at achieving searches, deletions and insertions in 0(1).
[2 Marks]
Problem 85
Two distinct keys hashing to the same index is known as collision.
(2 Marks]
Problem B6
When inserting data into a dynamic queue with data already in it, the only pointer that needs
to be updated is the rear pointer, which is set to point to the new node.
(2 Marks]
Problem 87
When inserting data into a dynamic queue with data already in it, the only pointer that needs
to be updated is the rear pointer, which is set to point to the new node.
(2 Marks]
5
|
|
7 Page 7 |
▲back to top |
Problem B8
Based on the AVL trees studied, the tree below is an AVL tree.
[2 Marks)
Problem B9
A Red-black tree is a type of Binary Search tree.
Problem B10
A Red-black tree has a linear height.
[2 Marks]
[2 Marks]
6
|
|
8 Page 8 |
▲back to top |
SECTIONC: Structured questions
• Answer all the questions in the provided booklet.
• The section consists of 6 problems.
[SOIVlarks]
Problem Cl
HuffmanCodingis a technique of compressing data to reduce its size without losing any of the details. Some of the
benefits of compressing data are that it can be transmitted faster over the network and can reduce "data" costs for
mobile subscribers for example. Huffman Coding is one of many examples of binary tree applications.
Suppose we have the following data compression table;
Character
Frequency
B
1
C
4
D
2
Code
00
1
01
Code Length
2
1
2
Task:
a) Redraw the Huffman tree for the above table.
(12 marks]
b) What is the total size of the string as it is or before compression (in bits)?
c) What is the size of the encoded string?
[4 marks]
(4 marks]
Problem C2
What is the time complexity of the following function?
void Myfunction(int n) {
for(int i=O;i < n; i++) {
for(int j=O;j < 5; j++) {
for(int k=O; k < n; k++) {
for(int m=O; m < 5; m++) {
System.out.println("DSA711S Exam");
} } }}
[4 marks)
7
|
|
9 Page 9 |
▲back to top |
Problem C3
Constructs an AVL tree for the following elements: 45, 70, 35, 74, 25, 81, 60 inserted in that order. [4
marks)
Problem C4
What is the time complexity of the function below?
void Myfunction(int n) {
for(int i=0; i < 5; i++) {
for{int j=0; j < 5; j++) {
for(int k=0; k < n; k++) {
for(int m=0; m < 5; m++) {
System.out.println("DSA711S Exam");
}}} }
[4 marks]
Problem CS
Name and briefly explain any four (4) properties of red-black tree.
[8 marks]
Problem C6
When given a recursive problem and you are required to write a recursive function to solve it, what are
the most important information you need to know about recursive functions that will assist you in
successfully writing one?
[10 marks)
******* * ***** ** ** ***** * ***** End of Exam***********************************
8