ch11i.txt

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

Chapter 11  Graphs: Instructor's CD questions

1. Which is not the name for a standard graph traversal?
*a) Preorder.
b) Depth first.
c) Breadth first.

2. Depth-first search is best implemented using:
*a) A stack or recursion.
b) A queue.
c) A tree.

3. Breadth-first search is best implemented using:
a) A stack or recursion.
*b) A queue.
c) A tree.

4. The goal of a topological sort is to:
a) Sort all of the graph vertices by value.
*b) Sort all of the graph vertices so that each vertex is listed prior to
any others that depend on it.
c) Sort all of the graph vertices by distance from the source vertex.

5. A topological sort requires all of the following except:
a) The graph be directed.
b) The graph contain no cycles.
*c) The graph contain weights on the edges.

6. The single-source shortest path problem can be used to:
a) Sort all of the graph vertices by value.
b) Sort all of the graph vertices so that each vertex is listed prior to
any others that depend on it.
*c) Sort all of the graph vertices by distance from the source vertex.

7. Dijkstra's algorithm requires that vertices be visited in:
a) Depth-first order.
b) Breadth-first order.
*c) Order of distance from the source vertex.
d) No particular order.

8. In the all-pairs shortest paths problem, a k-path is:
a) The shortest path to vertex k.
b) The sorest path that goes through vertex k.
*c) A path such that all intermediate vertices have index less than k.

9. For a graph of n nodes, no algorithm to solve the all-pairs
shortest paths problem could possibly have a cost less than:
a) Omega(log n)
b) Omega(n)
c) Omega(n log n)
*d) Omega(n^2)
e) Omega(2^n)

10. Which is a good example of a greedy algorithm?
a) Floyd's all-pairs shortest path algorithm.
*b) Prim's minimal-cost spanning tree algorithm.
c) Depth-first search.
d) Topological sorting.