Back to Subject

Unit 4: Graph Algorithms, Network Optimization, and Greedy Technique - Practice Quiz

CSE408 — Design And Analysis Of Algorithms 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 In a graph, what are the objects connected by edges called?

Introduction to Graphs Easy
A. Paths
B. Cycles
C. Vertices
D. Weights

2 What distinguishes a directed graph from an undirected graph?

Introduction to Graphs Easy
A. It contains no cycles
B. It contains one component
C. Its edges have directions
D. Its vertices have weights

3 Which data structure is primarily used by Breadth-First Search?

Breadth-First Search (BFS) Easy
A. Hash table
B. Queue
C. Stack
D. Heap

4 In an unweighted graph, BFS can be used to find which of the following?

Breadth-First Search (BFS) Easy
A. A minimum spanning tree by weight
B. A shortest path by edge count
C. A maximum-capacity network flow
D. A topological order with cycles

5 Which data structure is naturally associated with an iterative Depth-First Search?

Depth-First Search (DFS) Easy
A. Stack
B. Priority queue
C. Circular list
D. Queue

6 How does DFS typically explore a graph?

Depth-First Search (DFS) Easy
A. It follows one branch deeply
B. It sorts vertices by degree
C. It selects the lightest edge
D. It visits every level first

7 Topological sorting is defined for which type of graph?

Topological Sort Easy
A. Undirected weighted graph
B. Undirected connected graph
C. Directed acyclic graph
D. Directed cyclic graph

8 In a topological ordering, what must be true for every directed edge from to ?

Topological Sort Easy
A. and share a weight
B. appears next to
C. appears before
D. appears before

9 What does a greedy algorithm choose at each step?

Introduction to Greedy Approach Easy
A. Every possible available choice
B. The locally best available choice
C. The globally worst available choice
D. A randomly selected available choice

10 Which statement about greedy algorithms is generally true?

Introduction to Greedy Approach Easy
A. They always require a recursion tree
B. They build solutions through local choices
C. They always examine every possible solution
D. They work only on unweighted graphs

11 In the fractional knapsack problem, what is allowed?

Knapsack Problem Easy
A. Taking each item twice
B. Changing an item's weight
C. Taking part of an item
D. Ignoring the capacity limit

12 Which value is commonly used to select items greedily in the fractional knapsack problem?

Knapsack Problem Easy
A. Weight-to-capacity ratio
B. Capacity-to-value ratio
C. Item count ratio
D. Value-to-weight ratio

13 How many edges does a spanning tree of a connected graph with vertices contain?

Minimum Spanning Trees Easy
A.
B.
C.
D.

14 What is minimized by a minimum spanning tree?

Minimum Spanning Trees Easy
A. The maximum degree of each vertex
B. The total weight of its edges
C. The number of connected components
D. The total number of its vertices

15 How does Prim's algorithm build a minimum spanning tree?

Prim's Algorithm Easy
A. It removes every edge from the graph
B. It sorts all vertices by their labels
C. It grows one tree from a start vertex
D. It finds paths from every source vertex

16 In what order does Kruskal's algorithm consider the edges?

Kruskal's Algorithm Easy
A. Decreasing order of weight
B. Increasing order of degree
C. Increasing order of weight
D. Decreasing order of degree

17 What does a single-source shortest-path algorithm compute?

Single-Source Shortest Paths Easy
A. A valid topological ordering
B. A minimum-weight spanning tree
C. Shortest paths from one source
D. Shortest paths between every pair

18 Dijkstra's algorithm is normally applied when edge weights are which of the following?

Single-Source Shortest Paths Easy
A. Only fractional
B. All identical
C. All negative
D. Non-negative

19 What is the output of an all-pairs shortest-path algorithm?

All-Pairs Shortest Paths Easy
A. Distances from one chosen vertex
B. Edges of one spanning tree
C. Vertices in one traversal order
D. Distances between every vertex pair

20 Which algorithm is commonly used for the all-pairs shortest-path problem?

All-Pairs Shortest Paths Easy
A. Breadth-First Search
B. Floyd-Warshall algorithm
C. Prim's algorithm
D. Kruskal's algorithm

21 A connected undirected graph has 8 vertices and 7 edges. Which statement must be true?

Introduction to Graphs Medium
A. The graph is bipartite
B. The graph is a tree
C. The graph has one cycle
D. The graph is complete

22 A sparse graph has vertices and edges, where is much smaller than . Which representation is generally most space-efficient?

