Problem 1
Mark the following statements as true or false. a. \(A\) sequential search of a list assumes that the list elements are sorted in ascending order. b. \(A\) binary search of a list assumes that the list is sorted. c. A binary search is faster on ordered lists and slower on unordered lists. d. \(A\) binary search is faster on large lists, but a sequential search is faster on small lists. e. When you declare a vector object and specify its size as \(10,\) then only 10 elements can be stored in the object.
Problem 2
Consider the following list: 63453298465728100 Using a sequential search, how many comparisons are required to determine whether the following items are in the list or not? (Recall that comparisons mean item comparisons, not index comparisons.) 2\. 90 b. 57 c. 63 d. 120
Problem 3
a. Write a version of the sequential search algorithm that can be used to search a sorted list. b. Consider the following list: 51217354665788593110115 Using a sequential search on ordered lists, which you designed in (a), how many comparisons are required to determine whether the following items are in the list or not? (Recall that comparisons mean item comparisons, not index comparisons.) i. 35 ii. 60 iii. 78 iv. 120
Problem 4
Consider the following list: \(\begin{array}{lllllllllll}2 & 10 & 17 & 45 & 49 & 55 & 68 & 85 & 92 & 98 & 110\end{array}\) Using the binary search, how many comparisons are required to determine whether the following items are in the list or not? Show the values of first, last, and middle and the number of comparisons after each iteration of the loop. a. 15 b. 49 c. 98 d. 99
Problem 5
Sort the following list using the bubble sort algorithm as discussed in this chapter. Show the list after each iteration of the outer for loop. 26,45,17,65,33,55,12,18
Problem 6
Sort the following list using the selection sort algorithm as discussed in this chapter. Show the list after each iteration of the outer for loop. 36,55,17,35,63,85,12,48,3,66
Problem 7
Consider the following list: 5,18,21,10,55,20 The first three keys are in order. To move 10 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
Problem 8
Consider the following list: 7,28,31,40,5,20 The first four keys are in order. To move 5 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
Problem 9
Consider the following list: 28,18,21,10,25,30,12,71,32,58,15 This list is to be sorted using the insertion sort algorithm as described in this chapter. Show the resulting list after six passes of the sorting phase -that is, after six iterations of the for loop.
Problem 11
Suppose that \(L\) is a list of 10,000 elements. Find the average number of comparisons made by bubble sort, selection sort, and insertion sort to sort \(\mathrm{L}\).
