Deck 14: Applications of Arrays Searching and Sorting and Strings

Question 1

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

Answer 1

False

Question 2

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

Answer 2

False

Question 3

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

Answer 3

False

Question 4

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

Question 5

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.

Question 6

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

Question 7

Selection sort uses nested for loops.

Question 8

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

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

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

Question 11

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

Question 12

A sequential search is most efficient for large lists.

Question 13

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

Question 14

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

Question 15

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

Question 16

In a sequential search, the array must be sorted.

Question 17

Key comparisons are also called item comparisons.

Question 18

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

Question 19

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

Question 20

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

Question 21

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 22

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 23

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
B) 3
C) 5
D) 6

Question 24

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 25

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
B) 1
C) 7
D) 8

Question 26

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
B) 50
C) 51
D) 100

Question 27

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
B) 2
C) 3
D) 4

Question 28

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
B) 8
C) 9
D) 10

Question 29

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)
B) (ii)
C) (i) and (ii)
D) (i), (ii), and (iii)

Question 30

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
B) 4
C) 5
D) 8

Question 31

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

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

Question 32

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 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
B) 2
C) 3
D) 4

Question 34

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

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

Question 35

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
B) 5
C) 7
D) 8

Question 36

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 37

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 38

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

Question 39

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

Question 40

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
B) 5
C) 6
D) 8

Question 41

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
B) 35
C) 44
D) 98

Question 42

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
B) 3
C) 5
D) 7

Question 43

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
B) 5
C) 8
D) 12

Question 44

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
B) 7
C) 9
D) 10

Question 45

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
B) 42
C) 500
D) None of these

Question 46

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

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

Question 47

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
B) 3
C) 5
D) 6

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 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
B) first = 6, last = 7
C) first = 7, last = 6
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 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
B) first = 0, last = 3
C) first = 2, last = 4
D) None of these

Question 50

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
B) 2 * log₂n + 2
C) 2
D) n