 |
DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 1ST OPP - JUNE 2022 |
|
|
1 Page 1 |
▲back to top |
n Am I BI A u n IVER s I TY
OF SCIEnCE Ano TECHnOLOGY
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: JUNE 2022
PAPER: THEORY
DURATION: 1 HOUR
MARKS: 50
EXAMINER(S)
FIRST OPPORTUNITY EXAMINATION QUESTION PAPER
Mr S. TJIRASO
MODERATOR:
Mrs S. 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
(Including this front page)
|
|
2 Page 2 |
▲back to top |
SECTIONA: Multiple Choice Questions [10 Marks]
• Answer all the questions in the provided booklet.
• The section consists of 10 questions.
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.
2. How many rows does twoDimenArray or matrix have if it is created as follows;
int[][] twoDimenArray = { {14, 19, 9, 17}, {9, 21, 3, 20},{12,15,0,15},{22,1,0,18}};?
A.4
B.3
C. 12
D.O
3. Which of the following would you use to get the value in the second row and third column of a 2D
array/matrix called twoDimenArray?
A. twoDimenArray[2][3]
B. twoDimenArray[0][2]
C. twoDimenArray[1][2]
D. twoDimenArray[3] [2]
4. Given the following tree. Give its lnorder traversal algorithm output.
A. ABDHIECGFS
B. HDIBEAFCJG
C. HIDEBFSFCA
D. ABDHIECFGS
5. What are the applications of Stack?
A. Queues in routers/switches
B. check parenthesis matching in an expression
C. Process scheduling
D. Shared resource
Page I 1
|
|
3 Page 3 |
▲back to top |
6. Which of the following is/are the levels of implementation of data structures?
A. Abstract level
B. Application level
C. Implementation level
D. All the above
7. _is not a component of data structures and algorithms.
A. Operations
B. Storage Structures
C. Algorithms
D. None of the above
8. Two vertices in a graph are said to be adjacent vertices (or neighbors) if there is a path of length
__ connecting them.
A. At least 1
B. At least 2
C. At least less than 2
0.1
9. If the node to be deleted has ____J
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
10. Which of the following is an approach to traversing a graph?
A. Binary search.
B. Sequential search.
C. BothA and Bare approaches to traversing a graph.
D. None of A or Bis an approach to traversing a graph.
SECTION B: Structured Questions [40 Marks]
• Answer all the questions in the provided booklet.
• The section consists of 4 questions.
2.1. An expression tree is a binary tree in which each internal node corresponds to an operator and each
leaf node corresponds to an operand. Given the following expression tree, write down the outcome of in-
order traversal of the tree in the provided text fields in correct order. [18]. Note: Please write in
lowercase letters where necessary.
PageI 2
|
|
4 Page 4 |
▲back to top |
2.2. What is the height of the expression tree in 2.1 above? [2]
2.3. Given the pseudocode fragment below to find the largest number in a 20 matrix, rearrange the code
fragment in correct order according to the numbering provided to successfully execute or to complete a
correct algorithm. [10]
Please provide solution in the provided booklet.
if(myValue> maxNumber) then
Solution
1.
DO (row=0 to maxNumber.length-1)
2
myValue=0
3
Print maxNumber
4
End
5
ENDDO//end outer LOOP
6
ENDDO//end inner LOOP
7
DO (column=0 to maxNumber.length-1)
8
maxNumber =myValue
9
Page I 3
|
|
5 Page 5 |
▲back to top |
endif
10
myValue= maxNumber[row][ column]
11
maxNumber=Matrix[O][O]
12
Start
13
ENDCASE
maxNumber =55
isFound=true
2.4. Study the graph below and write an algorithm in pseudocode that implements this graph using an
adjacency matrix. Your matrix should be named, nustMap. Your program/algorithm should print the
resulting matrix. [10]
**************************** End of the Paper***********************************
Page I 4