Previous Section
 < Free Open Study > 
Next Section


Exercises

  1. Show the contents of the array

    Click To expand

    after the fourth iteration of

    1. BubbleSort

    2. SelectionSort

    3. InsertionSort

    1. Show how the values in the array in Exercise 1 would have to be rearranged to satisfy the heap property.

    2. Show how the array would look with four values in the sorted portion after reheaping.

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

  3. Given the array

    Click To expand

    tell which sorting algorithm would produce the following results after four iterations:

    Click To expand
  4. How many comparisons would be needed to sort an array containing 100 elements using ShortBubble.

    1. in the worst case?

    2. in the best case?

  5. A sorting function is called to sort a list of 100 integers that have been read from a file. If all 100 values are zero, what would the execution requirements (in terms of Big-0 notation) be if the sort used was

    1. Quicksort, with the first element used as the split value?

    2. ShortBubble?

    3. SelectionSort?

    4. HeapSort?

    5. InsertionSort?

    6. MergeSort?

  6. How many comparisons would be needed to sort an array containing 100 elements using SelectionSort if the original array values were already sorted?

    1. 10,000

    2. 9,900

    3. 4,950

    4. 99

    5. None of the above

  7. A merge sort is used to sort an array of 1,000 test scores in descending order. Which of the following statements is true?

    1. The sort is fastest if the original test scores are sorted from smallest to largest.

    2. The sort is fastest if the original test scores are in completely random order.

    3. The sort is fastest if the original test scores are sorted from largest to smallest.

    4. The sort is the same, no matter what the order of the original elements.

  8. A list is sorted from smallest to largest when a sort algorithm is called. Which of the following sorts would take the longest time to execute, and which would take the shortest time?

    1. Quicksort, with the first element used as the split value

    2. ShortBubble

    3. SelectionSort

    4. HeapSort

    5. InsertionSort

    6. MergeSort

    1. In what case(s), if any, is the bubble sort O(N)?

    2. In what case(s), if any, is the selection sort O(log2N)?

    3. In what case(s), if any, is quick sort O(N2)?

  9. A very large array of elements is to be sorted. The program will be run on a personal computer with limited memory. Which sort would be a better choice: a heap sort or a merge sort? Why?

  10. Use the Three-Question Method to verify MergeSort.

  11. True or false? Correct the false statements.

    1. MergeSort requires more space to execute than HeapSort.

    2. QuickSort (using the first element as the split value) is better for nearly sorted data than HeapSort.

    3. The efficiency of HeapSort is not affected by the order of the elements on entrance to the function.

  12. Which of the following is true about QuickSort?

    1. A recursive version executes faster than a nonrecursive version.

    2. A recursive version has fewer lines of code than a nonrecursive version.

    3. A nonrecursive version takes more space on the run-time stack than a recursive version.

    4. It can be programmed only as a recursive function.

  13. What is meant by the statement that "programmer time is an efficiency consideration"? Give an example of a situation in which programmer time is used to justify the choice of an algorithm, possibly at the expense of other efficiency considerations.

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

    1. the number of elements is very large.

    2. the individual elements are large in size.

    3. the sort is recursive.

    4. there are multiple keys on which to sort the elements.

  15. Go through the sorting algorithms coded in this chapter and determine which ones are stable as coded. If there are unstable algorithms (other than HeapSort), make them stable.

  16. Give arguments for and against using functions (such as Swap) to encapsulate frequently used code in a sorting routine.

  17. Write a version of the bubble sort algorithm that sorts a list of integers in descending order.

  18. We said that HeapSort is inherently unstable. Explain why.

  19. Sooey County is about to have its annual Big Pig Contest. Because the sheriffs son, Wilbur, is majoring in computer science, the county hires him to computerize the Big Pig judging. Each pig's name (string) and weight (integer) are to be read in from the keyboard. The county expects 500 entries this year.

    The output needed is a listing of the ten heaviest pigs, sorted from biggest to smallest. Because Wilbur has just learned some sorting methods in school, he feels up to the task of writing this "pork-gram." He writes a program to read in all the entries into an array of records, then uses a selection sort to put the entire array in order based on the pigWeight member. He then prints the ten largest values from the array.

    Can you think of a more efficient way to write this program? If so, write the algorithm.

  20. State University needs a listing of the overall SAT percentiles of the 14,226 students it has accepted in the past year. The data are in a text file, with one line per student. That line contains the student's ID number, SAT overall percentile, math score, English score, and high school grade point average. (At least one blank separates each two fields.) The output needed is a listing of all the percentile scores, one per line, sorted from highest to lowest. Duplicates should be printed. Outline an O(N) algorithm to produce the listing.

  21. Which sorting algorithm would you not use under the following conditions?

    1. The sort must be stable.

    2. Data are in descending order by key.

    3. Data are in ascending order by key.

    4. Space is very limited.

  22. Determine the Big-O measure for SelectionSort based on the number of elements moved rather than the number of comparisons,

    1. for the best case.

    2. for the worst case.

  23. Determine the Big-O measure for BubbleSort based on the number of elements moved rather than the number of comparisons,

    1. for the best case.

    2. for the worst case.

  24. Determine the Big-O measure for QuickSort based on the number of elements moved rather than the number of comparisons,

    1. for the best case.

    2. for the worst case.

  25. Determine the Big-O measure for MergeSort based on the number of elements moved rather than the number of comparisons,

    1. for the best case.

    2. for the worst case.

  26. Fill in the following table, showing the number of comparisons needed either to find the value or to determine that the value is not in the array, given the following array of values.

    Click To expand

    Values

    Search dataValues Sequentially

    Search sortedValues Sequentially

    Binary Search sortedValues

    Search Tree

    15

           

    17

           

    14

           

    5

           

    99

           

    100

           

    0

           

    For Exercises 29-32, use the following values:

    66 47 87 90 126 140 145 153 177 285 393 395 467 566 620 735

  27. Store the values into a hash table with 20 positions, using the division method of hashing and the linear probing method of resolving collisions.

  28. Store the values into a hash table with 20 positions, using rehashing as the method of collision resolution. Use key % tableSize as the hash function, and (key + 3) % tableSize as the rehash function.

  29. Store the values into a hash table with ten buckets, each containing three slots. If a bucket is full, use the next (sequential) bucket that contains a free slot.

  30. Store the values into a hash table that uses the hash function key % 10 to determine into which of ten chains to put the value.

  31. Fill in the following table, showing the number of comparisons needed to find each value using the hashing representations given in Exercises 29-32.

     

    Number of Comparisons

    Value

    Exercise 29

    Exercise 30

    Exercise 31

    Exercise 32

    66

           

    467

           

    566

           

    735

           

    285

           

    87

           
  32. If you know the index of an element stored in an array of N unsorted elements, which of the following best describes the order of the algorithm to retrieve the element?

    1. O(1)

    2. O(N)

    3. O(log2N)

    4. O(N2)

    5. O(0.5N)

  33. The element being searched for is not in an array of 100 elements. What is the average number of comparisons needed in a sequential search to determine that the element is not present

    1. if the elements are completely unsorted?

    2. if the elements are sorted from smallest to largest?

    3. if the elements are sorted from largest to smallest?

  34. The element being searched for is not in an array of 100 elements. What is the maximum number of comparisons needed in a sequential search to determine that the element is not present

    1. if the elements are completely unsorted?

    2. if the elements are sorted from smallest to largest?

    3. if the elements are sorted from largest to smallest?

  35. The element being searched for is in an array of 100 elements. What is the average number of comparisons needed in a sequential search to determine the position of the element

    1. if the elements are completely unsorted?

    2. if the elements are sorted from smallest to largest?

    3. if the elements are sorted from largest to smallest?

  36. Choose the answer that correctly completes the following sentence: The elements in an array may be sorted by highest probability of being requested so as to reduce

    1. the average number of comparisons needed to find an element in the list.

    2. the maximum number of comparisons needed to detect that an element is not in the list.

    3. the average number of comparisons needed to detect that an element is not in the list.

    4. the maximum number of comparisons needed to find an element that is in the list.

  37. True or false? Correct any false statements.

    1. A binary search of a sorted set of elements in an array is always faster than a sequential search of the elements.

    2. A binary search is an O(Nlog2N) algorithm.

    3. A binary search of elements in an array requires that the elements be sorted from smallest to largest.

    4. A high-probability ordering scheme would be a poor choice for arranging an array of elements that are equally likely to be requested.

    5. When a hash function is used to determine the placement of elements in an array, the order in which the elements are added does not affect the resulting array.

    6. When hashing is used, increasing the size of the array always reduces the number of collisions.

    7. If we use buckets in a hashing scheme, we do not have to worry about collision resolution.

    8. If we use chaining in a hashing scheme, we do not have to worry about collision resolution.

    9. The functions in this chapter are used only for external searching (i.e., not for disk searching).

    10. The goal of a successful hashing scheme is an O(1) search.

  38. Choose the answer that correctly completes the following sentence: The number of comparisons required to find an element in a hash table with N buckets, of which M are full,

    1. is always 1.

    2. is usually only slightly less than N.

    3. may be large if M is only slightly less than N.

    4. is approximately log2M.

    5. is approximately log2N.

  39. How might you order the elements in a list of C++'s reserved words to use the idea of high-probability ordering?

  40. How would you modify the radix sort algorithm to sort the list in descending order?

  41. The radix sort algorithm uses an array of queues. Would an array of stacks work just as well?

  42. On the Web, the file Sorts.in contains a minimal test plan for the sorting algorithms we have studied. Design a more comprehensive test plan and apply it using SortDr.cpp.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)