Sample Data Structures Questions
Chapter 15
Graphs
Data Structures and Other Objects Using C++
by
Michael Main
and
Walter Savitch
Second Edition ISBN 0201702975, Softcover, 816 pages, 2000
The Purpose of These Questions
These are typical exam questions from Chapter 15 of the textbook. These
exact questions might not be on your exam, but if you research and find
the right answers to these questions, that should be good preparation
for a real exam. (It's also possible that some of this material was
not covered in your class.) At the moment there are
8 short answer questions
and
10 multiple choice questions
in this file.
Short Answers
Short Answers Section 15.1 Graph Definitions


Draw a directed graph with five vertices and seven edges.
Exactly one of the edges should be a loop, and do not have any
multiple edges.

Draw an undirected graph with five edges and four vertices.
The vertices should be called v1, v2, v3 and v4and there must
be a path of length three from v1 to v4. Draw a squiggly line
along this path from v1 to v4.
Short Answers Section 15.2 Graph Implementations


Draw the directed graph that corresponds to this adjacency matrix:
0 1 2 3
0  true false true false 
1  true false false false 
2  false false false true 
3  true false true false 

Draw the edge lists that correspond to the graph from the previous
question.

What are the benefits of using an external iterator as opposed to
an internal iterator?
Short Answers Section 15.315.4 Graph Traversals and Path Algorithms


How may Djikstra's algorithm be modified to determine if it is
possible to get from a given vertex to all other vertices in the
graph?

In Djikstra's shortest path algorithm, what technique is used to
choose the next vertex to process?

Consider this graph:
v0 < v2
/ \
/ \
> v1 </ \> v4
/ \
/ \
/ \>v3 > v5
/ /
/ /
v6 </
In what order are the vertices visited for a depthfirst search that
starts at v0? In what order are the vertices visited for a
breadthfirst search that starts at v0?
Multiple Choice
Multiple Choice Section 15.1 Graph Definitions


Which of the following statements is true?
 A. A graph can drawn on paper in only one way.
 B. Graph vertices may be linked in any manner.
 C. A graph must have at least one vertex.
 D. A graph must have at least one edge.

Suppose you have a game with
5 coins in a row and each coin can be heads or
tails. What number of vertices might you expect to find in the state
graph?

Why is the state graph for tictactoe a directed graph rather
than an undirected graph?
 A. Once a move is made, it cannot be unmade.
 B. There is an odd number of vertices.
 C. There is an odd number of edges.
 D. There is more than one player in the game.

A simple graph has no loops. What other property must a simple
graph have?
 A. It must be directed.
 B. It must be undirected.
 C. It must have at least one vertex.
 D. It must have no multiple edges.

Suppose you have a directed graph representing all the flights that
an airline flies. What algorithm might be used to find the best sequence
of connections
from one city to another?
 A. Breadth first search.
 B. Depth first search.
 C. A cyclefinding algorithm.
 D. A shortestpath algorithm.
Multiple Choice Section 15.2 Graph Implementations


If G is an directed graph with 20 vertices, how many boolean
values will be needed to represent G using an adjacency matrix?
 A. 20
 B. 40
 C. 200
 D. 400

How many linked lists are used to represent a graph with n nodes
and m edges, when using an edge list representation,
 A. m
 B. n
 C. m + n
 D. m*n

How are loops represented in an edgelist representation of a graph?
 A. A vertex will be on its own edgelist.
 B. The edgelist will be a circular linked list.
 C. The edgelist will be empty for that particular vertex.
 D. The edgelist will be full for that particular vertex.
Which graph representation allows the most efficient determination
of the existence of a particular edge in a graph?
 A. An adjacency matrix.
 B. Edge lists.

What is the expected number of operations needed to loop through all
the edges terminating at a particular vertex given an adjacency
matrix representation of the graph? (Assume n vertices are in the
graph and m edges terminate at the desired node.)
 A. O(m)
 B. O(n)
 C. O(m²)
 D. O(n²)
Multiple Choice Section 15.315.4 Graph Traversals and Path Algorithms


What graph traversal algorithm uses a queue to keep track of
vertices which need to be processed?
 A. Breadthfirst search.
 B. Depthfirst search.
Data Structures and Other Objects Using C++
Michael Main
(main@colorado.edu)
and
Walter Savitch
(wsavitch@ucsd.edu)
Thank you for visiting
http://www.cs.colorado.edu/~main/questions/chap15q.html
Copyright © 2000
AddisonWesley Computer and Engineering Publishing Group