Questions Chapter 8

Question 1

Trees consist of ______ connected by ______.

Answer 1

Trees consist of nodes connected by edges.

Question 2

In a binary tree, a node has at most ____ children.

Answer 2

two

Question 3

In a binary tree, all the nodes that are _____ descendants of Node A have key values _____ than A; all the nodes that are A’s _____ descendants have key values ______ than or equal to A.

Answer 3

left descendants have key values less than A, right descendants have key values greater than or equal to A.

Question 4

Trees perform searches, insertions, and deletions in ______ time.

Answer 4

O(log N) time

Question 5

An unbalanced tree is one whose root has many more ______ descendants than _____ descendants or vice-versa.

Answer 5

left than right, right than left descendants

Question 6

Insertion involves finding the place to insert the new node and then changing a _______ field in its new _______ to refer to it.

Answer 6

change a child field in its new parent to refer to it

Question 7

An ________ traversal visits nodes in order of ascending keys.

Answer 7

inorder traversal

Question 8

When a node has ____ child/children, it can be deleted by setting the _____ field in its parent to null.

Answer 8

zero children, set child field in parent to null.

Question 9

When a node has _____ child/children, it can be deleted by setting the _______ field in its parent to point to its _______.

Answer 9

one child, set child field in parent to its child.

Question 10

When a node has ______ child/children, it can be deleted by replacing it with its successor.

Answer 10

two children

Question 11

The successor to node A can be found by finding the ________ node in the subtree whose ______ is A’s _____ child.

Answer 11

find the minimum node in the subtree whose root is A’s right child.

Question 12

Insertion and deletion in a tree require what big O time?

Answer 12

O(logN)

Question 13

A binary tree is a search tree if:

a. every non-leaf node has children whose key values are less than (or equal to) the parent.
b. every left child has a key less than the parent and every right child has a key greater than (or equal to) the parent
c. in the path from the root to every leaf node, the key of each node is greater than (or equal to ) the key of its parent
d. a node can have a maximum of two children

Answer 13

b. every left child has a key less than the parent and every right child has a key greater than (or equal to) the parent.

Question 14

True or False: Not all trees are binary trees.

Answer 14

True

Question 15

In a complete binary tree with 20 nodes, and the root considered to be at level 0, how many nodes are there at level 4?

Answer 15

5

Question 16

A subtree of a binary tree always has:

a. a root that is a child of the main tree’s root
b. a root unconnected to the main tree’s root
c. fewer nodes than the main tree
d. a sibling with the same numer of nodes

Answer 16

c. fewer nodes than the main tree.

Question 17

In the Java code for a tree, the ______ and the _______ are generally separate classes.

Answer 17

the node and the tree are separate classes.

Question 18

Finding a node in a binary search tree involves going from node to node, asking:

a. how big the node’s key is in relation to the search key
b. how big the node’s key is compared to its right or left children
c. what leaf node we want to reach
d. what level we are on

Answer 18

a. how big the node’s key is in relation to the search key

Question 19

An unbalanced tree is one:

a. in which most of the keys have values greater than the average
b. whose behaviour is unpredictable
c. in which the root or some other node has many more left children than right children, or vice versa.
d. that is shaped like an umbrella

Answer 19

c.

Question 20

Inserting a node starts with the same steps as ________ a node.

Answer 20

finding a node

Question 21

Suppose node A has a successor node S. Then S must have a key that is larger than _________, but smaller than or equal to ___________________.

Answer 21

S key larger than A, but smaller than or equal to A’s left child descendants

Question 22

In a binary tree used to represent a mathematical expression, which of the following is NOT true:

a. both children of an operator node must be operands
b. following a postorder traversal, no parenthesis need to be added
c. following an inorder traversal, parentheses must be added
d. in pre-order traversal, a node is visited before either of its children

Answer 22

d. in pre-order traversal, a node is visited before either of its children

Question 23

If a tree is represented by an array, the right child fo a node at index n has an index of _________.

Answer 23

2*index+2

Question 24

True or False: Deleting a node with one child from a binary search tree involves finding that node’s successor.

Answer 24

False