271 Final Exam Study Guide
Dordal, Fall 2009
The main thing we've covered since the midterm is "linked" data structures: linked lists, trees, and hash tables.
Some especially important sections of Bailey:
Chapter 9: linked lists
9.4: singly linked lists
9.5: doubly linked lists (basic idea only)
Chapter 10: stacks and queues
Know what they are, and the basic vector-based implementations (10.1.2, 10.2.3).
There will not be any simulating-recursion problem on the final.
Chapter 12: binary trees
12.4: basic implementation using Node pointers
12.6: different kinds of traversal
Chapter 14: binary search trees
basics of searching and inserting
14.5: splay trees (and rotations)
Not included in Bailey: AVL trees and rotations
Chapter 15: Maps
15.1 (though the compiler project will not be on the final)
15.4: hash tables, esp 15.4.2: external chaining
15.5: ordered maps (ie tree maps)
Here are a few suggested problems. They may involve the LCell (list cell) and TCell (Tree cell) declarations below:
class LCell<D> {
private D data;
private LCell<D> next;
public LCell(D d, LCell<D> n) {data=d; next=n;}
public D data() {return this.data;}
public LCell<D> next() {return this.next;}
}
class TCell<D> {
private D data;
private TCell<D> left, right;
public TCell(D d, LCell<D> l, LCell<D> r) {
data=d; left = l; right = r;
}
public D data() {return this.data;}
public TCell<D> left() {return this.left;}
public TCell<D> right() {return this.right;}
}
1. Write a function to search a linked list of Strings, based on
LCell<String>, for the string s. If the item is found, a pointer
to that cell should be returned, otherwise null is returned.
LCell<D> search(LCell<D> p, String s) {
}
2. Write statements to create the LCell<String> list
p -> [chicken] --> [turkey] --> [goose]
Use the format of problem 3, below.
3. Suppose we execute the following statements (all of p, q,r,s,t are LCell<String>)
p = new LCell<String>("apple", null);
p = new LCell<String>("pear", p);
p = new LCell<String>("grape", p);
r = new LCell<String>("fig", null);
s = new LCell<String>("date", r);
t = new LCell<String>("raisin", r);
Draw the lists pointed to by p, s, and t.
4. Suppose the hash function used in creating a hash table of Strings is basedon the first letter:
a --> 0
b --> 1
c --> 2
d --> 3
Suppose hashTable = new LCell<D>[4] (an array of 4 pointers to
LCells). Draw the table after the insertion of the following, in order:
apple
banana
cherry
barley
artichoke
basil
5. Suppose we execute the following statements (all of p,q,r,s,t,u are TCell<String>):
p = new TCell<String>("book", null, null);
q = new TCell<String>("dog", null, null);
r = new TCell<String>("cow", p, q);
u = new TCell<String>("moo", null, null)
t = new TCell<String>("pencil", u, null);
s = new TCell<String>("frog", r, t);
Draw the tree. Which pointer represents the tree root? Is the tree an ordered tree?
6. Write statements as in #5 to create a tree of numbers:
9
/ \
5 20
/ \ / \
2 7 11 23
7. (a). In the tree above, rotate the node 5 to the root.
(b). In the tree above, rotate the node 20 to the root.
8. In the tree of problem 6, list the elements
(a) following inorder traversal
(b) following postorder traversal
(c) following preorder traversal
(d) following level-wise traversal
9. In the following B-tree of degree 1 (so each node contains either 1 or 2 data values), insert the values 5, 6, and 7.
[3 8]
/ | \
[1] [4] [9,10]
10. Consider the following tree; it was an AVL tree until we added 10:
6
/ \
3 8
/ \
2 9
\
10
(a). Which nodes have a "balance factor" (height of left subtree - height of right subtree) bigger than 1 (in absolute value)?
(b). What is the result of doing rotations about those nodes?
11. Suppose s is a stack, initially empty. We then execute the following:
s.push(a)
s.push(b)
x = s.pop()
s.push(c)
s.push(d)
y = s.pop()
s.push(e)
What is on the stack, and what are the values of x and y?
12. Do problem 11 assuming that s is a queue instead of a stack, and that "push" represents "enqueue" and "pop" represents "dequeue".