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 exercises

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.

Given a binary search tree, write a method that prints all of the elements in the decreasing order (assuming no elements are equal).

Two trees are equal if they have the same shape and the same keys and values in every node. Write a method in a binary tree that takes another binary tree and determines if the two are equal. Write a method a helper method in a node that takes a node.

In a binary search tree write a method that takes a key and returns the number of elements in the tree that are greater than that key. Note: write a recursive method in a node class. Carefully think of the cases, test your method.

Write a method in a graph class that finds a vertex with the largest number of edges and returns its key.

A cycle in a graph is a directed path (following edges) from a vertex back to that same vertex. Write a method that takes a key and determines whether a vertex with that key is a part of a cycle. Hint: modify depth-first search or bread-first search for this problem.

CSci 2101 course web site.