Programming, Data Structures and Algorithms using Python · Quiz 1 · Jan 2025

**Step 1:** Python uses zero-based indexing. The initial call uses positions 1 and 3, containing 2 and 4; swapping gives [1,4,3,2,5,6]. **Step 2:** The recursive call uses (2,2). Its condition s1<s2 is false, so no further changes occur. Only the inclusive sublist from index 1 through 3 is reversed. **Answer: A — [1,4,3,2,5,6].** A: **Correct:** This is the result of swapping positions 1 and 3. B: **Incorrect:** The function reverses only the specified segment, not the whole list. C: **Incorrect:** This would swap positions 1 and 2 rather than 1 and 3. D: **Incorrect:** The initial condition is true, so the list does change.

**Step 1:** Dominant growth rates are \(f_1=\Theta(n^2), f_2=\Theta(n), f_3=\Theta(\log\log n), f_4=\Theta(\log n), f_5=\Theta(n\log n)\). In f2 the linear term eventually exceeds the squared logarithm. **Step 2:** Therefore the increasing order is \(f_3,f_4,f_2,f_5,f_1\). **Answer: D — f3, f4, f2, f5, f1.** A: **Incorrect:** This puts quadratic f1 before n log n f5. B: **Incorrect:** This puts logarithmic f4 after faster-growing polynomial terms. C: **Incorrect:** This reverses log log n and log n, and also reverses f1 and f5. D: **Correct:** All five functions are in increasing asymptotic order.

**Step 1:** This is exponentiation by squaring. If the remaining exponent is odd, multiply the accumulator by the current base; square the base and replace the exponent by its integer half. **Step 2:** The invariant is accumulator times current-base raised to remaining-exponent equals the original \(a^n\). At exponent zero, the accumulator is the answer. The exponent halves each time, giving \(\Theta(\log n)\) iterations for positive n. **Answer: C — Computes \(a^n\) in \(O(\log n)\) arithmetic operations.** **Convention note:** Assume n is a nonnegative integer and arithmetic operations have unit cost. Python arbitrary-precision multiplication has a size-dependent cost. As a pure upper bound, O(n) is also true; the intended choice gives the tight iteration count. A: **Incorrect:** It computes a power, not a factorial. B: **Incorrect:** The power is correct, but linear is a loose rather than tight bound. C: **Correct:** Both the power and the tight operation-count bound are correct. D: **Incorrect:** The accumulator selects powers according to binary exponent bits; it does not add a power series.

**Step 1:** At outer-loop index i, the inner loop compares positions i+1 through n−1, making exactly n−i−1 element comparisons. **Step 2:** The total is \((n-1)+(n-2)+\cdots+1=n(n-1)/2\), independent of values, initial order or swaps. **Answer: C — The number of comparisons is the same irrespective of the order of the .** A: **Incorrect:** Ascending order does not shorten the fixed inner scans. B: **Incorrect:** Descending order has the same count as every other order. C: **Correct:** The loop bounds alone determine the comparison count. D: **Incorrect:** Changing minpos or performing a swap does not change the inner-loop length.

**Step 1:** A shift occurs only when a preceding element is larger than the current key. The number of shifts equals the number of inversions. **Step 2:** Ascending input has no inversions, so zero shifts is the minimum. Descending distinct input has the maximum n(n−1)/2 shifts. **Answer: B — The number of shifts is minimum when the input list is in ascending order..** A: **Incorrect:** A terminating failed element comparison can occur without any corresponding shift. B: **Correct:** No preceding element exceeds the current key in ascending input. C: **Incorrect:** Descending order maximizes shifts for distinct elements. D: **Incorrect:** The inversion count depends directly on input order.

**Step 1:** Merge sort divides into two roughly equal halves and merges their sorted results in linear time: \(T(n)=2T(n/2)+\Theta(n)\). **Step 2:** There are \(\Theta(\log n)\) levels, each with total linear merging work. Worst-case time is \(\Theta(n\log n)\). **Answer: C — \(O(n\log n)\).** **Convention note:** Choose the tightest listed bound; Big-O notation also permits larger, loose upper bounds. A: **Incorrect:** A single level is linear; all recursion levels must be counted. B: **Incorrect:** \(n^2\log n\) is an unnecessarily loose upper bound. C: **Correct:** This is the tight worst-case bound. D: **Incorrect:** Quadratic is an upper bound but not the tight growth rate.

**Step 1:** Choosing the median value ensures balanced subproblems. Linear-time median finding plus partitioning still costs \(\Theta(n)\) per level, yielding \(\Theta(n\log n)\). **Step 2:** Choosing the last element of an already sorted distinct list always picks an extreme value. The remaining sizes are n−1 and 0, yielding \(\Theta(n^2)\). **Answer: D — I: \(O(n\log n)\); II: \(O(n^2)\).** **Convention note:** Complexities are interpreted as tight growth bounds, under the stated linear-time median selection. A: **Incorrect:** The median case is balanced, so its tight bound is not quadratic. B: **Incorrect:** Both claimed tight bounds are wrong. C: **Incorrect:** The last-element case is quadratic on sorted input. D: **Correct:** The median case is n log n and the last-element case is quadratic.

