Unit 6: Shortest Paths & Trees - Practice Quiz

1 In a weighted graph, what does the weight assigned to an edge typically represent?

2 A graph in which each vertex or edge is assigned a name or label is called a:

3 The shortest path between two vertices in a weighted graph is the path with the:

4 In an unweighted graph, the shortest path between two vertices is measured by the:

5 Dijkstra's algorithm is used to find the shortest path from:

6 A key limitation of Dijkstra's algorithm is that it does not work correctly with:

7 At each step, Dijkstra's algorithm selects the unvisited vertex with the:

8 A tree is best defined as a connected graph that:

9 A tree with vertices always has exactly how many edges?

10 How many paths exist between any two distinct vertices in a tree?

11 In a rooted tree, the topmost vertex from which the tree originates is called the:

12 In a rooted tree, a vertex that has no children is known as a:

13 A binary tree is a rooted tree in which every node has at most:

14 What is the maximum number of nodes at level of a binary tree, taking the root as level ?

15 A spanning tree of a connected graph is a subgraph that:

16 A spanning tree of a connected graph with vertices contains exactly how many edges?

17 A minimum spanning tree (MST) of a weighted graph is the spanning tree with the:

18 Kruskal's algorithm builds a minimum spanning tree by considering edges in order of:

19 While adding edges, Kruskal's algorithm avoids selecting an edge that would:

20 Prim's algorithm builds the minimum spanning tree by:

21 In a weighted graph, the sum of the weights of all edges in a path is called the:

22 A weighted graph has edges with weights that represent distances. If an edge between vertices and has weight and no edge exists between and , which statement is correct?

23 Which property must hold for a shortest path between two vertices in a weighted graph with non-negative weights?

24 A shortest path that minimizes the number of edges rather than total weight would be found by treating the graph as:

25 Dijkstra's algorithm fails to give correct results when the graph contains:

26 In Dijkstra's algorithm, once a vertex is marked as finalized (added to the set of visited vertices), its shortest distance:

27 Consider a graph with edges , , . Using Dijkstra from , the shortest distance to is:

28 Using a binary min-heap (priority queue), the time complexity of Dijkstra's algorithm for a graph with vertices and edges is:

29 A connected graph with vertices is a tree if and only if it has exactly:

30 Which of the following is NOT necessarily true for a tree?

31 In a rooted tree, a vertex with no children is called a:

32 In a rooted tree, the length of the path from the root to a given node is called that node's:

33 The maximum number of nodes in a binary tree of height (root at height ) is:

34 A binary tree with internal nodes, where every internal node has exactly two children (a full binary tree), has how many leaf nodes?

35 How many distinct binary trees can be formed using unlabelled nodes?

36 A spanning tree of a connected graph with vertices always contains:

37 By Cayley's formula, the number of distinct spanning trees of a complete graph is:

38 If all edge weights in a connected graph are distinct, then the minimum spanning tree is:

39 Kruskal's algorithm selects edges in increasing order of weight while avoiding cycles. Which data structure efficiently detects cycles during this process?

40 A key difference between Prim's and Kruskal's algorithms is that Prim's algorithm:

41 Dijkstra's algorithm may produce incorrect shortest-path results when a graph contains which of the following?

42 Using a binary min-heap as the priority queue, the time complexity of Dijkstra's algorithm on a graph with vertices and edges is:

43 If all edge weights in a connected weighted graph are distinct, which statement about its minimum spanning tree (MST) is true?

44 By Cayley's formula, the number of distinct spanning trees of the complete graph is:

45 The Union-Find data structure with union by rank and path compression is used in Kruskal's algorithm primarily to:

46 A binary tree has internal nodes each with exactly two children (a full binary tree). How many leaf nodes does it have?

47 Prim's algorithm grows the MST by repeatedly selecting the minimum-weight edge that:

48 A weighted graph has vertices. Which representation gives time to query the weight of a specific edge ?

49 Consider a connected weighted graph. If an edge is the unique maximum-weight edge on some cycle, which property guarantees is excluded from the MST?

50 In a weighted graph where every edge weight is multiplied by a positive constant , the shortest path between any two vertices:

51 In a rooted tree with nodes, what is the sum of the number of children over all nodes?

52 During Dijkstra's execution, at the moment a vertex is extracted from the priority queue, which invariant holds?

53 For a dense graph with edges, which MST algorithm/implementation is typically most efficient?

54 What is the maximum number of nodes in a binary tree of height (where a single node has height )?

55 A connected graph has vertices and edges. The number of edges that must be removed to obtain a spanning tree is:

56 Which statement correctly relates the MST and the shortest-path tree (SPT) rooted at a vertex in a weighted graph?

57 If a weighted directed graph contains a negative-weight cycle reachable from the source, the shortest-path problem:

58 Both Kruskal's and Prim's algorithms are greedy and correct because they rely on which fundamental principle?

59 In a complete -ary rooted tree with internal nodes, the total number of nodes is:

60 In a weighted graph, if a unique edge has strictly the smallest weight, then this edge: