# Quiz 14: Searching and Sorting

Computing

Free

True False

False

Free

True False

False

Free

True False

True

Free

True False

Q 5Q 5

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

Free

True False

Q 6Q 6

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.

Free

True False

Free

True False

Q 8Q 8

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

Free

True False

Q 9Q 9

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

Free

True False

Q 10Q 10

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

Free

True False

Free

True False

Free

True False

Q 13Q 13

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

Free

True False

Q 14Q 14

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

Free

True False

Free

True False

Free

True False

Free

True False

Free

True False

Q 19Q 19

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

Free

True False

Q 20Q 20

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.

Free

True False

Q 21Q 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.

Free

True False

Q 22Q 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.

Free

True False

Q 23Q 23

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

Free

True False

Q 24Q 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

_{2}n + 2 key (item) comparisons.Free

True False

Free

True False

Q 26Q 26

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

Free

Multiple Choice

Q 27Q 27

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

Free

Multiple Choice

Q 28Q 28

-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

Free

Multiple Choice

Q 29Q 29

-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

Free

Multiple Choice

Q 30Q 30

-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

Free

Multiple Choice

Q 31Q 31

-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

Free

Multiple Choice

Q 32Q 32

-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

Free

Multiple Choice

Q 33Q 33

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

Free

Multiple Choice

Q 34Q 34

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

Free

Multiple Choice

Q 35Q 35

If the list in the accompanying figure was sorted, what would be the middle element?
A) 7
C) 24
B) 16
D) 45

Free

Multiple Choice

Q 36Q 36

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

Free

Multiple Choice

Q 37Q 37

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)

Free

Multiple Choice

Q 38Q 38

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}

Free

Multiple Choice

Q 39Q 39

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}

Free

Multiple Choice

Q 40Q 40

-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

Free

Multiple Choice

Q 41Q 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

Free

Multiple Choice

Q 42Q 42

-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

Free

Multiple Choice

Q 43Q 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

Free

Multiple Choice

Q 44Q 44

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

Free

Multiple Choice

Q 45Q 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

Free

Multiple Choice

Q 46Q 46

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

Free

Multiple Choice

Q 47Q 47

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

Free

Multiple Choice

Q 48Q 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
C) first = 7, last = 6
B) first = 6, last = 7
D) None of these

Free

Multiple Choice

Q 49Q 49

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

Free

Multiple Choice

Q 50Q 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
C) 2
B) 2 * log

_{2}n + 2 D) nFree

Multiple Choice