 |
DSA521S - DATA STRUCTURES AND ALGORITHMS - 1ST OPP - NOV 2024 |
|
|
1 Pages 1-10 |
▲back to top |
|
|
1.1 Page 1 |
▲back to top |
nAmlBIA unlVERSITY
OFSCIEnCEAno TECHnOLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENTOF SOFTWAREENGINEERING
QUALIFICATION: BACHELOROF COMPUTERSCIENCE, BACHELOROF COMPUTER
SCIENCE IN CYBERSECURITYAND BACHELOROF INFORMATICS
QUALIFICATION CODE: 07BCMS, 07BCCY,
LEVEL: 5
07BAIT
COURSE: DATASTRUCTURESAND ALGORITHMS COURSE CODE: DSA521S
1
DATE: NOVEMBER2024
PAPER: THEORY
DURATION: 2 HOURS
MARKS: 100
FIRST OPPORTUNITY EXAMINATION QUESTION PAPER
EXAMINER
MODERATOR:
MRS. TJIRASO
MR N. INDONGO
MS N. IITUMBA
MR R. l<AVIMAKA
MR I. KANDJABANGA
MRSS. CHIVUNO-KURIA
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly.
THIS QUESTIONPAPERCONSISTSOF 12 PAGES
(Including this front page)
PERMISSIBLE MATERIALS
1. NON-PRGRAMMABLECALCULATOR
|
|
1.2 Page 2 |
▲back to top |
SECTIONA: Multiple ChoiceQuestions[20 Marks]
Answer all the questions in the booklet provided.
The section consists of 10 problems (A1-A10).
Problem Al
Given a list of elements; 8,12,6,16,30 inserted into a data structure in that order. An element is deleted
using a basic data structure operation. If the deleted element is 30, the data structure cannot be a?
A. Tree
(4 Marks]
B. Queue
C. Graph
D. None of the above
Problem A2
Study the code fragment below and answer the question that follows.
FOR(i= 1; i < n; i++)
temp =35
temp= array[i]
j = i -1
WHILE (j >= 0 AND arrayU] > temp)
array[j + 1] = arrayU]
j = j-1
ENDWHILE
array U+ 1] = temp
ENDFOR
1 )1--------
|
|
1.3 Page 3 |
▲back to top |
Which of the following statement(s) is true about the code fragment?
Statement A: Code fragment has the worst-case time complexity of O(n).
Statement B: Code fragment is a pseudocode for a searching algorithm.
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]
ProblemA3
Which one of the following cannot be used for sorting?
[2 Marks]
A. Selection Sort
B. Merge sort
C. Insertion Sort
D. Binary Sort
Problem A4
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 right subtree nodes does the tree have?
[2 Marks]
A.3
8.5
C. 7
D.6
E.4
F. None of the above
Problem AS
Which one of the following is the worst-case time complexity of selection sort algorithm?
[2 Marks]
A. 0(1)
2
|
|
1.4 Page 4 |
▲back to top |
B. O(n)
C. O(n2)
D. O(log n)
E. O(n log n)
F.O(n3)
G. None of the above
ProblemA6
Study the BSTbelow and answer the question that follows.
If we compute; 2h-1: where h is "height", what are we computing or trying to find out?
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
H.
Invalid computation
I.
Maximum number of leaf nodes in tree
[2 Marks]
3
|
|
1.5 Page 5 |
▲back to top |
J.
Maximum number of internal nodes in tree
K.
Maximum height
L.
Minimum number of leaf nodes in tree
ProblemA7
The operation for visiting each node in a tree data structure is known as......
A. inserting
B. Merging
C. Sorting
D. Traversal
E. none of the above
Problem AS
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
|
|
1.6 Page 6 |
▲back to top |
Problem A9
Which of the following statement(s) is true?
(2 Marks]
Statement A: Enqueue operation is concerned with adding an element to a queue data structure.
Statement B: Dequeue operation is concerned with searching for an element in a queue data structure.
A. Statement A is true, and Statement Bis 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.
ProblemA10
Which of the following statement(s) is true?
Statement A: Selection sort algorithm has a worst-case time complexity of O(n2).
Statement B: Selection sort algorithm has a best-case time complexity of O(n2).
A. Statement A is true, and Statement Bis false.
B. Statement A is false, and statement B is true.
C. Both Statement A and Statement B are true.
D. Both Statement A and Statement Bare false.
(2 Marks]
5
|
|
1.7 Page 7 |
▲back to top |
SECTIONB: True and FalseQuestions (20 Marks)
Answer all the questions in the booklet provided.
The section consists of 7 problems (B1-B7).
Problem Bl
Stack is an abstract data type where data are inserted from both ends provided that the isEmpty() function
is declared first and checked.
[2 Marks]
A. True
B. False
Problem 82
Selection sort algorithm has best and worst-case time complexity of O(n2).
[2 Marks]
A. True
B. False
Problem 83
In a linked list, insertion can be done at the End, Middle but not at the beginning of the list.
(2 Marks]
A. True
B. False
Problem 84
When we insert data into a 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]
A. True
B. False
Problem 85
The inorder traversal processes the left subtree first, then the root, and finally the right subtree. [2 Marks]
A. True
B. False
6
|
|
1.8 Page 8 |
▲back to top |
Problem 86
The postorder traversal processes the left subtree first, then the root, and finally the right subtree.
A. True
[2 Marks]
B. False
Problem 87
Consider the structure below and answer the question{s) that follows.
Orgchart
Organizartionchartforthe Facultyof Computingand lnformatics(FCI)
NOTE:somedepartments/rolems aybeommitledto for Binarytreerepresentation
Executive Dean:FCI
I
Associate Dean: CS
I
I
HoD:SE
I
HoD: Cyber
Associate Dean: IJMT
I
I
HoD: Informatics
HoD:JMT
{a) The preorder predecessor of HoD:SEin this binary tree is ExecutiveDean: FCI.
A. True
B. False
[2 Marks]
{b) The lnorder successor of HoD: InformaticsisAssociateDean: IJMT.
7
[2 Marks]
|
|
1.9 Page 9 |
▲back to top |
A. True
8. False
(c) The height of the node; HoD:JMT is two(2).
A. True
B. False
(d ) The height of the this binary tree is two(2).
A. True
8. False
[2 Marks)
[2 Marks]
8
|
|
1.10 Page 10 |
▲back to top |
SECTION C: Structured Questions
[60 Marks]
Answer all the questions in the booklet provided.
The section consists of 9 problems (Cl-C9).
Problem Cl
(a) Given the array {6, 8, 17, 20, 23, 27, 37, 51, 57, 73, 89} Write the pseudocode for the
binary search algorithm to search for the key=Sl.
[8 Marks]
(b) How many elements will Binary Search need to check to find the key=27?
(c) How many elements will Linear Search need to check to find the key 27?
(4 Marks]
(3 Marks]
(d) Discuss what will happen if you binary search the key=Sl in the array {20, 57, 6, 37, 73, 89, 23,
51,17,8,27,73}
(4 Marks]
Problem C2
Suppose that a selection sort of 500 items has completed 100 iterations/passes of the main(outer) loop.
How many items are now guaranteed to be in their final spot (never to be moved again)?
(2 Marks]
Problem C3
Here is an array of ten integers: 5, 3, 8, 9, 1, 7, 0, 2, 6, 4
(a) Draw this array after the FIRST iteration of the main(outer) loop in a selection sort (sorting from
smallest to largest).
[3 Marks]
(b) Draw this array after the FIRST iteration of the main(outer) loop in an insertion sort (sorting from
smallest to largest). This iteration has shifted at least one item in the array!
[3 Marks]
Problem C4
Describe a case where insertion sort algorithm will exhibit linear time O(n) in the best-case scenario.
Hint: when the inner loop never executes or may execute once for example.
(2 Marks]
9
|
|
2 Pages 11-20 |
▲back to top |
|
|
2.1 Page 11 |
▲back to top |
Problem CS
Here is an array which has just been partitioned by the first step of quicksort:
3, 0, 2, 4, 5, 8, 7, 6, 9
Which of these elements could be the pivot? (There may be more than one possibility!)
[4 Marks]
Problem C6
Briefly describe binary and linear search algorithms with respect to how they work given the following
array and searckKey;array={2,3,7,11,14,18,23,27} and searckKey=90.One of the key descriptions should
be about their respective worst-case time complexity or their asymptotic behavior.
[10 marks]
Problem C7
Study the tree data structure below and answer the following questions.
BinaryTree B
(a) Briefly discuss the height of each of the two (2) structures and how it affects a search operation.
[4 Marks]
(b) What will be the preorder, inorder and postorder traversal output for BinaryTreeA? [6 Marks]
(c) Which node is an inorder successorof node Din BinaryTree A?
[2 Marks]
10
|
|
2.2 Page 12 |
▲back to top |
Problem CS
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 numbers of left subtree nodes will the resulting tree have?
[2 Marks]
Problem C9
Consider the function below and fill in the missing code fragments.
quickSort(array, start, end) {
IF (start< end) {
pivot= start
i = start
j = end
WHILE(i < j){
WHILE (array[i] <= array[pivot] && i < end)
i =i+ 1
WHILE (arrayU] > ............................).....
j =j - 1
IF (i < j){
temp= ................................
array[i] = arrayU)
arrayU] = temp }
[3 Marks]
temp= array[pivot]
array[pivot] = arrayU]
array[j] = temp
quickSort(array, start, j+1)
quickSort(array, ..............................,..e. nd)
************************************End Of Paper*************************************
11
|
|
2.3 Page 13 |
▲back to top |
SECTIONA: Multiple Choice Questions [20 Marks]
Answer all the questions in the booklet provided.
The section consists of 10 problems (A1-A10).
Problem Al
Given a list of elements; 8,12,6,16,30 inserted into a data structure in that order. An element is deleted
using a basic data structure operation. If the deleted element is 30, the data structure cannot be a?
A. Tree
(4 Marks]
B. Queue
C. Graph
D. None of the above
Problem A2
Study the code fragment below and answer the question that follows.
FOR(i = 1; i < n; i++)
temp =35
temp = array[i]
j =i- 1
WHILE (j >= 0 AND array[j] > temp)
array[j + 1] = arrayLi]
j = j -1
ENDWHILE
array Li+ 1] = temp
ENDFOR
1