Question 1

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.

Accepted Answer

Binary search will first check the middle element (9 at index 4), then move to the left half (elements 1, 3, 5, 7) and check the middle of that segment (5 at index 2), then move to the right half of that segment (elements 7) and check the middle (7 at index 3). The loop terminates when the search range is invalid, with 'first' being 4.

Question 2

-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?

Accepted Answer

The answer of 
-What is the minimum number of comparisons...

Question 3

-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?

Accepted Answer

The answer of 
-In a sequential search, how many key...

Question 4

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?

Accepted Answer

The answer of Consider the following list. list = {20,...

Question 5

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.

Accepted Answer

In binary search, the list is divided in half repeatedly. Starting with the middle element (index 4, value 25), the search moves to the left half (indices 0 to 3) because 20 is less than 25. The next middle element is at index 1 (value 10), and since 20 is greater, the search moves to the right half (indices 2 to 3). The middle element is now at index 2 (value 15), and since 20 is greater, the search moves to index 3, where the value is 20. Thus, the index variable 'first' is 3 when the loop terminates.

Question 6

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.

Accepted Answer

The binary search algorithm repeatedly divides the search interval in half. Therefore, the number of key comparisons required is at most log₂n + 1. Since the algorithm also makes one comparison to determine whether the element is in the list, the total number of key comparisons is at most 2 * log₂n + 2.

Question 7

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

Accepted Answer

The answer of If the list in the accompanying figure...

Question 8

-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?

Accepted Answer

The answer of 
-On average in a sequential search, how...

Question 9

-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?

Accepted Answer

In a sequential search on an unordered list, each element is checked one by one. If the number 44 is the fifth element in the list, it would take 5 comparisons to find it.

Question 10

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

Accepted Answer

A binary search is faster than a sequential search on sorted lists because it divides the list in half repeatedly, reducing the search space exponentially, while a sequential search checks each element one by one.

Question 11

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?

Accepted Answer

The answer of Consider the following list. list = {24,...

Question 12

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

Accepted Answer

Binary search divides the list in half at each step, so the number of comparisons needed is log2(1024) = 10, not 22.

Question 13

-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?

Accepted Answer

In a sequential search, each element is checked one by one. If the number 24 is the third element in the list, it would take 3 comparisons to find it.

Question 14

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

Accepted Answer

The method needs the array and its length to perform sorting. A boolean indicating success is not necessary as sorting can be assumed successful if no errors occur.

Question 15

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

Accepted Answer

A binary search requires the list to be sorted in order to function correctly. If the list is not sorted, the binary search algorithm cannot properly divide and conquer the list to find the target value.

Question 16

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?

Accepted Answer

After three iterations of the insertion sort, the first three elements are sorted: {10, 20, 24}, and the rest remain unchanged.

Question 17

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

Accepted Answer

In selection sort, the algorithm searches for the smallest element in the list and swaps it with the first element. Here, 5 is the smallest element and would be swapped with 16, the first element in the list.

Question 18

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?

Accepted Answer

Sequential search compares the target value with each element in the list, starting from the first element. In this case, the target value is 95, and the list has 10 elements. Therefore, the sequential search algorithm will execute 10 key comparisons.

Question 19

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 ____.

Accepted Answer

In a sequential search, on average, you will check half of the elements before finding the target, so for a list of 100 elements, it would be 50 comparisons.

Question 20

-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?

Accepted Answer

In a sequential search, each element is compared one by one starting from the first element. If the search item is 10 and assuming it is the 7th element in the list, then a minimum of 7 comparisons are needed.

Quiz 14: Searching and Sorting