Question 1

What is the performance behavior of a linked adjacency list for determining whether an edge exists between two vertices?

Accepted Answer

A)   constant time
B)   O( N 2)  where N is the number of vertices
C)   linear with the length of the list
D)   logarithmic with the total number of verticesE) C) and D)
F) A) and B)

Question 2

In a DAG, there are no cycles.

Accepted Answer

A) True 
 B)False

Question 3

In a digraph, each edge has a source vertex and destination vertex.

Accepted Answer

A) True 
 B)False

Question 4

In the pseudocode for the dfs function for partitioning the vertices in a graph into disjointed components, what is the missing pseudocode statement? dfs(graph, v, s) :
Mark v as visited
S.add(v) 
For each vertex, w, adjacent to v:
If w is unvisited:
<missing pseudocode>

Accepted Answer

A)   s.add(w) 
B)   dfs(graph, v, s) 
C)   s.add(v) 
D)   dfs(graph, w, s) E) C) and D)
F) A) and D)

Question 5

When you traverse a graph, there is always a single direct link from one item to any other item.

Accepted Answer

A) True 
 B)False

Question 6

Repeated application of finding the minimum spanning tree for all the components in a graph yields a minimum spanning forest for a graph.

Accepted Answer

A) True 
 B)False

Question 7

In a component with n vertices, how many edges are in the spanning tree?

Accepted Answer

A)   n
B)   n 2
C)   n + 1
D)   n - 1E) B) and D)
F) B) and C)

Question 8

Which of the following is true about an undirected graph?

Accepted Answer

A)   a graph-processing algorithm can move in only one direction along an edge that connects two vertices
B)   their edges do not indicate direction
C)   there can be multiple edges connecting any two vertices
D)   there is a source vertex and a destination vertexE) None of the above
F) C) and D)

Question 9

What is the output of Dijkstra's algorithm?

Accepted Answer

A)   a three-dimensional array
B)   a two-dimensional grid
C)   a source vertex
D)   the number of vertices in the graphE) B) and C)
F) B) and D)

Question 10

The smallest sum of edge weights between two vertices describes which of the following?

Accepted Answer

A)   the shortest path
B)   topological order
C)   topological sort
D)   maximum spanning treeE) A) and B)
F) A) and C)

Question 11

In a complete undirected graph consisting of 3 vertices, how many total adjacencies will there be?

Accepted Answer

A)   2
B)   6
C)   9
D)   4E) A) and D)
F) A) and C)

Question 12

A graph is a set of edges and vertices such that each edge connects two vertices.

Accepted Answer

A) True 
 B)False

Question 13

In graph terms, what is a path that begins and ends at the same vertex?

Accepted Answer

A)   a simple path
B)   an undirected path
C)   a cycle
D)   a directed pathE) A) and D)
F) C) and D)

Question 14

What is the minimum sum of all weights in a spanning tree of a weighted graph?

Accepted Answer

A)   spanning forest
B)   minimum spanning tree
C)   shortest path spanning tree
D)   topological spanning treeE) None of the above
F) B) and C)

Question 15

In the LinkedDirectedGraph class, which of the following methods is an iterator?

Accepted Answer

A)   incidentEdges
B)   getEdge
C)   containsEdge
D)   sizeEdgesE) All of the above
F) A) and D)

Question 16

What makes a graph complete?

Accepted Answer

A)   when there is an edge from each vertex to all other vertices
B)   when there is a path from each vertex to all other vertices
C)   when there is a path between at least half the vertices
D)   when there are two or more edges between verticesE) All of the above
F) B) and D)

Question 17

What can be described as the assignment of a rank to each vertex in a graph such that the edges go from lower-to higher-ranked vertices?

Accepted Answer

A)   directed acyclic graph
B)   sparse graph
C)   topological order
D)   shortest-path problemE) B) and C)
F) A) and B)

Question 18

If vertex Penguins can reach vertex Capitals and vertex Capitals can reach vertex Islanders, but none of them can reach vertices Sharks or Ducks, what can you say about the set of vertices Penguins, Capitals, and Islanders?

Accepted Answer

A)   the set is a connected component
B)   the set describes a complete graph
C)   the vertices in the set are all adjacent to each other
D)   the set describes a connected graphE) C) and D)
F) A) and C)

Question 19

An example of a process or model that can be graphed is the links between pages on the Internet.

Accepted Answer

A) True 
 B)False

Question 20

The depth-first traversal of a graph uses a queue as the collection in the generic algorithm.

Accepted Answer

A) True 
 B)False

Exam 12: Graphs

The smallest sum of edge weights between two vertices describes which of the following?

Correct AnswerverifiedShow Answer

What can be described as the assignment of a rank to each vertex in a graph such that the edges go from lower-to higher-ranked vertices?

Correct AnswerverifiedShow Answer

In a component with n vertices, how many edges are in the spanning tree?

Correct AnswerverifiedShow Answer

An example of a process or model that can be graphed is the links between pages on the Internet.

Correct AnswerverifiedShow Answer

In the LinkedDirectedGraph class, which of the following methods is an iterator?

Correct AnswerverifiedShow Answer

In the pseudocode for the dfs function for partitioning the vertices in a graph into disjointed components, what is the missing pseudocode statement? dfs(graph, v, s) : Mark v as visited S.add(v) For each vertex, w, adjacent to v: If w is unvisited: <missing pseudocode>

Correct AnswerverifiedShow Answer

The depth-first traversal of a graph uses a queue as the collection in the generic algorithm.

Correct AnswerverifiedShow Answer

What is the minimum sum of all weights in a spanning tree of a weighted graph?

Correct AnswerverifiedShow Answer

What is the performance behavior of a linked adjacency list for determining whether an edge exists between two vertices?

Correct AnswerverifiedShow Answer

In graph terms, what is a path that begins and ends at the same vertex?

Correct AnswerverifiedShow Answer

What makes a graph complete?

Correct AnswerverifiedShow Answer

A graph is a set of edges and vertices such that each edge connects two vertices.

Correct AnswerverifiedShow Answer

If vertex Penguins can reach vertex Capitals and vertex Capitals can reach vertex Islanders, but none of them can reach vertices Sharks or Ducks, what can you say about the set of vertices Penguins, Capitals, and Islanders?

Correct AnswerverifiedShow Answer

Which of the following is true about an undirected graph?

Correct AnswerverifiedShow Answer

What is the output of Dijkstra's algorithm?

Correct AnswerverifiedShow Answer

In a digraph, each edge has a source vertex and destination vertex.

Correct AnswerverifiedShow Answer

In a DAG, there are no cycles.

Correct AnswerverifiedShow Answer

Repeated application of finding the minimum spanning tree for all the components in a graph yields a minimum spanning forest for a graph.

Correct AnswerverifiedShow Answer

In a complete undirected graph consisting of 3 vertices, how many total adjacencies will there be?

Correct AnswerverifiedShow Answer

When you traverse a graph, there is always a single direct link from one item to any other item.

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

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

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified