Final Exam Review Sheet C Sc 227 Summer 2012

  • Thursday 5-July 1:00 pm to 3:50 pm in our lecture room, GS 906
  • Or at the arranged time with your test proctor for section 901 students who cannot attend the final in person
  • The final is not comprehensive, about 9 pages, 20 questions, 200pts
  • It is worth 20% of your final grade
  • Closed book, closed notes, closed neighbors
  • No calculators or other electronic devices allowed
  • Use pencil, not pen (please)
  • Main topics: The Singly-Linked Structure, Recursion, and Binary Trees
  • Review session: Wednesday, 4-July 1:00-2:30 pm in 906 Gould Simpson
  • You will need your CatCard to enter by 228 GS (southwest corner)
  • Use the Practice Final for the scope and type of questions.
  • It is linked under Tuesday Announcements next to the practice final answers
  • Material: Chapters 15-19 and JavaCollectionFrameWork.pdf

Topics

The Singly-Linked Structure

  • We will use the same private inner Node class shown on the practice final inside of class LinkedList<E>
  • It stores these 2 things
  • The parameter E type as a reference to the data. Could match any java reference type, including Integer, Double, Character
  • A reference to another Node of the same type
  • It will have two constructors, so feel free to use either one (or use both).

privateclass Node {

private E data;

private Node next;

public Node(E objectReference) {

data = objectReference;

next = null;

}

public Node(E objectReference, Node nextReference) {

data = objectReference;

next = nextReference;

}

}

  • Then you can declare Node objects like this

Node ref2 = new Node(element); // element must be of type E
Node ref3 = new Node(element, ref1);

  • Add two methods to the same LinkedList<E> class shown on the practice final
  • Algorithms with linked structures might include
  • traverse the linked structure
  • find an element at a given index
  • find an element using compareTo
  • remove an element from a linked structure
  • insert an element into a linked structure
  • insert an element into a linked structure to maintain a natural ordering

list.get(0) <= list.get(1) < list.get(2),..., list.get(n-2) <= list.get(n-1)

Recursion

  • Show output from recursive methods
  • Determine return values from recursive methods
  • Write recursive methods with Strings, ints, and array processing

Trees

  • Tree Terminology: root, leaf, internal node, level, parent, child
  • Binary Trees
  • Tree traversals: in-, pre-, and post-order
  • The ordering property of Binary Search Trees
  • Tree algorithms in Java, both iterative and recursive
  • Add two methods to OrderedSetE
  • Like the 2 on the practice final or the first 11 from OrderedSet<E>

Java's Collection Framework

  • Topics are not in the book, see presentationJavaCollectionFrameWork.pdf
  • Some of the methods from interface java.util.List<E>
  • boolean add(E), E get(int), in size(), boolean contains(E), boolean remove(E)
  • Iterator<String> itr = list.iterator() and use itr.hasNext() and itr.next()
  • Some of the methods from interface java.util.Map<K, V>
  • V put(K, V), V get(K), boolean containsKey(K)
  • Collections polymorphic messages
  • sort, binarySearch, max, min

Not on the Final

  • GUIs and Events
  • HashTables