Review Questions

No solutions will be posted. We will solve a subset of the following problems in the lecture on December 8.

NOTE: As you may have noticed, we used a lot of examples and diagrams in the lectures. So email is not an effective method to answer questions related to course material. Please DO NOT ask how to solve the following problems via EMAIL. Attend the lecture on December 8 and come to the office hours.

Exercises from Textbook

Trees: C-7.3, C-7.4, C-7.21, C-7.24, C-7.31.
Note: Solve C-7.4 first then C-7.31. You may assume binary trees for these 2 problems to simplify the code.

BSTs, AVL Trees: R-10.1, R-10.4, R-10.7, R-10.9, R-10.10, R-10.11, C-10.1.

Heaps: C-8.14, C-8.17.

Hash Tables: R-9.5, R-9.6, R-9.7, R-9.8, R-9.12.

Graphs: R-13.2, R-13.8, R-13.9, R-13.10.

More Exercises

  1. Given the keys 1, 2, ..., 14, and 15, show a sequence of insertions that results in

    1. a nicely balanced binary search tree.
    2. a very unbalanced BST.

  2. Given the hash function h(x) = x % 10, insert the items: {4371, 1323, 6173, 4199, 4344, 9679, 1989} and show the resulting hash table for each of the following collision resolution policies:

    1. Separate (i.e. external) Chaining.
    2. Linear Probing.
    3. Quadratic Probing.
    4. Double hashing with h2(x)=7 - x % 7.

  3. Write Java code or pseudo-code for method insert and remove when using linear probing, quadratic probing, and double hashing.

  4. We want to insert the elements: 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2 into an initially empty heap.

    1. Draw the heap after inserting the elements one by one.
    2. Draw the heap after invoking the linear buildHeap method on an array containing the above elements in the order shown above.
    3. Invoke deleteMin three times on the heaps of parts (a) and (b) above and draw the two resulting heaps.

  5. Prove the following properties about a (min) heap of N elements:

    1. It has exactly ceil(N/2) leaves.
    2. Its largest element must be in a leaf.
    3. Every leaf must be examined to find the largest element.

  6. Suppose we use links (instead of an array) to represent a binary heap. Give an algorithm to find the tree node whose array index would have been i had we used an array to represent the heap.

    Hint: write i in binary

  7. Consider the following directed graph and the source being vertex 5. Show the contents of the arrays flag[ ], prev[ ], d[ ] at each step of the following algorithms:

    1. BFS
    2. DFS