Test 2

Question 1

In a tree, relate number of external nodes to number of internal nodes

Answer 1

e = i + 1

Question 2

In a tree, relate number of nodes to number of external nodes

Answer 2

n = 2e - 1

Question 3

In a tree, relate height to number of internal nodes

Answer 3

h ≤ i

Question 4

In a tree, relate height to total number of nodes

Answer 4

h ≤ (n - 1)/2

Question 5

In a tree, relate number of external nodes to height

Answer 5

e ≤ 2^h

Question 6

In a tree, logarithmically relate number of external nodes to height

Answer 6

log₂e ≤ h

Question 7

In a tree, logarithmically relate height to total number of nodes

Answer 7

h ≤ log₂(n + 1) – 1

Question 8

In a tree, an internal node is…

Answer 8

A node with children. Also called a branch node.

Question 9

In a tree, an external node is…

Answer 9

A node without children. Also called a leaf node.

Question 10

What is the depth of a tree node? What is the height of a tree?

Answer 10

Depth of a node is the number of ancestors; height is the maximum depth and the number of levels minus one (because the root doesn’t have an ancestor).

Question 11

When do you skip indexes when representing a binary tree in an array?

Answer 11

When a node does not have children.

Question 12

In an array-based binary tree, the left child is at the index…

Answer 12

2f(p) + 1 where f(p) is the current node’s index

Question 13

In an array-based binary tree, the right child is at the index…

Answer 13

2f(p) + 2, where f(p) is the current node’s index

Question 14

In an array-based binary tree, the parent is at the index…

Answer 14

⌊(f(p) – 1) / 2⌋, where f(p) is the current node’s index

Question 15

In preorder traversal…

Answer 15

Visit node before children

Question 16

In postorder traversal…

Answer 16

Visit children before node

Question 17

In inorder traversal (for a binary tree)…

Answer 17

Visit left child, then node, then right child

Question 18

In breadth-first traversal…

Answer 18

Initialize a queue to root node, and while the queue is not empty:
1. dequeue from the queue
2. visit the dequeued node
3. enqueue the children of the dequeued node.

Question 19

When searching for a key in a hash table…