DAT 305 Week 1 Apply – Course Pre-Assessment Quiz

Order the following algorithms in the ascending order of their best-case complexity:

• Bubble sort

• Selection sort

• Quick sort

• Merge sort

a. Bubble sort < Quick sort == Merge sort < Selection sort

b. Selection sort < Quick sort < Merge sort < Bubble sort

c. Selection sort < Bubble sort < Merge sort < Quick sort

d. Quick sort < Bubble sort == Merge sort < Selection sort

Which of the following statements is true for a bubble sort structure?

a. There are three for loops, all of them separate.

b. There is a single for loop.

c. There are two for loops, one nested in the other.

d. There is a while loop.

What is the result of the following expression in postfix notation?

40 10 / 4 * 20 +

a. 10

b. 6

c. 90

d. 36

What will be the output of the following program?

a. null

null

b. value1

value2

c. A Runtime Exception will be thrown.

d. value2

value2

What will be the output of the following program?

a. value1

b. A NullPointer Exception will be thrown.

c. value1

value2

d. value1

null

For the given class, which of the following would be the best hashCode function implementation?

How many elements can be stored in a binary search tree of depth = 9?

a. 512

b. 9

c. 1023

d. 256

Consider the following string: ALAMAKOTA, and pattern to be matched: AKO. By how many positions will the first shift be performed, using the bad character rule?

a. 2

b. 1

c. 3

d. 4

What is a graph in which every pair of distinct vertices are connected by a unique edge called?

a. A cycle graph

b. A simple graph

c. A directed cycle graph

d. A complete graph

Order the following algorithms by their complexity (ascending):

1. Dijkstra’s algorithm

2. Warshall’s algorithm

3. Bellman-Ford algorithm

4. Prim’s algorithm

a. 2 > 1 > 3 > 4

b. 2 == 3 > 1 > 4

c. 4 > 1 > 3 > 2

d. 2 > 3 > 1 > 4

The given definition describes which of the following terms?

A graph without self-loop and parallel edges in it.

a. A simple graph

b. A weighted graph

c. A directed graph

d. An undirected graph

Where is the following data entity used?

a. Graph

b. Linked list

c. Double linked list

d. Binary search tree

Which data structure has a O(1) constant time operation?

a. Stack

b. Binary search tree

c. Priority queue

d. Array

Identify the algorithm used in the following code. What is its Big-O?

a. Quick sort, O(n log n)

b. Merge sort, O(n log n)

c. Bubble sort, O(n^2)

d. Insertion sort, O(n^2)

Which algorithm is used to solve the halting problem?

a. None

b. Prim’s algorithm

c. Dijkstra’s algorithm

d. Ford-Fulkerson algorithm

What is the worst-case and best-case Big-O for a P-complete problem?

a. O(n^2) and O(n)

b. O(k^n) and O(n!)

c. O(n!) and O(1)

d. O(n^n) and O(n!)

Convert the following postfix expression to infix.

abc++

a. (a + b + c)

b. a + b + c

c. (a + (b + c))

d. (a + b) + c

Which of the following shows the merge sort algorithm sorting the array [41 29 7]?

a. [41 29 7] -> [41 29][7] -> [41][29][7] -> [7 29 41]

b. [41 29 7] -> [41 29][7] -> [29 41 7] -> [7 41 29] -> [7 29 41]

c. [41 29 7] -> [29 41 7] -> [7 29 41]

d. [41 29 7] -> [41 29][7] -> [41][29][7] -> [7 29][41] -> [7 29 41]

The following algorithm takes an input array and the output array has duplicate elements removed. What is the Big-O of this algorithm?

a. O(n log n)

b. O(n)

c. O(n!)

d. O(n^2)

Which of the following is an important operation to maintain the property of O(log n) search for a binary search tree?

a. Rehash the elements into the BST

b. Delete duplicate elements in the BST

c. Sort the elements in the BST

d. Rebalance the BST after an insert

What is the Big-O of a recursive bubble sort?

a. O(n^3)

b. O(n log n)

c. O(n)

d. O(n^2)

How many times is the swap function called in the insertion sort algorithm?

a. O(n log n)

b. O(n!)

c. O(n)

d. O(n^2)

What is the data structure used in the following code?

a. Single-linked list

b. Double-linked list

c. Priority queue

d. Binary search tree

If the letters ‘A’, ‘B’, ‘C’, and ‘D’ are inserted into a queue, in what order are they removed?

a. DBCA

b. ABCD

c. BACD

d. DCBA

For a hash table with five slots, and using chaining to resolve collisions what does the inserted sequence: 35, 2, 18, 6, 3, 10, 8, 5 look like in the hash table for the hash function h(x) = x % 5?

a. [ (5, 10, 35) , (2,6) , (3,8) , () ]

b. [ (3), (5,6), (8, 10), (35) ]

c. [ (35, 10, 5) , (6), (2), (3,8) , () ]

d. [ (3, 5, 6), (10), (35), () ]

What is the Big-O for the following function?

a. O(n)

b. O(n log n)

c. O(n^3)

d. O(n^2)