TRUE/FALSE 10 points

An undirected graph is symmetric.

Answer:

In a graph represented by an adjacency matrix, you cannot use boolean values for an unweighted graph.

Answer:

An adjacency matrix occupies a fixed amount of space dependent on the number of edges in the graph.

Answer:

In an adjacency list, space is not reserved for edges that do not exist.

Answer:

An adjacency matrix uses less memory than an adjacency list.

Answer:

For a dense graph, using an adjacency matrix to represent the graph is a better choice.

Answer:

Regardless of how you implement a graph, you need a container such as a dictionary for the graphs vertices.

Answer:

Using an adjacency list, you need to search the entire list to determine if an edge exists between any two given vertices.

Answer:

An adjacency matrix uses less space for a sparse graph than an adjacency list.

Answer:

Using an adjacency matrix, you can use an edge weight of infinity to represent that there is no edge between any two given vertices.

Explain the steps to add an edge to the ADT DirectedGraph.

Answer:

In the ADT DirectedGraph, what is the purpose of the data fields visited, previousVertex and cost?

Answer:

Explain why we use an inner class Edge even if there is no weight associated with edges.

Answer:

Multiple Choice (40 points)

1. A common implementation of a graph that uses a two dimensional array to represent the graphs edges is called a(n)

adjacency matrix

graph array

adjacency array

adjacency list

2. A common implementation of a graph that uses a list to represent the graphs edges is called a(n)

adjacency list

adjacency matrix

graph list

array list

3. In an adjacency matrix, each row and each column corresponds to

a vertex in the graph

an edge in the graph

both a & b

none of the above

4. The adjacency matrix for an undirected graph is

symmetric

asymmetric

weighted

irregular

5. In a graph represented by an adjacency matrix, you can determine if an edge exists between any two given vertices in _____ operations.

O(1)

O(n)

O(log n)

O(n²)

6. In a graph represented by an adjacency matrix, you can find all the neighbors of a given vertices in _____ operations.

O(n)

O(1)

O(log n)

O(n²)

7. An adjacency matrix occupies

a fixed amount of space dependent on the number of vertices in the graph

a fixed amount of space dependent on the number of edges in the graph

a variable amount of space dependent on the number of vertices in the graph

a variable amount of space dependent on the number of edges in the graph

8. For a sparse graph, an adjacency lists uses _____ memory than an adjacency matrix.

less

more

the same amount of

none of the above