## Pre-Quiz2-Spring 2008

Part I: REMOVEDked Lists
Write a method called shortenJoinLists(ContactList firstList, ContactList secondList) that takes in two ContactLists, changes the first to have at most three nodes and then combines the two ContactLists. ContactList firstList should precede ContactList secondList in the final result. It should then return the combined ContactList. You should also check for any special cases such as an empty list. For example: If the first ContactList contained A, B, C, D, E, F, nodes and the second ContactList contained W, X, Y, Z nodes then the method should return a ContactList containing A, B, C, W, X, Y, Z.

Assume that you have access to all of the methods you have written in ContactList and ContactNode.

ContactList:
- public void add(ContactNode contactToInsert) – inserts a new node into the list
- public boolean delete(ContactNode node) – deletes a node from the list
- public int size() – returns the number of elements in the list
- public ContactNode getHead() - returns the head of the list
- public ContactNode last() – returns the last node in the list

ContactNode:
- public void setNext(ContactNode next) – sets the next element of the ContactNode
- public ContactNode getNext() - gets the next element of the ContactNode

public ContactList shortenJoinLists(ContactList firstList, ContactList secondList)

Ask questions at Student1046

Part II: Trees
Insert the following numbers into a binary search tree and draw the finished tree in the space below. Represent the tree with circles denoting nodes and lines denoting relationships. Make sure that each node has a number inside it. After drawing the tree, list the numbers that would be printed after a pre-order traversal, an in-order traversal and a post-order traversal.

Numbers: 7, 5, 3, 12, 8, 2, 9, 6, 10

Ask questions at Spring08-Pre-Quiz2-Trees-Questions

Part III: True or False
For each of these statements mark True (T) or False (F)

1. The difference between a n-ary tree and a binary search tree is that there is no restriction for the number of children in a binary search tree.

2. A root node does not have a parent node.

3. A leaf node can only have one child node but not two.

4. A tree can have cycles (A -> B -> C -> A).

5. In a binary search tree, the larger node usually goes on the right and the smaller on the left.

6. It is harder to index a linked list than an array.

7. A binary search tree can only contain nodes with numbers or Strings, because there is no way to determine which node is greater otherwise.

8. Getters and setters are formally known as accessors and modifiers respectively.

Ask questions at Spring08-Pre-Quiz2-TrueFalse-Questions