Deck 14: Searching and Sorting

Question 1

In a selection sort, a list is sorted by selecting elements in the list, one at a time, and moving them to their proper positions.

Answer 1

True

Question 2

In a sequential search, you search an array starting from the middle component.

Answer 2

False

Question 3

A list is a set of related values that do not necessarily have the same type.

Answer 3

False

Question 4

To sort a list of 1000, selection sort makes about 5,000 key comparisons.

Question 5

In the binary search algorithm, two key comparisons are made through every iteration of the loop.

Question 6

In insertion sort, during the sorting phase the array containing the list is divided into three sublists.

Question 7

Selection sort swaps the smallest element in the unsorted portion of the list to a new position.

Question 8

Key comparisons are also called item comparisons.

Question 9

Suppose that you have the following list. int[] list = {2, 4, 6, 8, 10, 12, 14, 16}; Further assume that binary search is used to determine whether 15 is in list. When the loop terminates, the value of the index variable last is 6.

Question 10

In a sequential search, the array must be sorted.

Question 11

Selection sort uses nested for loops.

Question 12

A selection sort always starts with the middle element of the list.

Question 13

A sequential search is most efficient for large lists.

Question 14

The selection sort algorithm repeatedly moves the smallest element from the unsorted list to the top of the unsorted list.

Question 15

In selection sort, initially, the entire list, that is, list[0]...list[listLength], is the unsorted list.

Question 16

The insertion sort algorithm sorts a list by repeatedly inserting an element in its proper place into a sorted sublist.

Question 17

A binary search can be performed on both sorted and unsorted lists.

Question 18

On average, the number of comparisons made by a sequential search is equal to one-third the size of the list.

Question 19

Insertion sort makes approximately the same number of key comparisons as item assignments.

Question 20

A binary search starts by comparing the search item to the first item in the list.

Question 21

Suppose that you have the following list. int[] list = {1, 3, 5, 7, 9, 11, 13, 15, 17}; Further assume that binary search is used to determine whether 8 is in list. When the loop terminates, the value of the index variable first is 1.

Question 22

What is the minimum number of comparisons that have to be made to find 18 using a sequential search on the list shown in the accompanying figure?

A) 1
C) 3
B) 2
D) 4

Question 23

In a sequential search, how many key comparisons would have to be made on the list in the accompanying figure to find the number 5?

A) 4
C) 7
B) 5
D) 8

Question 24

Consider the following list. list = {20, 10, 17, 2, 18, 35, 30, 90, 48, 47}; Suppose that sequential search as discussed in the book is used to determine whether 2 is in list. Exactly how many key comparisons are executed by the sequential search algorithm?

A) 3
C) 5
B) 4
D) 8

Question 25

Suppose that you have the following list. int[] list = {5, 10, 15, 20, 25, 30, 35, 40, 45}; Further assume that binary search is used to determine whether 20 is in list. When the loop terminates, the value of the index variable first is 3.

Question 26

In general, if L is a sorted list of size n, to determine whether an element is in L, the binary search makes at most 2 * log₂n + 2 key (item) comparisons.

Question 27

If the list in the accompanying figure was sorted, what would be the middle element?

A) 7
C) 24
B) 16
D) 45

Question 28

On average in a sequential search, how many comparisons would have to be made to find an element in the list in the accompanying figure?

A) 2
C) 6
B) 5
D) 8

Question 29

If the list in the accompanying figure was to be searched using a sequential search on an unordered list, how many key comparisons would be made to find the number 44?

A) 1
C) 5
B) 3
D) 6

Question 30

A sequential search is faster than a binary search on sorted lists.

Question 31

Consider the following list. list = {24, 20, 10, 75, 70, 18, 60, 35} Suppose that list is sorted using the selection sort algorithm as discussed in the book. What is the resulting list after two passes of the sorting phase; that is, after two iterations of the outer for loop?

A) list = {10, 18, 24, 20, 75, 70, 60, 35}
B) list = {10, 18, 20, 24, 75, 70, 60, 35}
C) list = {10, 18, 24, 75, 70, 20, 60, 35}
D) list = {10, 20, 24, 75, 70, 20, 60, 35}

Question 32

To determine whether a given item is in an ordered list of length 1024, binary search makes at most 22 key comparisons.

Question 33

In a sequential search, how many key comparisons would have to be made on the list in the accompanying figure to find the number 24?

