Grade 9 AI & Computer Science Practice Questions — Set 3

ExplanationStep-by-step BFS execution: (1) Initialize: visited set (empty), queue with start vertex A. (2) Process vertices: each vertex is visited exactly once, contributing O(V) = O(8). (3) For each vertex, examine all adjacent edges: total edge examinations = E = 12. (4) Therefore, total complexity = O(V+E) = O(8+12) = O(20). Queue operations (enqueue/dequeue) each cost O(1). Space complexity: O(V) = O(8) for the visited set and queue.

ExplanationStep-by-step DFS execution: (1) Initialize: visited set (empty), stack (or recursion) starting at vertex S. (2) Process vertices: each vertex is pushed and visited exactly once, contributing O(V) = O(10). (3) For each vertex popped off the stack, examine all adjacent edges to decide which unvisited neighbors to push next: total edge examinations = E = 15. (4) Therefore, total complexity = O(V+E) = O(10+15) = O(25). Stack operations (push/pop), or equivalently each recursive call, each cost O(1). Space complexity: O(V) = O(10) for the visited set plus the stack/recursion depth. Because the graph has 15/10 = 1.5 avg edges per vertex, it is sparse, making adjacency list representation optimal.

ExplanationStep-by-step Dijkstra execution: (1) Initialize: visited set (empty), distance array with Infinity for all vertices except source = 0. (2) Process vertices: each vertex is visited exactly once, contributing O(V) = O(6). (3) For each vertex, examine all adjacent edges: total edge examinations = E = 9. (4) Therefore, total complexity = O(V+E) = O(6+9) = O(15). With min-heap: extract-min costs O(log V) = O(log 6) = O(3.0), called V times = O(V log V). Decrease-key called E times = O(E log V). Total: O((V+E) log V) = O(15 × 3) = O(45). Space complexity: O(V) = O(6) for visited set + queue/stack. Because the graph has 9/6 = 1.5 avg edges per vertex, it is sparse, making adjacency list representation optimal.

ExplanationStep-by-step Topological Sort execution using Kahn's algorithm: (1) Compute in-degrees for all vertices — A has in-degree 0, so it starts in the queue. (2) Process vertices: each of the V=7 vertices is dequeued and visited exactly once, contributing O(V) = O(7). (3) For each dequeued vertex, examine all its outgoing edges to decrement neighbors' in-degrees: total edge examinations across the whole run = E = 8. (4) Therefore, total complexity = O(V+E) = O(7+8) = O(15). Queue operations (enqueue/dequeue) each cost O(1). Space complexity: O(V) = O(7) for the in-degree array plus the queue. Because the graph has 8/7 ≈ 1.1 average edges per vertex, it is sparse, making the adjacency-list representation optimal.

ExplanationStep-by-step BFS shortest path execution: (1) Initialize: visited set (empty), queue with start vertex X. (2) Process vertices: each vertex is visited exactly once, contributing O(V) = O(12). (3) For each vertex, examine all adjacent edges: total edge examinations = E = 20. (4) Therefore, total complexity = O(V+E) = O(12+20) = O(32). Queue operations (enqueue/dequeue) each cost O(1). Space complexity: O(V) = O(12) for visited set + queue/stack. Because the graph has 20/12 = 1.7 avg edges per vertex, it is sparse, making adjacency list representation optimal.

ExplanationFor DFS-based cycle detection, here is the step-by-step execution: (1) Initialize an empty visited set and an empty recursion stack, then start the traversal at vertex A. (2) Each vertex is visited exactly once as DFS recurses into its unvisited neighbors, contributing O(V) = O(9). (3) For each vertex, all its adjacent edges are examined once, giving total edge examinations = E = 14; a cycle exists whenever DFS reaches a vertex that is already present in the current recursion stack (a back edge). (4) Therefore, total time complexity = O(V+E) = O(9+14) = O(23). Each stack push/pop operation costs O(1) time. Space complexity is O(V) = O(9) for the visited set plus the recursion stack. Since this graph has 14/9 = 1.6 average edges per vertex, it is sparse, making the adjacency-list representation optimal.

