DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 2ND OPP SUPL - JAN 2023


DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 2ND OPP SUPL - JAN 2023



1 Pages 1-10

▲back to top


1.1 Page 1

▲back to top


n Am I BI A u n IVER s ITY
OF SCIEnCE Ano TECHnDLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENT OF COMPUTER SCIENCE
QUALIFICATION: BACHELOR OF COMPUTER SCIENCE, BACHELOR OF INFORMATICS
QUALIFICATION CODE: 07BCMS, 07BAIT
LEVEL: 5
COURSE: DATA STRUCTURESAND ALGORITHMS 1
COURSE CODE: DSA521S
DATE: JANUARY 2023
PAPER: THEORY
DURATION: 2 HOURS
MARKS: 80
SECOND OPPORTUNITY/
EXAMINER($)
SUPPLEMENTARY EXAMINATION
MR. STEVEN TJIRASO
MR. RIAHAMA MUSUTUA
MR. HEREKO KAVIMAKA
MS. HILMA TOBIAS
QUESTION PAPER
MODERATOR.
MRS. SHILUMBE CHIVUNO-KURIA
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly
THIS QUESTION PAPER CONSISTS OF 5 PAGES
(Excluding this front page)
PERMISSIBLE MATERIALS
1. NON-PRGRAMMABLE CALCULATOR

1.2 Page 2

▲back to top


1.3 Page 3

▲back to top


QUESTION 2: Multiple Choice Questions [10 Marks]
• Answer all the questions in the provided booklet.
• The question consists of 10 questions.
1.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. Stack
D. Graph
1.2 What are the applications of queue data structure?
A. Queues in routers/switches
B. check parenthesis matching in an expression
C. Process scheduling
D. Shared resource
1.3 The worst-case time complexity of Binary Search Tree (BST}is
A. O(n)
B. O(log n)
C. O(N 2 )
D. O(n log n)
1.4 Two vertices in a graph are said to be adjacent vertices (or neighbours) if there is a path of length __
connecting them.
A. At least 1
B. At least 2
C. At least less than 2
D.1
1.5 If an array is sorted and size is large, it is recommended to use __
A. Sequential
B. Binary
C. Sentinel
D. Probability
search to search it.
1.6 If the node to be deleted has _,
we delete the node and attach the left subtree to the deleted
node's parent.
A. Only a left subtree
B. Only a right subtree
C. No children
D. Has no children
1.7 Push and pop operations are found in____
_
A. Queues
B. Lists
C. Stacks
D. Tail

1.4 Page 4

▲back to top


1.5 Page 5

▲back to top


1.8 What is the worst-case time complexity of a linear search algorithm?
A.0(1)
B. O(n)
C. O(log n)
D. O(n2)
1.9 Stack data structure works on____
principle.
A. Last In First Out (LIFO)
B. First In First Out (FIFO)
C. First In Last Out (FILO)
D. None of the above
1.10 Consider the following statements (i and ii) related to queues. Which of the choices; A, B, C or D is
correct about queues:
i) The insertion is done at REARand deletion at FRONTend.
ii) A queue is also known as LIFOlist.
A. Statement i) is true and ii) is false
B. Statement ii) is true and i) is false
C. Statement i) is false and ii) is false
D. Statement i) is true and ii) is true

1.6 Page 6

▲back to top


1.7 Page 7

▲back to top


QUESTION 2: Structured Questions [70 Marks]
• Answer all the questions in the provided booklet.
• The question consists of 8 questions.
2.1. Briefly discuss Give the difference between the following terms as used in Data Structures:
1. Big O Notation and Tree
[4 marks]
2. Binary search and Linear search algorithms
[4 marks]
3. Graph and Queue
[4 marks]
4. Which of the following permutations can be obtained in the same order using a stack.
Assuming that input is the sequence: 5, 6, 7, 8, 9, in that order?
i. 7, 8, 9, 5, 6
ii. 5, 9, 6, 7, 8
iii. 9, 8, 7, 5, 6
iv. 7, 8, 9, 6, 5
[3 Marks]
2.2. Study the BSTbelow and answer all the questions
a) Write a an pseudocode for the lnOrder traversal
[S marks]
b) Write down all its BSTtraversal outputs below: PreOrder, PostOrder and lnOrder [6 marks]

1.8 Page 8

▲back to top


1.9 Page 9

▲back to top


2.3. Study the BSTbelow:
a) Delete the following nodes: 16 and 3, Add node 12 and 15 and draw the new BST.
[6 marks]
b) What is the maximum height/level of the BSTafter the operations in (a)?
[3 marks]
2.4. Study the Pseudocode below.
Step-1 Start
Step-2 Input Sides of Triangle A,B,C
Step-3 S= (A+ B + C)/ 2.0
Step-4 Area= sqrt(S x (S-A)x (S-B)x(S-C))
Step-5 Perimeter= Sl + S2 + S3 or A+B+C
Step-6 Display Area, Perimeter
Step-7 Stop
Write a flowchart corresponding to the pseudocode program above.
[4 marks]
2.5. Use the Insertion sort algorithm to sort the array below: 4,3,2,10,12,1,5,6. Show content for each
step.
[6 marks]
2.6. Given the following array, Describe how a Jump search mechanism works, also calculate the number of
blocks needed to search for the element at index 11. Show your work.
[5 Marks]
11 12 13 1 4 1 5 16 111 113 119 145 1 65 182 1 91 1105 1200 1 300 1

1.10 Page 10

▲back to top


2 Pages 11-20

▲back to top


2.1 Page 11

▲back to top


Ir
'I
2. 7. The following diagram represents a graph of some towns.
Give the result if the graph is traversed using;
a) Depth-first-search starting at vertex WB.
b) Breadth-first-search starting at vertex WB.
[10 marks]
(6 Marks]
2.8 Study the two (2) sample codes below.
Sample code A
Sample code B
FOR (countl=0 to size-1)
FOR(count2=count1+1
PRINT (count2)
ENDFOR
ENDFOR
to size-1)
FOR(countl=0 to 100}
PRINT (count2)
ENDFOR
Considering time complexity classes we have studied in class such as constant/O(1), Linear/O(N),
quadratic/O(N 2), logarithmic/O(log N) etcetera;
a) What is the worst case time complexity of Sample code A?
[2 Marks]
b) What is the worst case time complexity of Sample code B?
(2 Marks]
*************************** End of Paper***********************************

2.2 Page 12

▲back to top


nRmlBIA
UnlVERSITY
CF S'1En(!! RnD
TECHnOLOGY
P/Bag13383
Windhoek
NAMIBIA
2022-10- 1 8
------{S~ FACULTOYFCOMPUTIN&GINFORMATICS
DEPARTMEl'H,CUMPIJTE~