cab301 a short practice PDF

Preview

Summary

Download cab301 a short practice PDF

Description

Review Test Submission: A short practicing final exam – ... (QUT Blackboard)

Units bal Menu

×

Enter Student Preview

Review Test Submission: A short practicing final exam

Edit Mode is:

Content Area

xity฀H

Module Page

Web Link User

Maolin Tang

Unit

Algorithms and Complexity

Subheader

Test

A short practicing final exam

Divider

Started

5/06/20 5:44 PM

Submitted

5/06/20 5:44 PM

Student ePortfolio

Status

Needs Grading

Unit Details

Attempt Score

Grade not available.

Learning Resources

Time Elapsed

0 minute out of 2 hours and 10 minutes

Instructions

Attempt all the questions online.

Assessment

Results Displayed All Answers, Correct Answers

Timed Online Exam Paper

Question 1

0 out of 1 points

Unit Management Use the definitions of O (upper bound), Θ (tight bound), and Ω (lower bound) to determine which of the following assertions is not true.

Control Panel Files

฀ Answers:

Unit Tools Evaluation

฀

Grade Centre

฀

3n 3 + 4n 2 + 5 ∈ Θ(n3)

฀

Packages and Utilities

฀

Help

3n 3 + 4n 2 + 5 ∈ O(n4)

3n 3 + 4n 2 + 5 ∈ O(n3)

Users and Groups Customisation

•

Review Test Submission: A short practicing final exa m

Tool Link

Unit Link

S ON

3n 3 + 4n 2 + 5 ∈ Ω(n4)

Question 2

Consider the following algorithm:

0 out of 1 points

Review Test Submission: A short practicing final exam – ... (QUT Blackboard)

What is the efficiency class of the algorithm?

Answers:

Ω(n) Θ(n) Θ(n2)

Θ(log n)

Question 3

0 out of 1 points

Which of the following statements is false?

Answers: Nodes in a linked list need not be stored in adjacent space in memory.

In a linked list pointers are used to store the location of the next node.

Data stored in a linked list can be accessed by index.

Linked lists are comprised of a collection of nodes that are linked together using pointers.

Question 4

0 out of 1 points

To delete a node having two children from a binary search tree (BST), we replace the node with ____ .

Answers: the left-most node in the right sub-BST of the node

Review Test Submission: A short practicing final exam – ... (QUT Blackboard)

the right-most node in the right sub-BST of the node the minimum element in the tree the maximum element in the tree

Question 5

0 out of 1 points

Binary search algorithm cannot be applied to _____ .

Answers:

sorted linked list

binary search trees sorted linear array pointer array

Question 6

0 out of 1 points

The best case, in terms of the asymptotic running time, for QuickSort happens when ______.

Answers:

the array is already sorted the array is sorted in reverse

the number of elements to the right of the pivot is approximately equivalent to the number of elements to the left of the pivot all elements of the array are negative

Question 7

0 out of 1 points

Review Test Submission: A short practicing final exam – ... (QUT Blackboard)

In order to get the contents of a binary search tree (BST) in ascending order, one has to traverse it in ______.

Answers:

pre-order in-order post-order

not possible

Question 8

0 out of 1 points

Refer to the following binary search tree:

What is the output of the post-order traversal of the binary search tree above?

Answers: EGFDCBA

GFDECBA

DFGEBCA GFDEBCA

Question 9

0 out of 1 points

Review Test Submission: A short practicing final exam – ... (QUT Blackboard)

How many character comparisons will be made by Horspool’s algorithm in searching for ABABA in the binary text of 100 A's?

Answers: 100 96

190

192

Question 10

0 out of 1 points

Assume that the hash function used by a hash table is h(k) = k mod 13. What is the value of h(50)?

Answers:

0 11

13

50

Question 11

Needs Grading

Refer to the following Insertion Sort algorithm to answer this question:

Review Test Submission: A short practicing final exam – ... (QUT Blackboard)

While applying the above algorithm to sort the following array: 4, 5, 7, 9, 1, 2, 3, 6, 8 What is the status of the array at the end of the iteration of the for loop when i = 1, 2, 3, 4, and 5?

Correct Answer:

Question 12

[4, 5, 7, 9, 1, 2, 3, 6, 8] i=1 4 5 7 9 1 2 3 6 8 i=2 4 5 7 9 1 2 3 6 8 i=3 4 5 7 9 1 2 3 6 8 i=4 1 4 5 7 9 2 3 6 8 i=5 12 4 5 7 9 3 6 8

Needs Grading

Use Dijkstra's algorithm to find the shortest distances to all vertices, with F as the source using the following graph. Show full details of your working to illustrate your understanding of the algorithm.

Correct Answer:

After initialisation: S = {F} W[0]=7 W[1]=--- W[2]=--- W[3]=2 W[4]=6 W[5]=--At the end of the iteration when i = 2 : S = {D, F} W[0]=7 W[1]=--- W[2]=9 W[3]=2 W[4]=6 W[5]=--At the end of the iteration when i = 3 : S = {D, E, F}

Review Test Submission: A short practicing final exam – ... (QUT Blackboard)

W[0]=7 W[1]=--- W[2]=8 W[3]=2 W[4]=6 W[5]=--At the end of the iteration when i = 4 : S = {A, D, E, F} W[0]=7 W[1]=15 W[2]=8 W[3]=2 W[4]=6 W[5]=--At the end of the iteration when i = 5 : S = {A, C, D, E, F} W[0]=7 W[1]=11 W[2]=8 W[3]=2 W[4]=6 W[5]=--At the end of the iteration when i = 6 : S = {A, B, C, D, E, F} W[0]=7 W[1]=11 W[2]=8 W[3]=2 W[4]=6 W[5]=--0: A 1: B 2: C 3: D 4: E 5: F

Friday, 5 June 2020 5:44:54 PM AEST

← OK

QUT Home

CRICOS No. 00213J Accessibility

HiQ

Digital Workplace

ABN 83 791 724 622 Copyright

Disclaimer

Privacy

Right to Information...