ch6i.txt

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

Chapter 6  Binary Trees: Instructor's CD questions

1. The primary ADT access functions used to traverse a general tree are:
a) left child and right sibling
b) left child and right child
*c) leftmost child and right sibling
d) leftmost child and next child

2. The tree traversal that makes the least sense for a general tree
is:
a) preorder traversal
*b) inorder traversal
c) postorder traversal

3. The primary access function used to navigate the general tree when performing UNION/FIND is:
a) left child
b) leftmost child
c) right child
d) right sibling
*e) parent

4. When using the weighted union rule for merging disjoint sets, the
maximum depth for any node in a tree of size n will be:
a) nearly constant
*b) log n
c) n
d) n log n
e) n^2

5. We use the parent pointer representation for general trees to solve 
which problem?
a) Shortest paths
b) General tree traversal
*c) Equivalence classes
d) Exact-match query

6. When using path compression along with the weighted union rule for
merging disjoint sets, the average cost for any UNION or FIND
operation in a tree of size n will be:
*a) nearly constant
b) log n
c) n
d) n log n
e) n^2

7. The most space efficient representation for general trees will
typically be:
a) List of children
*b) Left-child/right sibling
c) A K-ary tree.

8. The easiest way to represent a general tree is to:
a) convert to a list.
*b) convert to a binary tree.
c) convert to a graph.

9. As K gets bigger, the ratio of internal nodes to leaf nodes:
*a) Gets smaller.
b) Stays the same.
c) Gets bigger.
d) Cannot be determined, since it depends on the particular
configuration of the tree.

10. A sequential tree representation is best used for:
*a) Archiving the tree to disk.
b) Use in dynamic in-memory applications.
c) Encryption algorithms.
d) It is never better than a dynamic representation.