 |
DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 2ND OPP - DEC 2025 |
|
|
1 Pages 1-10 |
▲back to top |
|
|
1.1 Page 1 |
▲back to top |
nAmlBIA
UnlVERSITY
OF SCIEnCE Ano
TECHnOLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENT OF SOFTWARE EN GINEERING
QUALIFICATION: BACHELOR OF COMPUTER SC IENCE, BACHELOR OF INFORMATICS
QUALIFICATION CODE: 07BCMS, 07 BAIT
NQF LEVEL: 5
COURSE: DATA STRUCTURES & ALGORITHMS 1 COURSE CODE: DSA521 S
DATE: DECEMBER 2025
SESSION: THEORY
DURATION: 3 HOURS
MARl<S: 100
SUPPLEMENTARY EXAMINATION QUESTION PAPER
MR. NAFTALI INDONDO
MR. RIAHAMA MUSUTUA
EXAMINER(S)
MR FREDY EMBASHU
MS. TJIHIMISE KAUNATJIKE
MR. PHIUS PETRUS
MODERATOR
MRS. SHILUMBE CHIVUNO- KURIA
INSTRUCTIONS
1. Answer ALL the questions
2. Read all the questions carefully before answering
3. Write your answer in the space provided on the question paper
4. Number the answers clearly
THIS QUESTION PAPER CONSISTS OF 11 PAGES
(Including this front page)
PERMISSIBLE MATERIALS
1. NON-PROGRAMMABLE CALCULATOR
|
|
1.2 Page 2 |
▲back to top |
SECTION A: 10 MARKS
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 3, the
data structure can be a _ __ _ ?
A. Queue
B. Tree
C. Graph
D. None of the above
2. Which of the following operations cannot 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. None of the above
3. How many rows does the two-dimensional array or matrix have if it is created as follows:
int[][]twoDimenArray = {{14, 19, 9, 17},{12,15,0,15},{12,15,0,15},{22,1,0,18}}?
A. 4 rows
B. 3
C. 16
D. 2D
4. The formula used to calculate the middle index in Binary Search is:
A. (low+ high)/ 2
B. (low x high)/ 2
C. (low - high)/ 2
D. (low+ high)/ 2
5. Which element is chosen in Quiel< Sort to partition the array?
A. Always the middle element
B. The minimum element
C. The maximum element
D. The pivot element
6. Given the following tree. Give its inorder traversal algorithm output.
1
|
|
1.3 Page 3 |
▲back to top |
A. ABDH IECGFS
B. HDIBEAFCJG
C. HIDEBFJGCA
D. ABDHIECFGS
7. Which of the following is the best time complexity for a Binary Search algorithm?
A. O(n)
B. O(n2)
C. O(log n)
D. 0(1)
8. What are the applications of a stack?
A. Queues in routers/switches
B. Check parentheses matching in an expression
C. Process scheduling
D. Shared resource
9. If the node to be deleted has _ __, we replace it with its inorder successor (or
predecessor) and then delete that successor (or predecessor) node..
A. Only a left subtree
B. Only a right subtree
C. two children
D. Has one child
10. Which of the following is an approach to traversing a graph?
A. Binary search
B. Sequentia l search
C. Both A and B are approaches to traversing a graph.
D. None of A or B is an approach to traversing a graph
2
|
|
1.4 Page 4 |
▲back to top |
SECTION B: 10 MARKS
TRUE/FALSE (Determine whether the following statements are True or False)
1. In a stack, the push() operation inserts elements at the bottom of the stack.
A. True
B. False
2. A doubly linked list allows traversal in both directions, forward and backwards.
A. True
B. False
3. In a linked list, insertion can be done at the End, Middle, but not at the beginning.
A. True
B. False
4. In a queue, both front and rear pointers must be updated during enqueue operations.
A. True
B. False
5. Merge Sort is a divide-and-conquer algorithm that splits an array in half until subarrays
contain only one element.
A. True
B. False
6. Binary Search can be used on linked lists without modification.
A. True
B. False
7. Binary search can be performed on both sorted and unsorted arrays.
A. True
B. False
8. In a binary tree, each node can have at most three children.
A. True
B. False
9. The inorder traversal of a binary search tree produces elements in ascending order.
A. True
B. False
10. In Breadth First Search (BFS), a stack data structure is used ..
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 of 4 questions.
1. Linear Data Structures
1.1. Discuss the difference between a Stack and a Queue.
(25 Marks]
(4)
............... ............ .... .... ............ ............. ...... ............... ... .... ....... .... .. ............... ......... .. ..... ............
... ...................... ..... ... .......... .. ...................... .... .. .. ........................ .... ........................... .. ............
1.2. Six (6) DSAS21S students took a test and scored the fo llowing marks: 23, 37, 63, 13,
70, 33 in t hat order, starting with 23. By way of a diagram, illustrate how the above
test marks will be stored in a Stack using a linked list implementation
(6)
1.3. Study the code fragment below and answer the following question.
mystery (marks[], size)
FOR (outercounter:;Q to slze-1)
lowestlndiex= outerCounter
FOR (innerCounter= outerCounter +1 to size-1)
IF(marks[innerCounter] < marks[lowestlndiex) )THEN
lowestlndiex= innerCounter
ENDFOR
ENDIF
ENDFOR
marks[outerCounter) = marks(lowest lndiexJ
END mystery()
4
|
|
1.6 Page 6 |
▲back to top |
i. What is the fina l output of the algorithm if an array, marks= {45, 75, 62, 18}
is passed to the function mystery()?
(5)
... ......................................................................... .. ................................................
·······················································•••••••••••••••••• ••••• •••• ••••••••••••••••••••••••••••• •••••••••••••••
.......... ... ................................... ................... ................. ..... ......... ......... ......... .... ... .. .
................ ...................................... ...... ............ ........... ...... ...... .... ............ ........ ...... .
..................... ... ...... ..... .... ........................... ... ...................... .... .... ..... ... .. .................
··· ·········································•·•··•••••••••••••••••••••••••••• •••••••••••••••••••••••••••••••••••••••• ••• ••••• •
.. ............................... ................................. ....... ..... ............ ....... ...... .. .. ..... .. ............
············· ·· ·················· ·· ····················.......... ... .... ......... ..... ... ....... .......... ..... ............ .. .
ii. If the two (2) highlighted lines are added, what will be the output for the
same array, marks = {45,75, 62,18}? Show the state or content of the array
after each iteration of the outer loop.
(6)
mystery (marks!), size)
FOR (outerCounter=O to slze-1)
lowestlndiex= outerCountcr
FOR (innerCounler= outerCounter +l to size-1)
IF(markslinnerCounter) < marks[lowestlndiex] )THEN
lowestlndlex= innerCounter
ENDIF
ENDFOR
temp= markslouterCounter)
markslouterCounter]= marks(lowestlndiex]
marksllowestlndlex]= temp
5
|
|
1.7 Page 7 |
▲back to top |
1.4. Consider the function below and fill in the missing code fragments to display the
content of a dynamic queue, where 'data' is the variable name that holds the actual
va lue.
display ()
{
I F (front
AND rea r == ..................... ) THEN (2)
DISPLAY "Queue is empty"
ELSE
FOR ( i =
i < rear + 1; i ++) .
(1)
DISPLAY
( 1)
ENDFOR
ENDIF
2. Sorting Algorithms
[15 Marks]
2.1. Discuss the differences between selection and insertion sort algorithms.
(5)
········· ·········· ......................................................................................................................... .
........ ..... ...................................................... ... ............................................ ... ........................
... .............. .... ..... ...... ............... ............... .. ......... ....... ... ............ ......... ... .. .. ... ...... .. ..... .. ...... ......
................................................... ......................., .......... ..... ...................... .. ...... ........... .... ......
·······················································•·•••·•••·•••••••••• ••••••••••••••••••••••••••• ••• •••••••••••• ••••••••••••••••••••• •..
............. ................. ... ............................................................................................................
... ................. ....... ........................................ ...... ....... ...... ......... ................ ... ...... ............ ... ......
......... ...... ... ............................... .... .. ............ ............................ ... .................. ............. ........ ....
············· ···· ·· ·· ................ ......... ..... ... .. ....... .. ..... ...... ... ............ ... ......... ... ................... .... ... ........ .
2.2. Here is an array of ten integers:
5 38 9 17 0 264
Draw this array after the TWO recursive calls of merge sort are completed, and before
the final merge step has occurred.
(5)
2.3. Use the Quick Sort algorithm to sort t he array below: 4,3,2,10,12,1,5,6. Show content
for each step.
(5)
6
|
|
1.8 Page 8 |
▲back to top |
3. Searching Algorithms
(15 Marks]
3.1. What is the difference between Linear Search and Binary and explain in w hich
situations Linear Search is preferred over Binary Search
(4)
3.2. Given the array {6, 8, 17, 20, 23, 27, 37, 51, 57, 73, 89},
i. Write the pseudocode for the Linear Search algorithm to find the key 57. (8)
ii. How many elements will Binary Search need to check to find the key=27?
(3)
iii. How many elem ents will Linea r Sea rch need to check to find the key 27?
(3)
7
|
|
1.9 Page 9 |
▲back to top |
iv. Discuss what will happen if you linear search the key=38 in the array {20, 57, 6, 37,
73, 89, 23, 51,17,8,27,73}
(2)
4. Non-Linear Data Structures
4.1. Defin e the following terms:
4.1.1. Child node
4.1.2. Parent node
4.1.3. Edge
4.1.4. Path
4.1.5. Depth of node
[30 Marks]
(1)
(1)
(1)
{1)
(1)
4.2. Given the fo llowing array {20, 30, 60, 100, 90, 50, 130, 210, 160, 110}. Construct a
Binary Search Tree (BST) using a Preorder traversal.
(5)
8
|
|
1.10 Page 10 |
▲back to top |
4.3. Study the BST below:
4.3.1. Delete the following nodes: 8, 3, and 7, and draw the new BST
(5)
4.3.2. What is 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:
(5)
4.4.1. Represent the graph as an adjacency list.
(5)
9
|
|
2 Pages 11-20 |
▲back to top |
|
|
2.1 Page 11 |
▲back to top |
4.4.2. Use Breadth-First Search to traverse the graph using a queue data structure,
beginning with vertex a, and record the queue and visited vertices at each stage
of the traversal.
(8)
************************ End of the Paper************************
10