 |
DSA711S - DATA STRUCTURES AND ALGORITHMS 2 - 1ST OPP - JUNE 2023 |
|
|
1 Page 1 |
▲back to top |
nAm I BIA unlVE RS ITV
OF SCIEnCE Ano TECHnDLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENT OF SOFTWARE ENGINEERING
QUALIFICATION: BACHELOR OF COMPUTER SCIENCE
QUALIFICATION CODE: 07BCMS
COURSE: DATA STRUCTURESAND ALGORITHMS 2
DATE: JUNE 2023
DURATION: 3 HOURS
LEVEL: 7
COURSE CODE: DSA711S
PAPER: THEORY
MARKS: 90
EXAMINER(S)
FIRST OPPORTUNlrY EXAMINATION QUESTION PAPER
MRS. 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
I. 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 questions.
Problem Al
Which one of the below mentioned data structures is a linear data structure?
A. Binary tree
B. Binary search tree
C. Graph
D. Queue
Problem A2
Which of the following statement(s) is true?
Statement A: A binary tree is always a binary search tree.
Statement B: A binary search tree is a graph.
A. Statement A is true, and statement Bis false.
B. Statement A is false, and statement Bis true.
C. Both statement A and statement B are true.
D. Both statement A and statement Bare false.
Problem A3
Which of the following statement(s) is true?
Statement A: All trees are graphs.':
Statement B: Not all graphs are trees.
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 B are false.
[20 Marks]
[2 Marks]
[2 Marks]
[2 Marks]
Problem A4
Which one of the following operations can be performed
(2 Marks]
A. Insertion-adding a node into the BST
B. Deletion-removing a node from the graph
C. Traversal-visiting all nodes in a BST
D. All of the above
on a Binary Search Tree (BST)?
1
|
|
3 Page 3 |
▲back to top |
Problem AS
Given a java code snippet below, what is the output if n=3?
[2 Marks]
int add(int n}
{
int k;
if (n ==0)
return O;
else
k = n + add(n-1);
return k;
}
A.0
B.3
C. 6
D.4
Problem AG
Which one of the following is a time complexity of a recurrence relation for computing the nth
Fibonacci number?
[2 Marks]
A. T(n)= T(n-2) +c
B. T(n)= T(n-1) + T(n-2) +c
C. T(n)= T(n/2) +c
D. none of the above
Problem A7
What is the maximum number of edges a graph with 4 vertices can have?
A. 3
B. 6
C. 4
D.16
[2 Marks]
Problem A8
In ....., searching starts at the beginning of the list and checks every element in the list. [2
Marks]
A. Binary Search
B. Linear Search
C. Bubble Search
D. Jump Search
2
|
|
4 Page 4 |
▲back to top |
Problem A9
.....is the term used to delete an element from stack?
A. Pop
B. Insert
C. Delete
D. Push
[2 Marks]
Problem AlO
............are a series of instructions that are followed, step by step, to do something useful
or solve a problem.
[2 Marks]
A. Graph
B. Algorithm
C.Queue
D. Stack
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.
[10 Marks]
Problem Bl
A doubly-linked list is a linear data structure.
[2 Marks]
Problem B2
It is sensible to discuss depth-first and breadth-first searches in linear data structures.
[2 marks]
Problem B3
A Stack follows a LIFO (last-in-first-out) rule.
[2 marks]
Problem B4
Push and pop operations are associated with Binary Search Tree data structure.
[2 marks]
Problem BS
Big-0 and Big-0 (Big-Theta) are both asymptotic notations.
[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 3 questions.
[60 Marks]
Problem Cl
Study the tracing of the recursive function mystery below and answer all the questions that follow in the
provided booklet.
[18 Marks]
return 1 + o
a. Complete the missing return statements separated by commas.
[6 marks]
b. What will be the return value after the function mystery() finishes execution?
[2 marks]
c. Using a for loop, write a java program snippet to implement the function mystery().[10 marks]
Problem C2
Given a hash function h defined by, h(key)=key mod 5, with linear probing used to insert the keys: 17, 21,
22, 19, 13 into a table indexed from Oto 4. Populate the hash table.
[10 marks]
5
|
|
7 Page 7 |
▲back to top |
Problem C3
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.
Suppose the following string is to be sent over a network
le le IE IE IE Is 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]
Average code length: is calculated using the formula
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]
****** ****************************** Endof Exam****************************************
6