2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 1/9
Take Test: CAB301 Online Exam Paper
Test Information
Description
Instructions
Timed Test This test has a time limit of 2 hours and 10 minutes.This test will save and submit automatically when
the time expires.
Warnings appear when half the time, 5 minutes, 1 minute, and 30 seconds remain.
Multiple
Attempts
This test allows multiple attempts.
Force
Completion
This test can be saved and resumed at any point until time has expired. The timer will continue to run if
you leave the test.
–You may use any book and written materials
–You may use a calculator of any type, if you wish
–You are not allowed to google the Internet
–You are not allowed to use any electronic material
This is an open book exam. During this online exam:
Attempt all twenty-three (23) questions on this online exam paper.
Marks for each question are as indicated.
Total marks = 40.
QUESTION 1
Which of the following sorting algorithms is good choice for an array that has few
items out of place?
Heap sort
Merge sort
Quick sort
Insertion sort
1 points Save Answer
QUESTION 2
What is the output of the pre-order traversal of the binary tree below?
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 2/9
A B C D E F G H I J
A B D F E C H J I G
G C B A E D F H J I
G C B A E D F I J H
QUESTION 3
What is the output of the in-order traversal of the binary tree below?
A B C K E F G I H J
A B K F E G C I J H
A B C E F G H I J K
A K F H B E J C I G
1 points Save Answer
QUESTION 4
How many comparisions (both successful and unsuccessful) will be made by the
brute force string matching algorithm in searching for the pattern BEAUTIFUL in
the text
WHAT_A_BEAUTIFUL_DAY
14
15
16
17
1 points Save Answer
QUESTION 5
How many comparisions (both successful and unsuccessful) will be made by the
brute force string matching algorithm in searching for the pattern DAY in the
text
WHAT_A_BEAUTIFUL_DAY
20
21
22
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 3/9
23
QUESTION 6
If the sequence of operations
Enqueue(1); Enqueue(2); Enqueue(3); Dequeue(); Enqueue(4); Dequeue(); Enqueue(5)
are performed on a queue, which is initially empty, what is the state of the queue?
Assume that
the left-most value is the head of the queue and the right-most value is the tail of the
queue.
1 2 3
2 3 4
3 4 5
5 4 3
1 points Save Answer
QUESTION 7
Which of the following is false about a binary search tree?
The left child is always less than or equals to its parent.
The right child is always greater than or equals to its parent.
The left and right sub-trees should also be binary search trees.
The nodes visited by the in-order traversal are in decreasing order.
1 points Save Answer
QUESTION 8
Refer to the following weighted undirected graph to answer this question.
What is the cost weight of the Minimal Spanning Tree of this graph?
57
58
35
63
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 4/9
QUESTION 9
If the sequence of operations
Enqueue(1); Enqueue(2); Enqueue(3); Dequeue(); Enqueue(4); Dequeue(); Enqueue(5)
are performed on a queue, which is initially empty, what is the state of the queue?
Assume that
the left-most value is the head of the queue and the right-most value is the tail of the
queue.
1 2 3
2 3 4
3 4 5
5 4 3
1 points Save Answer
Path: p Words:0
QUESTION 10
Use Floyd’s algorithm to �nd the shortest distance between every pair of vertices in the graph below. Show
how the distance matrix, D, updates at the end of each iteration of the outmost for loop.
Arial 3 (12pt)
8 points Save Answer
QUESTION 11
Suppose the partition function of the quicksort algorithm is called on this array:
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 5/9
Suppose the partition function of the quicksort algorithm is called on this array:
12 21 18 15 3 24 0
Which of the arrays below will result from the call? (Assume partition chooses the
�rst element as the pivot)
0 3 12 15 18 21 24
3 0 12 15 18 24 21
12 0 3 15 18 21 24
3 0 15 12 18 24 21
QUESTION 12
An array of elements can be sorted using the heap sort algorithm. The �rst step of
the heap sort algorithm is to convert the array into a maximum heap. If the following
array is to be sorted:
80 65 55 35 5 75 40 45 10 15 25
What is the order of the elements in the array after the array is converted into a
maximum heap?
80 75 65 55 45 40 35 25 15 10 5
5 10 15 25 35 40 45 55 65 75 80
80 65 75 45 25 55 40 35 10 15 5
80 65 45 75 25 55 40 35 10 15 5
1 points Save Answer
QUESTION 13
Which of the folowing indicates constant time complexity in terms of big-O notation?
O(1)
O(n)
O(log n)
O(n2)
1 points Save Answer
QUESTION 14
Consider the node of a complete binary tree whose value is stored in data[6] for an
array implementation. Assume that the root value is stored in data[0]. If this node
has a left child, where
will the right child’s value be stored?
data[7]
data[12]
data[13]
data[14]
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 6/9
QUESTION 15
Consider an implementation of unsorted singly linked list. Suppose it has its
representation with a head pointer only. Given the representation, which of the
following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
I and II
I and III
I, II and III
I, II and IV
1 points Save Answer
QUESTION 16
What is the worst-case time complexity in big-O notation for the following
algorithm?
O(1)
O(log n)
O(n)
O(n2)
1 points Save Answer
QUESTION 17
a. Initially the hash table is empty. Insert 20, 21, 24, 37, 54 to the hash table in this order.
What is the resulting hash table after each of the insertions?
b. Initially the hash table is empty. Insert 17, 33, 50 in this order, then delete 33, and then
insert 67. What is the resulting hash table after each of the operations?
Assume that a hash table has 17 buckets. The hash function used by the hash table is H(k) = k %17, and the
collision resolution technique used by the hash table is Linear Probing.
Arial 3 (12pt)
5 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 7/9
Path: p Words:0
QUESTION 18
Binary search cannot be applied to ______ .
an array of sorted integers
an array of sorted objects
a binary search tree
a linked list of sorted nodes
1 points Save Answer
Path: p Words:0
QUESTION 19
Refer to the following Bubble Sort algorithm to answer this question:
While applying the above algorithm to sort the following array:
13, 5, 14, 7, 9, 1, 11, 2, 12, 3, 15, 6, 8, 10, 4
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, 6 and
7?
Arial 3 (12pt)
7 points Save Answer
QUESTION 20
If the elements A, B, C and D are placed in a stack and are deleted one at a time, what
is the order of removal?
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
javascript:;
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 8/9
ABCD
DCBA
DCAB
ABDC
QUESTION 21
What is the worst-case time complexity in big-O notation for the following
algorithm?
O(1)
O(n)
O(n2)
O(n3)
1 points Save Answer
QUESTION 22
The following graph is a Directed Acyclic Graph (DAG). Which of the following is NOT a
possible topological sort order for the DAG?
5 8 7 4 9 3 1 2 6
5 7 3 4 9 1 2 6 8
5 3 1 2 6 8 4 9 7
5 4 9 7 3 1 2 6 8
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers
2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)
https://blackboard.qut.edu.au/webapps/assessment/take/launch.jsp?course_assessment_id=_139097_1&course_id=_154917_1&content_id=_92… 9/9
5 4 9 7 3 1 2 6 8
QUESTION 23
Assume that among all nodes adjacent to the one currently being visited, the
numerically least one will be visited �rst. Starting at node 5, what is the order of
traversal for a depth �rst search of the graph below?
5 3 1 2 6 8 4 9 7
5 3 1 2 6 8 7 4 9
5 3 4 6 7 8 1 2 9
5 4 9 3 1 2 6 8 7
1 points Save Answer
Show Timer
Question Completion Status:
Click Save and Submit to save and submit. Click Save All Answers to save all answers. Save All Answers