Deck 18: Searching and Sorting

Question 1

What is the efficiency of linear search

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

Answer 1

C

Question 2

The merge sort algorithm sorts an array by splitting it into two equal-sized subarrays,sorting each subarray and merging them in one larger array.

Answer 2

True

Question 3

The Big O Notation measures the average case run time of an algorithm.

Answer 3

False
it measures the worst case run time of an algorithm.

Question 4

What is the efficiency of selection sort

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

Question 5

O(1)means that the algorithm has a constant run time.

Question 6

Linear search is faster and more complex than the binary search.

Question 7

Searching data involves determining whether a search key is present in the data and,if so,finding its location.

Question 8

A linear search algorithm will always search each and every element.

Question 9

Insertion sort is a simple and inefficient algorithm.

Question 10

If the search key is not in an array of 10 elements,how many comparisons must the linear search algorithm make

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

Question 11

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.

Question 12

The selection sort is a simple and efficient algorithm.

Question 13

After the ith iteration of an ascending order selection sort,the smallest i items of the array will be sorted in increasing order in the first i elements of the array.

Question 14

What is the efficiency of merge sort

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

Question 15

Which of the following is a negative aspect 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 16

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

A) 60 times
B) 4 times
C) 15 times
D) 16 times

Question 17

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 18

At the ith iteration of the insertion sort algorithm,the array will be sorted.

Question 19

Which of the following sorting algorithms is the fastest when sorting a large array

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