CSci 2101: Review for Final Exam

Theory of data structures

True or false (with explanation):

• Counting sort can be used to sort arbitrary strings alphabetically.
• Every binary search tree is an AVL tree
• There is no tree that's both a binary search tree and a priority heap.
• There is no tree with three nodes that is both a binary search tree and a priority heap.
• If there is an empty spot in a hashtable, a linear probing with any constant c will find it.

Problems:

• Draw a binary search tree with the following pre-order traversal: 10 6 3 15 12. Is it an AVL tree?
• Add the following elements to an AVL tree (in the given order), perform all necessary rotations: 20 18 13 15 14
• Draw a max-heap represented by the following array: 20 13 11 7 12 8. Remove the root, show all the needed operations step-by-step. Then add element 10, show all the operations step-by-step.
• Draw a binary search tree with the following pre-order: 7, 3, 4, 12, 10, 8, 9
• You are given a hash table of size 7. Here k is the key, h(k) = k % 7 is the primary hash function, i is the probe number, and h(k,i) is the function that gives the index for a key k and a probe i. Add the elements 8, 13, 10, 6, 17 using:
  • Separate chaining
  • Linear probing: h(k, i) = h(k) + 2*i.
  • Quadratic probing: h(k, i) = h(k) + i + i*i.
  • Double hashing with the function h(k,i) = h(k) + i * g(k), g(k) = k % 3 + 1 (what's the purpose of adding 1 in g(k)?)
• Give an example of an undirected graph of four vertices that has the same breadth-first and depth-first traversal. The graph must be connected (i.e. there is a path, i.e. a sequence of edges, from every vertex to every other vertex). Extra credit: give a second example with a different graph shape.

Types and subtyping

Is the following program syntactically correct? If not, comment out the lines that are causing compiler errors. What will be the result of running the program after that? Show all the output and all runtime exceptions (if any).

public interface A {
	public void m();
}

public class B implements A {

	@Override
	public void m() {
		System.out.println("This is m in B");
	}

	public void mmm() {
		System.out.println("This is mmm in B");
	}
}


public class C extends B {
	
	public void m() {
		System.out.println("This is m in C");
	}
	
	public void mmm() {
		System.out.println("This is mmm in C");
	}
}


public class TestSubtypes {
	public static void main(String [] args) {
		A a1 = new B();
		A a2 = new C();
		
		a1.m();
		a2.m();
		
		a1.mmm();
		((B) a1).mmm();
		((B) a2).mmm();
		((C) a2).mmm();
		((C) a1).mmm();
	}

}

Programming exercise

Write a method of binary tree (not a binary search tree!) that takes a key returns true if that key is found in the tree and false otherwise.

CSci 2101 course web site.