Grade 9 AI & Computer Science Practice Questions — Set 5

ExplanationPivot = arr[4] = 2. i starts at -1. j=0: arr[0]=8 > 2, skip. j=1: arr[1]=3 > 2, skip. j=2: arr[2]=1 <= 2, i=0, swap arr[0] and arr[2] → [1, 3, 8, 5, 2]. j=3: arr[3]=5 > 2, skip. After loop: swap arr[i+1]=arr[1] with arr[4] → [1, 2, 8, 5, 3]. Return i+1 = 1. Pivot 2 is now at index 1, with all elements <=2 to its left and all elements >2 to its right, exactly as the Lomuto partition scheme guarantees.

Explanationarr has 10 elements (indices 0-9). Iteration 1: lo=0, hi=9, mid=(0+9)//2=4, arr[4]=16 < 23, so lo=5. Iteration 2: lo=5, hi=9, mid=(5+9)//2=7, arr[7]=56 > 23, so hi=6. Iteration 3: lo=5, hi=6, mid=(5+6)//2=5, arr[5]=23 == 23, return 5. The target is found at index 5 after just 3 iterations — binary search's halving strategy (10 → 5 → 2 remaining elements) locates it in at most ceil(log2(10)) = 4 comparisons, far fewer than the 6 a linear scan of this array would need.

ExplanationCheck all pairs (i,j) where i<j and arr[i]>arr[j]: (5,3)✓ (5,1)✓ (5,4)✓ (5,2)✓ (3,1)✓ (3,4)✗ (3,2)✓ (1,4)✗ (1,2)✗ (4,2)✓. Total = 7 inversions. Note: max inversions for 5 elements would be C(5,2)=10 (fully reversed). This array has 7 out of that possible 10.

ExplanationString 1 '({[]})': the algorithm pushes '(', '{', '[' onto the stack, then each closing bracket matches the top of the stack in reverse order — ']' pops '[', '}' pops '{', ')' pops '(' — leaving the stack empty, so the function returns True. String 2 '({[}])': '(', '{', '[' are pushed the same way, but the 4th character '}' is checked against the stack top '[', and since pairs['}'] is '{' while stack[-1] is '[', the condition stack[-1] != pairs[ch] is true, so the function returns False immediately without processing the remaining ']' and ')'. String 3 '((()': three '(' are pushed, then ')' pops one of them, leaving two unmatched '(' on the stack when the loop ends; since len(stack) is 2 rather than 0, the function returns False. The three print statements therefore output True, False, and False in that order.

ExplanationTrace comparisons is initialized to 0 and the array starts as [4, 1, 3, 2]. For i=1, key=1 and j=0. The while condition checks arr[0]=4 > 1, which is true, so comparisons becomes 1, 4 shifts right, and j becomes -1. The loop now stops because j < 0, so the post-loop check (if j >= 0) does not add anything. Key 1 is placed at index 0: array is [1, 4, 3, 2]. Running total: 1. For i=2, key=3 and j=1. The while condition checks arr[1]=4 > 3, true, so comparisons becomes 2, 4 shifts right, j becomes 0. The while condition checks arr[0]=1 > 3, false, so the loop exits with j=0 still >= 0. The post-loop check fires, adding one more: comparisons becomes 3. Key 3 is placed at index 1: array is [1, 3, 4, 2]. Running total: 3. For i=3, key=2 and j=2. The while condition checks arr[2]=4 > 2, true, so comparisons becomes 4, 4 shifts right, j becomes 1. The while condition checks arr[1]=3 > 2, true, so comparisons becomes 5, 3 shifts right, j becomes 0. The while condition checks arr[0]=1 > 2, false, so the loop exits with j=0 still >= 0. The post-loop check fires, adding one more: comparisons becomes 6. Key 2 is placed at index 1: array is [1, 2, 3, 4]. Running total: 6. The function returns 6, and since arr is the same list object as data (Python passes the reference, and every update uses in-place indexing like arr[j+1] = arr[j]), the caller's data list is also sorted. The two printed lines are 6 and [1, 2, 3, 4]. The count of 4 undercounts by ignoring that a loop which exits because arr[j] is no longer greater than key still performed one real comparison — the failing one — which the post-loop check exists specifically to record. The count of 7 overcounts by assuming that check always fires, but when the key shifts all the way past every earlier element (as happens for the very first insertion here), j ends at -1 and there is no arr[j] left to compare against, so no stopping comparison is recorded for that insertion.

