Chapter.29 - Graphs Complete Test Bank

Chapter 29 - Graphs

True/False (11)

1. A graph that has no cycles is called acyclic.
2. Adjacent vertices are called neighbors.
3. Typical graphs are dense.
4. All graphs are trees but not all trees are graphs.
5. A tree is a connected graph without cycles.
6. The vertices in a graph may only have one topological order.
7. A topological order is not possible for a graph that has a cycle.
8. A graph may have more than one path between the same two vertices.
9. In an unweighted graph, the shortest path between two given vertices has the smallest length.
10. In a weighted graph, the shortest path between two given vertices has the largest edge-weight sum.
11. In the ADT graph, once you create it, you do not add vertices.

Short Answer (5)

1. If a directed graph has 9 vertices, how many edges can it have?
2. If an undirected graph has 9 vertices, how many edges can it have?
3. Give a topological sort for this graph.
   
4. Give the breadth-first traversal of the following graph beginning at vertex A.
   
5. Give the depth-first traversal of the following graph beginning at vertex A.
   

Multiple Choice (29) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. A(n) _____ is a collection of distinct vertices and distinct edges.
   1. graph
   2. binary search tree
   3. red-black tree
   4. AVL tree
2. In a graph, the circles are called
   1. vertices
   2. nodes
   3. both a & b
   4. none of the above
3. In a graph, the lines are called
   1. edges
   2. connectors
   3. both a & b
   4. none of the above
4. When an edge does not have a direction in a graph, it is called
   1. undirected
   2. non-directed
   3. disjunctive
   4. disjoint
5. A graph with directed edges is called a(n)
   1. directed graph
   2. digraph
   3. both a & b
   4. none of the above
6. A sequence of edges in a graph that leads from on vertex to another is called a(n)
   1. path
   2. connection
   3. simple cycle
   4. traversal
7. A path that does not pass through any vertex more than once is called a(n)
   1. simple path
   2. simple cycle
   3. cycle
   4. di-path
8. A path that begins and ends at the same vertex is called a(n)
   1. cycle
   2. simple path
   3. circle path
   4. acyclic path
9. A path in a directed graph is called a(n)
   1. directed path
   2. simple path
   3. cyclic path
   4. forced path
10. The number of edges in a path is the
    1. length
    2. edge count
    3. cycle count
    4. path count
11. A graph that has no cycles is
    1. acyclic
    2. simple
    3. disconnected
    4. directed
12. A graph that has a cost associated with the edges is called a(n)
    1. weighted graph
    2. digraph
    3. numbered graph
    4. acyclic graph
13. A graph that has a path between every pair of distinct vertices is called a(n)
    1. connected graph
    2. acyclic graph
    3. both a & b
    4. none of the above
14. A graph that has an edge between every pair of distinct vertices is called a(n)
    1. complete graph
    2. cyclic graph
    3. both a & b
    4. none of the above
15. Two vertices are _____ in an undirected graph if they are joined by an edge
    1. adjacent
    2. joined
    3. connected
    4. cyclic
16. Adjacent vertices are called
    1. neighbors
    2. siblings
    3. both a & b
    4. none of the above
17. If a directed graph has 5 vertices, how many edges can it have?
    1. 20
    2. 10
    3. 15
    4. 5
18. If a directed graph has n vertices, how many edges can it have?
    1. n x (n-1)
    2. n x (n-1) / 2
    3. n x (n+1)
    4. n x (n+1) /2
19. If an undirected graph has 5 vertices, how many edges can it have?
    1. 10
    2. 15
    3. 20
    4. 5
20. If a directed graph has n vertices, how many edges can it have?
    1. n x (n-1) / 2
    2. n x (n-1)
    3. n x (n+1) / 2
    4. n x (n+1)
21. A graph with relatively few edges is called
    1. sparse
    2. lean
    3. simple
    4. unpopulated
22. A graph with many edges is called
    1. dense
    2. sparse
    3. over-populated
    4. thick
23. A tree is a(n) _____ graph without cycles.
    1. connected
    2. disconnected
    3. weighted
    4. simple
24. A graph traversal begins at a vertex called the
    1. origin vertex
    2. root
    3. first node
    4. last node
25. Which graph traversal visits a vertex and then each of the vertex’s neighbors before advancing?
    1. breadth-first
    2. depth-first
    3. level-order
    4. cyclic order
26. Which graph traversal visits a vertex, then a neighbor of the vertex, a neighbor of the neighbor, and so on, advancing as far as possible from the original vertex?
    1. depth-first
    2. breadth-first
    3. level-order
    4. cyclic order
27. In a _____ order of the vertices in a directed graph without cycles, vertex a precedes vertex b whenever a directed edge exists from a to b.
    1. topological
    2. logical
    3. directed
    4. cyclic
28. Which operation(s) is(are) not performed on the ADT graph?
    1. add a vertex
    2. remove a vertex
    3. retrieve a vertex
    4. all of the above
29. Which terms describes the following graph?
    
    1. connected
    2. complete
    3. directed
    4. disconnected