 |
DSA711S - DATA STRUCTURES AND ALGORITHMS 2 - 2ND OPP - JULY 2023 |
|
|
1 Page 1 |
▲back to top |
nAmlBIA un1VERSITY
OF SCIEn CE Ano TECHn OLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENT OF SOFTWARE ENGINEERING
QUALIFICATION: BACHELOR OF COMPUTER SCIENCE
QUALIFICATION CODE: 07BCMS
COURSE: DATA STRUCTURESAND ALGORITHMS 2
DATE: JULY 2023
DURATION: 3 HOURS
LEVEL: 7
COURSE CODE: DSA711S
PAPER: THEORY
MARKS: 90
SECOND OPPORTUNITY/ SUPPLEMENTARY EXAMINATION 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 QUESTION PAPER CONSISTS OF 7 PAGES
{Including this front page)
PERMISSIBLE MATERIALS
1. NON-PRGRAMMABLE CALCULATOR
|
|
2 Page 2 |
▲back to top |
SECTION A: Multiple Choice Questions
• Answer all the questions in the provided booklet.
• The section consists of 10 questions.
Problem Al
Study the Binary Search Tree below.
[20 Marks]
What is the height of node 96?
A. 7
B. 82
C. 0
D. 2
[2 Marks]
Problem A2
Given an AVL tree of size n, what would be the maximum number of steps required to find a
node k placed anywhere in the tree?
[2 Marks]
E. O(e")
A. O(n)
B. O(log(n))
C. 0(1)
Problem A3
Given the BST below, what will be the value of height as returned by the function max? [2
marks]
20
1
|
|
3 Page 3 |
▲back to top |
height=max(height,, height,)+ 1
A. 1
B. 2
C. 0
D. None of the above
Problem A4
What is the depth of node 34 in the tree in Problem A3 above?
A. 0
B. 1
C. 2
D. None of the above
(2 Marks]
Problem AS
What is the height of node 60 in the tree in Problem A3 above?
A. 0
B. 1
C. 2
D. None of the above
(2 Marks]
Problem AG
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. 5
B. 7
C. 3
D. 6
Problem A7
A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 45,
46, 80, 56, 92, 19, 65 into a table indexed from Oto 6. What will be the location of key 19? (2
Marks]
A. 3
B. 6
C. 5
D. 4
Problem AB
Linear Probing is a conflict resolution technique in__ ?
A. Hashing
B. Searching
C. Queue
D. Sorting
(2 Marks]
2
|
|
4 Page 4 |
▲back to top |
Problem A9
Which of the following statement is correct with respect to pushing data onto stack data
structure?
[2 Marks)
A. Push(int data)
B. Push()
C. Pop(int data)
D. None of the above
Problem AlO
Which one of the following techniques is not used in the Binary tree?
A. lnorder traversal
B. Postorder traversal
C. Randomized traversal
D. Preorder traversal
[2 Marks)
3
|
|
5 Page 5 |
▲back to top |
SECTION B: True and False Questions
• Answer all the questions in the provided booklet.
• The section consists of 5 questions.
Problem Bl
A recursive function without a base case is equivalent to an infinite loop.
Problem B2
The head of a singly-linked always points to the last node.
Problem B3
Given the following recursive function;
[10 Marks]
[2 Marks]
[2 Marks]
The line below is the correct base and recurisve case(s) for the function.
Line: Base case is n == total and the recursive case total == n
Problem B4
Hashing is aimed at achieving searches, deletions and insertions in O(n).
Problem BS
Two distinct keys hashing to the same index is known as coalition.
[2 Marks]
[2 Marks]
[2 Marks]
4
|
|
6 Page 6 |
▲back to top |
SECTION C: Structured questions
• Answer all the questions in the provided booklet.
• The section consists of 5 questions.
Problem Cl
Study the Binary Search Tree below
34
[60 Marks]
60
Write down all its BSTtraversals output below:
i. Preorder traversal
ii. lnorder traversal
iii. Postorder traversal
iv. What is the depth of 60?
[2 Marks]
[2 Marks]
[2 Marks]
[2 Marks]
Problem C2
Explain the difference between recursion and iteration as problem-solving approaches?
[4 marks]
Problem C3
Construct a BSTfor the elements: 9, 8, 12, 16, 10, using post order traversal.
[10 marks]
Problem C4
Name and briefly explain any three types of AVL tree rotations
[6 marks]
Problem CS
Huffman Coding is 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.
5
|
|
7 Page 7 |
▲back to top |
Suppose the following string is to be sent over a network
IM IM 1 5 IE 1 5 1 5 IK I
Task:
a) What is the total size of the string as it is (in bits)?
[2 marks]
b) What is the average code length (ACL)of the compressed code?
[4 marks]
c) Apply Huffman Coding on the string and determine the Huffman tree, the code and code length of
each character.
[22 marks]
d) What is the size of the encoded string?
[4 marks]
* ** ******** ****** ** ********* End of Exam***********************************
6