Deck 9: Trees

Question 1

The predecessor of a node is called its __________.

A) sibling
B) parent
C) child
D) descendant

Answer 1

parent

Question 2

A(n) __________ of a node is a tree whose root is a child of that node.

Answer 2

subtree

Question 3

The height of a tree is the same as the height of its root node.

Answer 3

True

Question 4

A set of nodes T is a binary tree if either of the following is true:
• __________
• If T is not empty, it has a root node r with 0, 1, or 2 binary subtrees whose roots are connected to r by a branch.

A) T is complete
B) T is balanced
C) T is full
D) T is empty

Question 5

In an expression tree, operands are stored in the __________ node(s).

A) internal
B) leaf
C) root
D) ancestor

Question 6

To decode a file of letters and spaces, you walk down the Huffman tree, starting at the root, until you reach a(n) __________.

Question 7

Searching a binary search tree is an O(__________) process.

A) 1
B) log n
C) n
D) n log n

Question 8

A(n) complete binary tree of height h is filled up to depth __________ and, at depth h, any unfilled nodes are on the right.

Question 9

The process of walking through a tree in a prescribed order and visiting the nodes as they are encountered in known as tree __________.

Question 10

You may not define member functions in a C++ struct type.

Question 11

Complete the definition of Binary_Tree member function is_null.
template<typename Item_Type>
bool Binary_Tree<Item_Type>::is_null() const
{
/**missing code goes here*/
__________
}

Question 12

Which of the following lines completes the definition of is_leaf?

A) return root->left == NULL;
B) return root->right == NULL;
C) return root->left == NULL || root->right == NULL;
D) return root->left == NULL && root->right == NULL;

Question 13

A(n) __________ pointer is a class that acts like a pointer, but automatically deletes the object pointed to when the pointed-to object has no owners.

Question 14

In the worst case scenario, a search against an unbalanced binary search has a performance cost of O(__________).

A) 1
B) log n
C) n
D) n log n

Question 15

Which of the following lines completes the insert starter function?

A) return insert(root, item);
B) return insert(this->root, item);
C) return insert(item);
D) return insert(this, item);

Question 16

In a binary search tree, the parent must be smaller than all of the data fields in the left subtree and larger than all of the data fields in the right subtree.

Question 17

Enable the replace_parent function to maintain a connection to the subtree originally pointed to by local_root, by using the line __________.

Question 18

A(n) __________ is a substring that is delimited by a pair of delimiter characters (examples of delimiter characters are spaces and punctuation symbols).

Question 19

A heap is a complete binary tree with the following properties:
• The value in the root is greater than or equal to all items in the tree.
• __________

Question 20

Removal from a heap is always from the top.

Question 21

For a node at position p in a vector representing a heap, the left child is at __________.

A) 2p
B) 2p + 1
C) 2p + 2
D) 2p - 1

Question 22

Both heap insert and remove are O(__________), where n is the number of items in the heap.

A) log n
B) n
C) n²
D) n³

Question 23

Priority queues violate the FIFO property of an ordinary queue.

Question 24

To remove an item from the priority queue, we take the __________ item from the underlying vector container; this is the largest item.

Question 25

When using the ASCII code to make messages, the length of a message would be __________ where n is the total number of characters.

A) 8 * log n
B) 8 * n
C) 8 * n log n
D) 8 * n²