 |
DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 2ND OPP - JAN 2024 |
|
|
1 Page 1 |
▲back to top |
n Am I BI A u n IV ERs ITY
OF SCIEnCE Ano TECHnOLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENT OF SOFTWARE ENGINEERING
QUALIFICATION:BACHELOR OF COMPUTER SCIENCE,BACHELOR OF INFORMATICS
QUALIFICATIONCODE:07BCMS, 07BAIT
COURSE:DATA STRUCTURESAND ALGORITHMS 1
LEVEL:5
COURSECODE:DSA521S
DATE:JANUARY 2024
PAPER:THEORY
DURATION: 3 HOURS
MARKS: 100
SECONDOPPORTUNITY/ SUPPLEMENTARYEXAMINATIONQUESTIONPAPER
EXAMINER{S)
MRS. TJIRASO
MODERATOR:
MRS S. CHIVUNO-l(URIA
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly
4.
All things
that
should
not
be marked,
e.g., any "rough
work
11
,
have
to
be
crossed out unambiguously.
THIS QUESTION PAPERCONSISTSOF 7 PAGES
(Including this front page)
PERMISSIBLE MATERIALS
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 10 problems.
[20 Marks]
Problem Al
Which data structure can be used to implement a static queue?
A. Binary tree
B. Array
C. Linked List
D. Stack
[2 Marks]
Problem A2
Which of the following statement(s) is true?
Statement A: A tree is a linear structure.
Statement B: A binary search tree is a graph.
[2 Marks]
A. Statement A is true, and statement Bis false.
B. Statement A is false, and statement Bis true.
C. Both statement A and statement B are true.
D. Both statement A and statement Bare false.
Problem A3
Which of the following statement(s) is true?
[2 Marks]
Statement A: Preorder traversal algorithm visits parent, Left child then right child.
Statement B: Postorder traversal algorithm visits right child, Left child then, parent.
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.
Problem A4
Which one of the following operations are true about merge sort?
[2 Marks]
A. It is quadratic sorting algorithm
B. It uses divide and conquer technique
C. it uses pivot to divide the list
D. None of the above
Problem AS
Which one of the following is a worst case time complexity for linear search?
A. O(n)
B. 0(1)
C. T(n)= T(n/2) +c
D. 0 (log2 n)
[2 Marks]
1
|
|
3 Page 3 |
▲back to top |
Problem A6
Which linked list does not have a null value in the address part?
A. Doubly linked list
B. Circular linked list
C. Singly linked list
D. none of the above
Problem A7
What is the minimum number of edges a graph with 2 vertices can have?
A.6
B.O
C.4
D. none of the above
Problem A8
A node in a binary tree has at most _____
A. Two
B. Three
C. four
D. none of the above
children.
(2 Marks]
[2 Marks]
[2 Marks]
Problem A9
.....is the term used to insert an element onto stack?
A. Sort
B. Pop
C. Push
D. none of the above
(2 Marks]
Problem AlO
The following numbers; 5, 8,2,9,3 are inserted into a stack in that order. If a pop () operation
is called four (4) time. What is the correct order of removal?
(2 Marks]
A. 5,8,2,9
B. 3, 9, 2, 8
C. 3,9,8,2
D. None of the above
2
|
|
4 Page 4 |
▲back to top |
SECTIONB:True and False Questions
• Answer all the questions in the provided booklet ..
• The section consists of 5 problems.
[10 Marks]
Problem Bl
A binary search algorithm has a worst case time complexity of O(n).
(2 Marks]
Problem B2
The Push() operation is used to insert an element in a stack.
(2 marks]
Problem B3
A Stack is a linear data structure.
(2 marks]
Problem B4
A queue data structure is useful for resources allocation and /or scheduling in operating
systems.
(2 marks]
Problem BS
A tree data cannot have more than two(2) children.
(2 marks]
3
|
|
5 Page 5 |
▲back to top |
SECTIONC:Structured questions
• Answer all the questions in the provided booklet.
• The section consists of 15 problems.
Problem Cl
What is an algorithm?
Problem C2
Which data Structure uses Last-In First-out (LIFO)principle?
Problem C3
Consider the following two lists given below:
A= { 7, 9, 0, 11, 5, 3, 2, 1, 8}
B = {0, 1, 2, 3, 5, 7, 8, 9, 11}
Which one would you say is a better way of storing data? Justify your answer
[70 Marks]
[2 Marks]
[1 Mark]
[3 Marks]
Problem C4
Analyse the fragment of a program given below:
mysteryFunction(array,n)
FOR(i = 0; i < n - 1; i++)
min= i
FOR(j= i + 1; j < n; j++)
IF(arrayU] < array[min])THEN
min= j
ENDIF
ENDFOR
temp= array[i]
array[i] = array[min]
array[min] = temp
ENDFOR
If the calling part of the program passesthe following array {13, 2, 10, 15, 20, 17, 1} to
mysteryFunctio n(array, n)
a) What is the general task performed by the function given above?
[1 Mark]
b) How many times does the inner loop iterate?
[2 Marks]
c) Write down the state of the array on each pass of the outer loop, from the initial array given
above to the final array.
[6 Marks]
Problem CS
The following are statements to insert an integer element/ data into a non-empty static queue. [5 Marks]
a. Check if the queue is full
i. lfthe queue is full, display an appropriate message
b. If the queue is not full
i. Move rear to the next index
ii. Insert the element/ data in the queue
4
|
|
6 Page 6 |
▲back to top |
Taking num as the variable containing the data and n as the size of the queue, write a simple
pseudocode close to a programming language to satisfy all the statements in (a, a.i) and (b, b.i,
b.ii) above.
Problem C6
Write a pseudocode to display() the elements of a queue in problem CS.
[3 Marks]
Problem C7
There have been several security incidents at NUST. It is time to improve security at NUST. Management
wants to develop an App that can be used by security personnel to check the credentials of everyone
coming through the security gate. The App will accept as input a person's student/staff number, and
output "registered student", "staff member", "unknown person" depending on whether the person is
recognised as a registered student/staff member or not.
Task:
a) What searching algorithm will be the most appropriate for this scenario?
b) Explain one disadvantage/weakness of your solution in (a)
Problem CS
Discussthe difference between merge and quick sort algorithms.
(1 Mark]
[2 Marks]
[4 Marks]
Problem C9
Given that a list has n elements, what would be the best case that could occur when linear searching for
an element?
(2 marks]
Problem ClO
Given that a list has n elements, what would be the worst case that could occur when linear searching for
an element?
(2 marks]
Problem Cll
What would be the complexity of the best case for linear search?
[2 marks]
Problem C12
What would be the complexity of the worst case for linear search?
[2 marks]
Problem C13
Consider a sorted array below and answer the questions that follow.
I -7 I -1 1o 11 I 2 13 I 4 1s I 6 1 17 I 8 19 110 111 112 I 13 J 14 11s J 16 119 I 23 133 178 I
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
(a). How many elements must be checked to try to find the value 33 in the above sorted array using binary
search?
(2 marks]
(b). State which elements (give values not indices) must be checked to try to find the value 33 in the
above sorted array using binary search?
[2 marks]
(c). State which elements (give values not indices) must be checked to try to find the value -7 in the above
sorted array using binary search?
(2 marks]
5
|
|
7 Page 7 |
▲back to top |
(d). How many elements must be checked to try to find the value 22 in the above sorted array using
binary search?
[2 marks]
(e). State which elements (give values not indices) must be checked to try to find the value 22 in the
above sorted array using binary search?
[2 marks]
Problem C14
Given the binary search algorithm below,
a. Write a complete binary search algorithm by filling the missing code in provided booklet.
Note: n is the size of the array.
(7 marks]
binarySearch (a[], n, target){
lowerBound = __ _
upperBound = ___ _
WHILE(____________
_
middle= ________________
_
IF (target== a[middle]) THEN
return ______
_
ELSEIF(._________
) THEN
upperBound = middle - 1
ELSE
ENDIF
ENDWHILE
return -1
b. When searching for a target in an array using a binary search algorithm, which are the two main
conditions that determines when the searching stops.
[2 marks]
c. Given the array below
A[] = {1, 5, 6, 8, 10, 22, 30, 42}
target= 10
Provide a logical representation of a binary search algorithm when searching for the element 10 in the
array: A[].
[5 marks]
Problem ClS
(a). Draw the binary search tree that is created if the following values are inserted in the tree in the given
order; 10, 13, 1, 21, 27, 12
[6 marks]
(b). What will be the output of the pre-order and post order traversal algorithms for the tree in C15 (a)?
[2 marks]
**** ******* * * * * ***** *** * * ** * *** ** *** End of Exam****************************************
6