Question 1

In a complete undirected graph with five vertices how many cells will contain a value of 1 in an adjacency matrix?

Accepted Answer

A)   15
B)   10
C)   25
D)   125E) A) and B)
F) A) and C)

Question 2

Removing a vertex also entails removing any edges connecting it to other vertices.

Accepted Answer

A) True 
 B)False

Question 3

In a complete graph with six vertices, the degree of a vertex is five.

Accepted Answer

A) True 
 B)False

Question 4

In an adjacency matrix, a 1 is used to represent an edge between two vertices.

Accepted Answer

A) True 
 B)False

Question 5

A a depth-first traversal cannot be implemented recursively.

Accepted Answer

A) True 
 B)False

Question 6

Which of the following is NOT true after the initialization step in Dijkstra's algorithm?

Accepted Answer

A)   the cells in the included list are all False, except for the cell that corresponds to the row of the source vertex in the results grid
B)   the distance in a row's distance cell is either 0, infinity, or a positive number
C)   the shortest path from the source to a vertex is found and the vertex's cell is marked in the included list
D)   the vertex in a row's parent cell is either the source vertex or undefinedE) B) and C)
F) A) and D)

Question 7

The adjacency matrix representation of a graph stores graph information in an array of lists.

Accepted Answer

A) True 
 B)False

Question 8

To find the shortest path, you can use a wighted graph and sum the edge of the weights between two vertices.

Accepted Answer

A) True 
 B)False  True

Question 9

Which of the following is true about graphs?

Accepted Answer

A)   graphs consist of vertices and nodes
B)   the edges between vertices are always labeled
C)   an adjacency is when one vertex has a path to another vertex
D)   the length of a path is the number of edges on the pathE) None of the above
F) A) and B)

Question 10

Which of the following is NOT a process for which a graph can serve as a model?

Accepted Answer

A)   a road map between hotels a town
B)   a line at a movie theater
C)   the paths that data can travel in a network
D)   the routes between rooms in a buildingE) B) and D)
F) All of the above B

Question 11

In the implementation of a graph, the len function returns the number of the graph's vertices.

Accepted Answer

A) True 
 B)False

Question 12

The adjacency list supports finding all the vertices adjacent to a given vertex more efficiently than the adjacency matrix.

Accepted Answer

A) True 
 B)False

Question 13

A simple path in a graph is one in which a path passes through the same vertex at least twice.

Accepted Answer

A) True 
 B)False

Question 14

In the following code to add an edge in the LinkedDirectedGraph class, what is the missing code? def addEdge(self, fromLabel, toLabel, weight) :
FromVertex = self.getVertex(fromLabel)

FromVertex.addEdgeTo(toVertex, weight) 
Self.edgeCount += 1

Accepted Answer

A)   self.getVertex(toLabel)  = fromVertex
B)   fromVertex.addEdgeTo(fromVertex, weight) 
C)   self.weight += 1
D)   toVertex = self.getVertex(toLabel) E) C) and D)
F) A) and B)

Question 15

A topological order assigns a rank to each edge such that the vertices go from lower-to higher-ranked edges.

Accepted Answer

A) True 
 B)False

Question 16

Which term best describes a neighbor?

Accepted Answer

A)   a path exist between vertices
B)   a vertex is reachable from another vertex
C)   two vertices have consecutive labels
D)   two vertices are adjacentE) A) and C)
F) None of the above

Question 17

In a connected graph, there must be an edge from each vertex to every other vertex.

Accepted Answer

A) True 
 B)False

Question 18

A graph has a single length attribute, similar to the lists, queues, and stacks.

Accepted Answer

A) True 
 B)False

Question 19

What are edges called that emanate from a given source vertex?

Accepted Answer

A)   incident edges
B)   directed edges
C)   destination edges
D)   cyclical edgesE) None of the above
F) B) and D) A

Question 20

A spanning tree has the fewest number of edges possible while still retaining a connection between all the vertices in the component.

Accepted Answer

A) True 
 B)False

Exam 12: Graphs

In a complete undirected graph with five vertices how many cells will contain a value of 1 in an adjacency matrix?

Correct AnswerverifiedShow Answer

Removing a vertex also entails removing any edges connecting it to other vertices.

Correct AnswerverifiedShow Answer

In a complete graph with six vertices, the degree of a vertex is five.

Correct AnswerverifiedShow Answer

In an adjacency matrix, a 1 is used to represent an edge between two vertices.

Correct AnswerverifiedShow Answer

A a depth-first traversal cannot be implemented recursively.

Correct AnswerverifiedShow Answer

Which of the following is NOT true after the initialization step in Dijkstra's algorithm?

Correct AnswerverifiedShow Answer

The adjacency matrix representation of a graph stores graph information in an array of lists.

Correct AnswerverifiedShow Answer

To find the shortest path, you can use a wighted graph and sum the edge of the weights between two vertices.

Correct AnswerverifiedTrue

Which of the following is true about graphs?

Correct AnswerverifiedShow Answer

Which of the following is NOT a process for which a graph can serve as a model?

Correct AnswerverifiedB

In the implementation of a graph, the len function returns the number of the graph's vertices.

Correct AnswerverifiedShow Answer

The adjacency list supports finding all the vertices adjacent to a given vertex more efficiently than the adjacency matrix.

Correct AnswerverifiedShow Answer

A simple path in a graph is one in which a path passes through the same vertex at least twice.

Correct AnswerverifiedShow Answer

In the following code to add an edge in the LinkedDirectedGraph class, what is the missing code? def addEdge(self, fromLabel, toLabel, weight) : FromVertex = self.getVertex(fromLabel) < missing code > FromVertex.addEdgeTo(toVertex, weight) Self.edgeCount += 1

Correct AnswerverifiedShow Answer

A topological order assigns a rank to each edge such that the vertices go from lower-to higher-ranked edges.

Correct AnswerverifiedShow Answer

Which term best describes a neighbor?

Correct AnswerverifiedShow Answer

In a connected graph, there must be an edge from each vertex to every other vertex.

Correct AnswerverifiedShow Answer

A graph has a single length attribute, similar to the lists, queues, and stacks.

Correct AnswerverifiedShow Answer

What are edges called that emanate from a given source vertex?

Correct AnswerverifiedA

A spanning tree has the fewest number of edges possible while still retaining a connection between all the vertices in the component.

Correct AnswerverifiedShow Answer

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
True

Correct Answer
verified

Correct Answer
verified
B

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
A

Correct Answer
verified