**Step 1:** A stack reverses character order, allowing a palindrome check, and matches the most recent unmatched opening parenthesis with a closing one. Statements 1 and 2 are true. **Step 2:** Ordinary printer spooling processes requests in arrival order using a FIFO queue. A LIFO stack is not the standard structure for statement 3. **Answer: C — Statement 1 and Statement 2 are true.** A: **Incorrect:** Statement 3 is false, and this omits true statement 2. B: **Incorrect:** Statement 3 is false, and this omits true statement 1. C: **Correct:** These are the two standard stack applications. D: **Incorrect:** Printer spooling makes statement 3 false under the intended FIFO policy.

**Step 1:** Follow the smallest unvisited neighbor recursively: 2→1→4→5→6→3. At 3 all neighbors are visited, so return to 6. **Step 2:** Vertex 6 next visits 7. Backtracking completes the traversal, giving 2,1,4,5,6,3,7. **Answer: B — 2,1,4,5,6,3,7.** A: **Incorrect:** After 4, DFS must choose unvisited neighbor 5; there is no edge 4–3. B: **Correct:** This follows every recursive choice and the smallest-neighbor rule. C: **Incorrect:** At 6, unvisited neighbor 3 must be chosen before 7. D: **Incorrect:** After reaching 1 from 2, its next unvisited neighbor is 4, not 6.

**Step 1:** After the first loop, Q=[A,C,E] front-to-rear and S=[B,D,F] bottom-to-top. Transferring all three queue elements gives S=[B,D,F,A,C,E], Q=[]. **Step 2:** Popping twice appends E then C to Q, so Q=[E,C], S=[B,D,F,A]. The final dequeue returns E and final pop returns A. **Answer: A — E A.** A: **Correct:** The queue yields E and the stack yields A. B: **Incorrect:** The queue front is E, and the stack top is A. C: **Incorrect:** The stack value A is correct, but the queue value is E. D: **Incorrect:** The queue value E is correct, but the stack top is A.

**Step 1:** With head and tail references, prepend by updating head, append through tail, and remove the first node by moving head to head.next. Each uses a fixed number of pointer changes. **Step 2:** Removing the tail requires finding its predecessor, since links point only forward. Searching for an arbitrary value also may scan the entire list, so both have linear worst-case time. **Answer: A, B, C — Insertion of the new node at the front of the linked list.; Insertion of the new node at the end of the linked list.; Deletion of the first node of the linked list..** A: **Correct:** Update new.next and head in constant time. B: **Correct:** Attach through tail and update tail in constant time. C: **Correct:** Advance head once; update tail too if the list becomes empty. D: **Incorrect:** Finding the predecessor of the tail requires a traversal in the worst case. E: **Incorrect:** The desired value may be at the end or absent.

**Step 1:** A connected graph on six vertices needs at least five edges, so its degree sum must be even and at least 10. **Step 2:** The all-2 sequence is realized by a 6-cycle. For (1,1,2,2,3,5), connect the degree-5 vertex to all others, then add two edges forming a length-2 path among the residual degrees (0,0,1,1,2). **Answer: B, C — (2,2,2,2,2,2) and (1,1,2,2,3,5).** A: **Incorrect:** Its degree sum is 6, giving only three edges, insufficient for connectedness. B: **Correct:** A cycle on six vertices is connected and has every degree equal to 2. C: **Correct:** The universal-vertex construction gives exactly this sequence and is connected. D: **Incorrect:** Its degree sum is 13, which is odd and violates the handshaking lemma.

**Step 1:** BFS levels are H:0; D,F:1; E,A,G,I:2; B,C:3. An undirected edge can connect only equal or adjacent levels. **Step 2:** D–B has level gap 2 and H–C has gap 3, so each would shorten a distance and contradict the tree. The other listed edges can coexist with this BFS tree for a suitable neighbor order. **Answer: B, C — (D,B) and (H,C) cannot occur.** A: **Incorrect:** G and C have levels 2 and 3; this is possible if A discovers C first. B: **Correct:** Levels 1 and 3 differ by 2, so this is impossible. C: **Correct:** Levels 0 and 3 differ by 3, so this is impossible. D: **Incorrect:** Both vertices have level 2, so the edge is possible. E: **Incorrect:** Levels 1 and 2 differ by 1; processing D before F lets D discover A first.

**Step 1:** With modulus 11 and linear probing: 43→10; 12→1; 67 hashes to 1 and enters 2; 102→3; 38→5. **Step 2:** Key 89 hashes to 1. Slots 1,2,3 contain 12,67,102, respectively; slot 4 is free. Therefore 89 enters index 4. **Answer: 4.**

**Step 1:** For a simple undirected graph on n vertices, at most \(n(n-1)/2\) edges are possible. **Step 2:** Ten vertices allow 45 edges, too few. Eleven allow \(11\cdot10/2=55\), attained by the complete graph. Hence the minimum is 11. **Answer: 11.** **Convention note:** The standard simple-graph convention excludes parallel edges and self-loops; without that convention the question would have a different answer.