1
SECTION A
Attempt all multiple choice questions on the test answer sheet provided. Each of the questions
has four alternative answers. Choose only one (1) that best answers the question. No penalty is
given to wrong attempts. Total marks = 10.
QUESTION 1 [1 Mark]
Which of the following indicates constant time complexity in terms of big-O notation?
(a) O(1)
(b) O(n)
(c) O(log n)
(d) O(n2)
QUESTION 2 [1 Mark]
What is the worst-case time complexity in big-O notation for the following pseudocode fragment?
for i← 0 to n− 1 do
for j ← 0 to 2n− 2 do
x← x+ 1
(a) O(n)
(b) O(n2)
(c) O(n6)
(d) O(n12)
QUESTION 3 [1 Mark]
Which of the following statements is false?
(a) Nodes in a linked list need not be stored in adjacent space in memory.
(b) In a linked list pointers are used to store the location of the next node.
(c) Data stored in a linked list can be accessed by index.
(d) Linked lists are comprised of a collection of nodes that are linked together using pointers.
CAB301P1.211 cont/. . .
2
QUESTION 4 [1 Mark]
To delete a node having two children from a binary search tree (BST), we replace the node with
.
(a) the left-most node in the right sub-BST of the node
(b) the right-most node in the right sub-BST of the node
(c) the minimum element in the tree
(d) the maximum element in the tree
CAB301P1.211 cont/. . .
3
QUESTION 5 [1 Mark]
Binary search algorithm cannot be applied to .
(a) sorted linked list
(b) binary search trees
(c) sorted linear array
(d) pointer array
QUESTION 6 [1 Mark]
A stack accesses its elements in order.
(a) last in first out
(b) last in last out
(c) first in first out
(d) none of the above
CAB301P1.211 cont/. . .
4
QUESTION 7 [1 Mark]
If all edges have the same weight in an undirected graph, which algorithm will find the shortest
path between two nodes more efficiently?
(a) Dijkstra’s algorithm
(b) Floyd’s algorithm
(c) Depth-first search algorithm
(d) Breadth-first search algorithm
QUESTION 8 [1 Mark]
How many character comparisons will be made by Boyer-Moore’s algorithm in searching for
00001 in the binary text of 100 zeros?
(a) 100
(b) 96
(c) 190
(d) 192
QUESTION 9 [1 Mark]
Assume that the hash function used by a hash table is h(k) = k mod 13. What is the value of
h(50)?
(a) 0
(b) 11
(c) 13
(d) 50
CAB301P1.211 cont/. . .
5
QUESTION 10 [1 Mark]
Refer to the following graph to answer this question.
A
DE
CB
What is the minimum cost weight for the Minimum Spanning Tree of this graph?
(a) 24
(b) 25
(c) 26
(d) 27
CAB301P1.211 cont/. . .
6
SECTION B
Attempt all questions in the examination booklets. Marks for each question are as indicated. Total
marks = 10.
QUESTION 11 [7 Marks]
Refer to the following Selection Sort algorithm to answer this question:
While applying the above algorithm to sort the following array:
9 15 6 14 5 12 10 18 8 17 7 16 4 13 11
What is the status of the array at the end of the iteration of the outer for loop when i = 0, 1, 2, 3,
4, 5, and 6?
CAB301P1.211 cont/. . .
7
QUESTION 12 [3 Marks]
For the following binary tree, show the resulting order in which the nodes in the binary tree are
visited by:
(a) Pre-order traversal
(b) Post-order traversal
(c) In-order traversal
END OF PAPER
CAB301P1.211