Exam Prep - Graph Implementations Chapter.30

Chapter 30 - Graph Implementations

True/False (10)

1. An undirected graph is symmetric.
2. In an unweighted graph represented by an adjacency matrix, you cannot use boolean values.
3. An adjacency matrix occupies a fixed amount of space dependent on the number of edges in the graph.
4. In an adjacency list, space is not reserved for edges that do not exist.
5. An adjacency matrix uses less memory than an adjacency list.
6. For a dense graph, using an adjacency matrix to represent the graph is a better choice.
7. Regardless of how you implement a graph, you need a container such as a dictionary for the graph’s vertices.
8. Using an adjacency list, you might need to search the entire list to determine if an edge exists between any two given vertices.
9. An adjacency matrix uses less space for a sparse graph than an adjacency list.
10. Using an adjacency matrix, you can use an edge weight of infinity to represent that there is no edge between any two given vertices.

Short Answer (5)

1. Fill in the adjacency matrix for the following graph.
   

1. Fill in the adjacency matrix for the following graph.
   
   

1. Explain the steps to add an edge to the ADT DirectedGraph.
2. In the ADT DirectedGraph, what is the purpose of the data fields visited, previousVertex and cost?
3. Explain why we use an inner class Edge even if there is no weight associated with edges.

Multiple Choice (19) 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 common implementation of a graph that uses a two dimensional array to represent the graph’s edges is called a(n)
   1. adjacency matrix
   2. graph array
   3. adjacency array
   4. adjacency list
2. A common implementation of a graph that uses a list to represent the graph’s edges is called a(n)
   1. adjacency list
   2. adjacency matrix
   3. graph list
   4. array list
3. In an adjacency matrix, each row and each column corresponds to
   1. a vertex in the graph
   2. an edge in the graph
   3. both a & b
   4. none of the above
4. What type of values are typically stores in unweighted graphs?
   1. boolean
   2. integers
   3. 0 and 1
   4. strings
5. The adjacency matrix for an undirected graph is
   1. symmetric
   2. asymmetric
   3. weighted
   4. irregular
6. In a graph represented by an adjacency matrix, you can determine if an edge exists between any two given vertices in _____ operations.
   1. O(1)
   2. O(n)
   3. O(log n)
   4. O(n2)
7. In a graph represented by an adjacency matrix, you can find all the neighbors of a given vertices in _____ operations.
   1. O(n)
   2. O(1)
   3. O(log n)
   4. O(n2)
8. An adjacency matrix occupies
   1. a fixed amount of space dependent on the number of vertices in the graph
   2. a fixed amount of space dependent on the number of edges in the graph
   3. a variable amount of space dependent on the number of vertices in the graph
   4. a variable amount of space dependent on the number of edges in the graph
9. For a sparse graph, an adjacency list uses _____ memory than an adjacency matrix.
   1. less
   2. more
   3. the same amount of
   4. none of the above
10. Each vertex in a graph of n vertices can be the origin of at most _____ edges.
    1. n – 1
    2. n + 1
    3. n
    4. 1
11. In the interface VertexInterface, the connect methods
    1. connect two vertices
    2. connect two edges
    3. connect two graphs
    4. none of the above
12. In the interface VertexInterface, the connect methods require _____ operations.
    1. O(n)
    2. O(1)
    3. O(log n)
    4. O(n2)
13. In the ADT graph, the method addVertex has efficiency
    1. O(n)
    2. O(log n)
    3. O(n²)
    4. O(1)
14. In the ADT graph, the method addEdge has efficiency
    1. O(n)
    2. O(log n)
    3. O(n²)
    4. O(1)
15. In the ADT graph, the method hasEdge has efficiency
    1. O(n)
    2. O(log n)
    3. O(n²)
    4. O(1)
16. In the ADT graph, the method isEmpty has efficiency
    1. O(1)
    2. O(log n)
    3. O(n²)
    4. O(n)
17. In the ADT graph, the method getNumberOfVertices has efficiency
    1. O(1)
    2. O(log n)
    3. O(n²)
    4. O(n)
18. In the ADT graph, the method getNumberOfEdges has efficiency
    1. O(1)
    2. O(log n)
    3. O(n²)
    4. O(n)
19. In the ADT graph, the method clear has efficiency
    1. O(1)
    2. O(log n)
    3. O(n²)
    4. O(n)