CS计算机代考程序代写 javascript Java algorithm 2021/6/15 Take Test: CAB301 Online Exam Paper – CAB301_21se1 (QUT Blackboard)

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