## Pre-Quiz2-Spring 2008

**Part I: REMOVEDked Lists**

Write a method called `shortenJoinLists(ContactList firstList, ContactList secondList)` that takes in two `ContactList`s, changes the first to have at most three nodes and then combines the two `ContactList`s. `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

### Links to this Page