ExplanationDog.speak() overrides Animal.speak(), returning 'Rex barks'. Cat has no speak() method, so Python looks up the MRO to Animal.speak(), returning 'Whiskers makes a sound'. Animal('Bird').speak() returns 'Bird makes a sound'. This is polymorphism: the same method call .speak() produces different results depending on the actual class of the object. Cat inherits everything from Animal since it uses pass.

ExplanationTrace: stack=[A]. Pop A, visited=[A], push reversed(['B','C'])=['C','B'], stack=[C,B]. Pop B, visited=[A,B], push reversed(['D','E'])=['E','D'], stack=[C,E,D]. Pop D, visited=[A,B,D], no neighbors, stack=[C,E]. Pop E, visited=[A,B,D,E], no neighbors, stack=[C]. Pop C, visited=[A,B,D,E,C], push reversed(['F'])=['F'], stack=[F]. Pop F, visited=[A,B,D,E,C,F]. The reversed() call ensures each node's neighbors are pushed in reverse order, so the first-listed neighbor lands on top of the stack and is popped first — giving the same left-to-right traversal order as recursive DFS.

ExplanationTrace through 'aaabbbccaa': i=1: a==a, count=2. i=2: a==a, count=3. i=3: b≠a, append 'a3', count=1. i=4: b==b, count=2. i=5: b==b, count=3. i=6: c≠b, append 'b3', count=1. i=7: c==c, count=2. i=8: a≠c, append 'c2', count=1. i=9: a==a, count=2. After loop: append 'a2'. Result: 'a3b3c2a2'. The algorithm treats consecutive runs independently — the two 'a' groups are separate because they are not adjacent.

ExplanationTrace the algorithm with max_sum = current = -2 (the first element). For x=-3: current = max(-3, -2 + -3) = max(-3, -5) = -3, so max_sum stays -2. For x=4: current = max(4, -3 + 4) = max(4, 1) = 4, so max_sum becomes 4. For x=-1: current = max(-1, 4 + -1) = 3, max_sum stays 4. For x=-2: current = max(-2, 3 + -2) = 1, max_sum stays 4. For x=1: current = max(1, 1 + 1) = 2, max_sum stays 4. For x=5: current = max(5, 2 + 5) = 7, so max_sum updates to 7. For x=-3: current = max(-3, 7 + -3) = 4, max_sum stays 7. The final answer is 7, matching the contiguous run [4, -1, -2, 1, 5] (4 - 1 - 2 + 1 + 5 = 7). The key insight is the line `current = max(x, current + x)`: the running sum only restarts at the current element when extending the previous run would make things worse, not simply whenever a negative number appears — that is why the dip through -1 and -2 stays inside the winning subarray instead of breaking it. Picking just the largest single number ignores that combining it with a nearby run can score higher, and summing all positive numbers ignores the requirement that the elements be contiguous.

ExplanationPython dict iteration follows insertion order, so the outer loop calls dfs('A') first, then dfs('B'), dfs('C'), dfs('D') — though only dfs('A') and dfs('D') do real work, since 'B' and 'C' get visited during A's recursion. dfs('A') recurses into 'B' (via graph.get('A', [])), which recurses into 'C' (via graph.get('B', [])); 'C' has no neighbors, so it is appended first, giving result=['C']. Returning up, 'B' is appended (result=['C','B']), then 'A' is appended (result=['C','B','A']). The outer loop's next calls, dfs('B') and dfs('C'), return immediately because both nodes are already in visited — a revisit simply triggers the early-return guard, not an error or infinite recursion. The call dfs('D') then runs: graph.get('D', []) = ['C'], so it calls dfs('C'), which returns immediately since 'C' is visited, and then 'D' is appended, giving result=['C','B','A','D']. Reversing this list with result[::-1] produces the printed output ['D','A','B','C']. This ordering respects every edge in the graph (A before B, B before C, D before C), but it is only one of several orderings that would be mathematically valid — a different valid ordering is not automatically what this exact code prints, since the output is fixed by the specific traversal order the code follows.

ExplanationTrace insertions: push(5): data=[5]. push(3): data=[5,3], sift_up: 3<5 → swap → [3,5]. push(8): data=[3,5,8], 8>3 → no swap. push(1): data=[3,5,8,1], sift_up: i=3, parent=1, 1<5 → swap → [3,1,8,5], i=1, parent=0, 1<3 → swap → [1,3,8,5]. push(4): data=[1,3,8,5,4], i=4, parent=1, 4>3 → stop. Final: [1,3,8,5,4]. Root (index 0) is always the minimum. The heap is NOT fully sorted — it only guarantees parent ≤ children. The heap-order property ensures correctness because the parent is always smaller than or equal to its children.

Explanationcount_paths(None, 3, 3) counts paths from (0,0) to (3,3) in a grid, moving only down (r-1) or right (c-1). Base case: any cell in row 0 or column 0 has exactly 1 path. The total equals C(r+c, r) = C(6, 3) = 20. Verification: count_paths(3,3) = count_paths(2,3) + count_paths(3,2). The recursion builds Pascal's triangle: row/col 0 all 1s, each interior cell = sum of cell above + cell to the left. The grid of values: [1,1,1,1], [1,2,3,4], [1,3,6,10], [1,4,10,20]. Answer: 20.

ExplanationIn the first call, prefix starts as 'classroom'. Comparing it against 'classify' inside common_prefix, the two strings match at the first five positions — c, l, a, s, s — and disagree at the sixth character, where 'classroom' has 'r' and 'classify' has 'i'. So the inner while loop stops with i = 5, and common_prefix returns 'classroom'[:5], which is 'class'. That value becomes the new prefix. Comparing 'class' against 'class' next, every character matches all the way through (i reaches 5, the length of both strings), so the prefix stays 'class', and lcp returns 'class' for the first print. In the second call, prefix starts as 'apple'. Comparing it against 'banana', the very first characters already disagree ('a' vs 'b'), so the while loop body never executes and common_prefix returns 'apple'[:0], an empty string. Since prefix is now empty, the function returns '' immediately — 'cherry' is never even examined. So the second print shows an empty string. The key idea is that common_prefix only ever shrinks the prefix by comparing it pairwise against each next string, and a mismatch at position i means exactly i characters matched before that point.

ExplanationThe list is 1→2→3→4→5 with the tail node e (value 5) looping back to c (value 3), forming the cycle 3→4→5→3. Tracing the pointers: after the first iteration slow sits at value 2 and fast at value 3 (no match); after the second iteration slow is at value 3 and fast is at value 5 (no match); after the third iteration slow advances to value 4 and fast also lands on value 4, so slow == fast fires and the function returns True. This works because once both pointers are inside the cycle, fast reduces its distance to slow by exactly one node per iteration, guaranteeing a collision without ever needing to know the cycle's length in advance. The comparison succeeds because slow and fast end up referencing the identical Node object, and Python's default object equality is identity-based, not dependent on how many other nodes point to it. Nothing here raises an error either — print() just displays the boolean that detect_cycle returns, since the algorithm is a simple iterative while loop that never attempts to print or recurse over the linked list itself.

ExplanationItems: (w=2,v=3), (w=3,v=4), (w=4,v=5), (w=5,v=6). Capacity=5. DP builds a table where dp[i][w] = max value using the first i items with capacity w. Key cells: dp[1][2]=3, dp[2][3]=4, dp[2][5]=7 (take both items 1 and 2: 2+3=5, 3+4=7), dp[3][4]=5, dp[3][5]=max(dp[2][5]=7, item3+dp[2][1]=5+0=5)=7, dp[4][5]=max(dp[3][5]=7, item4+dp[3][0]=6+0=6)=7. The optimal solution picks items 1 and 2 (weights 2+3=5, values 3+4=7), which beats taking the single item of weight 5 (value 6). The recurrence considers both including and excluding the current item because each item can either contribute to the optimal solution or not.

ExplanationThe monotonic deque maintains indices in decreasing value order. Trace with k=3: i=0(1): dq=[0]. i=1(3): pop 0 (1≤3), dq=[1]. i=2(-1): dq=[1,2], i≥2 → result=[3]. i=3(-3): dq=[1,2,3], dq[0]=1 ≤ 3-3=0? No. result=[3,3]. i=4(5): pop 3,2,1 (all ≤5), dq=[4], result=[3,3,5]. i=5(3): dq=[4,5], result=[3,3,5,5]. i=6(6): pop 5,4, dq=[6], result=[3,3,5,5,6]. i=7(7): pop 6, dq=[7], result=[3,3,5,5,6,7]. The deque ensures O(n) total time because each index is pushed and popped at most once.

ExplanationIn a URL, everything after '?' is the query string. The '&' character separates multiple key-value pairs. So '?genre=science&grade=9' gives two parameters: genre=science and grade=9. In Express.js: req.query gives {genre: 'science', grade: '9'}. In Flask: request.args.get('genre'). Query strings are visible in the URL (unlike POST body data), making them ideal for filters, searches, and pagination in GET requests. They are also bookmarkable and cacheable.

ExplanationBFS uses a queue (FIFO). Start: enqueue Delhi (level 0). Dequeue Delhi → enqueue its unvisited neighbors: Jaipur, Agra, Lucknow (all level 1, because they are directly connected). Dequeue Jaipur → enqueue Ahmedabad (level 2, since Delhi already visited). Dequeue Agra → enqueue Kanpur (level 2, because Delhi visited). Dequeue Lucknow → Kanpur already queued. Dequeue Ahmedabad → Jaipur visited. Dequeue Kanpur → all visited. This produces the result [Delhi, Jaipur, Agra, Lucknow, Ahmedabad, Kanpur] because BFS guarantees shortest path in unweighted graphs — Kanpur is exactly 2 hops from Delhi via either Agra or Lucknow.

ExplanationinnerHTML interprets the assigned string as HTML markup. When the HTML parser encounters a <script> element inserted this way, browsers intentionally refuse to execute it — per the HTML5 specification, script elements created via innerHTML are marked non-executing, so the exact alert("hacked") payload shown here would not actually fire. This is a common misconception, and the code is still a genuine XSS vulnerability: innerHTML will happily render and execute any other event-handler-based payload, such as '<img src=x onerror=alert(1)>' or '<svg onload=alert(1)>', neither of which uses a script tag at all. The fix is the same either way: use textContent (node.textContent = studentScore), which treats the value as plain text and never parses it as HTML, or use a sanitization library like DOMPurify when HTML rendering is genuinely required. XSS is ranked among the OWASP Top 10 web application vulnerabilities.

ExplanationDijkstra's greedy approach finalizes nodes in order of increasing distance. Once a node is finalized, its shortest distance is set permanently. With negative edges, a later-discovered path through a negative edge could reduce an already-finalized distance — but Dijkstra's never rechecks finalized nodes. Example: A→B=5, A→C=2, C→B=-4. Dijkstra finalizes B at distance 5, but the actual shortest is A→C→B = 2+(-4) = -2. Bellman-Ford relaxes all edges V-1 times, catching these cases. It also detects negative cycles (infinite shortest path).