COP 3530 FINAL EXAM
15 points
1. Consider
class SNode {
Object data;
SNode next;
SNode(){};
SNode(Object d, SNode n) {
data = d;
next = n;
}
} // end SNode
If SNode
p references a SNode in a singly linked list with a
list head write the method
void deleteLast(SNode head);
that deletes the last SNode on
the list. Include an error check if necessary.
15 points
2. Consider
class DNode {
Object data;
DNode previous;
DNode next;
DNode(){}
DNode(Object d, DNode p,
DNode n) {
data = d;
previous = p;
next = n;
}
} // end DNode
Suppose that DNode head
references the list head in a circular doubly linked list with a list head.
Write the method
void insertFirst(Object
x, DNode head);
that insert x into the list as the first DNode in the
list.
15 pts.
3. What is the output of the following segment?
String out = "";
List list = new LinkedList();
ListIterator itr = list.listIterator();
itr.add(new Integer(1));
itr.add(new Integer(2));
itr.add(new Integer(3));
itr.add(new Integer(4));
itr = list.listIterator();
out += list + "\n";
itr.next();
itr.next();
itr.next();
itr.add(new Integer(37));
out += list + "\n";
out += itr.previous() + "\n";
itr.remove();
itr.previous();
itr.previous();
itr.set(new Integer(37));
out += list + "\n";
JOptionPane.showMessageDialog(null,out);
15 pts.
4. Suppose that a is an ArrayList whose elements are Queues of Objects. Write a method
String deleteFronts(ArrayList a);
that deletes the front of each Queue in the ArrayList a.
10 points
5. The Big O average
case running time of the boolean contains(Object x)
method for the Java class
10 points
6. A ListHashSet has O(1) expected case
running time for the operations, contains(Object x), add(Object x) and
remove(Object x) like HashSet but the Iterator
returns the elements in the order they were added like a List. Design a data structure
to implement a ListHashSet. You do not need to provide any code and a
picture could be helpful.
10 points
7. Suppose c is a Collection of Comparable objects. Write the method
void
displayNaturalOrder(Collection c);
that outputs the elements of the Collection c in their natural order.
15 pts.
8. Write a recursive method
int
sum(ArrayList A, int right);
that returns the sum of the Integer objects in the ArrayList A of from index 0 to index right.
15 points
9. Suppose c is a Java Collection. Write a method
void removeAllLessThan(Collection
c, Object x);
that removes all elements
from c that are less than x. Use the natural comparator for x to do the
comparisons..
5 points
10. What is the running time of the inorder order traversal algorithm for a binary tree?
10 points
11. Give the expression tree for the algebraic expression a*b*(c+d)/e + f*(g-h)
15 points
12. Write a method
int numberOfNodes(Tree t);
that returns the number of Nodes in the Tree t.
NOTE: You cannot use any global variables.
10 points
13. Given the Binary Search Tree show the tree after the operations add(6), remove(15), and remove(7) are performed.
7
/ \
/ \
5 15
/ \ / \
1 11 17
/ \ / \ / \
3 9 13 16
/ \ / \ / \ / \
10 points
14. Given the array A = {7, 5, 15, 14, 6, 11, 4, 1, 3} , show the array after constructing a binary heap from it using the pushDown method.
15 points
15. Write a recursive
method
int numberOfLeaves(BinaryTree t);
that returns the number of leaves in the
BinaryTree t. NOTE: You cannot use any global variables.
15 points
16. Given the
following graph:
Show the previous and
distance values at each node after applying the all shortest paths for weighted
graphs algorithm starting from 0.
15 points
17. Let s be the Set
of cities (as in Assignment Five) and ds be the
DisjointSets objects after Kruskal’s algorithm has been run as
at the end of Assignment Five. Assume that a spanning forest not necessarily a
spanning tree has been constructed. Describe ( you
do not need to provide any code ) how to write a method
void
display(Set s, DisjointSets ds);
that displays the cities in each of the sets in
ds in the following format:
Set 0 : [list of cities in Set 0]
Set 1 : [list of cities in Set 1]
...
Set n : [list of cities in Set n]
Note: Some of the
sets could be empty.