 |
DSA711S - DATA STRUCTURES AND ALGORITHMS 2 - 1ST OPP - JUNE 2024 |
|
|
1 Page 1 |
▲back to top |
n Am I BIA u n IVE Rs ITY
OF SCIEnCEAno
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENTOF SOFTWAREENGINEERING
QUALIFICATION:BACHELOROF COMPUTERSCIENCE
QUALIFICATIONCODE:07BCMS
COURSE:DATASTRUCTURESAND ALGORITHMS2
DATE:JUNE 2024
DURATION: 2 HOURS
LEVEL:7
COURSECODE: DSA711S
PAPER:THEORY
MARKS: 90
EXAMINER(S)
FIRSTOPPORTUNITYEXAMINATION QUESTION PAPER
MRS. TJIRASO
MODERATOR:
MRS P. DOLIAN
INSTRUCTIONS
1. Answer ALLthe questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly
THIS QUESTION PAPERCONSISTSOF 10 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 8 problems.
[40 Marks]
Problem Al
Which one is the worst case time complexity of the function; f(n) = 9n3 - 10000n 3 + n2 + n4? [2
Marks]
A. O(n},
B. O(n2}
C. O(n4 )
D. O(n12}
E. O(n3)
Problem A2
Consider the function; f(n) = 10n3 - 10n3 + n2 .
Statement A: The function f(n) has polynomial time complexity.
Statement B: The function f(n) has linear time complexity.
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.
2 Marks]
Problem A3
Consider the function; f(n) = 100 + 9n3?
Statement A: The function f(n) has linear time complexity.
Statement B: The function f(n) has_Quadratic time complexity.
A. Statement A is true, and Statement B is false.
B. Statement A is false, and statement Bis true.
C. Both Statement A and Statement Bare true.
D. Both Statement A and Statement Bare false.
[2 Marks]
Problem A4
Consider the program snippet below.
[2 Marks]
1
|
|
3 Page 3 |
▲back to top |
void testFunc(int n) {
for(int i=0; i < n; i++) {
for(int j=0; j < n; j++) {
for(int k=0; k < n; k++) {
for(int m=0; m <100; m++) {
System.out.println(" !");
}}}}
Statement A: The program has O(n4 ) time complexity.
Statement B: The program has O(n3) time complexity
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 AS
............is not an example of a recursive problem.
A. Problem with more than one (1) base cases
B. Problem without a base case
C. Finding the length of a string
D. Finding the nth Fibonacci number
[2 Marks]
Problem AG
Given the code snippet below. What will happen when the code is executed?
void recurse(){
recurse();
}
main(){
recurse();
}
[2 Marks]
A. program will successfully execute but no output will be generated
B. Infinite loop will be generated
C. Program will generate an error
D. program will successfully execute but no output will be generated
Problem A7
Study the binary search tree below and answer the questions that follow;
2
|
|
4 Page 4 |
▲back to top |
a). What node is the successor of node A?
A. B
B. C
C. F
D. M
E. G
F. L
G. None of the above
b). what node is the successor of node F?
A. J
B.C
C. K
D. E
E. G
F. I
G. None of the above
c). what node is the predecessor of node A?
A.J
B. K
C.B
D.M
E. G
F. L
G. None of the above
d). what is the height of the tree?
A. 2
B. 1
[2 Marks]
[2 Marks]
[2 Marks]
[2 Marks]
3
|
|
5 Page 5 |
▲back to top |
C. 4
D.8
E.3
F.5
G. None of the above
e). is the tree an AVL tree?
A.No
B. Yes
f). if we remove only node H, is the result an AVL tree?
A.No
B. Yes
g). lfwe remove only node J, is the result an AVL tree?
A.No
B. Yes
h). If we remove only node K, is the result an AVL tree?
A.No
B. Yes
i). If we remove only node M, is the result an AVL tree?
A.No
B. Yes
(2 Marks]
(2 Marks]
[2 Marks]
(2 Marks]
[2 Marks]
Problem AS
Study the news headline from the Namibia Newspaper below and answer the questions.
mines and energy minister tom alweendo says local companies should play a part in shaping the
new oil regulating policy that will guide the industry. He was speaking at the ongoing Namibian
Local Content Conference yesterday at LUderitz, where he also urged local businesses to take full
advantage of the emerging oil and gas sector to accrue maximum financial benefits.
NOTE: Consider only the text in bold, including spaces to answer all the questions in problem
A8.
4
|
|
6 Page 6 |
▲back to top |
a). Which type of data compression algorithm will be the most appropriate to compress this
news article?
(2 Marks]
A. Lossy methods
8. Lossless compression
C. None of the above
b). what is the total number of bits needed to store the bolded headline of this article before
compression? Include spaces in the bolded text. Assuming 8-bit ASCIIencoding is used. (2
Marks]
A.2
8. 1200
C. 512
D.8
E. 1184
F.5
G. None of the above
c). How many unique characters are in the text?
A. 24
8. 19
C. 512
D.8
E. 158
F. 12
G. None of the above
(2 Marks]
d). what is the code word or encoded string of the bolded text after compression using run
length encoding? Use underscore(_) for space.
(4 Marks]
A.2
8. m04i12n1le 12s05_24a 1ld05r05g05y05 t09o07110w03c13 p05h05u04
C. 512
D. m04il0nllel2s05_24alld05r08g05y05t09o07110w03c13p05h05u04
E.m0li0ln0le0ls0l_0la0ln0ld0l_0le0ln0le0lr0lg0ly0l_0lm0li0ln0li0ls0lt0le0lr
01_01tOlo0lm0l_ 0la0ll0l w01e03n01d01o01 _0ls0la0l y0ls0l_ 01101o01c01a01101-
01c0 lo01m01 p01a01n01i01e01s01 _01s01h01o01u01101d01_ 01p01101a01y01_01a01_ 01
p0la0lr0lt0l_ 0li01n01_ 0ls01h01a01p01i01n01g01 _01t01h01e01 _01n01e01 w0l _0lo0
li01101_01r01e0lg01u01101a01t01i01n01g01_01p01o01101i01c01y01_01t01h01a01t01_
01w01i01101101_01g01u01i01d01e01_01t0lh01e01_01i01n01d01u01s01t01r01y01
F. 5
G. None of the above
5
|
|
7 Page 7 |
▲back to top |
SECTIONB: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 Maries]
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]
6
|
|
8 Page 8 |
▲back to top |
SECTIONC:Structured questions
• Answer all the questions in the provided booklet.
• The section consists of 4 questions.
(40 Marks]
Problem Cl
What is the worst case time complexity for the function f(n) below using" big-Oh" notation?
You must choose your answer from the following list. The list is not in any particular order and any item in
the list could be the answer for 0, 1, or more than 1 question.
O(n), O(n2);0(2"), O(n112}, O(n114}, O(n3 ), O(n4}, O(n5), O(n6), O(n7), O(n8), O(n9 ),
O(log3 n), O(n2 log n), O(log8 n), O(log4 _n},O(n log3 n}, O(log2 n), O(log n), O(l);O(n 3 log n),
O(n"), O(n log log n), O(n log2 n), O(log log n), O(n log n)
a. f(n) = 9n3 - 8n3 + n2
(2 marks]
(2 marks]
c. f(n) = 100 + 9n
(2 marks]
Problem C2
Describe the worst case running time of the following code in " big-Oh" notation in terms of the variable
n. You should give the tightest bound possible. You must choose your answer from the following list. (2
marks]
O(n), O(n2);0(2"), O(n112), O(n114), O(n3 ), O(n4), O(n5), O(n6), O(n7), O(n8 ), O(n9),
O(log3 n), O(n2 log n), O(log8 n), O(log4 n), O(n log3 n), O(log2 n), O(log n), O(l);O(n 3 log n),
O(n"), O(n log log n), O(n log2 n), O(log log n), O(n log n)
(a) void myFunction(int n) {
for(int i=0; i < n; i++) {
for(int j=0; j < n; j++) {
for(int k=0; k < 100; k++) {
for(int m=0; m < 10; m++) {
System.out.println(" DSA711S");
} } }}
7
|
|
9 Page 9 |
▲back to top |
(b) void myFunction(int n) {
for(int i=0; i < n; i++) {
for(int j=0; j < n; j++) {
for(int k=0; k < n; k++) {
System.out.println(" DSA711S");
}}}
Problem C3
Consider a hash table with separate chaining, M = 10 positions with integer keys, and a hash function h(x)
= x mod M.
Starting from an empty table, show the resulting table after inserting the keys 41, 12, 98, 183, 483, 74,
722, 3313, 30, 5001, 4202, 465, 18181, 199, 999 and 1267.
[10 marks]
Problem C4
Huffman Codingis 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
Task:
a) What is the total size of the string as it is (in bits) or before compression, assuming 8-bit ASCII
encoding is used?
[2 marks]
b) Apply Huffman Coding on the string and determine the Huffman tree, by completing the tree
below. The first few steps are done for you.
[4 marks]
8
|
|
10 Page 10 |
▲back to top |
0
0
2
1
1
c) Determine the code and code length of each character.
Character
Frequency
Code
Code Length
C0
11
FE
22
d) Compute the size of the encoded string?
e) Provide the encoded string or code word?
(8 marks]
(4 marks]
(4 marks]
**** ******************* ****** ****** End of Exam****************************************
9