CIS 246: Exam 3 Answers

Nbr Pts Question/Answer
1 5 Define what it means for a tree to be balanced.

Each node has the same number of dependents on each side
2 5 What is the purpose of a hash function?

Hash functions return a value for a search key that is within the size of the array.
3 5 Define "Open Addressing" in reference to a hash table.

Only one item per index position is permitted
4 5 Define "Separate Chaining" in reference to a hash table.

Each element in the array points to a linked list, permitting more than one item per index position.
5 5 Define what is meant by "Collisions" in reference to a hash table.

Hash function returns an index of an occupied position.
6 5 Define "Linear Probing" in reference to a hash table.

Stepping by 1 to search for an available index position.
7 5 Define "Quadratic Probing" in reference to a hash table.

Stepping by the square of the step number to search for an available index position.
8 5 Define "Double Hashing" in reference to a hash table.

Hash the value by a second hash function and use that value as your step value.
9 5 What should be true of a table size in order for hashing to be successful?

Table size should be large and a prime number
10 5 How is a location determined for strings in a hash table? 

Words are converted to numbers.
11 5 What is the main characteristic of a Heap (Priority Queue)?

The value with the highest priority is at the top of the queue, and is the next value to be removed.
12 10 What are the 2 characteristics of a Red-Black tree?
  1. The nodes are colored
  2. During insertion and deletion, rules are followed to preserve the arrangements of the colors
13 10 What are the 2 actions for balancing a Red-Black tree?
  1. Change the color of the nodes
  2. Perform rotations
14 10 What are the 2 characteristics of a Binary tree?
  1. Each node has no more than two children
  2. Children on the left are smaller than the parent, children on the right are larger than the parent.
15 10 Explain the process of in-order traversal.
  1. Traverse left sub-tree
  2. Visit node
  3. Traverse right sub-tree
16 10 Explain the process of pre-order traversal.
  1. Visit node
  2. Traverse left sub-tree
  3. Traverse right sub-tree
17 10 Explain the process of post-order traversal.
  1. Traverse left sub-tree
  2. Travers right sub-tree
  3. Visit node
18 10 What are the 3 value/children configurations for nodes in a 2-3-4 tree?
  1. One value and two children
  2. Two values and three children
  3. Three values and four children
19 15 What are the formulas for parent, left child, and right child in a heap?
  1. parent = (x-1)/2
  2. lchild = 2*x+1
  3.  rchild = 2*x+2
20 20 What are the 4 rules governing Red-Black trees?
  1. Every node is either black or red
  2. The root node is always black
  3. If the node is red, the children must be black
  4. Every path from the root to a leaf, or null child, must contain the same number of black nodes
21 20 Explain insertion into a heap and the trickle-up process.

Place new value in last available position. Repeatedly swap the new value with it's parent as long as the parent is smaller than the new value.
22 20 Explain deletion from a heap and the trickle-down process.

Swap the first node with the last. Repeatedly swap the parent with it's larger child until it is larger than both it's children.