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. Counting only the graph's connected components
B. Sorting all graph vertices alphabetically
C. Visiting vertices and edges in a graph
D. Deleting every edge from a graph

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. Visited array
C. Hash calculator
D. Priority queue

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

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

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

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

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

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

6 What does BFS find efficiently in an unweighted graph?

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

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

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

8 How does DFS generally explore a graph?

Depth-first search Easy
A. It visits all neighbors at once
B. It examines vertices in sorted order
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. Removing isolated vertices
B. Detecting cycles
C. Adding weights to edges
D. Making every edge undirected

10 What is the shortest path between two vertices?

Shortest path algorithms Easy
A. A path with minimum total cost
B. A path containing every vertex
C. A path containing the most edges
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. One
B. Zero
C. The number of vertices
D. Infinity

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

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

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

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

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

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

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

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

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

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

17 What important problem can Bellman-Ford detect?

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

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-edge shortest paths
D. Single-source paths only

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

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

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. Repeat the traversal from every edge
B. Start a traversal from each unvisited vertex
C. Sort all vertices by their degrees
D. Convert the graph into a complete graph

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 disconnected
B. The graph contains an even-length cycle
C. The graph must be acyclic
D. The graph contains an odd-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 cross edge proving connectivity
D. It is a tree edge indicating a leaf

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 increasing discovery time
C. List vertices by decreasing discovery time
D. List vertices by decreasing finishing time

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

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

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. Relax edges in topological order
B. Run Floyd-Warshall once
C. Run BFS from the source
D. Apply Dijkstra without a heap

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 direct edges are always shortest
B. , because only the final edge matters
C. , because a later negative edge improves
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. The source vertex is disconnected
D. A reachable negative-weight cycle exists

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

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

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 cross; is back
B. is back; is cross
C. is forward; is cross
D. is back; is forward

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 decreasing vertex degree
B. From first to last
C. From last to first
D. By increasing DFS finish time

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

Depth-first search Hard
A. No DFS forest contains a cross edge
B. Every vertex has a distinct finish time
C. No DFS forest contains a back edge
D. Every DFS tree contains a forward 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 two DFS children; a non-root needs a child with
B. A root needs no back edge; a non-root needs a child with
C. A root needs two graph neighbors; a non-root needs
D. A root needs one DFS child; 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. Run Dijkstra with a binary heap
B. Run Bellman-Ford for passes
C. Run Floyd-Warshall from the source
D. Relax edges in topological order

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 is first inserted into the queue
B. When an edge entering is first scanned
C. When every neighbor of is discovered
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 - walk using at most edges
B. The minimum weight of an - walk using exactly edges
C. The minimum weight of an - path visiting at most vertices
D. The minimum weight of an - path containing at most negative 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 assigns negative infinity to that component
B. It does not report that unreachable cycle
C. It fails during the first relaxation pass
D. It reports every negative cycle in the graph

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 satisfying only
B. Pairs satisfying only or
C. Pairs with finite and finite
D. Pairs with finite and finite

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 at most total edges
B. It is shortest among paths whose endpoints lie in
C. It is shortest among paths containing exactly intermediate vertices
D. It is shortest among paths whose intermediate vertices lie in
Previous MCQ
Unit 5