1) Give an example of an AVL tree with the minimal number of nodes with a height of 4.
20
/ \
10 30
/ \ / \
5 15 25 40
/ / / \
1 22 35 50
/
45
In class we proved that the minimal number of nodes in an AVL tree of height h was Fh+3-1, where Fh+3 represents the (h+3) Fibonacci number.
2) Given the heap below, insert the number 13 and show the resulting heap after percolateUp is called. (Draw a box around your final answer.)
3
/ \
33 4
/ \ / \
39 85 88 7
3
/ \
13 4
/ \ / \
33 85 88 7
/
39
3) Consider inserting the element 13 into the AVL tree below. Draw the resulting tree after the element is inserted and the necessary rotation (as indicated by the code fragments in the book) to keep the tree a valid AVL tree is made. (Draw a box around your final answer.)
20
/ \
10 30
/ \ \
5 15 40
/ \
12 17
20
/ \
12 30
/ \ \
10 15 40
/ / \
5 13 17
4) Consider a hash table of size 7 that uses quadratic probing. Imagine searching for an element with a hash value of 2. After searching index 2 of the hash table, what are the next four indexes that would get searched using the quadratic probing strategy?
2+ 12 = 3 mod 7
2+ 22 = 6 mod 7
2+ 32 = 4 mod 7
2+ 42 = 4 mod 7
Next four slots: 3, 6, 4, 4.
5) Imagine the hash table above using the hash function f(x) = x2 + 3x + 4 (mod 7). After inserting the values 2, 5, and 1 into the table, we decide to dynamically expand our table to hold 17 elements when the value of 6 is inserted into the table. In which indexes do the four values appear in the dynamically expanded hash table?
Value: 1 Index: 8, since f(1) = 12 + 3(1) + 4 = 8 (mod 17)
Value: 2 Index: 14, since f(2) =22 + 3(2) + 4 = 14 (mod 17)
Value: 5 Index: 10, since f(5) = 52 + 3(5) + 4 = 10 (mod 17)
Value: 6 Index: 7, since f(6) = 62 + 3(6) + 4 = 7 (mod 17)
6) Given the following set of random values, show the result of running the Make Heap algorithm on it:
89
/ \
56 13
/ \ / \
8 2 9 7
/ \ / \ / \ /
4 12 17 1 6 5 3
1
/ \
2 3
/ \ / \
4 17 5 7
/ \ / \ / \ /
8 12 89 56 6 9 13
7) Let a BinTreeNode object store a single node of a binary tree with the following instance variables:
private int data;
private BinTreeNode left;
private BinTreeNode right;
Write an inorder traversal on the binary tree rooted at the current object that prints out the value at each node in its inorder order. (You may assume that the current object itself is not null, so that all tree traversals will print out at least one value. But, you should not make any recursive calls to "null objects.")
public void Inorder() {
if (left != null)
left.Inorder();
System.out.print(data+" ");
if (right != null)
right.Inorder();
}
8) Name each type of instance variable necessary for each of the four following classes using the specified implementation. Also, describe the purpose of each of these instance variables. (Note: More than enough blanks have been provided below. Use the minimum number of blanks necessary.)
a) A stack class using an array
Type of Instance Variable : array Purpose: store all the values
Type of Instance Variable : int Purpose: index to the top of the stack
Type of Instance Variable : ______Purpose: ______
b) A stack class using a linked list
Type of Instance Variable : Node Purpose: A reference to the top of the stack
Type of Instance Variable : ______Purpose: ______
Type of Instance Variable : ______Purpose: ______
c) A queue class using an array
Type of Instance Variable : array Purpose: store all the values
Type of Instance Variable : int Purpose: number of elements stored
Type of Instance Variable : int Purpose: index of front element
d) A queue class using a linked list
Type of Instance Variable : Node Purpose: A reference to the front of the list
Type of Instance Variable : Node Purpose: A reference to the back of the list
Type of Instance Variable : ______Purpose: ______