5e Verified Test Bank Chapter.25 - Tree Implementations

Chapter 25 - Tree Implementations

True/False (11)

1. The most common implementation of a tree uses a linked structure.
2. A node object in a binary tree references other nodes in the tree.
3. A binary tree node references another binary tree.
4. Typically, details of the class that represents a node in a tree are hidden from the client.
5. Implementing binary tree traversals as iterators makes the code less flexible for the client.
6. An iterator object that has not traversed the entire binary tree can be adversely affected by changes to the tree.
7. The preorder traversal of a binary tree and a general tree are different.
8. The postorder traversal of a general tree is the same as the inorder traversal of a binary tree.
9. You can derive an expression tree from the class of basic binary trees.
10. A node in a general tree is an object that references its children and a data object.
11. You cannot use a binary tree to represent a general tree.

Short Answer (14)

1. Write pseudocode for the binary tree method isLeaf() that returns true if the node is a leaf and false if not.
2. Show the contents of the stack as an inorder traversal is performed on the following binary tree.
   

a
empty (a is removed)
b
b c
b (c is removed)
empty (b is removed)
d
d e
d (e is removed)
empty (d is removed)

1. Show the contents of the stack as a preorder traversal is performed on the following binary tree.
   

a
empty (a is removed)
b
empty (b is removed)
d
d c
d (c is removed)
empty (d is removed)
e
empty (e is removed)

1. Show the contents of the stack as a postorder traversal is performed on the following binary tree.
   

a
a b
a b c
a b (c is removed)
a b d
a b d e
a b d (e is removed)
a b (d is removed)
a (b is removed)
empty (a is removed)

1. Given the following binary expression tree, what value is returned from the method evaluate in the class ExpressionTree if w = 7, x = 2, y = 1, and z = 8?
   
2. Given the following binary expression tree, what value is returned from the method evaluate in the class ExpressionTree if w = 5, x = 3, y = 7, and z = 8?
   
3. Give the preorder traversal of the following general tree.
   
4. Give the postorder traversal of the following general tree.
   
5. Give the preorder traversal of the following general tree.

1. Give the postorder traversal of the following general tree.

1. Draw the binary tree that gave the following traversals:
   Inorder: Q Y R Z X T
   Preorder: T Q Y Z R X

1. Draw the binary tree that gave the following traversals:
   Postorder: Y Q R X Z T
   Inorder: Q Y T R Z X

1. Draw the binary tree that gave the following traversals:
   Inorder: S A E U Y Q R P D F K L M
   Preorder: F A S Q Y E U P R D K L M

1. Draw the binary tree that gave the following traversals:
   Postorder: S Y U A E R P Q D L K F
   Inorder: S A Y U F K Q E R P L D

Multiple Choice (15) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. The most common implementation of a tree uses a(n)
   1. linked structure
   2. array
   3. bag
   4. priority queue
2. The elements in a tree are called
   1. nodes
   2. search keys
   3. entries
   4. indexes
3. In a binary tree, if both the left and right child of a node are null
   1. the node is a leaf
   2. the node is the root of the tree
   3. the node is invalid
   4. the node contains the key-value pair being searched for
4. An iterative version of an inorder traversal for a binary tree uses a(n)
   1. stack
   2. queue
   3. priority queue
   4. bag
5. An iterative version of an preorder traversal for a binary tree uses a(n)
   1. stack
   2. queue
   3. priority queue
   4. bag
6. An iterative version of an postorder traversal for a binary tree uses a(n)
   1. stack
   2. queue
   3. priority queue
   4. bag
7. An iterative version of a level order traversal for a binary tree uses a(n)
   1. queue
   2. priority queue
   3. stack
   4. bag
8. A complete traversal of an n-node binary tree is a(n) _____ operation if visiting a node is O(1) for the recursive implementation.
   1. O(n)
   2. O(1)
   3. O(log n)
   4. O(n2)
9. A complete traversal of an n-node binary tree is a(n) _____ operation if visiting a node is O(1) for the iterative implementation.
   1. O(n)
   2. O(1)
   3. O(log n)
   4. O(n2)
10. A complete traversal of an n-node binary tree is an O(n) operation if visiting a node is _____ for the recursive implementation.
    1. O(1)
    2. O(log n)
    3. O(ln)
    4. O(n2)
11. A complete traversal of an n-node binary tree is an O(n) operation if visiting a node is _____ for the iterative implementation.
    1. O(1)
    2. O(log n)
    3. O(ln)
    4. O(n2)
12. Given the following binary expression tree, what value is returned from the method evaluate in the class ExpressionTree if w = 7, x = 2, y = 1, and z = 8?
    
    
    1. 64
    2. 16
    3. 15
    4. 57
13. The postorder traversal of a general tree is the same as the _____ traversal of a binary tree.
    1. inorder
    2. postorder
    3. preorder
    4. level order
14. The preorder traversal of a general tree is the same as the _____ traversal of a binary tree.
    1. preorder
    2. postorder
    3. inorder
    4. level order
15. A node in a binary tree is an object that references a data object and
    1. two child nodes in the tree
    2. a linked list containing the child nodes
    3. a vector containing the list of child nodes
    4. none of the above