A) 1
C) 3
B) 2
D) 4

Question 34

To design a general-purpose sort method, sortList, to sort a list, which of the following must be parameters of the method sortList. (i) The array containing the list (ii) The length of the list (iii) A boolean variable indicating whether the sort was successful

A) (i)
C) (i) and (ii)
B) (ii)
D) (i), (ii), and (iii)

Question 35

Why can't a binary search be used on the list as it appears in the accompanying figure?

A) Because the list is too big
B) Because the list is not sorted
C) Because it is a list of integers
D) A binary search can be used on the list

Question 36

Consider the following list. list = {24, 20, 10, 75, 70, 18, 60, 35} Suppose that list is sorted using the insertion sort algorithm as discussed in the book. What is the resulting list after two passes of the sorting phase; that is, after three iterations of the for loop?

A) list = {10, 18, 20, 24, 75, 70, 60, 35}
B) list = {10, 20, 24, 75, 70, 18, 60, 35}
C) list = {10, 18, 20, 24, 35, 70, 60, 75}
D) list = {10, 20, 20, 18, 35, 70, 60, 75}

Question 37

If the list in the accompanying figure was sorted using selection sort, which two elements would be swapped first?

A) 5 and 16
C) 5 and 45
B) 65 and 16
D) 7 and 30

Question 38

Consider the following list. list = {20, 10, 17, 2, 18, 35, 30, 90, 48, 47}; Suppose that sequential search as discussed in the book is used to determine whether 95 is in list. Exactly how many key comparisons are executed by the sequential search algorithm?

A) 1
C) 9
B) 8
D) 10

Question 39

Suppose that L is a list of length 100. In a successful search, to determine whether an item is in L, on average the number of key comparisons executed by the sequential search algorithm, as discussed in this book, is ____.

A) 49
C) 51
B) 50
D) 100

Question 40

Based on the accompanying figure, in a sequential search, what is the minimum number of comparisons that have to be made if the search item was 10?

A) 0
C) 7
B) 1
D) 8

Question 41

If the list in the accompanying figure were to be searched using a sequential search on an ordered list, how many key comparisons would be made to find the number 44?

A) 1
C) 5
B) 3
D) 6

Question 42

What is the maximum number of key comparisons made when searching a list L of length n for an item using a binary search?

A) log n
C) 2
B) 2 * log₂n + 2
D) n

Question 43

If the list in the accompanying figure was to be searched for the number 44 using a binary search, how many key comparisons would have to be made?

A) 1
C) 5
B) 3
D) 7

Question 44

Suppose that L is a sorted list of length 1000. To determine whether an item is in L, the maximum number of comparisons executed by the binary search algorithm, as discussed in this book, is ____.

A) 1
C) 500
B) 42
D) None of these

Question 45

Consider the following list. list = {5, 11, 25, 28, 45, 78, 100, 120, 125}; Suppose that binary search as discussed in the book is used to determine whether 28 is in list. Exactly how many key comparisons are executed by binary search?

A) 6
C) 9
B) 7
D) 10

Question 46

Which technique does a binary search use to find an element in a list?

A) divide and conquer
C) first to last
B) row and column
D) hunt and peck

Question 47

If a binary search was used on the list in the accompanying figure, which element would the search element be compared to first?

A) 4
C) 44
B) 35
D) 98

Question 48

Consider the following list. list = {5, 11, 25, 28, 45, 78, 100, 120, 125}; Suppose that binary search as discussed in the book is used to determine whether 28 is in list. What are the values of first and last when the while loop in the body of the binarySearch method terminates?

A) first = 3, last = 3
C) first = 2, last = 4
B) first = 0, last = 3
D) None of these

Question 49

Consider the following list. list = {5, 11, 25, 28, 45, 78, 100, 120, 125}; Suppose that binary search as discussed in the book is used to determine whether 110 is in list. Exactly how many key comparisons are executed by binary search?

A) 3
C) 8
B) 5
D) 12

Question 50

Consider the following list. list = {5, 11, 25, 28, 45, 78, 100, 120, 125}; Suppose that binary search as discussed in the book is used to determine whether 110 is in list. What are the values of first and last when the while loop, in the body of the binarySearch method, terminates?

A) first = 6, last = 6
C) first = 7, last = 6
B) first = 6, last = 7
D) None of these