ch13i.txt

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

Chapter 13  Advanced Tree Structures: Instructor's CD questions

1. A trie is different from a BST in that the trie uses:
a) an object space decomposition.
*b) a key space decomposition.

2. In a trie,
a) The internal nodes and the leaf nodes store data.
b) The internal nodes store data and the leaf nodes are placeholders.
*c) The leaf nodes store data and the internal nodes direct the search.

3. Which of the following is NOT guaranteed to have height O(log n)
when storing n nodes?
a) AVL tree.
*b) Splay tree.
c) 2-3 tree.

4. Which of the following is NOT a form of BST?
a) AVL tree.
b) Splay tree.
*c) 2-3 tree.
d) b and c.

5. Combining multidimensional coordinates into a single key value to
store in a BST would make which operation inefficient?
a) insert.
b) delete.
c) exact-match queries.
*d) multidimensional range queries.

6. Which of the following is an example of a trie?
a) K-d tree.
b) Point quadtree.
*c) PR quadtree.

7. Which of the following is a simple variation on a BST?
*a) K-d tree.
b) Point quadtree.
c) PR quadtree.
d) Bintree.

8. In general, a flyweight is:
a) An empty leaf node.
*b) An object that is created once and used at many places in the data
structure.
c) An internal node.

9. Which is not a splay tree rotation?
a) single rotation.
b) zigzag rotation.
*c) clockwise rotation.

10. Which best characterizes the performance of the splay tree?
a) All operations require O(log n) time.
*b) m operations require a total of O(m log n) time for m > n.
c) All operations require O(n) time.