CSci 2101: Review for Final Exam

Theory of data structures

True or false (with explanation):


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 {

	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();
		((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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.