ExplanationBellman-Ford's core invariant: after relaxing every edge k times, all shortest paths using at most k edges are guaranteed correct. Since a simple shortest path in a graph with V vertices has at most V−1 edges, the algorithm must relax all E edges across V−1 separate passes to guarantee convergence. Here that's (V−1)×E = (5−1)×8 = 32 relaxation operations, which is O(V×E) = O(5×8) = O(40), since V−1 passes is the same asymptotic order as V passes. The min-heap claim wrongly imports Dijkstra's mechanism — Bellman-Ford never uses a priority queue, and a greedy min-heap approach actually fails on negative edge weights, which is precisely the case Bellman-Ford exists to handle. The single-pass BFS-like claim (O(V+E)) only suffices for a DAG processed in topological order; on a general graph, one pass can miss the true shortest path, so all V−1 passes are required. The brute-force distance-matrix claim confuses Bellman-Ford with a pairwise all-pairs approach — Bellman-Ford never builds or scans a V×V matrix; it only walks the E edges in each of its V−1 passes, so the edge count E is central to its cost, not irrelevant.

ExplanationStep-by-step React render cycle: (1) Initial render: React calls App(), useState initializes count = 0, and React commits the initial VDOM to the real DOM. (2) On each click: setCount(count + 1) schedules a state update inside that click's own event handler invocation. (3) React 18's automatic batching merges multiple state updates only when they occur within the same event handler call; it does not merge updates across separate, sequential click events. (4) Because each click is its own handler invocation, each one independently triggers React to re-run App(), diff the new JSX against the previous VDOM, and commit the change. (5) Across 5 separate clicks, this produces 5 separate re-renders — one per click.

ExplanationReact always runs an effect once after the component's very first commit, regardless of what's in the dependency array — that's run #1, logging count = 0. After every later render, React compares each value in the dependency array to its value from the previous render, and re-runs the effect only if something changed. Click 1 calls setCount(count + 1), changing count from 0 to 1; since 1 differs from 0, the effect re-runs (run #2, count = 1). Click 2 changes count to 2 (run #3), click 3 changes it to 3 (run #4), and click 4 changes it to 4 (run #5). That's 1 mount run plus 4 update runs = 5 total executions. Option A wrongly assumes effects skip the initial mount, but React always fires an effect after the first render commit no matter what dependencies it lists. Option B invents a second execution per click — there is no setState call inside this effect, so it has no way to trigger itself a second time per click. Option D confuses a non-empty dependency array with an empty one: passing [] makes an effect run exactly once (mount only), but passing [count] makes it re-run on mount AND on every subsequent render where count's value differs from before.

ExplanationAuto-fill first decides the column COUNT using each track's minimum size (150px) plus gaps (10px), not the final size. Test n=4: 4×150 + 3×10 = 600 + 30 = 630px, which fits within the 650px container. Test n=5: 5×150 + 4×10 = 750 + 40 = 790px, which exceeds 650px. So the algorithm settles on 4 columns — it never creates 5 or 7. Once the count is fixed at 4, the 1fr in minmax(150px, 1fr) is free to grow: subtract the 3 gaps between 4 columns (650 − 30 = 620px) and divide by 4 columns to get 155px per column (155px ≥ 150px, so the minimum is not violated — minmax() only caps growth from below, it does not freeze the track at its floor). With 4 columns and 7 items, the items wrap after every 4th item: row 1 holds items 1–4, row 2 holds items 5–7, giving 2 rows total. Final answer: 4 columns, 155px each, 2 rows.

ExplanationConvert the memory limit into a byte count first: 128 MiB = 128 × 1,048,576 bytes = 134,217,728 bytes. Since every key-value pair, including overhead, takes exactly 128 bytes, the cache can hold 134,217,728 ÷ 128 = 1,048,576 entries before it is full. Writes arrive at 1024 new unique keys per second, so the cache fills after 1,048,576 ÷ 1024 = 1024 seconds. Only once that limit is reached does allkeys-lru start evicting the least-recently-used key for each further SET — eviction does not start at the very first write, because there is free capacity to fill first. Using decimal megabytes (128,000,000 bytes) instead of the true binary 128 MiB understates capacity to 1,000,000 entries, which would exhaust in about 976.6 seconds — too early, since it uses the wrong byte count for the limit. Dividing the raw byte limit (134,217,728) directly by the write rate without first converting to an entry count gives 131,072 seconds — too late, since it skips accounting for the 128-byte size of each entry. The correct figure accounts for both the byte-to-entry conversion and the binary (not decimal) definition of MiB, giving exactly 1024 seconds.

ExplanationThis _insert method handles all four AVL imbalance cases, not just one: bf > 1 with val < node.left.val is the left-left case, corrected by a single rotateRight; bf < -1 with val > node.right.val is the right-right case, corrected by a single rotateLeft; bf > 1 with val > node.left.val is the left-right case, corrected by rotating node.left left, then rotating node right; and bf < -1 with val < node.right.val is the right-left case, corrected by rotating node.right right, then rotating node left. Because every possible imbalance is caught and fixed immediately after each insertion, the tree's height is always kept within a constant factor of log2(n) — this holds even for strictly ascending input, where each new value would otherwise build a right-leaning chain but is instead caught by the right-right case and rotated back to balance. For n = 100,000, log2(100000) ≈ 16.6, so about 17 levels are visited on a root-to-leaf walk during each insert, giving O(log n) time per insertion.

ExplanationThe black-height rule only counts black nodes along a root-to-leaf path; red nodes are permitted to sit on that same path as long as no red node has a red child. That means the shortest possible path (all black) reflects the true minimum height, about log2(500,001) ≈ 19, while the longest possible path can alternate red and black nodes and run to roughly twice that length, about 2 x log2(500,001) ≈ 38. This 2x factor is the standard worst-case height bound for red-black trees, and it is what keeps insert, search, and delete at O(log n) even though the tree is not as tightly balanced as an AVL tree. Believing the height stays fixed at exactly 19 mistakes the black-height guarantee for a guarantee on total height, when only the black-node count is equalized across paths, not the total node count. Believing sorted-order insertion collapses the tree into a linear chain describes what happens to a plain, unbalanced binary search tree with no rebalancing; red-black insertion specifically performs rotations and color flips (rotateLeft, rotateRight, flipColors) to fix right-leaning red links and split temporary 4-nodes, which prevents that collapse regardless of insertion order. Believing the tree gets a +-1 AVL-style balance factor confuses two different balancing strategies: AVL trees bound height using a strict per-node balance factor, giving a tighter bound near 1.44 x log2 n, while red-black trees use the looser color-based black-height rule instead, which is exactly why their worst-case bound is 2x rather than 1.44x.

ExplanationA* scores every node on the open list with f(n) = g(n) + h(n) and always expands the node with the smallest f-value, since that node offers the best current estimate of total path cost. Computing f for each node: A = 2+9 = 11, B = 8+1 = 9, C = 5+3 = 8, D = 9+10 = 19. Node C has the smallest f-value, 8, so A* expands it next. Picking the node with the lowest g(n) alone (node A, g=2) describes Dijkstra's algorithm, which ignores the heuristic entirely and can waste effort on paths that are cheap so far but far from the goal. Picking the node with the lowest h(n) alone (node B, h=1) describes Greedy Best-First Search, which chases whatever looks closest to the goal while ignoring how expensive it was to reach — this can miss the actual shortest path. Picking the node with the highest combined g(n)+h(n) (node D, 19) has the logic backwards: a higher f-value means a worse estimated total cost, so A* would never prioritize it over a lower one.

ExplanationFor a B-tree of minimum degree t=3, the height h satisfies h = O(log_t n): each internal node holds up to 2t-1 keys and 2t children, so descending one level narrows the search to a subtree containing roughly 1/t of the remaining keys. With n=1,000,000 elements, log_3(1,000,000) is approximately 12.6, which rounds up to a height of 13 levels — the same figure the O(log_t n) bound predicts, with no contradiction between the formula and the count. In the worst case, search costs exactly this height, O(log_t n), because every lookup follows a single root-to-leaf path, and the tree's split/merge rebalancing on insertion and deletion keeps that path length logarithmic no matter the insertion order — unlike an unbalanced binary search tree, which can degrade to O(n) on sorted input.

