AP Test Take Home Quiz #2         NAME_______________________________ PERIOD ______

For each of the following terms, find the best keyword or keywords (where applicable) in Java and explain what the term means. Then give an example of implementation. (I am not looking for a full-blown class implementation, just a line or few lines of code that make clear you know how to use the concept.

Queue

Superclass:

Meaning:

Draw a picture of a queue.

Stack

Superclass:

Meaning:

Draw a picture of a stack.

Priority Queue

Meaning:

Draw a picture of a priority queue.

Circular Queue

Meaning:

Draw a picture of a circular queue.

Recursion

Definition:

Necessary elements:

Write the fibonacci method (use long for all data types) using recursion. Draw a diagram of fibonacci(4). You can choose between the exponential algorithm O(xn) and a good algorithm O(n), but diagramming how it works needs to be done either way.

Tree

Meaning:

Binary Tree

Meaning:

Traversal

Meaning:

Three types:

Binary Search Tree (BST)

Meaning:

Write a program that takes the numbers 0 to 999 and inserts them in a BST in random order.

Write a program that does the first program ten thousand times and returns the average depth of the resulting trees. Before you run this program, predict the average depth.

Complete Binary Tree

Meaning:

Full Binary Tree

Meaning:

TreeSet

Meaning:

TreeMap

Meaning: