Deck 18: Searching and Sorting Algorithms

Question 1

Consider the following list:int list[] = {4, 8, 19, 25, 34, 39, 45, 48, 66, 75, 89, 95} When performing a binary search for 75, after the first comparison, the search is restricted to ____.

A) list[0]...list[6]
B) list[0]...list[7]
C) list[5]...list[11]
D) list[6]...list[11]

Answer 1

D

Question 2

The selection sort algorithm finds the location of the smallest element in the unsorted portion of the list.

Answer 2

True

Question 3

A sequential search of an n-element list takes ____ key comparisons if the item is not in the list.

A) 0
B) n/2
C) n
D) n²

Answer 3

C

Question 4

The binary search algorithm can be written iteratively or recursively.

Question 5

In a bubble sort, the smaller elements move toward the bottom, and the larger elements move toward the top of the list.

Question 6

With the binary search algorithm, ____ key comparison(s) is/are made in the successful case-the last time through the loop.

A) one
B) two
C) n-2
D) n

Question 7

The sequential search algorithm does not require that the list be sorted.

Question 8

In a binary search, first, the search item is compared with the last element of the list.

Question 9

The swap function of quick sort is written differently from the swap function for selection sort.

Question 10

In the average case, sequential search typically searches ____.

A) one quarter of the list
B) one third of the list
C) one half of the list
D) the entire list

Question 11

The formula to find the index of the middle element of a list is ____.

A) (mid + last)/2
B) (first + last) - 2
C) (first + last) / 2
D) (first + mid ) * 2

Question 12

Assume that list consists of the following elements.What is the result after bubble sort completes? int list[] = {2, 56, 34, 25, 73, 46, 89, 10, 5, 16};

A) 89 73 56 46 34 25 16 10 5 2
B) 2 56 34 25 5 16 89 46 73
C) 2 5 10 16 25 34 46 56 73 89
D) 2 10 16 25 34 46 56 73 89

Question 13

In a bubble sort for list of length n, the first step is to compare elements ____.

A) list[0] and list[n]
B) list[0] and list[n-1]
C) list[0] and list[1]
D) list[n-1] and list[n+1]

Question 14

Consider the following list:int list[] = {4, 8, 19, 25, 34, 39, 45, 48, 66, 75, 89, 95} When performing a binary search, the target is first compared with ____.

A) 4
B) 25
C) 39
D) 95

Question 15

The sequential search algorithm uses a(n) ____ variable to track whether the item is found.

A) int
B) bool
C) char
D) double

Question 16

In the bubble sort algorithm, the following code accomplishes swapping values in elements at positions index and index + 1.

A) list[index] = list[index + 1]
List[index + 1] = list[index]
B) list[index + 1] = list[index]
List[index] = list[index + 1]
C) list[index] = temp;
List[index] = list[index + 1];
Temp = list[index + 1];
D) temp = list[index];
List[index] = list[index + 1];
List[index + 1] = temp;

Question 17

Suppose that L is a sorted list of size 1024, and we want to determine whether an item x is in L.From the binary search algorithm, it follows that every iteration of the while loop cuts the size of the search list by half.

Question 18

During the sorting phase of insertion sort, the array containing the list is divided into two sublists, sorted and unsorted.

Question 19

A sequential search of an n-element list takes ____ key comparisons on average to determine whether the search item is in the list.

A) 0
B) n/2
C) n
D) n²

Question 20

If n = 1000, then to sort the list, selection sort makes about 50,000 key comparisons.

Question 21

With insertion sort, the variable firstOutOfOrder is initialized to ____, assuming n is the length of the list.

A) 0
B) 1
C) n - 1
D) n

Question 22

The top node of a comparison tree is call the ____________________ node.

Question 23

For a list of length n, selection sort makes ____ item assignments.

A) n(n - 1)/2
B) 3(n - 1)
C) 3(n)
D) 4(n + 1)

Question 24

____ sort requires knowing where the middle element of the list is.

A) Merge
B) Bubble
C) Insertion
D) Selection

Question 25

A comparison tree is a(n) ____________________ tree.

Question 26

Assuming the following list declaration, which element is at the position 0 after the first iteration of selection sort? int list[] = {16, 30, 24, 7, 62, 45, 5, 55}

A) 5
B) 7
C) 16
D) 62

Question 27

The first step in the quick sort partition algorithm is to determine the ____________________ and swap it with the first element in the list.

Question 28

When moving array values for insertion sort, to move list[4] into list[2], first ____.

A) move list[2] to list[3]
B) delete list[2]
C) move list[4] to list[3]
D) copy list[4] into temp

Question 29

Let f be a function of n.By the term ____________________, we mean the study of the function f as n becomes larger and larger without bound.

Question 30

When working with the unsorted portion of a list, the second step in a selection sort is to ____.

A) divide the list into two parts
B) move the smallest element to the top of the list (position 0)
C) move the smallest element to the beginning of the unsorted list
D) find the smallest element

Question 31

If n = 1000, to sort the list, bubble sort makes about ____ item assignments.

A) 10,000
B) 100,000
C) 250,000
D) 500,000

Question 32

For a list of length n, insertion sort makes ____ key comparisons, in the worst case.

A) n(n - 1)/4
B) n(n - 1)/2
C) n²
D) n³

Question 33

For a list of length n, the bubble sort makes exactly ____________________ key comparisons.

Question 34

The ____________________ search algorithm is the optimal worst-case algorithm for solving search problems by using the comparison method.

Question 35

The behavior of quick sort is ____ in the worst case and ____ in the average case.

A) O(nlog₂n), O(nlog₂n)
B) O(n²), O(n)
C) O(nlog₂n), O(n²)
D) O(n²), O(nlog₂n)

Question 36

To construct a search algorithm of the order less than log₂n, it cannot be ____________________ based.

Question 37

We can trace the execution of a comparison-based algorithm by using a graph called a ____.

A) pivot table
B) partition table
C) comparison tree
D) merge tree

Question 38

A sequence of branches in a comparison tree is called a(n) ____________________.

Question 39

In a quick sort, all of the sorting work is done by the function ____________________.

Question 40

The behavior of merge sort is ____ in the worst case and ____ in the average case.

A) O(nlog₂n), O(nlog₂n)
B) O(n²), O(n)
C) O(nlog₂n), O(n²)
D) O(n²), O(nlog₂n)