Chapter 24 Self-Assessment Quiz: Trees and Graphs
Section 1: Multiple Choice
Q1. In a binary search tree, in-order traversal produces:
(a) The elements in the order they were inserted (b) The elements in sorted order (c) The elements in reverse order (d) The elements level by level
Answer
(b) In-order traversal visits Left, then Node, then Right. Since BST ordering guarantees Left < Node < Right, in-order traversal produces all elements in ascending sorted order.Q2. What is the worst-case time complexity of searching in an unbalanced BST with n nodes?
(a) O(1) (b) O(log n) (c) O(n) (d) O(n log n)
Answer
(c) An unbalanced BST can degenerate into a linked list (e.g., when values are inserted in sorted order). In this case, search must traverse all n nodes, giving O(n) worst case. A balanced BST guarantees O(log n).Q3. Which traversal is most useful for safely freeing all nodes in a binary tree?
(a) In-order (b) Pre-order (c) Post-order (d) Level-order
Answer
(c) Post-order traversal processes children before the parent. This means when you free a node, its children have already been freed, preventing dangling pointers. Pre-order would free the parent first, losing access to the children.Q4. An adjacency list is preferred over an adjacency matrix when:
(a) The graph is dense (many edges) (b) You need O(1) edge lookup (c) The graph is sparse (few edges) (d) The graph has self-loops
Answer
(c) For sparse graphs, an adjacency list uses O(V + E) space compared to the matrix's O(V²). With few edges, most matrix entries would be zero, wasting space. Dense graphs may favor the matrix for O(1) edge lookup.Q5. BFS finds the shortest path in:
(a) Weighted graphs with negative edges (b) Weighted graphs with positive edges (c) Unweighted graphs only (d) All graphs
Answer
(c) BFS finds shortest paths measured in number of edges (all edges have equal weight). For weighted graphs with positive edges, use Dijkstra's algorithm. For negative edges, use Bellman-Ford.Q6. Dijkstra's algorithm uses which strategy?
(a) Divide and conquer (b) Dynamic programming (c) Greedy (d) Backtracking
Answer
(c) Dijkstra's algorithm greedily picks the unvisited vertex with the smallest tentative distance at each step. This greedy choice is provably correct for graphs with non-negative edge weights.Q7. To delete a node with two children from a BST, you replace it with:
(a) Its left child (b) Its right child (c) Its in-order successor or predecessor (d) The root of the tree
Answer
(c) Replace the node's value with its in-order successor (smallest value in right subtree) or in-order predecessor (largest value in left subtree), then delete that successor/predecessor (which has at most one child). This preserves the BST property.Q8. What data structure does BFS use internally?
(a) Stack (b) Queue (c) Priority queue (d) Hash table
Answer
(b) BFS uses a queue (FIFO) to explore vertices in order of increasing distance from the source. DFS uses a stack. Dijkstra's uses a priority queue. Hash tables are not used for traversal.Section 2: True or False
Q9. True or False: Every binary tree is a binary search tree.
Answer
False. A binary tree is any tree where each node has at most two children. A BST additionally requires that left children are smaller and right children are larger. Many binary trees do not satisfy this ordering property.Q10. True or False: A tree with n nodes always has exactly n-1 edges.
Answer
True. Every node except the root has exactly one edge connecting it to its parent. With n nodes and 1 root, there are n-1 parent edges. This is a fundamental property of trees.Q11. True or False: DFS can detect cycles in a directed graph.
Answer
True. During DFS, if you encounter a vertex that is currently being explored (a "gray" vertex in three-color marking), you have found a back edge, which indicates a cycle.Q12. True or False: Dijkstra's algorithm works correctly on graphs with negative edge weights.
Answer
False. Dijkstra's algorithm assumes that once a vertex's shortest distance is finalized, it cannot be improved. Negative edges can violate this assumption, leading to incorrect shortest distances. Use the Bellman-Ford algorithm for graphs with negative weights.Section 3: Short Answer
Q13. Draw the BST that results from inserting these values in order: 5, 3, 7, 1, 4, 6, 8. Then delete 3 and draw the result.
Answer
After insertion:
5
/ \
3 7
/ \ / \
1 4 6 8
Delete 3 (two children): replace with in-order successor (4), then delete 4 from right subtree.
5
/ \
4 7
/ / \
1 6 8
Q14. Given a graph with vertices {A, B, C, D} and edges {A-B:1, A-C:4, B-C:2, B-D:5, C-D:1}, trace Dijkstra's algorithm from A. Show the final distances.
Answer
Initial: A=0, B=inf, C=inf, D=inf. Visit A: update B=1, C=4. Visit B (dist 1): update C=min(4, 1+2)=3, D=min(inf, 1+5)=6. Visit C (dist 3): update D=min(6, 3+1)=4. Visit D (dist 4): done. Final: A=0, B=1, C=3, D=4. Shortest path to D: A→B→C→D (cost 4).Q15. Explain the "first child, next sibling" representation for N-ary trees. What advantage does it have over a fixed-size child array?