Back to Subject

Unit 6: Graphs - Practice Quiz

CSE205 — Data Structures And Algorithms 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is graph traversal?

Graph traversal Easy
A. Deleting every edge from a graph
B. Visiting vertices and edges in a graph
C. Sorting all graph vertices alphabetically
D. Counting only the graph's connected components

2 Which data structure is commonly used to record vertices that have already been visited during graph traversal?

Graph traversal Easy
A. Sorting table
B. Priority queue
C. Hash calculator
D. Visited array

3 What is the main purpose of marking a vertex as visited?

Graph traversal Easy
A. To change it into a root vertex
B. To avoid processing it repeatedly
C. To increase its edge weight
D. To remove it from the graph

4 Which data structure is typically used by Breadth-First Search (BFS)?

Breadth-first search Easy
A. Queue
B. Heap
C. Stack
D. Hash table

5 In an unweighted graph, BFS visits vertices primarily according to their:

Breadth-first search Easy
A. Alphabetical vertex labels
B. Distance from the source
C. Order in the input file
D. Number of outgoing edges

6 What does BFS find efficiently in an unweighted graph?

Breadth-first search Easy
A. Minimum spanning cycles
B. All negative-weight edges
C. Largest edge weights
D. Shortest paths by edge count

7 Which data structure is commonly used by Depth-First Search (DFS)?

Depth-first search Easy
A. Queue
B. Priority queue
C. Stack
D. Circular buffer

8 How does DFS generally explore a graph?

Depth-first search Easy
A. It examines vertices in sorted order
B. It visits all neighbors at once
C. It always selects the heaviest edge
D. It follows one path before backtracking

9 Which task can DFS help perform in a directed graph?

Depth-first search Easy
A. Adding weights to edges
B. Detecting cycles
C. Removing isolated vertices
D. Making every edge undirected

10 What is the shortest path between two vertices?

Shortest path algorithms Easy
A. A path containing the most edges
B. A path containing every vertex
C. A path with minimum total cost
D. A path with maximum total cost

11 What does the distance value for a source vertex usually start as?

Shortest path algorithms Easy
A. Zero
B. Infinity
C. One
D. The number of vertices

12 What value is commonly assigned initially to vertices that are unreachable from the source?

Shortest path algorithms Easy
A. Negative one
B. Zero
C. Infinity
D. The edge count

13 Dijkstra's algorithm is designed to find shortest paths from:

Dijkstra's algorithm Easy
A. One destination only
B. Every edge independently
C. A set of disconnected edges
D. One source vertex

14 What restriction applies to edge weights in Dijkstra's algorithm?

Dijkstra's algorithm Easy
A. They must all equal zero
B. They must be nonnegative
C. They must be identical
D. They must all be negative

15 Which vertex does Dijkstra's algorithm typically select next?

Dijkstra's algorithm Easy
A. The vertex with the most neighbors
B. The visited vertex with largest degree
C. The unvisited vertex with largest weight
D. The unvisited vertex with smallest distance

16 Which type of edge weight can Bellman-Ford handle that Dijkstra's algorithm cannot generally handle?

Bellman-Ford algorithm Easy
A. Equal edge weight
B. Negative edge weight
C. Positive edge weight
D. Zero edge weight

17 What important problem can Bellman-Ford detect?

Bellman-Ford algorithm Easy
A. Duplicate vertex names
B. Unsorted adjacency lists
C. Negative-weight cycles
D. Disconnected input files

18 How many times does Bellman-Ford normally relax all edges in a graph with vertices?

Bellman-Ford algorithm Easy
A. times
B. times
C. times
D. times

19 What type of shortest-path problem does Floyd-Warshall solve?

Floyd-Warshall algorithm Easy
A. Maximum spanning paths
B. All-pairs shortest paths
C. Single-source paths only
D. Single-edge shortest paths

20 Which technique is used by the Floyd-Warshall algorithm?

Floyd-Warshall algorithm Easy
A. Randomized sampling
B. Dynamic programming
C. Hashing
D. Binary searching

21 A graph with vertices and edges is represented using adjacency lists. What is the worst-case time complexity of traversing the entire graph using either BFS or DFS?

Graph traversal Medium
A.
B.
C.
D.

22 A graph is disconnected, and a traversal starts from only one vertex. What modification is required to guarantee that every vertex is visited?

Graph traversal Medium
A. Sort all vertices by their degrees
B. Convert the graph into a complete graph
C. Repeat the traversal from every edge
D. Start a traversal from each unvisited vertex

23 Consider an undirected graph with adjacency lists , , and . BFS starts at , and neighbors are processed in the listed order. What is the queue immediately after has been processed?

Breadth-first search Medium
A.
B.
C.
D.

