Grade 8 AI & Computer Science Practice Questions — Set 2

ExplanationFirst, linear search iterates through every element, requiring up to n comparisons in the worst case. For 1000 items, this is 1000 comparisons. Then, binary search halves the search space each time, requiring at most log₂(1000) ≈ 10 comparisons. For finding element 999 in a sorted list, binary search is dramatically faster. Use linear search when: data is unsorted, list is small (< 50 items), or you need to find all matches. Use binary search when: data is sorted and list is large. Option B misses the exponential difference. Option C reverses the complexity. Option D is false; binary search handles duplicates fine; it just may not return the first occurrence without modification. For a 1000-item sorted list, that 1000-versus-10 gap is exactly why production code defaults to binary search once a collection is sorted and searched repeatedly.

ExplanationThe sorted() function with a key parameter sorts elements based on a computed value rather than the elements themselves. key=lambda x: x[1] extracts the second element (the grade) from each tuple for comparison, so the tuples are compared using 95, 87, and 92. Sorting these grades in ascending order gives 87, 92, 95; with reverse=True, that order is flipped to descending: 95, 92, 87. Mapping these grades back to their tuples produces [('Alice', 95), ('Charlie', 92), ('Bob', 87)]. The key function only controls the comparison — it does not leave the tuples unmodified in their original positions, which rules out the claim that sorted_students equals the original list. The reverse=True argument flips the ascending order the key produces; it is not silently ignored, which rules out the claim that the result stays ascending. And key=lambda x: x[1] indexes the second element of each tuple (the grade), not the first element (the name), which rules out the name-based, reverse-alphabetical ordering. Descending order by grade is the only result consistent with how sorted(), key, and reverse=True actually interact here.

ExplanationFirst, the retry function attempts func() up to 3 times. If it succeeds, return immediately. Then, if it raises an exception: check if this is the last attempt (attempt == 2, since range(3) = 0,1,2). If not the last, pass and retry. If it is the last attempt, re-raise the exception. This pattern is useful for operations that fail temporarily (network requests, database connections). For example, a network request might timeout once but succeed on retry. The function maintains the last exception by re-raising if all attempts fail. Option B is false; it limits to max_attempts. Option C is false; it re-raises on final attempt. Option D is false; it catches all exceptions. Finally, understanding retry patterns is important for robust distributed systems.

ExplanationUnion by rank alone (keeping trees balanced by attaching the smaller tree under the larger one's root) already caps every find at O(log n), since tree height never exceeds log n. Path compression adds an extra boost on top of that: every time find() walks a path to the root, it re-points every node on that path directly to the root, so future finds along that path become instant. Combining both gives a result proven by Tarjan: the amortized cost per operation, averaged over any long sequence of operations, is O(α(n)), where α is the inverse Ackermann function. α(n) grows so unbelievably slowly that it stays at 4 or less for any n up to numbers far larger than the count of atoms in the observable universe (~10^80) — which is why union-find operations feel like O(1) in every real program. But mathematically α(n) is still not a true constant: it does keep growing, without any fixed upper bound, as n grows without limit, so the honest tight bound is written O(α(n)), not O(1). Option A is wrong because it ignores the extra speedup path compression provides beyond what union by rank achieves alone — together they beat plain O(log n). Option C overclaims exact O(1): compression flattens only the specific path already walked, so a fresh find down a path that hasn't been visited yet (e.g., after new unions extend the structure) still takes more than one step. Option D is wrong because path compression only updates the parent pointers of the nodes actually lying on the current search path from a node to its root — it never touches the other, unrelated elements in the structure.

ExplanationProduct except self uses prefix/suffix products. Standard approach: compute left[i] and right[i] arrays, where left[i] = product of elements before i, right[i] = product of elements after i, and result[i] = left[i] * right[i]. For [1,2,3,4]: left=[1,1,2,6], right=[24,12,4,1], result=[24,12,8,6]. That approach is O(n) time and O(n) space for the left/right arrays. The space-optimized version reuses the result array to hold left products, then multiplies in the right products on the fly during a reverse pass. Initialize result[0]=1. Forward pass: result[i]=result[i-1]*nums[i-1], giving result=[1,1,2,6]. Reverse pass: start right=1; for i from 3 down to 0, result[i]*=right, then right*=nums[i]. Starting at i=3: result[3]=6*1=6, right becomes 4. At i=2: result[2]=2*4=8, right becomes 12. At i=1: result[1]=1*12=12, right becomes 24. At i=0: result[0]=1*24=24, right becomes 24. Final result=[24,12,8,6], matching the direct computation and confirming result[1]=12. This runs in O(n) time using only O(1) extra space beyond the output array. Option B relies on division, which breaks when the array contains a zero (or more than one zero, where every product becomes zero but division is undefined). Option A's nested-loop approach avoids division but costs O(n²) time, which the O(1)-space forward/reverse-pass method does not require. Option D's claim that sorting is needed is false and would also destroy the original index order needed for the result.

ExplanationInteger break is solved with a calculus-flavored insight: for a fixed number of equal parts k, the product (n/k)^k is maximized when each part equals e ≈ 2.718. Since the parts must be positive integers, 3 is the closest integer to e, so breaking n into mostly 3s maximizes the product (3 beats 2 as a building block because 3^(1/3) ≈ 1.442 exceeds 2^(1/2) ≈ 1.414 — cube roots of 3 outproduce square roots of 2 per unit of n used). This gives the rule: divide n by 3. If the remainder is 0, use all 3s. If the remainder is 2, keep one extra part of 2. If the remainder is 1, don't leave a lonely 1 (since 3×1=3 is wasteful) — instead combine it with one 3 to make a 4 (since 3+1=4 and keeping them together gives 4 > 3×1). For n=10: 10 mod 3 = 1, so use two 3s and one 4 instead of three 3s and a 1, giving 10 = 3+3+4 and product 3×3×4 = 36. This mathematical approach runs in O(1) time, versus O(n²) for the bottom-up DP where DP[i] = max over j of j×(i−j) and j×DP[i−j].

ExplanationPython's operator precedence evaluates ** (exponentiation) before * (multiplication), which in turn is evaluated before + (addition). Applying this to a + b * c ** 2 with a=3, b=4, c=2: first c ** 2 = 4, then b * 4 = 16, and finally a + 16 = 19. So result stores 19. Treating + and * as equal precedence, reversing * and **, or evaluating strictly left to right with no precedence at all each produce a different (incorrect) value — 28, 67, and 196 respectively — which is why memorizing the precedence order (** > * > +) rather than reading left to right matters.

ExplanationFirst, binary search halves the search space with each comparison, achieving O(log n) complexity. For 1,000,000 elements: after 1 comparison → 500,000, after 2 → 250,000, ... Then, after 20 → ~1 element. Worst case = ⌈log₂(1,000,000)⌉ = 20 comparisons. This is exponentially faster than linear search's 500K comparisons. The misconception in option C (1,000,000) comes from confusing binary search with linear search—binary doesn't check every element. Option D's √n estimate applies to block/jump search, not binary search. This is fundamental to understanding logarithmic time complexity: doubling the input size only adds 1 comparison.

ExplanationAppend mode ('a') creates the file if it doesn't exist, then appends each write to the end of whatever is already there. The first `with` block opens log.txt, creating it, and writes 'entry1\n'. The second `with` block reopens the same file in append mode and adds 'entry2\n' after the existing text rather than erasing it, so the file now holds 'entry1\nentry2\n' — exactly what the read call returns. The claim that append mode needs the file to pre-exist is wrong, since 'a' creates missing files automatically. The claim that the file gets overwritten each time it is opened describes write mode ('w'), not append mode. The claim that the second write fails silently is also wrong: both writes succeed, and their output accumulates in the file rather than one of them being dropped.

ExplanationWhen divide(10, 0) runs, a / b raises a ZeroDivisionError, so the except ZeroDivisionError block catches it and sets up a return value of -1. Before that return actually happens, the finally block always executes, printing 'cleanup'. Only after finally completes does the function actually return -1, so the printed output is 'cleanup' followed by -1. Believing the except block returns before finally runs reverses the real order, since finally always executes on the way out of a try statement regardless of whether a return is pending. Believing finally overrides the return value confuses running side-effect code with replacing a value — that only happens if finally itself contains a return statement, which this one does not. Believing the program crashes ignores that the except clause already handled the ZeroDivisionError, so nothing is left unhandled by the time finally runs.

ExplanationFirst, int('abc') raises ValueError, so the inner except catches it, prints 'inner caught', and then raises RuntimeError('converted'). That new RuntimeError propagates out of the inner try block into the outer except, which catches it, prints 'outer caught: converted', and then the function returns 'done', which print(risky()) displays. Raising a different exception type from inside an except block is valid Python — the newly raised exception simply propagates outward like any other. The claim that the outer except can't catch it because RuntimeError differs from ValueError is wrong, since the outer except is written specifically to catch RuntimeError. The claim that this kind of re-raise crashes the program is also wrong — Python permits raising a new exception from within an except block, and it gets caught normally by any matching handler further out. The idea that the inner print gets skipped is wrong too — it runs before the raise, not after. So the actual trace is: 'inner caught', then 'outer caught: converted', then 'done'.

Explanationevens(10) walks i from 0 to 9 and yields only the values where i % 2 == 0, producing 0, 2, 4, 6, 8. squared() then consumes that generator one value at a time and yields x ** 2 for each: 0²=0, 2²=4, 4²=16, 6²=36, 8²=64. Wrapping the chained generators in list() forces evaluation and collects [0, 4, 16, 36, 64], since evens() filters before squared() transforms. The claim that squared() ignores the evenness filter and squares every value from 0 to 9 skips the filtering step entirely. The claim that the pipeline halts after one value misunderstands how yield behaves inside a for-loop — it pauses and resumes each iteration rather than exhausting after the first. The claim that every value is squared first and evens are filtered afterward reverses the actual call order, since evens(10) is the innermost generator that squared() consumes first.

ExplanationFirst, identify the odd numbers in [1, 2, 3, 4, 5]: 1, 3, 5. Squaring each gives 1, 9, 25, which sum to 35 for both gen_sum and list_sum. Generator expressions (parentheses) use lazy evaluation, yielding values on-demand with minimal memory, while list comprehensions (square brackets) use eager evaluation, building the full list immediately — but both traverse every matching element, so neither skips values nor doubles them. The claim that generators halt after the first match is wrong: generators evaluate every element that satisfies the filter, exactly like list comprehensions. The claim that sum() cannot accept a generator directly is wrong: sum() consumes any iterable, generators included, with no wrapping needed. The claim that list comprehensions double each squared value is wrong: squaring happens exactly once per element, giving 35, not 70. The only real difference between the two approaches is memory efficiency, not the final result.

Explanationzip(fruits, prices) pairs items positionally: ('apple', 40), ('mango', 90), ('kiwi', 150). enumerate(..., start=1) then numbers these pairs starting from 1, giving (1, ('apple', 40)), (2, ('mango', 90)), (3, ('kiwi', 150)). The loop unpacks each as i, (fruit, price), so the second iteration has i=2, fruit='mango', price=90 — printing "2. mango - Rs.90". The choice "1. mango - Rs.90" wrongly assumes enumerate ignores the start=1 argument and begins counting from 0 anyway. The choice "2. kiwi - Rs.90" keeps the correct index but mismatches the fruit, as if the pairing had shifted forward by one position — kiwi is actually the THIRD pair (i=3), not the second. The choice "2. mango - Rs.150" keeps the correct fruit but takes the price from the next pair instead — 150 is the price zip() paired with kiwi, not mango. Only one line — "2. mango - Rs.90" — is consistent with how zip() forms pairs positionally and how enumerate(start=1) numbers them.

ExplanationInorder traversal visits the left subtree, then the node itself, then the right subtree. For root=2 with left=1 and right=3: inorder(2) = inorder(1) + [2] + inorder(3). Since nodes 1 and 3 are leaves, inorder(1) = [1] and inorder(3) = [3], so the full result is [1] + [2] + [3] = [1, 2, 3] — this matches because the tree happens to be a valid BST, and inorder traversal of a BST always yields sorted values. The claim of an empty output is wrong because the base case (node is None) only halts recursion past a leaf's missing children — it does not prevent real node values from being collected further up. The claim of [2, 1, 3] is wrong because it places the root's value before visiting the left subtree, which describes preorder, not inorder. The claim of [1, 3, 2] is wrong because it visits the right subtree before placing the root's value, breaking the required left-root-right order.

ExplanationTracing gcd(48, 18): 48 % 18 = 12, so the pair becomes (18, 12); 18 % 12 = 6, so the pair becomes (12, 6); 12 % 6 = 0, so the pair becomes (6, 0) and the loop exits, returning 6. For the lcm call, gcd(12, 8) is traced the same way: 12 % 8 = 4 gives (8, 4), then 8 % 4 = 0 gives (4, 0), so gcd(12, 8) = 4, and lcm(12, 8) = 12 * 8 // 4 = 96 // 4 = 24. So the program prints 6 and then 24. The modulo version needs so few iterations because a single division can cut a number down to a small fraction of its previous size, whereas subtracting the smaller number over and over only chops off one small piece per step — for a big size gap between a and b, that difference means a handful of modulo steps versus a much longer run of subtractions. The claim that the loop halts as soon as a value first drops below the previous b skips real iterations of the while loop and stops before b actually reaches 0. The claim that lcm is just the raw product ignores the division by gcd(a, b) that the return statement performs. The claim that % is internally just repeated subtraction misdescribes how division-based remainder computation works, and it is exactly why the loop runs in O(log n) rather than O(n) in the first place.

ExplanationFirst, sum_tree(root): node.value=5 + sum_tree(left) + sum_tree(right). sum_tree(left=3): 3+sum_tree(None)+sum_tree(None)=3+0+0=3. Then, sum_tree(right=7): 7+0+0=7. Total: 5+3+7=15. The recursion adds the current node's value, then recurses into the left and right subtrees and sums all the results — that is why stopping at the root gives too small a total, counting children instead of summing their values gives 10, and doubling each value would only make sense if the function added node.value twice, which it does not.

ExplanationBFS adds each vertex to the queue exactly once, so vertex processing costs O(V). For every vertex it dequeues, BFS scans that vertex's adjacency list, and across the whole graph each edge is examined at most twice (once from each endpoint), so edge processing costs O(E). Queue operations (popleft, append) and set operations (add, membership check) all run in O(1). Adding these costs together gives a total time complexity of O(V + E), which is optimal for unweighted shortest-path search. The claim of O(log V) is wrong because BFS never performs a binary search -- it explores neighbors level by level. The claim of O(V squared) is wrong because BFS does not compare every pair of vertices; it only visits each vertex's actual neighbors. The claim of O(E) alone is wrong because it ignores the O(V) cost of dequeuing and tracking each vertex.

ExplanationMerge sort's auxiliary space is O(n): at every level of merging, the temporary result/left/right arrays built across all merge calls at that level total O(n) elements, and this O(n) figure does not stack across levels because memory from finished lower-level merges is freed as recursion unwinds. The recursion itself adds only an O(log n) call stack, which is smaller than the O(n) term and does not multiply against it. The in-place claim is wrong because merge() explicitly builds new list objects (result, and the slices left, right) instead of reusing arr. The exponential O(2^n) claim is wrong because the recursion tree has depth O(log n), not enough branching to produce exponential space. The O(n log n) claim is wrong because it treats space as accumulating across every recursion level simultaneously, rather than recognizing that each level's arrays are released before the next level needs them. The correct total auxiliary space is therefore O(n), dominated by the temporary merge arrays rather than the smaller O(log n) recursion stack.

ExplanationFirst, sorted() with key=lambda x: x[1] sorts by score, and reverse=True sorts in descending order: 92 > 85 > 78 = Bob > Alice > Charlie. The list comprehension extracts names: ['Bob', 'Alice', 'Charlie']. The reverse parameter flips the entire sort order, not just particular elements. Option A's misconception: reverse=True applies to the key function's values (scores), not the original dictionary order. Option C's misconception: sorted() fully respects the reverse parameter for dictionary items; the parameter is not ignored. Option D's misconception: reverse swaps the entire sorted sequence, not just endpoints. The combination of key and reverse enables flexible sorting: any attribute in any order.