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. Cycles
B. Weights
C. Paths
D. Vertices

2 What distinguishes a directed graph from an undirected graph?

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

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

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

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 maximum-capacity network flow
C. A topological order with cycles
D. A shortest path by edge count

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

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

6 How does DFS typically explore a graph?

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

7 Topological sorting is defined for which type of graph?

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

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

Topological Sort Easy
A. appears before
B. appears next to
C. and share a weight
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 globally worst available choice
C. The locally best 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 examine every possible solution
B. They always require a recursion tree
C. They work only on unweighted graphs
D. They build solutions through local choices

11 In the fractional knapsack problem, what is allowed?

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

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

Knapsack Problem Easy
A. Capacity-to-value ratio
B. Value-to-weight ratio
C. Weight-to-capacity ratio
D. Item count 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 number of connected components
C. The total number of its vertices
D. The total weight of its edges

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

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

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

Kruskal's Algorithm Easy
A. Increasing order of degree
B. Decreasing order of weight
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. Shortest paths between every pair
B. A minimum-weight spanning tree
C. A valid topological ordering
D. Shortest paths from one source

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

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

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

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

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

All-Pairs Shortest Paths Easy
A. Breadth-First Search
B. Prim's algorithm
C. Floyd-Warshall 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 is complete
D. The graph has one cycle

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 incidence matrix using space
B. An adjacency list using space
C. An adjacency matrix using space
D. A distance 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. 4 edges
B. 2 edges
C. 5 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 back edge and a directed cycle
B. A forward edge and a shortest path
C. A cross edge and an acyclic graph
D. A tree edge and a new component

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 cannot represent the amount exactly
B. It uses 3 coins, although 2 are sufficient
C. It uses 4 coins, although 3 are sufficient
D. It uses 2 coins, which is optimal

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 6
B. of weight 4
C. of weight 2
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 contains every light edge
B. It has minimum degree 2
C. It is a shortest-path tree
D. It is unique

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. A reachable negative-weight cycle exists
B. The graph must be disconnected
C. A zero-weight edge remains unprocessed
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 may be tree or forward
B. It must be a tree edge
C. It must be a forward edge
D. It may be back or cross

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 vertices at the same depth
B. Every non-tree edge joins two different DFS trees
C. Every non-tree edge joins an ancestor and a descendant
D. Every non-tree edge joins vertices whose depths differ by one

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. Every vertex except has positive out-degree
D. The DAG has exactly one source and one sink

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 gives a factor- approximation for every weight assignment
B. It is optimal only when every maximal feasible set is unique
C. It is optimal only when all element weights are distinct
D. It is optimal because the feasible family forms a matroid

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. Some MST contains
B. No MST excluding exists
C. Edge is the unique light edge
D. Every MST contains

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 not minimum because is lighter than its cycle
C. is an MST but is not unique
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. One component's MST in time
B. One component's MST in time
C. A minimum spanning forest in time
D. A minimum spanning forest 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 reachable edge can still be relaxed
C. Any edge still has a negative weight
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