24 In an unweighted graph, BFS begins at vertex . Vertex is first discovered while processing a vertex whose BFS distance is . What distance is assigned to ?

Breadth-first search Medium
A.
B.
C.
D.

25 While using BFS to test whether an undirected graph is bipartite, an edge is found between two vertices assigned the same color. What does this imply?

Breadth-first search Medium
A. The graph must be acyclic
B. The graph must be disconnected
C. The graph contains an odd-length cycle
D. The graph contains an even-length cycle

26 A recursive DFS starts at in a directed graph with adjacency lists , , , , , and . Neighbors are processed in the listed order. What is the discovery order?

Depth-first search Medium
A.
B.
C.
D.

27 During DFS of a directed graph, an edge from the current vertex leads to a vertex that is discovered but not yet finished. How is this edge interpreted?

Depth-first search Medium
A. It is a forward edge proving acyclicity
B. It is a back edge indicating a cycle
C. It is a tree edge indicating a leaf
D. It is a cross edge proving connectivity

28 How can DFS finishing times be used to obtain a topological ordering of a directed acyclic graph?

Depth-first search Medium
A. List vertices by increasing finishing time
B. List vertices by decreasing discovery time
C. List vertices by decreasing finishing time
D. List vertices by increasing discovery time

29 Which algorithm is most appropriate for finding shortest paths from one source in an unweighted graph?

Shortest path algorithms Medium
A. Floyd-Warshall algorithm
B. Breadth-first search
C. Depth-first search
D. Bellman-Ford algorithm

30 A weighted directed graph is a DAG and may contain negative edge weights. Which approach finds single-source shortest paths in time?

Shortest path algorithms Medium
A. Apply Dijkstra without a heap
B. Relax edges in topological order
C. Run BFS from the source
D. Run Floyd-Warshall once

31 Consider directed edges with weight , with weight , with weight , with weight , with weight , and with weight . What is the order in which vertices are settled by Dijkstra's algorithm from ?

Dijkstra's algorithm Medium
A.
B.
C.
D.

32 A directed graph has edges , , , , , and . What shortest distance does Dijkstra's algorithm compute from to ?

Dijkstra's algorithm Medium
A.
B.
C.
D.

33 A graph contains edges with weight , with weight , and with weight . What is the true shortest distance from to , and why can Dijkstra's algorithm fail?

Dijkstra's algorithm Medium
A. , because a later negative edge improves
B. , because direct edges are always shortest
C. , because only the final edge matters
D. , because is reached before

34 For edges , , , , and , what distances does Bellman-Ford compute from ?

Bellman-Ford algorithm Medium
A. , ,
B. , ,
C. , ,
D. , ,

35 After full relaxation passes, an edge whose source has a finite distance can still be relaxed. What does Bellman-Ford conclude?

Bellman-Ford algorithm Medium
A. A reachable positive-weight cycle exists
B. All shortest paths are finalized
C. A reachable negative-weight cycle exists
D. The source vertex is disconnected

36 During Bellman-Ford, a complete pass over all edges causes no distance update. What is the correct action?

Bellman-Ford algorithm Medium
A. Restart with a different source
B. Switch immediately to DFS
C. Stop because distances are final
D. Perform exactly more passes

37 Which recurrence correctly describes the Floyd-Warshall update when vertex is allowed as an intermediate vertex?

Floyd-Warshall algorithm Medium
A.
B.
C.
D.

38 Before considering vertex as an intermediate vertex, the current distances are , , and . What is the updated value of ?

Floyd-Warshall algorithm Medium
A.
B.
C.
D.

39 After Floyd-Warshall finishes, which matrix condition indicates that the graph contains a negative-weight cycle?

Floyd-Warshall algorithm Medium
A. Some off-diagonal entry equals
B. Some diagonal entry satisfies
C. Some diagonal entry satisfies
D. Some off-diagonal entry equals

40 A directed graph has edges , , , and . What shortest distance from to will Floyd-Warshall compute?

Floyd-Warshall algorithm Medium
A.
B.
C.
D.

41 A graph has vertices and edges and may be disconnected. A complete traversal runs BFS from every still-unvisited vertex. What are the tight worst-case running times when the graph is represented by an adjacency list and by an adjacency matrix, respectively?

Graph traversal Hard
A. and
B. and
C. and
D. and

42 An undirected, unweighted graph has edges --, --, --, --, --, --, --, --, --, and --. How many distinct shortest paths exist from to ?

Breadth-first search Hard
A.
B.
C.
D.

43 BFS starts at in the directed graph with ordered adjacency lists: , , , , , , , , , and all other lists empty. Vertices are marked when enqueued. What is the maximum number of vertices simultaneously in the queue?

Breadth-first search Hard
A.
B.
C.
D.