ExplanationEach edge in the graph can cause at most one pq.push() (the earlier, larger key value for that vertex simply becomes a stale heap entry, later skipped by the `if (inMST[u]) continue;` check). A binary heap holding up to V elements has height O(log V), and inserting a new element only requires sifting it up along one root-to-leaf path -- so each push costs O(log V), not O(1) and not O(V). With E = 5000 edges and log2(1000) approx 10, total heap-insertion work is E x log2V = 5000 x 10 = 50,000 operations. Compare this to the array-based version of Prim's algorithm, which does not use a heap at all: on every one of its V iterations it linearly scans all V vertices to find the current minimum key, costing O(V) per extraction and O(V^2) = 1000 x 1000 = 1,000,000 operations overall. Because this graph is sparse (E = 5000 is far smaller than V^2 = 1,000,000), the heap-based bound of O(E log V) = 50,000 is about 20 times faster than the array-based O(V^2) = 1,000,000. This is exactly why textbooks recommend a binary-heap priority queue for Prim's algorithm on sparse graphs: the true cost driver is E (how many edges actually get relaxed), each paying only O(log V) for its heap insertion -- not a full O(V) rescan of every vertex.

ExplanationFloyd-Warshall's three nested loops each run the full range 0 to V-1 independently of one another, so the total work is V times V times V = V^3; for V=200 that is 200^3 = 8,000,000 relaxation checks. The array-based (no-heap) version of Dijkstra costs O(V^2) for a single source, because finding the nearest unvisited vertex means scanning all V vertices at each of V steps — without a heap there is no O(log V) extraction. Running that O(V^2) procedure once from every one of the V=200 vertices multiplies the per-call cost by the number of calls: V times V^2 = V^3 = 200 times 40,000 = 8,000,000. So both approaches land on the same order, 8,000,000 operations, for this graph. The claim that repeated Dijkstra stays at O(V^2) ignores that it must be run V separate times, one per source; the claim that Floyd-Warshall is O(V^2) misreads its k-loop as a free index lookup when it is a full V-iteration loop just like the other two; and O(log V) minimum extraction requires a heap-based priority queue, not the array-based scan this question specifies.

ExplanationThe tree is a complete binary tree built over the n=100,000 leaves, so its height is ceil(log2(n)) = ceil(log2(100000)) = 17. In _query, each recursive call either returns immediately (node fully outside or fully inside [l,r]) or splits into two calls covering the left and right halves of the current range, so the recursion depth along any explored path is bounded by the tree height, giving O(log n) = O(17) work per query. For 100,000 queries, total operations = 17 per query x 100,000 queries = 1,700,000 operations. Worst case occurs when the query range [l,r] straddles the midpoint at every level (e.g., a range like [1, n-2]), forcing the recursion to branch into both children at each of the 17 levels instead of returning early, but the branching is still bounded by O(log n) per level so the total stays at O(log n) per query rather than degrading further.

ExplanationUnion-find reaches its O(alpha(n)) amortized bound only when both optimizations shown in the code are present together. In find(), the line this.parent[x] = this.find(this.parent[x]) performs full path compression: every node visited on the way to the root is repointed directly to that root, not just halfway. In union(), the three-way comparison on this.rank always attaches the shorter tree beneath the taller one and only increments rank on a tie, which is union by rank; this guarantees no tree can grow taller than needed for its size. Together these two mechanisms are what force the amortized cost per operation down to O(alpha(n)), where alpha is the inverse Ackermann function, an extraordinarily slow-growing function that stays at most 4 for any n up to far beyond 100,000. That gives the worst-case prediction directly: even a sequence of operations deliberately chosen to maximize tree height cannot push a single find or union past this bound once amortized, so for n=100,000 elements a sequence of m operations completes in O(m * alpha(100,000)) = O(4m) total steps rather than O(m log n) or O(mn). This is the precise reason the algorithm is described as "near-constant per operation" while still not being a strict O(1) worst case for every single call.

ExplanationTrie autocomplete reaches its target node by walking one child pointer per prefix character (cost L), then performs a depth-first traversal of only the subtree rooted there to collect matches (cost k, the total characters across matched words) — a total of O(L+k) work that is independent of n, the total number of words stored. For the given inputs, prefix length L=5 and k=20 characters of results gives the average-case figure of 25 operations. The worst case arises not from n directly but from k: if the prefix matches a large fraction of the stored vocabulary — for instance if most of the n=50,000 words share the same 5-character prefix — the matching subtree can contain close to all n words, pushing k up to roughly n. In that scenario, total work approaches O(L+n) = O(5+50,000) ≈ 50,005 operations, roughly 2,000 times the 25-operation average case, even though the O(L+k) form of the bound never changes.