Multiple Choice Identify the
choice that best completes the statement or answers the question.
|
|
1.
|
Consider a shortest route problem in which a bank courier must travel between
branches and the main operations center. When represented with a network,
a. | the branches are the arcs and the operations center is the node. | b. | the branches are the
nodes and the operations center is the source. | c. | the branches and the operations center are all
nodes and the streets are the arcs. | d. | the branches are the network and the operations
center is the node. |
|
|
2.
|
The shortest-route problem finds the shortest-route
a. | from the source to the sink. | b. | from the source to any other
node. | c. | from any node to any other node. | d. | from any node to the
sink. |
|
|
3.
|
Consider a maximal flow problem in which vehicle traffic entering a city is
routed among several routes before eventually leaving the city. When represented with a
network,
a. | the nodes represent stoplights. | b. | the arcs represent one way
streets. | c. | the nodes represent locations where speed limits change. | d. | None of the
alternatives is correct. |
|
|
4.
|
We assume in the maximal flow problem that
a. | the flow out of a node is equal to the flow into the node. | b. | the source and sink
nodes are at opposite ends of the network. | c. | the number of arcs entering a node is equal to
the number of arcs exiting the node. | d. | None of the alternatives is
correct. |
|
|
5.
|
Consider a minimal spanning tree problem in which pipe must be laid to connect
sprinklers on a golf course. When represented with a network,
a. | the pipes are the arcs and the sprinklers are the nodes. | b. | the pipes are the
nodes and the sprinklers are the arcs. | c. | the pipes and the sprinklers are the
tree. | d. | each sprinkler must be connected to every other
sprinkler. |
|
|
6.
|
The minimal spanning tree algorithm is considered to be:
a. | a greedy algorithm. | b. | an arc algorithm. | c. | a non-optimal
algorithm. | d. | a non-feasible algorithm. |
|
|
7.
|
The minimal spanning tree algorithm has connected nodes 8 and 9. Node 8 could be
connected to nodes 11 (distance 6) and 12 (distance 5) and node 9 could be connected to node 12
(distance 3) and node 13 (distance 2). Which will you do next?
a. | connect 8 to 11 | b. | connect 8 to 12 | c. | connect 9 to
12 | d. | connect 9 to 13 |
|
|
8.
|
For a network consisting of N nodes, a minimal spanning tree will consist
of:
a. | N - 2 arcs. | b. | N - 1 arcs. | c. | N arcs. | d. | N + 1
arcs. |
|
|
9.
|
The minimal spanning tree algorithm will:
a. | sometimes fail to produce a feasible solution. | b. | always produce a
feasible, but not necessarily optimal, solution. | c. | always produce an optimal
solution. | d. | always produce an optimal, but not necessarily feasible,
solution. |
|