15-111 Final Exam At
A Glance
[ Note: Java code for LinkedList and BST classes included
below ]
Structural Information
|
True/False: |
10% |
10 questions |
|
Multiple Guess: |
10% |
5 questions |
|
Sentence-or-two answer: |
20% |
4 questions |
|
Few sentences answer |
25% |
5 questions |
|
Short coding: |
15% |
3 questions |
|
Code tracing: |
5% |
1 question |
|
Data structure manipulation coding: |
5% |
1 question |
|
Drawing: |
10% |
2 questions |
Data Structure Skeletons included with exam:
BST
LinkedList
Topical Coverage
Arrays, 1-dimensional and 2-dimensional
Hash tables
Singly Linked Lists
Queues
Stacks
Heaps, chaining and probing
BSTs
Time complexity, analysis given algorithm or code or strategy
Big-O, best-case, expected case, intutition
Sorting techniques: insertion, selection, quick, merge
Sorting techniques: selecting among techniques, including subtleties
Backtracking, including recursive implementation
Recursion, generally
Recursion, binary
Recursion, in place of iteration
Strings, Java class – know basic methods
////////////////////////////////////////////////
////////////////////////////////////////////////
/// Listing 1: The Linked List Class. ///
////////////////////////////////////////////////
////////////////////////////////////////////////
import
java.util.*;
public
class LinkedList {
private Node head;
/**
* Constructs an empty list
*/
public LinkedList() {
head = null;
}
/**
* Returns true if the list is empty
*/
public boolean isEmpty() {
return head == null;
}
/**
* Inserts a new node at the beginning of
this list.
*/
public void addFirst(Object item) {
head = new Node(item, head);
}
/**
* Returns a string representation
*/
public String toString() {
StringBuffer result = new StringBuffer();
for(Node tmp = head; tmp != null; tmp =
tmp.next)
result.append(tmp.data + "
");
return result.toString();
}
private static class Node {
private Object data;
private Node next;
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
}
////////////////////////////////////////////////
////////////////////////////////////////////////
///
Listing 2: The Binary Search Tree Class. ///
////////////////////////////////////////////////
////////////////////////////////////////////////
import
java.util.*;
public
class BST{
private Node root;
public BST(){
root = null;
}
/**
* Inserts a new item
*/
public void insert(Comparable data){
root
= insert(root, data);
}
private Node insert(Node p, Comparable
toInsert){
if (p == null)
return new Node(toInsert);
if (toInsert.compareTo(p.data) == 0)
return p;
if (toInsert.compareTo(p.data) < 0)
p.left = insert(p.left, toInsert);
else
p.right = insert(p.right, toInsert);
return p;
}
/**
* Searches for an item
*/
public boolean search(Comparable toSearch){
return search(root, toSearch);
}
private boolean search(Node p, Comparable
toSearch){
if (p == null)
return false;
else if (toSearch.compareTo(p.data) == 0)
return true;
else if (toSearch.compareTo(p.data) < 0)
return search(p.left, toSearch);
else
return search(p.right, toSearch);
}
private static class Node {
private Comparable data;
private Node left, right;
public Node(Comparable data) {
left = right = null;
this.data = data;
}
public Node(Comparable data, Node l, Node
r){
left = l; right = r;
this.data = data;
}
public String toString() {
return data.toString();
}
}
}