44 BFS is run from source in a directed, unweighted graph. For a directed edge where both endpoints are reachable from , which relation is always guaranteed?

Breadth-first search Hard
A.
B.
C.
D.

45 Recursive DFS begins at using adjacency lists , , , and . Neighbors are processed in listed order. How are edges and classified?

Depth-first search Hard
A. is back; is cross
B. is back; is forward
C. is cross; is back
D. is forward; is cross

46 An iterative DFS uses a stack, marks a vertex when it is popped, and pushes all of its currently unvisited neighbors. To reproduce the discovery order of recursive DFS that scans each adjacency list from first to last, in what order should the iterative algorithm push the neighbors?

Depth-first search Hard
A. By increasing DFS finish time
B. From last to first
C. From first to last
D. By decreasing vertex degree

47 Which DFS condition is both necessary and sufficient for a directed graph to be acyclic?

Depth-first search Hard
A. Every DFS tree contains a forward edge
B. Every vertex has a distinct finish time
C. No DFS forest contains a cross edge
D. No DFS forest contains a back edge

48 In the standard DFS low-link algorithm for articulation points in an undirected graph, which criterion is correct?

Depth-first search Hard
A. A root needs one DFS child; a non-root needs a child with
B. A root needs two graph neighbors; a non-root needs
C. A root needs two DFS children; a non-root needs a child with
D. A root needs no back edge; a non-root needs a child with

49 Johnson's algorithm computes potentials using Bellman-Ford. Which reweighting both preserves shortest-path ordering and makes every edge nonnegative when no negative cycle exists?

Shortest path algorithms Hard
A.
B.
C.
D.

50 A weighted directed graph is a DAG but may contain negative edge weights. Which method computes single-source shortest paths in tight time ?

Shortest path algorithms Hard
A. Relax edges in topological order
B. Run Floyd-Warshall from the source
C. Run Dijkstra with a binary heap
D. Run Bellman-Ford for passes

51 Dijkstra's algorithm runs from on directed edges , , , , , , , and . What is the order in which vertices are permanently settled?

Dijkstra's algorithm Hard
A.
B.
C.
D.

52 Consider directed edges , , and . Standard Dijkstra finalizes a vertex when extracted and never changes a finalized distance. What distance does it report for , and what is the true shortest distance?

Dijkstra's algorithm Hard
A. Reported ; true
B. Reported ; true
C. Reported ; true
D. Reported ; true

53 Dijkstra's algorithm uses a binary heap without decrease-key: every strict distance improvement inserts a new pair, and stale pairs are ignored when extracted. For edges , , , , , , , and , how many stale pairs are eventually extracted?

Dijkstra's algorithm Hard
A.
B.
C.
D.

54 When all edge weights are nonnegative, at which event may Dijkstra's algorithm safely terminate if only the distance from to target is required?

Dijkstra's algorithm Hard
A. When every neighbor of is discovered
B. When an edge entering is first scanned
C. When is first inserted into the queue
D. When is extracted with minimum key

55 Suppose Bellman-Ford performs synchronous passes, so every relaxation in pass reads distances produced only by pass . After pass , what does represent?

Bellman-Ford algorithm Hard
A. The minimum weight of an - path containing at most negative edges
B. The minimum weight of an - path visiting at most vertices
C. The minimum weight of an - walk using at most edges
D. The minimum weight of an - walk using exactly edges

56 A graph contains a negative-weight cycle in a component unreachable from source . What does standard single-source Bellman-Ford initialized with and all other distances infinite do?

Bellman-Ford algorithm Hard
A. It fails during the first relaxation pass
B. It reports every negative cycle in the graph
C. It does not report that unreachable cycle
D. It assigns negative infinity to that component

57 Bellman-Ford runs from on edges , , , , , , , , , and . What is after convergence?

Bellman-Ford algorithm Hard
A.
B.
C.
D.

58 Immediately before Floyd-Warshall allows vertex as an intermediate, its distance matrix is What is the first row immediately after this phase?

Floyd-Warshall algorithm Hard
A.
B.
C.
D.

59 After Floyd-Warshall finishes, suppose . For which ordered pairs is there no finite shortest-walk value because the negative cycle can be used arbitrarily many times?

Floyd-Warshall algorithm Hard
A. Pairs with finite and finite
B. Pairs satisfying only or
C. Pairs with finite and finite
D. Pairs satisfying only

60 In Floyd-Warshall, after completing the outer-loop iteration for intermediate vertex , what invariant is maintained by ?

Floyd-Warshall algorithm Hard
A. It is shortest among paths containing exactly intermediate vertices
B. It is shortest among paths whose intermediate vertices lie in
C. It is shortest among paths whose endpoints lie in
D. It is shortest among paths containing at most total edges
Previous MCQ
Unit 5