Deck 19: Searching, Sorting and Big O

Question 1

How many comparisons will the linear search algorithm make if the search key is not in an array of 10 elements?

A)0.
B)10.
C)9.
D)5.

Answer 1

B

Question 2

What is the efficiency of selection sort?

A)O(n2).
B)O(n log n).
C)O(n).
D)O(1).

Answer 2

A

Question 3

What is the efficiency of linear search?

A)O(1).
B)O(log n).
C)O(n).
D)O(n2).

Answer 3

C

Question 4

Which of the following sorting algorithms is the fastest?

A)Selection sort.
B)Insertion sort.
C)Merge sort.
D)They all run at roughly the same speed.

Question 5

What does the first pass of selection sort do?

A)Splits the array into two approximately equal pieces.
B)Orders the first two elements of the array.
C)Partitions the array into two unequal pieces depending on whether each element in the array is greater or less that some pivot element.
D)Locates the smallest element in the array and swaps it into the zeroth position.

Question 6

Which of the following is a negative of binary search?

A)It requires significantly more memory than linear search.
B)It is slower than linear search.
C)The data must be in sorted order.
D)None of the above.

Question 7

Which of the following is not a name for a big O run time?

A)Constant run time.
B)Variable run time.
C)Linear run time.
D)Quadratic run time.

Question 8

What is the efficiency of merge sort?

A)O(log n).
B)O(n).
C)O(n log n).
D)O(n2).

Question 9

What is the base case for the recursive merge sort algorithm?

A)Any array that is already sorted.
B)A two-element array.
C)A one-element array.
D)A zero-element array.

Question 10

Which of the following is a way to sort data?

A)Alphabetically.
B)In increasing numerical order.
C)Based on an account number.
D)All of the above.

Question 11

What is the maximum number of comparisons required to find a search key in a 31-element array?

A)4.
B)5.
C)32.
D)1.

Question 12

What does each iteration of the insertion sort algorithm do?

A)Each iteration takes the next smallest element and inserts it at the beginning of the array.
B)Each iteration takes the next element in the unsorted portion of the array and inserts it into the sorted portion.
C)Sorted subarrays are inserted into the larger array.
D)Each iteration determines the location of a pivot and inserts it into place.

Question 13

How much faster is insertion sort with a 15-element array than with a 60-element array?

A)60 times.
B)4 times.
C)15 times.
D)19 times.

Question 14

What is the term used for binary search's run time?

A)Linear run time.
B)Quadratic run time.
C)Constant run time.
D)Logarithmic run time.