Deck 10: Graphs

Question 1

For an undirected graph, symmetric entries are required.

Answer 1

True

Question 2

In a breadth first search, the nodes that are lower down in the picked-up graph are visited before nodes that are higher up in the graph.

Answer 2

False

Question 3

Edges can be represented by an array of lists called weighted lists.

Answer 3

False

Question 4

Any graph that is connected and contains no cycles can be viewed as a tree by picking one of its vertices as the root.

Question 5

If the set of vertices is empty, the set of edges must also be empty.

Question 6

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

Question 7

____________________ represent paths or connections between vertices.

Question 8

The edges of a graph are ____________________ if the existence of an edge from A to B does not necessarily guarantee that there is a path in both directions.

Question 9

A graph that contains undirected edges is known as a(n) ____________________ graph.

Question 10

Directed ____________________ are represented as lines with an arrow on one end.

Question 11

The edges of a graph may have values associated with them known as their ____________________.

Question 12

A graph with weighted edges is known as a(n) ____________________ graph.

Question 13

A(n) ____________________ is a sequence of vertices in which each successive vertex is adjacent to its predecessor.

Question 14

An undirected graph is called a(n) ____________________ if there is a path from every vertex to every other vertex.

Question 15

The ____________________ matrix uses a two-dimensional array to represent the graph.

Question 16

A(n) ____ is one in which |E| is close to but less than |V|².

A) dense graph
B) sparse graph
C) adjacency matrix
D) matrix graph

Question 17

A(n) ___ is one in which |E| is much less than |V|².

A) dense graph
B) matrix graph
C) adjacency graph
D) sparse graph

Question 18

In a(n) ____ search, we visit the start node first, then all nodes that are adjacent to it next, then all nodes that can be reached by a path from the start node containing two edges, three edges, and so on.

A) depth-first
B) binary
C) breadth-first
D) linear

Question 19

The following is an algorithm for a(n) ____.
Take an arbitrary start vertex, mark it identified and place it in a queue.
While the queue is not empty
Take a vertex, u, out of the queue and visit u.
For all vertices, v, adjacent to this vertex u
If v has not been identified or visited
Mark it identified
Insert vertex v into the queue.
We are now finished visiting u.

A) depth-first search
B) linear search
C) breadth-first search
D) binary search

Question 20

The following is an algorithm for a(n) ____.
Mark the current vertex, u, visited and enter it in the discovery order list
For each vertex, v, adjacent to the current vertex, u
If v has not been visited
Set parent of v to u.
Recursively apply this algorithm starting at v.
Mark u finished and enter u into the finish order list.

A) breadth-first search
B) linear search
C) binary search
D) depth-first search

Question 21

A(n) ____ is a subset of the edges of a graph such that there is only one edge between each vertex, and all of the vertices are connected.

A) adjacency matrix
B) spanning tree
C) maze
D) iterator

Question 22

The cost of a(n) ____ is the sum of the weights of the edges.

A) spanning tree
B) depth-first search
C) adjacency matrix
D) breadth-first search

Question 23

The following algorithm is known as ____.
Initialize S with the start vertex, s, and V-S with the remaining vertices.
For all v in V-S

A) Dijkstra's algorithm
B) Kim's algorithm
C) Prim's algorithm
D) Topological sort algorithm

Question 24

|V| means the ____ of V.

A) cardinality
B) edge
C) matrix
D) graph

Question 25

The ____ of a graph is the ratio of |E| to |V|².

A) cardinality
B) density
C) edge
D) vertex