CS210 - Quiz 2 Master Question Bank

Big-O Analysis

Find the Big-O for each statement

Find the Big-O complexity for each of the following statements. Type your answer (e.g. O(1), O(n), O(n²), O(n log n)).

2 pts

Statement	Your Big-O Answer
The number of exchanges in a sorted data set using Insertion Sort.
The space requirements in Merge Sort, assuming the worst-case scenario is happening.
The runtime of Quick Sort on reverse-sorted data if the pivot is chosen to be the last element.
Number of data movements required by Selection Sort if the data set is already sorted.

Multiple Choice

Sorting Algorithms

The running time characterization to sort the sequence [3, 5, 7, 9, 11, 14] using Insertion Sort in ascending order is:

1 pt

A O(1) B O(n) C O(n²) D O(n log n)

The running time characterization to sort the sequence [3, 3, 3, 3, 3, 3, 3] using Selection Sort in ascending order is:

1 pt

A O(1) B O(n) C O(n²) D O(n log n)

Given the array [3, 5, 7, 9, 11, 14], the number of swaps needed to sort this sequence using Insertion Sort in ascending order is:

1 pt

A O(1) B O(n) C O(n²) D O(n log n)

Assume that you have an array of repeated values. Which of these algorithms sorts the data in the least possible time?

1 pt

A Selection Sort B Insertion Sort C Merge Sort D Quick Sort

Given the array [17, 12, 10, 8, 6, 4, 3], the best choice of pivot to perform Quick Sort is:

1 pt

A First element B Last element C Random element D Does not matter

Which of the following array sequences would result in the Quick Sort algorithm running in O(n²) time, assuming the pivot is the last element?

1 pt

A 10, 13, 17, 8, 16, 2, 15 B 15, 2, 16, 8, 17, 13, 10 C 16, 15, 17, 13, 10, 8, 2 D 17, 16, 15, 13, 10, 8, 2

The best-case scenario for Selection Sort is:

1 pt

A O(1) B O(n) C O(n²) D O(n log n)

Having both array sequences [3, 5, 7, 9, 11, 14] and [14, 11, 9, 7, 5, 3] will result in the same running time characterization when sorted using Merge Sort in ascending order.

1 pt

A True B False

MCQ - Trace

Selection Sort & Quick Sort Steps

Q10

Given the following array sequence, choose the correct sequence of steps to perform Selection Sort:

[ G | A | F | D | Z | E | C | R ]

1 pt

Step 1: A G F D Z E C R
Step 2: A G F D Z E C R (no swap, G already compared)
Step 3: A F G D Z E C R
Step 4: A D F G Z E C R

Step 1: A G F D Z E C R
Step 2: A C F D Z E G R
Step 3: A C D F Z E G R
Step 4: A C D E Z F G R

Step 1: A G F D Z E C R
Step 2: A G F D Z E C R
Step 3: A C F D Z E G R
Step 4: A C D F Z E G R

Step 1: G A F D Z E C R (unsorted, no change yet)
Step 2: A G F D Z E C R
Step 3: A C F D Z E G R
Step 4: A C D F Z E G R

Q11

Given the following array sequence, choose the correct partitioning of arrays after using Quick Sort with the pivot being the last element (after the first round of choosing the pivot):

[ 10 | 5 | 9 | 3 | 12 | 7 | 20 | 8 ]
Pivot = 8 (last element)

1 pt

Left sub-array: 7 | 5 | 3 · Right sub-array: 12 | 10 | 20 | 9

Left sub-array: 5 | 3 | 7 · Right sub-array: 10 | 9 | 12 | 20

Left sub-array: 3 | 5 | 7 · Right sub-array: 9 | 10 | 12 | 20

Left sub-array: 10 | 5 | 3 · Right sub-array: 9 | 12 | 7 | 20

Written / Code

Implementation & Analysis

Q12

Assume you have a queue of strings. Write a method that counts the number of strings with length <= X.

Note: the queue must not be destroyed.

3 pts

Q13

Find the runtime complexity of the stringLength method you wrote in Q12, and justify your answer.

1 pt

Q14

Sort the following array using Merge Sort. Show all the steps required (the full split and merge tree).

[ RUH | AMM | DMM | JED | KWI | DXB | SFO ]

2 pts

Drawing the tree is required on paper - describe the split levels and final merged result below.

Your Score

- %

- / - points

Correct

Incorrect

Partial

Scroll up to see detailed feedback under each question.