Sample Data Structures Questions
Chapter 15
Graphs

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, 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

  1. 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.

  2. Draw an undirected graph with five edges and four vertices. The vertices should be called v1, v2, v3 and v4--and 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

  3. 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  |
    

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

  5. What are the benefits of using an external iterator as opposed to an internal iterator?

    Short Answers
    Section 15.3-15.4
    Graph Traversals
    and Path Algorithms

  6. 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?

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

  8. Consider this graph:
                        v0 <------- v2
                       / \
                      /   \
             -> v1 <-/     \-> v4
            /    \     
           /      \
          /        \->v3 -------> v5
         /            /
        /            /
       v6 <---------/
    
    In what order are the vertices visited for a depth-first search that starts at v0? In what order are the vertices visited for a breadth-first search that starts at v0?

Multiple Choice

    Multiple Choice
    Section 15.1
    Graph Definitions

  1. Which of the following statements is true?

  2. 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?

  3. Why is the state graph for tic-tac-toe a directed graph rather than an undirected graph?

  4. A simple graph has no loops. What other property must a simple graph have?

  5. 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?

    Multiple Choice
    Section 15.2
    Graph Implementations

  6. If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix?

  7. How many linked lists are used to represent a graph with n nodes and m edges, when using an edge list representation,

  8. How are loops represented in an edge-list representation of a graph?

    Which graph representation allows the most efficient determination of the existence of a particular edge in a graph?

  9. 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.)

    Multiple Choice
    Section 15.3-15.4
    Graph Traversals
    and Path Algorithms

  10. What graph traversal algorithm uses a queue to keep track of vertices which need to be processed?


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 Addison-Wesley Computer and Engineering Publishing Group