Introduction to Graphs Medium
A. An adjacency list using space
B. An incidence matrix using space
C. A distance matrix using space
D. An adjacency matrix using space

23 An undirected graph has edges , , , , , , and . Starting BFS at and visiting adjacent vertices alphabetically, what is the traversal order?

Breadth-First Search (BFS) Medium
A.
B.
C.
D.

24 An unweighted undirected graph has edges , , , , , , and . What shortest-path distance does BFS compute from to ?

Breadth-First Search (BFS) Medium
A. 5 edges
B. 2 edges
C. 4 edges
D. 3 edges

25 An undirected graph has edges , , , , , , and . Starting recursive DFS at and choosing adjacent vertices alphabetically, what is the traversal order?

Depth-First Search (DFS) Medium
A.
B.
C.
D.

26 During DFS of a directed graph, an edge from the current vertex reaches a gray vertex . What does this indicate?

Depth-First Search (DFS) Medium
A. A forward edge and a shortest path
B. A tree edge and a new component
C. A back edge and a directed cycle
D. A cross edge and an acyclic graph

27 A directed acyclic graph has edges , , , , and . Which sequence is a valid topological ordering?

Topological Sort Medium
A.
B.
C.
D.

28 A DAG contains edges , , , and . Which added edge would make topological sorting impossible?

Topological Sort Medium
A.
B.
C.
D.

29 For activity selection, the intervals are , , , , , and . Using the earliest-finish-time greedy rule, which set is selected?

Introduction to Greedy Approach Medium
A.
B.
C.
D.

30 A greedy coin-change algorithm always chooses the largest usable coin. For denominations and amount , what happens?

Introduction to Greedy Approach Medium
A. It uses 2 coins, which is optimal
B. It uses 4 coins, although 3 are sufficient
C. It uses 3 coins, although 2 are sufficient
D. It cannot represent the amount exactly

31 In a fractional knapsack of capacity 50, the items have pairs , , and . What maximum value can be obtained?

Knapsack Problem Medium
A.
B.
C.
D.

32 For the 0/1 knapsack with capacity 50 and items , , and , what is the optimal total value?

Knapsack Problem Medium
A.
B.
C.
D.

33 For the cut and , the crossing edges are of weight 4, of weight 6, of weight 2, and of weight 5. Which edge is safe to add to an MST?

Minimum Spanning Trees Medium
A. of weight 4
B. of weight 2
C. of weight 6
D. of weight 5

34 A connected undirected graph has distinct weights on all its edges. What can be concluded about its minimum spanning tree?

Minimum Spanning Trees Medium
A. It is unique
B. It is a shortest-path tree
C. It contains every light edge
D. It has minimum degree 2

35 Consider edges , , , , , , and . Starting Prim's algorithm at , which edge sequence is selected?

Prim's Algorithm Medium
A.
B.
C.
D.

36 Prim's algorithm is implemented with adjacency lists and a binary min-heap. What is its standard time complexity?

Prim's Algorithm Medium
A.
B.
C.
D.

37 Using edges , , , , , , and , which edges does Kruskal's algorithm select, in order?

Kruskal's Algorithm Medium
A.
B.
C.
D.

38 A directed graph has edges , , , , , , and . What distance from to does Dijkstra's algorithm find?

Single-Source Shortest Paths Medium
A.
B.
C.
D.

39 After relaxation passes in Bellman-Ford, an additional pass still decreases the distance of a vertex reachable from the source. What does this show?

Single-Source Shortest Paths Medium
A. The graph must be disconnected
B. A zero-weight edge remains unprocessed
C. A reachable negative-weight cycle exists
D. The shortest-path tree is unique

40 During Floyd-Warshall, suppose the current values are , , and . What is the updated value of when is allowed as an intermediate vertex?

All-Pairs Shortest Paths Medium
A.
B.
C.
D.

41 A simple undirected graph on vertices has edges . If is its adjacency matrix, what are the number of distinct triangles and the value of , respectively?

Introduction to Graphs Hard
A. triangles and
B. triangles and
C. triangles and
D. triangles and

42 The condensation graph of a directed graph has more than one vertex, with exactly three source strongly connected components and two sink strongly connected components. If arbitrary directed edges may be added, what is the minimum number required to make the original graph strongly connected?

Introduction to Graphs Hard
A. edges
B. edges
C. edges
D. edges

43 BFS is run from source in a directed, unweighted graph. For an edge where is reachable from , which relationship between the BFS distances is always guaranteed?

Breadth-First Search (BFS) Hard
A.
B.
C.
D.

