Sample Data Structures Questions
Chapter 13
Sorting

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000

The Purpose of These Questions

Short Answers

Short Answers Section 13.1 Quadratic Sorting Algorithms

1. Here is an array of ten integers:

         5  3  8  9  1  7  0  2  6  4
   

   Draw this array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).

2. Here is an array of ten integers:

         5  3  8  9  1  7  0  2  6  4
   

   Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array!

3. Suppose that you are writing a program that has the usual selectionsort function available:

       void selectionsort(int data[ ], size_t n);
   

   Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses selectionsort to sort all of x; the second call uses selectionsort to sort x[3]..x[9].

   Short Answers Section 13.2 Recursive Sorting Algorithms

4. Describe a case where quicksort will result in quadratic behavior.

5. Here is an array which has just been partitioned by the first step of quicksort:

         3, 0, 2, 4, 5, 8, 7, 6, 9
   

   Which of these elements could be the pivot? (There may be more than one possibility!)

6. Give a concise accurate description of a good way for quicksort to choose a pivot element. Your approach should be better than "use the entry at location [0]".

7. Give a concise accurate description of a good way for quicksort to improve its performance by using insertionsort.

8. Here is an array of ten integers:

         5  3  8  9  1  7  0  2  6  4
   

   Suppose we partition this array using quicksort's partition function and using 5 for the pivot. Draw the resulting array after the partition finishes.

9. Here is an array of ten integers:

         5  3  8  9  1  7  0  2  6  4
   

   Draw this array after the TWO recursive calls of merge sort are completed, and before the final merge step has occured.

10. Implement the following function:

        void merge(int data[ ], size_t n1, size_t n2);
        // Precondition: The first n1 elements of data are sorted, and the 
        // next n2 elements of data are sorted (from smallest to largest).
        // Postcondition: The n1+n2 elements of data are now completely
        // sorted.
    

    Short Answers Section 13.3 An O(n log n) Algorithm Using a Heap

11. Write two or three clear sentences to describe how a heapsort works.

12. Fill in the following table for the times to sort an array of n items. Use only big-O notation, and do not have any extraneous constants in your expressions.

    	Worst Case	Average Case
    Binary search of a sorted array	.	.
    Insertion sort	.	.
    Merge sort	.	.
    Quick sort without "median of three" pivot selection	.	.
    Quick sort with "median of three" pivot selection	.	.
    Selection sort	.	.
    Heap sort	.	.

    Short Answers Beyond the Book

13. Suppose that you are writing a program that has these two functions available:

        int compare_ints(const void* p1, const void* p2);
        // Precondition: p1 and p2 are really pointers to integers.
        // Postcondition: The return value is:
        //   (a) negative if *p1 < *p2
        //   (b) zero if *p1 == *p2
        //   (c) positive if *p1 > *p2
    
        void qsort(
            void* base,
            size_t n,
            size_t bytes,
            int compar(const void*, const void*)
        );
        // Same specification as the standard library qsort function. 
    

    Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses qsort to sort all of x; the second call uses qsort to sort x[3]..x[9].

14. Suppose that you implement quicksort nonrecursively using a stack, as in your last programming assignment. You use your algorithm to sort an array of 100 items, and at the start of the final iteration of the while loop, the stack contains just two numbers: 10 (on top) and 90 (on bottom). Write one or two clear sentences to describe which parts of the array are sorted at this point, and which parts of the array remain to be sorted.

Multiple Choice

Multiple Choice Section 13.1 Quadratic Sorting Algorithms

1. In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?
   • A. 1
   • B. n - 1
   • C. n log n
   • D. n²

2. Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?
   • A. O(n log n) sorts
   • B. Divide-and-conquer sorts
   • C. Interchange sorts
   • D. Average time is quadratic.

3. Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?
   • A. 21
   • B. 41
   • C. 42
   • D. 43

4. Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

       1  2  3  4  5  0  6  7  8  9
   

   Which statement is correct? (Note: Our selectionsort picks largest items first.)
   • A. The algorithm might be either selectionsort or insertionsort.
   • B. The algorithm might be selectionsort, but could not be insertionsort.
   • C. The algorithm might be insertionsort, but could not be selectionsort.
   • D. The algorithm is neither selectionsort nor insertionsort.

5. Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

       2  4  5  7  8  1  3  6
   

   Which statement is correct? (Note: Our selectionsort picks largest items first.)
   • A. The algorithm might be either selectionsort or insertionsort.
   • B. The algorithm might be selectionsort, but it is not insertionsort.
   • C. The algorithm is not selectionsort, but it might be insertionsort.
   • D. The algorithm is neither selectionsort nor insertionsort.

6. When is insertionsort a good choice for sorting an array?
   • A. Each component of the array requires a large amount of memory.
   • B. Each component of the array requires a small amount of memory.
   • C. The array has only a few items out of place.
   • D. The processor speed is fast.

   Multiple Choice Section 13.2 Recursive Sorting Algorithms

7. What is the worst-case time for mergesort to sort an array of n elements?
   • A. O(log n)
   • B. O(n)
   • C. O(n log n)
   • D. O(n²)

8. What is the worst-case time for quicksort to sort an array of n elements?
   • A. O(log n)
   • B. O(n)
   • C. O(n log n)
   • D. O(n²)

9. Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
   • A. The array elements form a heap.
   • B. Elements in each half of the array are sorted amongst themselves.
   • C. Elements in the first half of the array are less than or equal to elements in the second half of the array.
   • D. None of the above.

10. Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

        2  5  1  7  9  12  11  10
    

    Which statement is correct?
    • A. The pivot could be either the 7 or the 9.
    • B. The pivot could be the 7, but it is not the 9.
    • C. The pivot is not the 7, but it could be the 9.
    • D. Neither the 7 nor the 9 is the pivot.

11. What is the worst-case time for heapsort to sort an array of n elements?
    • A. O(log n)
    • B. O(n)
    • C. O(n log n)
    • D. O(n²)

    Multiple Choice Section 13.3 An O(n log n) Algorithm Using a Heap

12. Suppose we are sorting an array of eight integers using heapsort, and we have just finished one of the reheapifications downward. The array now looks like this:

        6  4  5  1  2  7  8
    

    How many reheapifications downward have been performed so far?
    • A. 1
    • B. 2
    • C. 3 or 4
    • D. 5 or 6

Data Structures and Other Objects Using C++

Thank you for visiting http://www.cs.colorado.edu/~main/questions/chap13q.html
Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group