 |
DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 1ST OPP - NOV 2025 |
|
|
1 Pages 1-10 |
▲back to top |
|
|
1.1 Page 1 |
▲back to top |
nAmlBIA
UnlVERSITY
OF SCIEnCE RnD
TECH noLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENT OF SOFTWARE ENGINEERING
QUALIFICATION: BACHELOR OF COMPUTER SCIENCE, BACH ELOR OF INFORMATICS
QUALIFICATION CODE: 07BCMS, 07BAIT
NQF LEVEL: 5
COURSE: DATA STRUCTURES &ALGORITHMS 1 COURSE CODE: DSA521S
DATE: NOVEMBER 2025
SESSION: TH EORY
DURATION: 3 HOURS
MARl<S: 100
FIRST OPPORTUNITY EXAMINATION QUESTION PAPER
MR. NAFTALI INDONDO
MR. RIAHAMA MUSUTUA
EXAMINER(S)
MR FREDY EMBASHU
MS. TJIHIMISE l<AUNATJll<E
MR. PHIUS PETRUS
MODERATOR
MRS. SHILU MBE CH IVU NO- l<URIA
INSTRUCTIONS
1. Answer ALL the questions
2. Read all the questions carefu lly before answering
3. Answers should be written in the space provided in the question paper
4. Number the answers clearly
THIS QUESTION PAPER CONSISTS OF 11 PAGES
(Including t his front page)
PERMISSIBLE MATERIALS
1. NON-PROGRAMMABLE CALCULATOR
|
|
1.2 Page 2 |
▲back to top |
SECTION A: 10 MARl<S
MULTIPLE CHOICE (Select the letter that corresponds to the correct answer.}
1. Given a list of elements, 3,12,6,16,9 inserted into a data structure in that order. An
element is deleted using a basic data structure operation. If the deleted element is
9, the data structure cannot be a?
A. Queue
B. Tree
C. Graph
D. None of the above
2. _ _ _is not a component of data structures and algorithms
A. Operations
B. Storage Structures
C. Cloud storage
D. None of the above
3. Which of the following operations can be performed on a singly-linked list, a doubly-
linked list, and a circular list?
A. Insertion- adding an element to the list.
B. Deletion - removing an element from the list
C. Search - seek for an element in a given list
D. All of the above
4. Which of the following would you use to get the value in the third row and fourth
column from a 2D array/matrix called twoDimenArray?
A. twoDimenArray[2][3]
B. twoDimenArray[3][4]
C. twoDimenArray[4][3]
D. None of the above
5. In Quick Sort, the pivot element is used to:
A. Sort the array immediately.
B. Partition the array into two sub-arrays.
C. Merge the sub-arrays into one sorted array.
D. Compare elements to find the maximum.
6. Which of the following cannot be used for searching in an unordered array?
A. Linear Search
B. Binary Search
C. Quick Search
D. Merge Sort
1
|
|
1.3 Page 3 |
▲back to top |
7. Given the following tree. Give its inorder traversal algorithm output.
A. ABDHIECGFS
B. HDIBEAFCJG
C. HIDEBFSFCA
D. ABDHIECFGS
8. Two vertices in a graph are said to be adjacent vertices (or neighbours) of length
___ connecting them.
A. At least 1
B. At least 2
C. At least less than 2
D. 1
9. If the node to be deleted has _ _ _ , we delete the node and attach the left
subtree to the deleted node.
A. Only a left subtree
B. Only a right subtree
C. No children
D. One child
10. Which of the following is an approach to traversing a graph?
A. Binary search
B. Sequential search
C. Breadth First Search (BFS)
D. None of the above
2
|
|
1.4 Page 4 |
▲back to top |
SECTION B: 10 MARl<S
TRUE/FALSE (Determine whether the following statements are True or False)
1. The time complexity of the front variable in the Queue data structure is Big O(n).
A. True
B. False
2. A stack is an abstract data type where data is inserted from both ends, provided that the
isEmpty() function is declared first and checked.
A. True
B. False
3. In a stack, the pop() operation removes the element at the bottom of the stack.
A. True
B. False
5. In a linked list, insertion can be done at the End, Middle, but not at the beginning.
A. True
B. False
6. Merge Sort is a divide-and-conquer algorithm that splits an array in half until subarrays
conta in only one element.
A. True
B. False
7. Binary search can be performed on both sorted and unsorted arrays.
A. Tru e
B. False
8. In a full binary tree, every node has either zero or two children.
A. True
B. False
9. Linear Search returns the index of the t arget element if found.
A. True
B. False
10. A perfect binary tree has all leaf nodes at different levels.
A. True
B. False
3
|
|
1.5 Page 5 |
▲back to top |
SECTION C: 80 MARl<S
STRUCTURED QUESTIONS
• Answer all the questions in the space provided.
• This section consists of4 questions.
1. Linear Data Structures
[25 MARl<S]
1.1 . Discuss the difference between a Queue and an Array.
(4)
...................................................... ............................................. ........................
..................................,...................... ..................................................................
···························••••••··••·•••••••••••••••••••••••••••••••••• •••••• ••• ••••••••••••••••••••••••••••••••• •••• •• •••
························•·••·••·•·•••·••·• ••••••••••••• •• •••••• ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
·························•••••••••·••••••·••••••••••••••• ••• •••••• •••••••••••••••••••••••••••••••••••••••••••••••••••••••••
························•·····•·•••••••••••••••••••••••••••••••••••••••••••••••••••••••••• •••••••••••••••••••••••••••••••••
······························ ····••••••••••••••••• ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
········································••·•••••••• ••••••••••••••••••••••••••••••••••••••••••••••••••• •••••••••••••••••••••
··········································•·••••••••••••••••••• ••••••••••••••••••••• ••••••••••••••• ••••••••••••••••••• •••••
1.2. Consider the following data elements: DSA, INP, BST, BCMS, DPG, PRG. By way
of a diagram, show how the above data can be stored in an array, conceptua lly.
Your diagram must clearly show both t he cells and their corresponding cell
indices.
(6)
1.3. Study the code fragment below and answer the following question.
mystery (marks!), size)
FOR (outerCounter=0 to slze-1)
lowestlndiex= outerCounter
FOR (innerCounter= outerCounter +1 to size-1)
IF(marks[lnnerCounter] < marksllowestl ndiex] )THEN
lowestlndiex= innerCounter
ENDFOR
ENDIF
ENDFOR
marks(outerCounter]= marks(lowestlndlex)
END mystery()
4
|
|
1.6 Page 6 |
▲back to top |
What is the final output of the algorithm if an array, marks= {45, 75, 62, 18} is
passed to the function mystery()?
(5)
1.4. Study the flow chart below.
Art1• 1qrt(Sa(UWS..S)x(S-CI)
Perim.tt,- A♦ B♦C
Write a pseudocode corre sponding t o t he Flowchart program
(6)
1.5. Consider the function below and fill in the missing code fragments to display the
• content of a dynamic queue.
5
|
|
1.7 Page 7 |
▲back to top |
display ()
{
IF ( front == .................. AND rear
............... )THEN
(1)
DISPLAY "empty"
ELSE
temp = .......................... ...................
(1)
WHILE(temp ! = null)
DISPALY temp ->................................................
( 1)
temp=temp->nex t .............................................
( 1)
ENDWHILE
ENDIF
}
2. Sorting Algorithms
[15 Marks]
2.1. Discu ss the differences between selection and insertion sort algorithms. (5)
2.2. Here is an array that has just been partitioned by t he first step of quicksort:
3,0,2,4,5,8, 7,6,9
Wh ich of these elements could be the pivot? (There may be more than one
possibility!)
(5)
2.3. Consider an array of elements arr[5]= {5,4,3,2,1}. Perform the steps of
insertion done while doing insertion sort in the array?
(5)
6
|
|
1.8 Page 8 |
▲back to top |
3. Searching Algorithms
[20 Marks]
3.1. What is the difference between Linear Search and Binary and explain in which
situations Linear Search is preferred over Binary Search
(6)
······ ··· ·······················•·······•••••••••••••••• ••••••••• •••••••••••••••• •••••••••••••• •• •••••••••• •• ••••••••••••••
·······································•··•·•···•••••·••••••••••••••• ••••••••••••••••••••••••••••••••••••••••••••••••••••••
··········································•·· ••••••••••••••••••••••••••••••••• •••••• ••••••••••• ••••••• ••••• ••••••••••••••••
······························ ···•··•·•••••·•·••••••••••••••••• ••••••••••••••••••••••••••••••••• •••••••••••••••••• •• •••••••
············································•·•••••••••••••• •••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
······························ ··········•••·•·•• ·•••••••••••••• •••••••••••••••••••••••••••••••••••••••••• ••••••••••••••••••
···········································••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• •••••••••••••••
······························•··········•••••••••••••••••••••••••••••••••••••••••••••••••••••••••• ••• •••••••••••••••••••••
·············································•·••••·••••••••••••••••••••••••••••••••••• ••••••••••••••••••••••••••••••••••••
·········································••·••····•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
3.2. Given the array {6, 8, 17, 20, 23, 27, 37, 51, 57, 73, 89},
i. Write the pseudocode for the Binary Search algorithm to find the key 57. (6)
ii. How many elements will Binary Search need to checl< to find the key=57?
... ......... ... ·····················... ............... •......
(3)
iii. How many elements will Linear Search need to check to find the key 57?
............ ... ... ............ ... ... ... ... ... ... ............
(3)
iv. Discuss what will happen if you binary search the key=38 in the array {20,
57,6,37, 73,89,23,51,17,8,27,73}
(2)
·····································•·••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
································· ····················· ·•···•··••••••••••••••••••••••••••••••••••••••••••..............
···········································•·········••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
·········································•••••••••••••••••••••••••••••••••••••••••••••••••••••• ••••••••••••••••••••••
............ ..................................................................................................... ......
7
|
|
1.9 Page 9 |
▲back to top |
······ ···························•••·•·•••••• •••••••••••••••••••••••• ••• ••••••••••••••••••••••••••• •• •••••••• •••••• ••
.............................. ... ..................................................................... ...............
····························•······•··•••••••••••••••• •••••••••••••••••• •••••••••••••••••••••••••••••••••••••••••••••
···········································•••·••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• •••••••••
4. Non-Linear Data Structures
[30 Marks]
4.1. Define the following terms:
4.1 .1. Root node
(1)
·······················•••·••··•··••·•··••••••••••••••••••••••••••••• •••••••••••• ••• ••••••••••••••••••••••••••••••
················· ·····················•••••••••••••••• ••••••••••••••• ••••••••••••••••• •• •••• •••••• •••••• •• ••• ••• ••
····························••••••·••·•••••••••••••••••••• ••••••••••••• •••• ••• ••••••••••••••• •••••••••••••••••••••
4.1.2. Leaf node
(1)
,, ·················································••••••••••• ••• •••••••••••••••••••••••••••••••••••••••••••••••••••
·······································•·••••••·•••••••••••••••••••••••• ••••••••••••••••••••••••••••••••••••••••••
·······························•·····•····••••••••••••••••••••••••••••••••• ••••••••• ••• ••••••••••••••• ••••••••••••
4.1.3 . Edge
(1)
····························••··•·····•••••••••••••••••••••••••••••••••• ••••••••••••••••••••••••••••••••••••••••••
································••···•·····•••••••••••••••••••••••••• ••••••••• •••••• •••••••••••••••••••••• •• ••••••
·································•·•·····••••••••••••••••••• •••••••••••• •••••• •••••••••••••••••••••••• •• ••••••••••
4.1.4. Path
(1)
······ ···························•····•····•···•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
··································•·······•···••••••••••••••••• •••••••••••••••••••••••••••••••••••••••••••••••••••
··································•·•···•••••••••••••••••••••••••••••••• ••••••••• •••••••••••••••••••••••••••••••••
4 .1 .5. Level of node
(1)
···························••••••••••···•••••••••••••••••••••••••••••••••• ••••••••••••••••••••••••••••••••••••••••
····································•····••·• ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• ••••••
·································•·••·•··•••· ••· •••••••••••••••••• ••••••••••••••••••••••••••••••••••••••••••••••••
4.2 . Given the following array {20, 30, 60, 100, 90, 50, 130,210, 160, 11 0}. Construct
a Binary Search Tree (BST) using a Postorder traversal.
(5)
8
|
|
1.10 Page 10 |
▲back to top |
4.3. Study the BST belo~:
4.3.1. Delete the following nodes: 10, 32, and 50, and draw the new BST
(5)
4.3.2. Find the maximum height/level of the BST after the operations in 4.2.1 ? (2)
4.4. Consider the graph below, and answer the following questions:
9
|
|
2 Pages 11-20 |
▲back to top |
|
|
2.1 Page 11 |
▲back to top |
4.4.1. Represent the graph as an adjacency matrix.
(5)
4.4.2. Use Depth-First Search to traverse the graph using a stack data structure,
beginning with vertex a, and record the stack and visited vertices at each
stage of the traversal.
(8)
************************ End of the Paper************************
10