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

Accepted Answer

Binary search works by dividing the search space in half at every step, based on the comparison with the middle element. Here, the middle element is 34. Since 75 is greater than 34, we can eliminate the first half of the list and focus only on the second half. Therefore, the search is restricted to list[6] through list[11]. So, option D is the correct choice.

Question 2

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

Accepted Answer

This is true. In each iteration of the selection sort algorithm, the smallest element is found in the unsorted portion of the list and is placed at the beginning of the sorted portion of the list.

Question 3

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

Accepted Answer

In a sequential search, the algorithm compares the key with each element in a list until it finds a match or reaches the end of the list. Therefore, if the item is not in the list, the algorithm will have to compare the key with all n elements, resulting in n key comparisons.

Question 4

The binary search algorithm can be written iteratively or recursively.

Accepted Answer

The binary search algorithm can be implemented using both iterative and recursive approaches.

Question 5

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

Accepted Answer

In a bubble sort, the larger elements move toward the end (top) of the list, and the smaller elements move toward the beginning (bottom) of the list through successive swapping of adjacent elements.

Question 6

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

Accepted Answer

In the successful case, the binary search algorithm halves the search interval at every iteration. Therefore, the number of key comparisons made is equal to the number of times the interval can be halved before the key is found. This is equal to the logarithm (base 2) of the size of the interval, which is represented by n. Therefore, the answer is log2(n). In the last iteration, when the key is found, only one comparison is made. Therefore, the answer is A, one.

Question 7

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

Accepted Answer

The sequential search algorithm checks each element in the list one by one until the target element is found. It does not rely on the list being sorted.

Question 8

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

Accepted Answer

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

Question 9

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

Accepted Answer

The swap function used in sorting algorithms like quick sort and selection sort performs the same basic operation: it swaps the values of two elements in the array. The implementation of the swap function itself does not inherently change based on the sorting algorithm in which it is used.

Question 10

In the average case, sequential search typically searches ____.

Accepted Answer

In the average case, sequential search typically searches through half of the list before finding the target element or determining it is not in the list. This is because, on average, the target will be somewhere in the middle of the list.

Question 11

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

Accepted Answer

To find the index of the middle element, we need to calculate the average of the first and last index. So, option C: (first + last) / 2, is the correct formula to find the index of the middle element.

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};

Accepted Answer

Bubble sort works by comparing adjacent elements and swapping them if they are not in the correct order. It then repeats the process until the list is in the correct order. So, after the first pass, the largest element (89) will be at the end of the list. In the second pass, the second largest element (73) will be sorted to the penultimate position and so on until the list is sorted in ascending order. Therefore, the correct answer is C.

Question 13

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

Accepted Answer

In a bubble sort, the comparison starts with the first two elements of the list, which are list[0] and list[1]. The algorithm then compares adjacent elements and swaps them if they are not in the correct order. This process is repeated until the list is sorted. Therefore, the correct choice is C.

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

Accepted Answer

In a binary search, the target is first compared with the middle element of the sorted array. In this case, the middle element is 39, as it is the median of the sorted list provided.

Question 15

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

Accepted Answer

The best choice is a boolean variable because its value can only be true or false, which is appropriate for tracking whether an item has been found or not during the sequential search algorithm.

Question 16

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

Accepted Answer

The code provided in option D uses a temporary variable to store the value of the element at the current index before it is overwritten by the value of the element at the next index. This ensures that the value at the current index is not lost during the swapping process. Therefore, option D is the best choice for swapping values in the bubble sort algorithm.

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.

Accepted Answer

Yes, every iteration of binary search algorithm cuts the size of the search list by half. Therefore, after log₂(1024) iterations, the list will be reduced to a single item.

Question 18

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

Accepted Answer

During the sorting phase, the array is divided into two sublists: sorted and unsorted. The sorted sublist is initially empty, and the unsorted sublist contains all the elements in the original list.

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.

Accepted Answer

On average, a sequential search will compare the search item with half of the elements in the list before finding a match or determining the item is not in the list, hence n/2 comparisons.

Question 20

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

Accepted Answer

Selection sort makes approximately $n^2/2$ key comparisons, so for $n = 1000$, it would make about $1000^2/2 = 500,000$ key comparisons, not 50,000.

Quiz 18: Searching and Sorting Algorithms