Question 1

The predecessor of a node is called its __________.
A) sibling
B) parent
C) child
D) descendant

Accepted Answer

The predecessor of a node in a tree structure is called its parent, which is the node directly above it and connected to it.

Question 2

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

Accepted Answer

subtree

Question 3

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

Accepted Answer

The height of a tree is defined as the maximum number of edges from the root node to any leaf node. Since the root node is also a leaf node, the height of the tree is the same as the height of its root node.

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

Accepted Answer

A binary tree can be empty, which is a base condition for defining a binary tree. If it's not empty, it must have a root node that could have up to two subtrees.

Question 5

In an expression tree, operands are stored in the __________ node(s).
A) internal
B) leaf
C) root
D) ancestor

Accepted Answer

In an expression tree, operands are stored in the leaf nodes, while operators are stored in the internal nodes. The root node can be either an operator or an operand, depending on the expression's complexity, but typically it's an operator for non-trivial expressions.

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) __________.

Accepted Answer

The answer of To decode a file of letters and...

Question 7

Searching a binary search tree is an O(__________) process.
A) 1
B) log n
C) n
D) n log n

Accepted Answer

Searching a binary search tree has a time complexity of O(log n) in the average and best-case scenarios, assuming the tree is balanced.

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.

Accepted Answer

The answer of A(n) complete binary tree of height h...

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 __________.

Accepted Answer

The answer of The process of walking through a tree...

Question 10

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

Accepted Answer

In C++, structs can have member functions, including constructors and destructors, similar to classes.

Question 11

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

Accepted Answer

The answer of Complete the definition of Binary_Tree member function...

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;

Accepted Answer

The answer of Which of the following lines completes the...

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.

Accepted Answer

The answer of A(n) __________ pointer is a class that...

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

Accepted Answer

In the worst case scenario, an unbalanced binary search tree can degenerate into a structure similar to a linked list, especially if elements are inserted in a sorted order. This means that for every search operation, you might need to traverse through all the elements, leading to a time complexity of O(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);

Accepted Answer

The answer of Which of the following lines completes the...

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.

Accepted Answer

In a binary search tree, the parent must be larger than all of the data fields in the left subtree and smaller 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 __________.

Accepted Answer

The answer of Enable the replace_parent function to maintain a...

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).

Accepted Answer

The answer of A(n) __________ is a substring that is...

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.
• __________

Accepted Answer

The answer of A heap is a complete binary tree...

Question 20

Removal from a heap is always from the top.

Accepted Answer

In a heap, removal always occurs from the top, specifically from the root node, to maintain the heap property.

Quiz 9: Trees

The predecessor of a node is called its __________.

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

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

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.

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