This sample final contains the kinds of questions that will be on
the actual final. It is much longer than the final will be.
At least one question on the final will be all but identical to one
here. The final is comprehensive: at least one question will come from the
first half of the course.
See the sample midterm for examples of such questions.
We will not post solutions to the sample final problems because, in
our experience, people will be tempted to look at the solution before
completely doing the problem. If anyone wishes to check their
answers, they may give us a paper copy for review.
- Given a binary tree class called TreeSet that uses instances
of a class called Node, write a method that writes
the nodes on an output stream for debugging purposes. Your
method should show the parent-child relationships in the
tree. Give a sample tree, and show how the output looks.
class TreeSet <T extends Comparable<T>> {
private static class Node<T> {
T data;
Node<T> left, right;
Node(T d) {data = d; }
}
private Node<T> root;
private void doPrint(Node n, int indent) { ... }
public void print() { doPrint(root,0); }
...
};
It is your task to implement doPrint, a helper method
for print.
This member function should print the tree where each element is
indented by two spaces more than the parent, and the data should be
printed in order.
For example, in the following picture, the tree on the left should be
printed in the manner shown on the right:
- Implement a Queue template using the Java standard class
ArrayList.
You should implement the five functions:
isEmpty, size, enqueue, front, and
dequeue.
- Do the same for Stack with methods
isEmpty, size, push, peek, and
pop.
- Repeat the last two
questions but use a circular doubly-linked list ADT with a
dummy node.
- Implement the
Dictionary ADT with a single-linked list without
a dummy node.
- Suppose we wished to implement a (directed) Graph ADT using
edge lists. Nodes are implemented as (small) integers in the
range
where 
is the number of nodes:
NB: THIS QUESTION IS STILL IN C++
class Graph {
private:
unsigned int nodes;
vector<vector<int> > adjacent;
public:
Graph(unsigned);
unsigned get_nodes() const;
void add(int from, int to);
typedef vector<int>::const_iterator const_iterator;
const_iterator adj_begin(int) const;
const_iterator adj_end(int) const;
};
- This representation doesn't give a way to indicate edge
weight. Why not? What would have to be changed in order to
do so?
- This data structure permits a node to have multiple edges to the
same destination node. Explain how this
could be changed by changing the data structure.
- Implement the ADT.
- Use the ADT to write a recursive depth-first search.
- A bank keeps track of its collection of customer records and
collection of accounts with two nested classes
Customer and Account classes:
class Customer {
public Customer(String name) {...}
public void setAccount(Account a) {...}
public Account getAccount() {...}
}
class Account {
public Account(Money initial) {...}
public void setBalance(Money b) {...}
Money getBalance() {...}
}
For a new customer that does not yet have an account, both a customer
record and an account get dynamically allocated, with an initial
deposit of $100 (i.e., Money(100)). The customer record and the account must be added to their respective collections in the most convenient way.
Write the body of a function that creates a new customer and account
(with 100 dollars) using the customer name passed as a string:
Collection<Customer> customers;
Collection<Account> accounts;
...
Customer createCustomerAndInitialAccount(string name)
{
// {Your code here!}
}
- For the same Bank as above, write a
totalDeposits
function that computes the total amount of money in all the
accounts. Assume that Money has a method:
void add(Money m);
Make sure you don't modify any of the accounts!
Money totalDeposits()
{
Money total = new Money(0);
// Your code here!
// System.out.println("The total amount is " + total);
return total;
}
- How can an array be used to implement a Stack ADT?
Please complete the class declaration, then give the
member function implementations separately:
class Stack<T> {
T[] contents;
int used;
private T[] makeArray(int n) {
contents = (T[])new Object[n];
}
public Stack() { ... }
public boolean isEmpty() { ... }
public void push(T x) { ... }
public T pop() { ... }
};
- Describe (no code!) how an array can be effectively used to
implement a Queue.
- Implement a map that uses an (unsorted) linked list of entries
to keep the map data. Don't worry about efficiency at all - just
get the map working. You may assume the existence of
MyEntry
NB: You should use both AbstractMap and AbstractSet.
(Why?)
- Implement a depth-first search of a graph using
a recursive function. The result should print the
nodes along the path. Use the following node class.
/*
* Each node permits iteration to the djoining nodes.
*/
class Node implements Iterable<Node> {
public String getName();
...
};
/*
* Return whether a path can be found to the goal.
* Return null if no path can be found.
*/
List<Node> findPath(Node from, Node to, Set<Node> visited, List<Node> sofar) {
...
}
- Implement a hash table with quadratic hashing.
- Write a routine to check the invariant of a hashtable using
chained hashing. Assume the following data structure:
class HashTable<K,V> ... {
static class HashEntry<K,V> ... {
K key;
V value;
HashEntry<K,V> next;
};
HashEntry<K,V>[] contents;
int numEntries;
int hash(K key) { ... } // return value in range [0,contents.length)
}
You can assume the existence of boolean _report(String s).
You don't need to check that there are no duplicates.
- Write a routine to check the invariant of a hashtable using
linear probing. Assume the following data structure:
class HashSet<K> ... {
K[] contents;
int numEntries;
K nullObject = (K) new Object(); // fill-in for null
K noObject = (K) new Object(); // place holder for removed entry
int hash(K key) { ... } // return value in range [0,contents.length)
}
NB: make sure you handle the result of probing.
You don't need to check that there are no duplicates.
Hint: you don't need to treat nullObject specially. (Why not?)
(NB: This question by itself is too hard for a final exam.)
- Consider a drawing program that uses a class called Canvas to display the
following classes:
- A Shape class...
class Shape {
// draw the shape on a canvas
public void draw(Canvas c) {}
// translate the shape by vector in d
public void move(Delta d) {
throw new UnsupportedOperationException("move not implemented");
}
}
- A Line class derived from Shape...
class Line extends Shape {
private Point point1, point2;
public Line(Point p1, Point p2) {
point1 = p1;
point2 = p2;
}
// @Override
public void drawShape(Canvas c) { ... }
@Override
public void move(Delta d) { ...}
}
- A Square class derived from Shape ...
class Square extends Shape {
public Square(Point c, int s) { ...}
// @Override
public void drawShape(Canvas c) { ...}
public void move(int dx, int dy) { ...}
private Point center;
private int size;
}
- The test driver code for Shape, etc. looks like this:
...
List<Shape> shapes = new ArrayList<Shape>();
shapes.add(new Square(new Point(10,10),4));
shapes.add(new Line(new Point(0,0), new Point(30,30)));
Canvas canvas = new Canvas(40,40);
for (Shape s : shapes) {
sh.draw(canvas);
}
canvas.dump(System.out);
shapes.get(0).move(new Delta(5,0)); // move Square
When the program is run, the canvas never gets anything drawn on it,
and then when we try to move the square, it aborts. Why ?
Assume the method bodies with ... are correctly implemented, and
further assume Canvas works correctly.
How should the
Shape class be modified to avoid errors related to its' subclasses?
We have written the following code to implement cloning of a Set
implemented with binary search trees (with parent pointers):
class Set<T> {
private static class Node<T> {
Node<T> parent;
T data;
Node<T> left,right;
Node(Node<T> p, T d) {
parent = p;
data = d;
}
}
private Comparator<T> comparator;
private Node<T> root;
private int numItems = 0;
...
@SuppressWarnings("unchecked")
public Set<T> clone()
{
Set<T> result;
try
{
result = (Set<T>) super.clone( );
}
catch (CloneNotSupportedException e)
{
// This exception should not occur. But if it does, it would probably
// indicate a programming error that made super.clone unavailable.
// The most common error would be forgetting the "Implements Cloneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}
result.root = new Node<T>(null,root.data);
result.root.left = root.left;
result.root.right = root.right;
return result;
}
}
This code works fine when the set has exactly one element, but crashes
if it is empty, and strange things sometimes seem to handle if there is more
then one element. For instance the invariant might fail suddenly at
the start of a public method.
- Why does this code crash if the set is empty?
- Why doesn't it work correctly when there is more than one node?
- Give example client (outside) code which will cause an invariant
error to happen. Explain why.
- Assume the class
SortedList is just a sequence of values that
are kept sorted in ascending order.
Consider the following version of SortedList#locate for a linked list
implementation:
class SortedList<T> {
static class Node {
T data;
Node pNext;
};
Node pHead;
...
};
...
/** Return (0-based) position of item in sorted list.
* In other words, return number of items before this one in the list.
* Return -1 if the item isn't found.
* preconditions: none
*/
public int locate(T item)
{
Node p = pHead;
int count = 0;
while (p.pNext != null && p.pNext.data != item) {
p = p.pNext;
count++;
if (p.data == item) return count;
}
return -1;
}
The code does not work:
- If we ask for the location of something in an empty list, we get
a null pointer exception
segmentation fault. Explain why this happens.
- In all other cases, whether not the item is found, it returns
-1. Explain why this happens.
- Fix both problems by neatly editing the code.
- Someone else working on the same method tried the following:
public int locate(T item)
{
Node p = pHead;
int count = 0;
while (p.pNext != null && p.data != item) {
p = p.Next;
++count;
}
return (p.pNext == 0) ? -1 : count;
}
If you call locate() on an empty SortedList, the program
dies with a null pointer exception.
If the item you're looking for is at the end of the list, the method
returns -1.
Otherwise, the correct value is returned. What is wrong? Fix the problem(s).
- An
XMLEntity class includes the following methods:
public void addAttribute(String name, String value) { ... } // warn
public void addXMLEntity(XMLEntity value) { }
Someone implemented Item incorrectly:
private int worth;
public void addAttribute(String key, int value) {
println("Got here!");
if (key == "worth") {
worth = value;
}
super.addAttribute(key,"value");
}
But no matter what they put in the XML, it never printed
Got here.
- They wanted to write:
super.addAttribute(key,value)
but Eclipse said that was an error. Putting quotes around
"value" worked. Why is this the wrong solution, in any case?
- What is the connection between this ``fix'' and the problem that
Got here never gets printed?
- Even when this is fixed, we get the message
- Everything compiled, but when we tested it on some
test cases, we got the messages:
Unknown attribute: worth
and all objects have zero worth when we sell them.
What is the problem?
- After that problem is solved, items now have non-zero worth (if
specified in the XML), but we still get the warning messages.
Why?
- Fix the code by neatly editing it, or by rewriting it.
- The following series of classes was designed using inheritance:
public class Person {
private int id;
private String firstName, lastName;
public Person() {}
public Person(int id, String firstName, String lastName) {
this.id = id;
this.firstName = firstName;
this.lastName = lastName;
}
public String getFormattedName() {
return firstName + " " + lastName;
}
}
public class Student extends Person {
private double gpa;
public Student(int id, String firstName, String lastName, double gpa) {
this.gpa = gpa;
}
public double getGPA() {
return gpa;
}
}
public class Teacher extends Person {
private String title;
private boolean isTenured;
public Teacher(int id, String firstName, String lastName,
String title, boolean isTenured) {
this.title = title;
this.isTenured = isTenured;
}
public boolean getIsTenured() {
return isTenured;
}
@Override
public String getFormattedName() {
return title + " " + firstName + " " + lastName; // error #1
}
}
We use the following driver:
public class Main {
public static void main(String[] args) {
Teacher a = new Teacher(100, "Mary", "Jo", "Dr.", true);
Person b = new Student(200, "John", "Doe", 3.8);
printPersonInfo(a);
printPersonInfo(b);
}
public static void printPersonInfo(Person p) {
System.out.println(p.getFormattedName());
if(p instanceof Student) {
System.out.println("GPA: " + p.getGPA()); // error #2
} else if(p instanceof Teacher) {
System.out.println("Tenured: " + p.getIsTenured()); // error #3
}
}
}
- We get the following compiler errors:
- error #1
- The fields
firstName and lastName are not visible.
- error #2
- The method
getGPA is undefined for the type Person.
- error #3
- The method
getIsTenured is undefined for the type Person.
Explain each of these error messages.
- Fix the compiler errors by only changing the lines marked with
errors. Either edit the code neatly or place the fixes below:
- After the compiler errors are fixed, the program runs and prints
the following unexpected output:
Dr. null null
Tenured: true
null null
GPA: 3.8
Why? Please explain!
- Fix the problems.
