 |
DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 1ST OPP - NOV 2022 |
|
|
1 Page 1 |
▲back to top |
n Am I BI A u n IVER s ITY
OF SCIEnCE Ano TECHn OLOGY
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: NOVEMBER 2022
PAPER:THEORY
DURATION: 2 HOURS
MARKS: 80
EXAMINER(S)
MODERATOR:
FIRST OPPORTUNITY EXAMINATION QUESTION PAPER
MR. STEVEN TJIRASO
MR. RIAHAMA MUSUTUA
MR. HEREKO KAVIMAKA
MS. HILMA TOBIAS
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 4 PAGES
(Excluding this front page)
PERMISSIBLE MATERIALS
1. NON-PRGRAMMABLE CALCULATOR
|
|
2 Page 2 |
▲back to top |
|
|
3 Page 3 |
▲back to top |
QUESTION 1: Multiple Choice Questions [10 Marks]
• Answer all the questions in the provided booklet.
• The question consists of 10 questions.
1.1. Which of the following operations can be performed on singly-linked list, doubly-linked list and circular
linked 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.
1.2. When trying to delete data from a stack, but the stack is empty; this condition is usually called ...
A. Underflow
B. Overflow
C. FullCapacity
D. Error
1.3. A sorting algorithm that uses a divide and conquer approach to sorting lists is
A. Insertion Sort
B. Bubble Sort
C. Quick Sort
D. Selection Sort
1.4. Which of the following would you use to get the value in the first row and second column of a 2D
array/matrix called twoDimenArray?
A. twoDimenArray[2][3]
B. twoDimenArray[0] [1]
C. twoDimenArray[1] [2]
D. twoDimenArray[3] [2]
1.5. Given the following tree. Give its postorder traversal algorithm output.
A. ABDHIECGFJ
B. HDIBEAFCJG
C. HIDEBFJGCA
D. HDIBEGFCJA
1.6. What are the applications of Stack?
A. Queues in routers/switches
Page 11
|
|
4 Page 4 |
▲back to top |
|
|
5 Page 5 |
▲back to top |
B. Check parenthesis matching in an expression
C. Process scheduling
D. Shared resource
1.7. Which one of the following is a non-linear data structure?
A. Queue
B. Stack
C. Graph
D. All the above
1.8. 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.9. If the node to be deleted has ___,
node's parent.
A. Only a left subtree
B. Only a right subtree
C. No children
D. Has no children
we delete the node and attach the left subtree to the deleted
1.10.
Which one of the following is a searching algorithm?
A. Merge Search
B. Sequential search
C. Quick Search
D. Selection search
PageI 2
|
|
6 Page 6 |
▲back to top |
|
|
7 Page 7 |
▲back to top |
QUESTION 2: Structured Questions (70 Marks]
• Answer all the questions in the provided booklet.
• The Question consists of 5 questions.
2.1 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, conceptually. Your diagram
must clearly show the cells as well as the cell index.
[12 Marks]
2.2 Consider the following data elements: 23, 12, 10, 56, 8, by way of a diagram show how the above
data can be stored using a singly-linked list.
[12 Marks]
2.3 Study the code fragment below and answers the following questions.
mystery (marks[], size)
FOR (outerCounter=O to size-1)
lowestlndiex= outerCounter
FOR (innerCounter= outerCounter +1 to size-1)
IF(marks[innerCounter] < marks[lowestlndiex] )THEN
lowestlndiex= innerCounter
ENDFOR
ENDIF
ENDFOR
marks[outerCounter]=
marks[lowestlndiex]
END mystery()
a) What is the final output of the algorithm if an array, marks= {45, 75, 62, 18} is passed to
function mystery()?
[8 marks]
b} If the two (2) highlighted lines are added, what will be the output for the same array,
marks={45,75, 62,18}. Show state or content of array after each iteration of the outer loop.
[6 Marks]
mystery (marks[], size)
FOR (outerCounter=O to size-1)
lowestlndiex= outerCounter
FOR (innerCounter= outerCounter +1 to size-1)
IF(marks[innerCounter] < marks[lowestlndiex] )THEN
lowestlndiex= innerCounter
ENDIF
ENDFOR
temp= marks[outerCounter]
marks[ outerCounter ]= marks [lowestl ndiex]
marks[lowestlndiex]= temp
Page I 3
|
|
8 Page 8 |
▲back to top |
|
|
9 Page 9 |
▲back to top |
ENDFOR
ENDmystery()
45, 75, 62, 18 (original list)
AFTER 1st iteration of outer loop
AFTER2nd iteration of outer loop
AFTER3rd iteration of outer loop
c) What is the general task performed by the function mystery() in (b) above?
[ 2 marks]
2.4 Given the following output of a postorder traversal of a binary tree;
Output: 21, 40,65,41,30
a) Recreate the binary tree for the postorder traversal output provided above.
[10 marks]
b) What is the output of a preorder traversal of the tree you created in 2.4(a) above?
Output:
[4 marks]
c) What is the output of an inorder traversal of the tree you created in 2.4(a) above?
Output:
[4 marks]
2.5 Study the below and answer the questions that follows.
a) One of the ways to represent a graph data structure is an adjacency matrix. Draw the adjacency
matrix for this graph.
[10 Marks]
b) What is the in-degree of the node WB?
[2 Marks]
**************************** Endof the Paper ***********************************
Page I 4
|
|
10 Page 10 |
▲back to top |
