## Test Prep Plan - Take a practice test

# Graph Data Structures Chapter Exam

Choose your answers to the questions and click 'Next' to see the next set of questions. You can skip questions if you would like and come back to them later with the "Go To First Skipped Question" button. When you have completed the practice exam, a green submit button will appear. Click it to see your results. Good luck!

### Page 1

#### Question 1 1. What is the shortest path problem?

####
Question 2
2.
Suppose we are using Dijkstra's algorithm to find the shortest path from *A* to *D* in the graph shown. The first step is to mark the ending vertex, *D*, with a 0, label it as current and put a circle around it as shown. In the next step, we identify *E* and *C* as vertices that are connected by an edge to the current vertex. What would we mark vertex *E* and vertex *C* with, and what vertex would be the next current vertex in the algorithm?

#### Question 3 3. What do we use Dijkstra's algorithm for?

#### Question 4 4. Which of the following does NOT describe a step in Dijkstra's algorithm?

####
Question 5
5.
Assume the following graph described in python code:

graph = {'A': [('B', 2), ('C', 3)],

'B': [('A', 2), ('C', 2), ('D', 8)],

'C': [('A', 3), ('B', 2), ('D', 4)],

'D': (['B', 8), ('C', 4)}

After a Dijkstra execution, which are the values of the **pred** array? (Let A be the starting node.)

graph = {'A': [('B', 2), ('C', 3)],

'B': [('A', 2), ('C', 2), ('D', 8)],

'C': [('A', 3), ('B', 2), ('D', 4)],

'D': (['B', 8), ('C', 4)}

**pred**array? (Let A be the starting node.)

### Page 2

####
Question 6
6.
Assume the following graph described in python code:

graph = {'A': [('B', 2), ('C', 3)],

'B': [('A', 2), ('C', 2), ('D', 8)],

'C': [('A', 3), ('B', 2), ('D', 4)],

'D': [('B', 8), ('C', 4)]}

After a Dijkstra execution, which are the values of the **dist** array? (Let A be the starting node.)

graph = {'A': [('B', 2), ('C', 3)],

'B': [('A', 2), ('C', 2), ('D', 8)],

'C': [('A', 3), ('B', 2), ('D', 4)],

'D': [('B', 8), ('C', 4)]}

**dist**array? (Let A be the starting node.)

#### Question 7 7. The Dijkstra algorithm only finds the shortest path between:

#### Question 8 8. The following graph contains a negative edge. For this reason, the Dijkstra Algorithm will not compute the correct shortest path in one case. In which path would this error occur? (Let A be the source node)

#### Question 9 9. In the graph shown, the vertices represent cities, and the edges represent flights between those cities. The weights of the edges represent the cost of the flights, in hundreds of dollars. Based on this, what two cities are the cheapest to fly between, and what is the cost?

#### Question 10 10. Suppose that a dating service is determining couples that would make a good match. In the graph shown, two sets of clients are represented with vertices, and the edges between the vertices indicate that the clients make a good match. Based on the graph, how many possible matches are there for Erin?

### Page 3

#### Question 11 11. Which graph in discrete mathematics has a path of edges between every pair of vertices in the graph?

#### Question 12 12. Which of the following statements is NOT true?

#### Question 13 13. How many bridges does this graph have?

#### Question 14 14. How many vertices does this graph have?

#### Question 15 15. What is the shortest path length you can use to get from point 6 to point 2?

### Page 4

#### Question 16 16. How many edges does this graph have?

#### Question 17 17. Which type of graph is this?

#### Question 18 18. A graph is said to be _____ if the number of edges is closer to the minimal number of edges.

#### Question 19 19. The edges in directed graphs are _____?

#### Question 20 20. Which type of graph is the following?

### Page 5

#### Question 21 21. Which of the following will get you from point 3 to point 5?

#### Question 22 22. Which of the following describes a loop?

#### Question 23 23. How many vertices are in this graph?

#### Question 24 24. How many edges does this graph have?

####
Question 25
25.
Suppose we just performed Dijkstra's algorithm on the graph shown to find the shortest path from vertex *A* to vertex *C*, so all of the vertices have been visited as indicated with the *X* ' s, including the starting vertex of *A*. Based on the graph and all of its final marks, what is the length of the shortest path from vertex *A* to vertex *C*?

### Page 6

#### Question 26 26. The Dijkstra algorithm will fail if:

#### Question 27 27. What is the difference between a directed and an undirected graph?

#### Question 28 28. How many components does this graph have?

#### Question 29 29. Graphs come under which category of data structures?

#### Question 30 30. How many vertices are in this graph?

#### Graph Data Structures Chapter Exam Instructions

Choose your answers to the questions and click 'Next' to see the next set of questions. You can skip questions if you would like and come back to them later with the "Go To First Skipped Question" button. When you have completed the practice exam, a green submit button will appear. Click it to see your results. Good luck!