Question 1

A(n) __________ is a data structure that consists of a set of vertices (or nodes) and a set of edges (relations) between the pairs of vertices.

Accepted Answer

graph

Question 2

A vertex is __________ to another vertex if there is an edge to it from that other vertex.

Accepted Answer

adjacent

Question 3

Suppose an undirected graph G consists of the following sets:
1) V = {New York, Islip, Philadelphia, Chicago, Seattle}
2) E = {{Islip, New York},{New York, Philadelphia},{Philadelphia, Chicago},
{Chicago, Islip},{Chicago, Seattle},{Chicago, New York},{Seattle, New York}}
Which of the following paths consisting of vertices in V represents a cycle?
A) Philadelphia -> Chicago -> Seattle -> New York
B) New York-> Philadelphia -> Chicago -> Seattle -> New York
C) Philadelphia -> Chicago -> Seattle -> New York -> Islip -> Chicago
D) New York-> Philadelphia -> Chicago -> New York -> Islip

Accepted Answer

CB) New York -> Philadelphia -> Chicago -> Seattle -> New York forms a cycle because it starts and ends at the same vertex (New York) without repeating any edges.C) Philadelphia -> Chicago -> Seattle -> New York -> Islip -> Chicago also forms a cycle because it starts and ends at the same vertex (Chicago) without repeating any edges.

Question 4

A graph that is unconnected has no connected components.

Accepted Answer

A graph that is unconnected has at least two connected components, as it is not entirely connected.

Question 5

Any graph that is connected and contains no cycles can be viewed as a(n) __________ by picking one of its vertices (nodes) as the root.

Accepted Answer

The answer of Any graph that is connected and contains...

Question 6

The term __________ refers to visiting all the vertices in a graph.
A) traversal
B) disconnection
C) cycle
D) path

Accepted Answer

Traversal is the correct term for visiting all the vertices in a graph. This process involves going through the graph to visit each vertex at least once.

Question 7

We can represent all the vertices of a graph (elements of the set V) by integers from 0 up to, but not including, __________.
A) |V| - 2
B) |V| - 1
C) |V|
D) V

Accepted Answer

The vertices of a graph can be represented by integers starting from 0 up to, but not including, the total number of vertices, which is |V|. This means we have integers 0 through |V|-1, totaling |V| different integers.

Question 8

Complete the definition of an operator== member function for the Edge class. The function compares the source and dest fields only to determine equivalence between two Edge objects. 
bool Edge::operator==(const Edge& other)
{
__________
}

Accepted Answer

The answer of Complete the definition of an operator== member...

Question 9

A(n) adjacency __________ uses a two-dimensional array to represent a graph.
A) list
B) matrix
C) stack
D) queue

Accepted Answer

An adjacency matrix uses a two-dimensional array to represent a graph, where each cell [i][j] indicates the presence or absence of an edge from vertex i to vertex j.

Question 10

A dense graph is one in which |E| is close to but less than __________. A) |V| B) |V|² C) |V|³ D) |V|⁴

Accepted Answer

In a dense graph, the number of edges |E| is close to the maximum number of edges possible, which is |V|^2 for a directed graph without self-loops (|V| choose 2 for an undirected graph), where |V| is the number of vertices.

Question 11

If a graph is dense, the adjacency matrix representation is best, and if a graph is sparse, the adjacency list representation is best.

Accepted Answer

The adjacency matrix representation is more space-efficient for dense graphs because it uses a fixed amount of memory, while the adjacency list representation is more space-efficient for sparse graphs because it only stores the existing edges, thus saving memory.

Question 12

An adjacency list uses less (more) storage when less than (more than) __________ percent of the adjacency matrix would be filled.

Accepted Answer

The answer of An adjacency list uses less (more) storage...

Question 13

The breadth-first search algorithm stores identified vertices in a __________.
A) queue
B) stack
C) binary tree
D) B tree

Accepted Answer

The breadth-first search algorithm uses a queue to store identified vertices. This allows the algorithm to explore the graph level by level, starting from the source node.

Question 14

Suppose G is an undirected graph consisting of the following sets:
1) V = {0, 1, 2, 3, 4, 5, 6}
2) E = {{0,1},{0,2}, {1,2},{1,3}, {1,4},{2, 5},{2,6}}
Starting at vertex 0, a possible visit sequence representing a breadth-first search of G is _________.
A) 0 1 3 4 2 5 6
B) 0 2 6 5 1 4 3
C) 0 1 2 3 4 5 6
D) 0 3 4 5 6 1 2

Accepted Answer

In a breadth-first search (BFS) starting from vertex 0, the algorithm visits all immediate neighbors of 0 first, which are 1 and 2, then proceeds to visit their unvisited neighbors in order. The sequence 0 1 2 3 4 5 6 correctly follows the BFS order, visiting all neighbors of 0, then all neighbors of these neighbors, and so on.

Question 15

The breadth-first search algorithm is O(__________).

Accepted Answer

The answer of The breadth-first search algorithm is O(__________)....

Question 16

A(n) __________ search algorithm visits an initial vertex, fully explores a single branch and then backtracks to a new vertex (if one exists).

Accepted Answer

The answer of A(n) __________ search algorithm visits an initial...

Question 17

Back edges that connect a vertex with its ancestors are part of a depth-first search tree.

Accepted Answer

Back edges in a depth-first search (DFS) tree connect a vertex to one of its ancestors, but they are not part of the DFS tree itself; they indicate cycles in the graph and are part of the graph's cycle structure, not the spanning tree structure created by DFS.

Question 18

Excluding the coloring step, the depth-first search algorithm is O(__________). A) |E| B) |E|² C) |E||V| D) |V|

Accepted Answer

The answer of Excluding the coloring step, the depth-first search...

Question 19

The collection of trees that may be generated by a depth-first search is called a(n) __________.

Accepted Answer

The answer of The collection of trees that may be...

Question 20

A(n) __________ sort of the vertices of a DAG (directed acyclic graph) is an ordering of the vertices such that if (u, v) is an edge, then u appears before v.

Accepted Answer

The answer of A(n) __________ sort of the vertices of...

Quiz 13: Graphs

A(n) __________ is a data structure that consists of a set of vertices (or nodes) and a set of edges (relations) between the pairs of vertices.

A vertex is __________ to another vertex if there is an edge to it from that other vertex.

A graph that is unconnected has no connected components.

Any graph that is connected and contains no cycles can be viewed as a(n) __________ by picking one of its vertices (nodes) as the root.

The term __________ refers to visiting all the vertices in a graph.

We can represent all the vertices of a graph (elements of the set V) by integers from 0 up to, but not including, __________.

Complete the definition of an operator== member function for the Edge class. The function compares the source and dest fields only to determine equivalence between two Edge objects. bool Edge::operator==(const Edge& other) { __________ }

A(n) adjacency __________ uses a two-dimensional array to represent a graph.

A dense graph is one in which |E| is close to but less than __________.