CSC 222: Data Structures and Algorithms, Fall 2008

Practice Exam 2

This exam is open-book and open-note. Please allow some time to check your work. If you need extra space, write on the back.

1. Show the result after each pass of Insertion Sort on the input E A S Y O N E, where the letters will be sorted in alphabetic order. Fill in only the letters which have moved to a new position from the previous row.

   	0	1	2	3	4	5	6
   input:	E	A	S	Y	O	N	E
   pass 1:
   pass 2:
   pass 3:
   pass 4:
   pass 5:
   pass 6:

2. For each of the following questions, be sure to justify your answer. Just saying the name of the algorithm without giving a reason will not get full credit.
   1. Which of the sorting algorithms discussed in class would be the best choice for re-sorting a telephone directory containing 100,000 entries, after adding 100 new entries at the end (that is, the 100 new entries are not in their correct sorted positions yet, although the rest of the directory is already in order)?
   2. Which of the sorting algorithms discussed in class would be the best choice for sorting 100 complex objects, where exchanging a pair of objects requires moving thousands of bytes of data?
   3. Answer the previous question for 100,000 objects instead of 100.
3. Suppose we have a hash table using linear probe open addressing where the key values are integers and the hash function is simply the identity function. Therefore, if the table has size m, the key k will hash to the index k mod m (that is, k % m). Let m = 10 and give an example of a sequence of five distinct keys that will require the maximum amount of probing to insert in an initially empty table.

   What is the big-O running time of the worst case for inserting N values in an open-addressed hash table of size 2N?

4. Show the 2-3-4 tree that results from inserting the values 42, 19, 37, 65, 55, 49, and 51, in order.
5. Draw a red-black tree that corresponds to the result of the previous question (mark the red nodes with a star or some other special notation).
6. Show the result of inserting the number 45 in the above red-black tree.
7. Show the binary (minimum) heap that results from inserting the values 42, 19, 37, 65, 55, 49, and 51, in order, into an initially empty heap.
8. Given the resulting heap from the previous question, which value will be popped off first? Show the resulting heap after removing this element.
9. Show the result of applying the "build heap" operation to an array containing the values 42, 19, 37, 65, 55, 49, and 51.
10. Consider the following prefix encoding trie:

           *
       0 /   \ 1
        /     \
       *       *
    0 / \ 1 0 / \ 1
     S   I   M   P
    

    1. Use this trie to encode the word "MISS".
    2. How many bits will be needed to encode "MISSISSIPPI"?
    3. Is there a better prefix encoding trie for "MISSISSIPPI"? If not, explain why not; if so, give an example.
11. Trace the operation of the quickselect algorithm in finding the median of the values 42, 19, 37, 65, 55, 49, and 51. Use the naive choice of the first element as pivot.

DePauw University, Computer Science Department, Fall 2008
Maintained by Brian Howard (bhoward@depauw.edu). Last updated