Chapter 16 Questions
Multiple Choice
1. What is the first step in implementing a tree?
a. choose a data structure to represent its nodes
b. determine the type of item to be stored in the tree
c. determine the height of the tree
d. determine how many items will be in the tree
2. Consider an array-based representation of a tree and a variable called root as the index to
the tree’s root node. What value does the text suggest to assign to root if the tree is empty?
a. 0
b. -1
c. 1
d. nullptr
3. In an array-based representation of a tree, what keeps track of available nodes?
a. the variable emptyCount
b. the variable nextAvailable
c. the free list
d. the node list
4. What do you do if you remove a node from a tree in an array-based implementation?
a. assign it to nullPtr
b. nothing, leave it as is, just don’t link anything to it
c. remove it from the array
d. add it to the free list
5. In the class BinaryNode, which of the following methods are specified as type bool?
a. isLeaf
b. setItem
c. setLeftChildPtr
d. getLeftChildPtr
6. In the class BinaryNode, what value is stored in rootPtr if the tree is empty?
a. 0
b. -1
c. 1
d. nullptr
7. In the class BinaryNode, if the tree is not empty, what points to the root’s left child?
Chapter 16 Questions
a. getLeftHildPtr()
b. rootPtr–>getLeftChildPtr()
c. getLeftChildPtr()–> rootPtr
d. leftChildPtr
8. What overladed operator did the class BinaryNodeTree have specified in the text?
a. less than
b. not
c. assignment
d. plus (concatenation)
9. To copy a tree, traverse it in __________ and add each data item visited to a new node.
a. inorder
b. postorder
c. reorder
d. preorder
10. What is the classification of the method getHeightHelper?
a. protected
b. private
c. public
d. restricted
11. Given the following code from BinaryNodeTree
template<class ItemType>
bool BinaryNodeTree<ItemType>::________(const ItemType&
newData)
{
auto newNodePtr =
std::make_shared<BinaryNode<ItemType>>(newData);
rootPtr = balancedAdd(rootPtr, newNodePtr);
return true;
} // end add
What is the name of this method?
a. getHeight
b. add
c. remove
d. getEntry
Chapter 16 Questions
12. In the class BinaryNodeTree, the protected method inorder has a parameter visit. What is the
specification for this parameter?
a. virtual
b. value
c. reference
d. dummy
13. To save a binary search tree in a file and then restore it to its original shape, what type of
traversal should be used?
a. postorder
b. inorder
c. reorder
d. preorder
14. To remove a leaf in a binary search tree, what must be done?
a. set the pointer in the leaf’s parent to nullptr
b. set the pointer in the leaf to nullptr
c. set the pointer in the root to nullptr
d. delete the data from the leaf
15. If node N is being removed from a binary search tree and has a left child, what must be done
if P is the parent of N?
a. let the left child of N adopt P
b. let P adopt the left child of N
c. store the data of the left child of N in N
d. store the data of N in P
16. If a file contains items in a specified order, how must they be added to put them into a binary
search tree in that same order?
a. use the method addInOrder
b. use the method inOrderAdd
c. use the method add
d. use the method reOrderAdd
17. What efficiency is the tree sort in the average case?
a. O(n)
b. O(log2 n)
c. O(n2)
d. O(n * log n)
Chapter 16 Questions
True or False
1. According to the text, it is natural to make each node an object.
2. In an array-based implementation of a binary tree, the data member free is the index of
the index of the first node in the free list. Therefore the next available node will always
be at index free + 1.
3. When a node is removed from a tree and returned to the free list, it could be anywhere in
the array.
4. According to the text, an array-based implementation of a binary tree is much less
attractive when the tree is complete.
5. If you use an array-based implementation of a complete binary tree, you must be sure that
the tree remains complete as a result of additions or removals.
6. The class BinaryNodeTree had only the default constructor.
7. For class BinaryNodeTree, the copy constructor and the destructor implicitly use
traversal.
8. For class BinaryNodeTree, the copy constructor and the destructor each call a
recursive method.
9. The add method of BinaryNodeTree concatenates two trees.
10. The add method of BinaryNodeTree does not indicate where that new data should
be in the tree.
11. In the class BinaryNodeTree, the public traversal methods each call a protected
method that performs the actual recursion.
12. A reference parameter in a protected method does not allow the client code to modify the
parameter.
Chapter 16 Questions
13. In the class BinaryNodeTree, the methods that use the parameter visit can modify
the tree’s data, but not its structure.
14. A binary search tree is a binary tree.
15. The postorder traversal of a binary search tree will visit the tree’s data items in sorted
order.
16. Making methods protected enables a derived class to use them directly
17. A balanced binary search tree decreases the efficiency of the ADT operations.
18. This is a tree of minimum height that is not
complete.
19. The traversals of a binary search tree differ from the traversals of a binary tree.
20. A full tree with exactly n = 2h − 1 nodes for some height h has the exact middle of the
data items in its root.
Chapter 16 Questions
21. Short Answer
1. What must each node of a tree contain?
2. Name two of the items in a TreeNode classified as private.
3. What does a free list keep track of?
4. In an array-based implementation of a binary tree, what is stored in leftChild or rightChid
if the node has no child?
5. Given the binary tree of names at the right. In the
array tree below fill in the left and right child
fields.
item
leftChild
rightChild
0
Jose
1
Deepak
2
Quang
3
Anton
4
Elisa
5
Mia
6. In the class BinaryNode, name two void methods that are public.
7. For the class BinaryNodeTree, name two ways in which the constructors enable a
client to define binary trees.
Chapter 16 Questions
8. What kind of traversal does BinaryNodeTree use in the copyTree method?
9. What kind of traversal does BinaryNodeTree use in the destroyTree method?
10. Given the diagram of a binary tree to the
right. Draw the next node which would
be placed by the method add in
BinaryNodeTree.
11. Given the binary search tree (based on the
names) to the right.
Where would the node with the the name
Kody be added?
12. Describe the three cases for the node N containing an item to be removed