COS 226 1996 Midterm

There are twelve questions, all of equal weight. This exam is open-book, open-notes: you may use the textbook, your notes, your corrected homework, and any handouts or on-line materials.

Give the result of 3-sorting, then 2-sorting, the keys B E A T U C L A.

Show how the keys B E A T U C L A are sorted with bottom-up mergesort.

Show the result of inserting the keys B E A T U C L A into an initially empty binary tree, using the standard algorithm.

Take the occurrence of a letter to mean insert and the occurrence of an asterisk to mean remove largest in the sequence B E * A T * * U C * L * A * * *. Give the sequence of heaps produced when these operations are performed on an initially empty heap.

Show the result of inserting the keys B E A T U C L A into an initially empty binomial queue.

Show the result of inserting the keys B E A T U C L A into an initially empty binary tree, using the root insertion algorithm.

Show the result of inserting the keys B E A T U C L A into an initially empty red-black tree.

Show the results of the first two passes when the following file is sorted with binary LSD radix sort (straight radix sort): 00010 00101 00001 10100 10101 00011 01100 00001

Show the binary trie defined by the keys B E A T U C L, using the five-bit binary encoding of i for the ith letter of the alphabet (see question 8).

Give the expected time for unsuccessful search using double hashing in a table of size M with just one empty slot.

Give the contents of the three subfiles after the first partitioning stage when the keys to be or not to be that is the are sorted with three-way radix Quicksort.

Show the multiway trie defined by the keys to be or not to be that is the (do not show null nodes).