1 Mark the following statements as true or false A sequentia

1. Mark the following statements as true or false. A sequential search of a list assumes that the list elements are sorted in ascending order a. b. A binary search of a list assumes that the list is sorted 2. Consider the following list 63 45 32 98 46 57 28 100 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.) a. 90 b.57 c. 63 d. 120 3. Consider the following list: 2 10 17 45 49 55 68 85 92 98 110 Using the binary search, how man 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 y comparisons are required to determine whether the 4. Sort the following list using the bubble sort algorithm. Show the list after each iteration of the outer for loop. 26, 45, 17, 65, 33, 55, 12, 18 5. Sort the following list using the selection sort algorithm. Show the list after each iteration of the outer for loop. 36, 55, 17, 35, 63, 85, 12, 48, 3, 66 6. 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? 7. 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? 8. 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. Show the resulting list after six

Solution

You have posted 12 questions at once. I’m answering the first two full questions - one of which contains two sub-parts and the other one contains 4 sub-parts.

-------------------------------------------------------------------------------------------------------

(1 – (a))

This statement is false.

Explanation: A sequential search simply means that the given element is matched against each of the elements in the list in a sequential manner. It doesn’t require the list to be sorted.

-------------------------------------------------------------------------------------------------------

(1 – (b))

This statement is true.

Explanation: Suppose the task is to search if list contains the element k. Then binary search involves matching the middle element of the list with k. And depending on whether the middle element is greater than or less than k, we eliminate the bottom half or the top half of the list from further matching.

Eliminating half of the list requires us to know whether the top half (or the bottom half) elements are greater than or less than the middle element.

Therefore, the list needs to be sorted.

-------------------------------------------------------------------------------------------------------

(2 – (a))

The list contains 8 elements.

90 is matched against all the 8 given elements in a sequential way (that is one after another). Then it reports that 90 was not found.

So, 8 comparisons are needed.

-------------------------------------------------------------------------------------------------------

(2 – (b))

57 is compared against 3, 45, 32, 98, 46 and 57 in that order. Then it reports that 57 is found.

So, 6 comparisons are needed.

-------------------------------------------------------------------------------------------------------

(2 – (c))

63 is compared against the first element of the list (which is 63) and reports that it is found.

So, only 1 comparison is needed.

-------------------------------------------------------------------------------------------------------

(2 – (d))

120 is compared against all the elements one by one and then reports that it is not found in the list. This is similar to part 2- (a)

So, 8 comparisons are needed.

-------------------------------------------------------------------------------------------------------

If you have any queries regarding the above, please ask in the comments and I will make sure to help you with it.