 |
DSA521S - DATA STRUCTURES AND ALGORITHMS - 2ND OPP - JAN 2025 |
|
|
1 Page 1 |
▲back to top |
nAmlBIA UnlVERSITY
OF SCIEnCE Ano 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: JANUARY2025
PAPER: THEORY
DURATION: 2 HOURS
MARKS: 100
SUPPLEMENTARY/ SECOND OPPORTUNITY EXAMINATION QUESTION PAPER
EXAMINERS
MODERATOR:
MRS. TJIRASO
MR N. INDONGO
MS N. IITUMBA
MR R. l<AVIMAl<A
MR I. l<ANDJABANGA
MRSS. CHIVUNO-KURIA
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly.
THIS QUESTIONPAPERCONSISTSOF 1O PAGES
(Including this front page)
PERMISSIBLE MATERIALS
1. NON-PRGRAMMABLECALCULATOR
|
|
2 Page 2 |
▲back to top |
SECTION A: Multiple Choice Questions [20 Marks]
Answer all the questions in the booklet provided.
The section consists of 10 problems (A1-A10).
Problem Al
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
Problem A2
Which of the following is the best-case time complexity for a Binary Search algorithm?
A. O(n)
B. O(n2)
C. O(log n)
D. 0(1)
Problem A3
What are the applications of queue?
A. parentheses matching check
B. Breadth First Search (BFS)Algorithms
C. Evaluation of arithmetic expressions
D. None of the above
(2 marks]
(2 marks]
(2 marks]
1
|
|
3 Page 3 |
▲back to top |
ProblemA4
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.
[2 marks]
Problem AS
Which of the following is true about the Linear Search algorithm?
A. It works only on sorted arrays.
B. It uses a divide-and-conquer technique.
C. It checks each element sequentially.
D. It always has a time complexity of 0(1).
[2 marks]
Problem A6
What is the maximum number of edges a graph with 4 vertices can have?
[2 marks]
A. 3
B.6
C. 4
D. 16
Problem A7
Which of the following is the average time complexity of searching for an element in a
sorted array using binary search
[2 marks]
A. O(n)
B. O(log n)
c. O(n log n)
D. 0(1)
2
|
|
4 Page 4 |
▲back to top |
Problem AS
Which data structure is used to represent a graph in an adjacency list?
A. Array
B. Linked List
C. Hash Map
D. Stack
Problem A9
In a circular linked list, the last node points to which of the following?
A. Itself
s. The first node
C. Null
o. A random node
Problem AlO
Which of the following is NOT a valid operation on a stack?
A. Push()
B. Pop()
C. Peek()
o. Random()
[2 marks]
[2 marks]
[2 marks]
3
|
|
5 Page 5 |
▲back to top |
SECTION B: True and False Questions [20 Marks]
Answer all the questions in the booklet provided.
The section consists of 10 problems(Bl-810).
Problem B1
In Merge Sort, the merge step always combines two sorted arrays into one sorted array.
[2 marks]
A. True
B. False
Problem B2
In Quick Sort, elements larger than the pivot element are placed to the left of the pivot.
[2 marks]
A. True
B. False
Problem B3
Binary Search can be performed on both sorted and unsorted arrays.
[2 marks]
A. True
B. False
Problem B4
The best-case time complexity of linear Search is 0(1).
[2 marks]
A. True
B. False
Problem BS
Merge Sort is a divide-and-conquer algorithm that splits an array in half until subarrays contain only one
element.
[2 marks]
A. True
B. False
4
|
|
6 Page 6 |
▲back to top |
Problem B6
A subtree is any connected structure below the root.
[2 marks]
A. True
B. False
Problem B7
Time and space are not the two main measures of the efficiency of algorithms.
(2 marks]
A. True
B. False
Problem B8
The first thing to consider when using binary search to search for an element in an array is
whether the array can be recursively divided into sub-arrays.
(2 marks]
A. True
B. False
Problem B9
Given the tree below, A is a child node and Band Care root nodes.
(2 marks]
Root Node
A. True
B. False
Problem B10
The bottom of a stacl< can be accessed directly for insertion and removal of elements. (2
marks]
A. True
B. False
5
|
|
7 Page 7 |
▲back to top |
SECTIONC: Structured Questions
(60 Marks]
Answer all the questions in the booklet provided.
The section consists of 7 problems(C1-C7).
Problem Cl
Define the following terms:
a) Algorithm
b) Data structure
c) Stack
d) Parent node
(8 marks]
Problem C2
Use selection sort algorithm to sort the array below: Show content for each step/pass. (6 marks]
15
28
17
12
18
9
6
Problem C3
Consider an array {20, 57, 6, 37, 73, 89, 23} with the starting position start and its ending position end.
Sort the array using the quick sort algorithm in ascending order by selecting the mid element as a pivot.
[6 Marks)
Problem C4
Study the code fragment below and answer the questions that follows.
FOR(i = 1; i < n; i++)
temp =35
temp= array[i]
j =i- 1
WHILE (j >=0 AND array[j] > temp)
6
|
|
8 Page 8 |
▲back to top |
array(j + 1) = array[j]
j = j-1
ENDWHILE
array [j + 1] = temp
ENDFOR
(a). How many times does the inner loop{WHILE loop) iterate after complete execution of
the program for the array below;
[4 Marks]
array= {12,5,17,4,70,3}?
(b). What is the value of temp when i=3?
[2 Marks]
(c ). What is the output of the program if the code fragment highlighted in bold is added
to the algorithm?
[8 Marks]
FOR (i = 1; i < n; i++)
temp =35
temp = array[i]
j =i- 1
WHILE (j >= 0 AND arrayu] > temp)
array[j + 1] = array[j]
j = j -1
ENDWHILE
array[j + 1] = temp
FOR(count=0;count < n; count++)
DISPLAYarray[count]
ENDFOR
ENDFOR
7
|
|
9 Page 9 |
▲back to top |
Problem CS
Consider the function below and fill in the missing code fragments to display the content of a
dynamic queue if; data is the variable name that holds the actual value.
mergeSort(array[], lowerlndex, upperlndex)
{
IF(.......................................).THEN
mid= (lowerlndex + upperlndex)/2
[1 Mark]
[1 Mark]
[1 Mark]
[1 Mark]
ENDIF
}
Problem CG
MTC Namibia hires you to implement a call center management system. The system should be
able to put the incoming calls on hold until an agent is available to attend to the customer call.
The data structure should expand and shrink based on the number of calls waiting to be served.
(a). What data structure is the most suitable for the implementation of the call
management system scenario described above? Justify your answer.
[3 Marks]
(b). Provide a diagrammatic representation of the data structure you chose in Problem
C6(a)above, if three customers; cus1, cus2 and cus3 are waiting to be served in that order
respectively.
[3 Marks]
(c ). Write a pseudocode to display the customers on hold.
[8 Marks]
Problem C7
Consider the function below and fill in the missing code fragments to display the content of a
dynamic queue if; data is the variable name that holds the actual value.
[8 Marks]
display ()
8
|
|
10 Page 10 |
▲back to top |
,•
IF(front == null AND rear
............................T..H...EN
DISPLAY "empty"
ELSE
temp = [................].....
WHILE(temp != null)
DISPALY temp -> [....................................]...............
[ .........................]..
ENDWHILE
ENDIF
[2 marks]
[2 marks]
[2 marks]
[2 marks]
**************************** Endof the Paper***********************************
9