- Trees Ch.24 Test Bank Answers 5th Edition

Chapter 24 - Trees

True/False (13)

1. In a tree, nodes are arranged in levels that indicate the nodes’ hierarchy.
2. In a tree, the root is the only node that has no parent.
3. Every general tree is an n-ary tree.
4. A subtree of a tree is a subtree of the tree’s root.
5. The path between a tree’s root and any other node is not unique.
6. The height of a tree equals the number of nodes along the longest path between the root and a leaf.
7. All leaves in a full binary tree are on the same level.
8. Completely balance binary trees are not necessarily full.
9. All nodes in a balanced binary tree are balanced.
10. A level-order traversal of a binary tree is an example of a depth-first traversal.
11. A preorder traversal of a binary tree is an example of a depth-first traversal.
12. An inorder traversal is not well defined for a general tree.
13. Every node in a binary search tree is the root of a binary search tree.

Short Answer (19)

1. How many nodes are in a full binary tree of height 8?
2. What is the height of a complete tree that contains 18 nodes?
3. List the steps of a preorder traversal of a binary tree.

b) visit all the nodes in the root’s left subtree
c) visit all the nodes in the root’s right subtree

1. List the steps of a postorder traversal of a binary tree.

b) visit all the nodes in the root’s right subtree
c) visit the root

1. List the steps of an inorder traversal of a binary tree.

b) visit the root
c) visit all the nodes in the root’s right subtree

1. Given the following binary tree, list the leaf nodes.

1. Given the following binary tree, list the nonleaf nodes.

1. Give the preorder traversal of the following binary tree.
   
2. Give the inorder traversal of the following binary tree.
   
3. Give the postorder traversal of the following binary tree.
   
4. Give the level order traversal of the following binary tree.
   
5. Build the binary expression tree for the following input.
   (7 + (2 – 1)) 8

1. What is the minimum height possible for a binary tree with 11 nodes? Construct an example tree.

1. What is the maximum height possible for a binary tree with 7 nodes? Construct an example tree.

1. Given the following general tree, list the leaf nodes.

1. Given the following general tree, what are the siblings of node C?

1. Given the following general tree, what are the descendants of node C?

1. Given the following general tree, what are the ancestors of node M?

1. Given the following general tree, which nodes are parents?

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

1. When you classify data into groups and subgroups, you are using a(n) _____ order.
   1. hierarchical
   2. linear
   3. circular
   4. group
2. A family tree is typically organized into a(n) _____ order.
   1. hierarchical
   2. linear
   3. circular
   4. group
3. An example of a data organization that is hierarchical is a(n)
   1. family tree
   2. university administration structure
   3. file directories
   4. all of the above
4. A _____ is a set of nodes connected by edges that indicate the relationships among the nodes.
   1. tree
   2. bag
   3. hierarchy
   4. linked list
5. A tree is a set of _____ connected by edges that indicate the relationships among the nodes.
   1. nodes
   2. links
   3. lists
   4. bags
6. A tree is a set of nodes connected by _____ that indicate the relationships among the nodes.
   1. edges
   2. lists
   3. bags
   4. siblings
7. At the top level of a tree is a single node called the _____.
   1. root
   2. top
   3. pinnacle
   4. front
8. The nodes at each successive level of a tree are called _____.
   1. children
   2. parents
   3. roots
   4. keys
9. A node that has children is a(n) _____.
   1. parent
   2. sibling
   3. key
   4. edge
10. Nodes that are children of the same parent node are called _____.
    1. siblings
    2. descendants
    3. ancestors
    4. roots
11. A node with no children is called a(n) _____.
    1. leaf
    2. parent
    3. both a & b
    4. none of the above
12. A node that has children is called a(n) _____.
    1. nonleaf
    2. interior node
    3. both a & b
    4. none of the above
13. A tree in which each node may have an arbitrary number of children is called a(n) _____ tree.
    1. general
    2. multi-faceted
    3. branching
    4. super
14. A tree in which each node may have at most two children is called a(n) _____ tree.
    1. binary
    2. general
    3. bi-lingual
    4. n-ary
15. A tree in which each node may have no more than n children is called a(n) _____ tree.
    1. n-ary
    2. binary
    3. general
    4. branching
16. The _____ node is the only node that has no parent.
    1. root
    2. child
    3. binary
    4. n-ary
17. Any node and its descendants form a _____ of the original tree.
    1. subtree
    2. nested
    3. super tree
    4. separate tree
18. A subtree of a node is a tree rooted at
    1. a child of that node
    2. the root of the tree
    3. a sibling of that node
    4. the node itself
19. The number of levels in a tree is called the
    1. height
    2. node count
    3. branch level
    4. size
20. A binary tree has at most two children called
    1. the left child
    2. the right child
    3. both a & b
    4. none of the above
21. When a binary tree of height h has all of its leaves at level h and every nonleaf has exactly two children, the tree is said to be
    1. full
    2. populated
    3. organized
    4. congested
22. When a binary tree is full to its next-to-last level and its leaves on the last level are filled from left to right, the tree is said to be
    1. complete
    2. organized
    3. populated
    4. ordered
23. A node in a binary tree whose subtrees differ in height by no more than 1 is known as a(n) _____ node.
    1. balanced
    2. orphan
    3. leaf
    4. terminating
24. The height of a full tree that has n nodes is
    1. log₂(n+1)
    2. log₂(n-1)
    3. n + 1
    4. n
25. The height of a complete tree that has n nodes is
    1. log₂(n+1)
    2. log₂(n-1)
    3. n + 1
    4. n
26. How many nodes are in a full binary tree of height 5?
    1. 31
    2. 32
    3. 33
    4. 5
27. What is the height of a complete tree that contains 11 nodes?
    1. 4
    2. 3
    3. 5
    4. 11
28. In a(n) _____ traversal of a binary tree, you visit the root node before you visit the root’s subtrees.
    1. preorder
    2. postorder
    3. inorder
    4. level order
29. In a(n) _____ traversal of a binary tree, you visit the root of a binary tree between visiting the nodes of the root’s subtrees.
    1. inorder
    2. preorder
    3. postorder
    4. level order
30. In a(n) _____ traversal of a binary tree, you visit the root of a binary tree after you visit the root’s subtrees.
    1. postorder
    2. preorder
    3. inorder
    4. level order
31. In a(n) _____ traversal of a binary tree, you begin at the root and visit nodes one level at a time.
    1. level order
    2. inorder
    3. flat order
    4. straight order
32. The nodes in a binary search tree contain _____ objects.
    1. Comparable
    2. Sorted
    3. key-value pair
    4. binary
33. A _____ is a complete binary tree such that each node in the tree contains a Comparable object that is greater than or equal to the objects in the node’s descendants.
    1. maxheap
    2. minheap
    3. binheap
    4. fullheap