ch5i.txt

（英文原版）数据结构与算法分析（C++版）单选试题与答案

Chapter 5  Binary Trees: Instructor's CD questions

1. The height of a binary tree is:
a) The height of the deepest node.
b) The depth of the deepest node.
*c) One more than the depth of the deepest node.

2. A full binary tree is one in which:
*a) Every internal node has two non-empty children.
b) all of the levels, except possibly the bottom level, are filled.

3. The relationship between a full and a complete binary tree is:
a) Every complete binary tree is full.
b) Every full binary tree is complete.
*c) None of the above.

4. The Full Binary Tree Theorem states that:
*a) The number of leaves in a non-empty full binary tree is one more
than the number of internal nodes.
b) The number of leaves in a non-empty full binary tree is one less
than the number of internal nodes.
c) The number of leaves in a non-empty full binary tree is one half of
the number of internal nodes.
d) The number of internal nodes in a non-empty full binary tree is one
half of the number of leaves.

5. The correct traversal to use on a BST to visit the nodes in sorted
   order is:
a) Preorder traversal.
*b) Inorder traversal.
c) Postorder traversal.

6. When every node of a full binary tree stores a 4-byte data field,
   two 4-byte child pointers, and a 4-byte parent pointer, the
   overhead fraction is approximately:
a) one quarter.
b) one third.
c) one half.
d) two thirds.
*e) three quarters.
f) none of the above.

7. When every node of a full binary tree stores an 8-byte data field and
   two 4-byte child pointers, the overhead fraction is approximately:
a) one quarter.
b) one third.
*c) one half.
d) two thirds.
e) three quarters.
f) none of the above.

8. When every node of a full binary tree stores a 4-byte data field
   and the internal nodes store two 4-byte child pointers, the
   overhead fraction is approximately:
a) one quarter.
b) one third.
*c) one half.
d) two thirds.
e) three quarters.
f) none of the above.

9. If a node is at position r in the array implementation for a
   complete binary tree, then its parent is at:
*a) (r - 1)/2 if r > 0
b) 2r + 1 if (2r + 1) < n
c) 2r + 2 if (2r + 2) < n
d) r - 1 if r is even
e) r + 1 if r is odd.

10. If a node is at position r in the array implementation for a
   complete binary tree, then its right child is at:
a) (r - 1)/2 if r > 0
b) 2r + 1 if (2r + 1) < n
*c) 2r + 2 if (2r + 2) < n
d) r - 1 if r is even
e) r + 1 if r is odd.

11. Assume a BST is implemented so that all nodes in the left subtree
    of a given node have values less than that node, and all nodes in
    the right subtree have values greater than or equal to that node.
    When implementing the delete routine, we must select as its
    replacement:
a) The greatest value from the left subtree.
*b) The least value from the right subtree.
c) Either of the above.

12. Which of the following is a true statement:
a) In a BST, the left child of any node is less than the right child,
and in a heap, the left child of any node is less than the right
child.
*b) In a BST, the left child of any node is less than the right child,
but in a heap, the left child of any node could be less than or
greater than the right child.
c) In a BST, the left child of any node could be less or greater than
the right child, but in a heap, the left child of any node must be
less than the right child.
d) In both a BST and a heap, the left child of any node could be
either less than or greater than the right child.

13. When implementing heaps and BSTs, which is the best answer?
a) The time to build a BST of n nodes is O(n log n), and the time to
build a heap of n nodes is O(n log n).
b) The time to build a BST of n nodes is O(n), and the time to
build a heap of n nodes is O(n log n).
*c) The time to build a BST of n nodes is O(n log n), and the time to
build a heap of n nodes is O(n).
d) The time to build a BST of n nodes is O(n), and the time to
build a heap of n nodes is O(n).

14. The Huffman coding tree works best when the frequencies for
    letters are
a) Roughly the same for all letters.
*b) Skewed so that there is a great difference in relative frequencies
    for various letters.

15. Huffman coding provides the optimal coding when:
a) The messages are in English.
b) The messages are binary numbers.
*c) The frequency of occurrence for a letter is independent of its
context within the message.
d) Never.