1. Show the contents of the array
43 7 10 23 18 4 19 5 66 14 0 1 2 3 4 5 6 7 8 9
after the fourth iteration of
a.BubbleSort
b.SelectionSort
c.InsertionSort
3.
a.Show how the values in the array in Exercise 1 would be arranged immediately before the execution of the function Merge in the original (nonrecursive) call to MergeSort.
b.Show how the values in the array in Exercise 1 would be arranged immediately before the first recursive call to QuickSort.
4. Given the array
26 24 3 17 25 24 13 60 47 1 0 1 2 3 4 5 6 7 8 9
tell which sorting algorithm would produce the following results after four iterations:
a.
1 3 13 17 26 24 24 25 47 60 0 1 2 3 4 5 6 7 8 9
b.
1 3 13 17 25 24 24 60 47 26 0 1 2 3 4 5 6 7 8 9
c.
3 17 24 26 25 24 13 60 47 1 0 1 2 3 4 5 6 7 8 9
7. How many comparisons would be needed to sort an array containing 100 elements using SelectionSort if the original array values were already sorted?
a.10,000
b.9,900
c.4,950
d.99
e.None of the above
8. A merge sort is used to sort an array of 1,000 test scores in descending order. Which of the following statements is true?
a.The sort is fastest if the original test scores are sorted from smallest to largest.
b.The sort is fastest if the original test scores are in completely random order.
c.The sort is fastest if the original test scores are sorted from largest to smallest. d.The sort is the same, no matter what the order of the original elements.
10.
a.In what cases, if any, is the bubble sort O(N)?
b.In what cases, if any, is the selection sort O(log2N)?
c.In what cases, if any, is quick sort O(N2)?
14. Which of the following is true about QuickSort?
a.A recursive version executes faster than a nonrecursive version.
b.A recursive version has fewer lines of code than a nonrecursive version.
c.A nonrecursive version takes more space on the run-time stack than a recursive version. d.It can be programmed only as a recursive function.
16. Identify one or more correct answers: Reordering an array of pointers to list elements, rather than sorting the elements themselves, is a good idea when
a.the number of elements is very large.
b.the individual elements are large in size.
c.the sort is recursive. (this will save stack space)
d.there are multiple keys on which to sort the elements.