44 A directed unweighted graph has edges , , , , , , and , . How many distinct shortest paths exist from to ?

Breadth-First Search (BFS) Hard
A.
B.
C.
D.

45 In a DFS of a directed graph, the timestamp intervals are and . If edge exists, how can that edge be classified using only these timestamps?

Depth-First Search (DFS) Hard
A. It must be a tree edge
B. It may be tree or forward
C. It may be back or cross
D. It must be a forward edge

46 Which statement is always true about a DFS forest of an undirected graph?

Depth-First Search (DFS) Hard
A. Every non-tree edge joins two different DFS trees
B. Every non-tree edge joins vertices whose depths differ by one
C. Every non-tree edge joins an ancestor and a descendant
D. Every non-tree edge joins vertices at the same depth

47 For a DAG, which condition is necessary and sufficient for its topological ordering to be unique?

Topological Sort Hard
A. Every pair of vertices has a common descendant
B. An edge exists for every
C. The DAG has exactly one source and one sink
D. Every vertex except has positive out-degree

48 A DAG on contains exactly the edges , , , , , , and . How many topological orderings does it have?

Topological Sort Hard
A.
B.
C.
D.

49 A family of feasible subsets is hereditary and satisfies the exchange property: whenever feasible sets and satisfy , some makes feasible. What does this imply about repeatedly selecting the highest-weight feasible element for arbitrary nonnegative weights?

Introduction to Greedy Approach Hard
A. It is optimal only when every maximal feasible set is unique
B. It is optimal because the feasible family forms a matroid
C. It gives a factor- approximation for every weight assignment
D. It is optimal only when all element weights are distinct

50 Weighted activities are , , , and , where each tuple is . What values are obtained by earliest-finish-time greedy selection and by an optimal weighted selection, respectively?

Introduction to Greedy Approach Hard
A. and
B. and
C. and
D. and

51 A knapsack has capacity . Items have pairs , , , and . What are the optimal values for the fractional and variants, respectively?

Knapsack Problem Hard
A. and
B. and
C. and
D. and

52 Let be a subset of edges contained in some MST. A cut respects , and edge is a minimum-weight edge crossing that cut, with ties allowed. Which conclusion is guaranteed?

Minimum Spanning Trees Hard
A. Every MST contains
B. Some MST contains
C. Edge is the unique light edge
D. No MST excluding exists

53 A spanning tree has edges of weight , of weight , and of weight . The remaining graph edges are of weight , of weight , and of weight . Which statement is correct?

Minimum Spanning Trees Hard
A. is an MST and is unique
B. is an MST but is not unique
C. is not minimum because is lighter than its cycle
D. is not minimum because can replace

54 Prim's algorithm starts at on a graph with weighted edges , , , , , , and . What is the order of selected edges?

Prim's Algorithm Hard
A.
B.
C.
D.

55 Prim's algorithm is implemented with an adjacency matrix and run on a disconnected graph without restarting after the initial source component is exhausted. Which result and running time are expected?

Prim's Algorithm Hard
A. A minimum spanning forest in time
B. A minimum spanning forest in time
C. One component's MST in time
D. One component's MST in time

56 Kruskal's algorithm is run on vertices with edges , , , , , , , and . Equal-weight edges are processed lexicographically. Which sequence of edges is accepted?

Kruskal's Algorithm Hard
A.
B.
C.
D.

57 A directed graph has edges , , , , and . A standard label-setting Dijkstra implementation never revisits finalized vertices. What distance to does it return, and what is the true shortest distance?

Single-Source Shortest Paths Hard
A. It returns ; the true distance is
B. It returns ; the true distance is
C. It returns ; the true distance is
D. It returns ; the true distance is

58 Bellman-Ford performs full relaxation passes from source , followed by one additional pass. Which event proves that a negative-weight cycle reachable from exists?

Single-Source Shortest Paths Hard
A. Any finite distance remains greater than zero
B. Any edge still has a negative weight
C. Any reachable edge can still be relaxed
D. Any unreachable vertex retains infinite distance

59 A directed graph has edges , , , , and . After Floyd-Warshall completes, what are the distances and ?

All-Pairs Shortest Paths Hard
A. and
B. and
C. and
D. and

60 In Johnson's algorithm, Bellman-Ford produces potentials , and each edge is reweighted as . If Dijkstra computes using , how is the original shortest-path distance recovered?

All-Pairs Shortest Paths Hard
A.
B.
C.
D.
Previous MCQ
Unit 3
Next MCQ
Unit 5