Programming, Data Structures and Algorithms using Python · Quiz 1 · Sep 2024

**Step 1:** Sorting by the first coordinate puts key groups in order 1,2,8,9. Stability additionally preserves the original order within each equal-key group. **Step 2:** For key 2, B must precede E; for key 8, A must precede D. The result is [(1,C),(2,B),(2,E),(8,A),(8,D),(9,F)]. **Answer: D — [(1,C),(2,B),(2,E),(8,A),(8,D),(9,F)].** A: **Incorrect:** This reverses A and D within key 8. B: **Incorrect:** This reverses both equal-key groups. C: **Incorrect:** This reverses B and E within key 2. D: **Correct:** Both key order and original order within ties are preserved.

**Step 1:** Recent-first access suggests a stack; matrix multiplication uses an indexed array/list representation. **Step 2:** A printer spooler uses a FIFO queue, while social friendships and mutual-friend suggestions use a graph. Thus 1-d,2-a,3-c,4-b. **Answer: B — 1-d, 2-a, 3-c, 4-b.** **Convention note:** This is the textbook recent-first interpretation. A real recent-files feature may use an ordered list or another structure to support deduplication and arbitrary access. A: **Incorrect:** Matrix storage should be array/list and friendships a graph, not the reverse. B: **Correct:** All four mappings fit the applications. C: **Incorrect:** This exchanges the queue and graph applications. D: **Incorrect:** A stack is not the appropriate matrix representation; this also changes the intended recent-first structure.

**Step 1:** Push at the head sets new.next=head and then head=new. This changes only a fixed number of references. **Step 2:** Pop reads the head value and advances head=head.next. No traversal is needed, so both operations take constant time. **Answer: A — Push \(O(1)\), pop \(O(1)\).** A: **Correct:** Both operations access only the head and its successor. B: **Incorrect:** Pop does not scan the list. C: **Incorrect:** Push at the head does not scan the list. D: **Incorrect:** Neither operation needs a traversal.

**Step 1:** The element at the middle position need not have the median value. An adversarial input can make it a minimum or maximum at each recursive stage. **Step 2:** Partitioning then leaves one subproblem of size n−1: \(T(n)=T(n-1)+\Theta(n)\). Summing the linear partition costs gives \(\Theta(n^2)\). **Answer: B — \(T(n)=T(n-1)+O(n)\), worst-case \(O(n^2)\).** A: **Incorrect:** This omits the other recursive half in a balanced split and does not describe worst-case middle-position pivoting. B: **Correct:** An extreme-valued middle-position pivot gives this worst-case recurrence. C: **Incorrect:** This is balanced quicksort behavior, which is not guaranteed by choosing a middle position. D: **Incorrect:** Partitioning is linear, not constant; middle-position pivoting also need not balance the partitions.

**Step 1:** Starting at 5, discover its neighbors in order 1,4,7. Processing 1 then discovers 0 and 3; processing 4 adds nobody; processing 7 discovers 6. **Step 2:** The queue now processes 0,3,6 in that order. Vertex 0 discovers 2, which is appended after 6. The traversal is 5,1,4,7,0,3,6,2. **Answer: A — 5, 1, 4, 7, 0, 3, 6, 2.** A: **Correct:** This follows the FIFO queue and ascending neighbor order. B: **Incorrect:** Vertex 7 is already queued before 0, so it must appear first. C: **Incorrect:** Vertex 6 is queued before 2, so it must appear first. D: **Incorrect:** Vertex 3 is queued before 2, so it must appear first.

**Step 1:** The prerequisite chain Maths-I→Maths-II→Python→DBMS→MAD-I→MAD-II contains six one-month courses, so at least six months are necessary. **Step 2:** A feasible schedule is: month 1 Maths-I and CT; month 2 Maths-II; month 3 Python; month 4 PDSA and DBMS; month 5 MAD-I and MAD-I Project; month 6 MAD-II and MAD-II Project. This meets the lower bound. **Answer: B — 6.** A: **Incorrect:** Seven months are unnecessary because independent courses can run in parallel. B: **Correct:** A six-month schedule exists and matches the longest prerequisite chain. C: **Incorrect:** Five months cannot fit the six-course prerequisite chain. D: **Incorrect:** Four months cannot fit the six-course prerequisite chain.

**Step 1:** The pointers p,q,r track the current node, its predecessor and its predecessor’s predecessor as p advances. At loop exit p is 30, q is 25 and r is 22. **Step 2:** Assigning r.next=p links 22 directly to 30, bypassing 25. The reachable list is 10,5,7,20,18,15,22,30. **Answer: C — 10,5,7,20,18,15,22,30.** A: **Incorrect:** This removes 15, but the bypassed node is 25. B: **Incorrect:** This removes 22, but r itself stays in the list. C: **Correct:** This correctly bypasses the penultimate node 25. D: **Incorrect:** The last node 30 remains reachable; the operation removes 25.

**1. Extract the dominant terms:** \(f(n)=10n^4+6n^3=\Theta(n^4)\), \(g(n)=10n^3+2n^2=\Theta(n^3)\), and \(h(n)=12n^3\log n+6n^2=\Theta(n^3\log n)\). **2. Compare ratios:** \(f/g\) grows like n, \(g/h\) is bounded and tends to zero, \(f/h\) grows like \(n/\log n\), and \(h/f\) tends to zero. Therefore g=O(h) and h=O(f), while the other two claimed upper bounds fail. **Answer: B, D — B and D.** A: **Incorrect:** A quartic cannot be bounded by a constant times a cubic for all large n. B: **Correct:** The extra logarithm makes h grow at least as fast as g. C: **Incorrect:** n/log n is unbounded, so h cannot upper-bound f up to a constant. D: **Correct:** n³ log n grows more slowly than n⁴.

**Step 1:** Every undirected graph has an even degree sum. In a simple four-vertex graph, a degree-3 vertex is adjacent to all other vertices. **Step 2:** Sequence (2,2,3,3) is realized by K4 with the edge between the two degree-2 vertices removed. Sequence (3,3,3,3) is K4 itself. Both are connected. **Answer: B, D — 2, 2, 3, 3; 3, 3, 3, 3.** A: **Incorrect:** The degree sum 7 is odd. B: **Correct:** Removing one edge from K4 produces this connected graph. C: **Incorrect:** Each of the two degree-3 vertices must touch both other vertices, forcing those vertices to have degree at least 2, contrary to 1. D: **Correct:** The complete four-vertex graph has this degree sequence.

**Step 1:** DFS must finish exploring a vertex’s reachable unvisited neighbors before returning to its parent. The relevant edges are A–B,A–C,B–D,B–E,D–H,E–H,H–F,F–C,C–G. **Step 2:** B is realized by the path A→C→F→H→E→B→D, then backtracking to C and visiting G. D is realized by A→B→D→H→E, backtracking to H, then H→F→C→G. **Answer: B, D — A, C, F, H, E, B, D, G; A, B, D, H, E, F, C, G.** A: **Incorrect:** After E finishes, H still has unvisited neighbor F; DFS must visit F before returning far enough to visit C. B: **Correct:** All successive discoveries and the final backtracking to G obey DFS. C: **Incorrect:** After H→D, D must visit its unvisited neighbor B before E can be visited. D: **Correct:** Returning from E to H and continuing through F,C,G is a valid DFS execution.

**Step 1:** The arrows impose F before C and A; C before D; A before E; and both D and E before B. **Step 2:** A and B respect every constraint. C and D place B before E, violating E→B. **Answer: A, B — F, C, A, E, D, B; F, A, C, E, D, B.** A: **Correct:** F,C,A,E,D,B respects all six edges. B: **Correct:** F,A,C,E,D,B respects all six edges. C: **Incorrect:** E→B requires E before B, but this order puts B first. D: **Incorrect:** E→B is reversed by placing B before E.

**Step 1:** With zero-based indices 0 through 9, the first midpoint is (0+9)//2=4. Its value is 19, smaller than 159, so keep indices 5 through 9. **Step 2:** The next midpoint is (5+9)//2=7, whose value is 159. The search succeeds on the second midpoint comparison. **Answer: 2.** **Convention note:** Count one comparison with a midpoint as one logical search probe, as in the source key.

**Step 1:** Insert 6→6, 16→7 after a collision, 80→0, 91→1, and 145→5. **Step 2:** Insert 190 next. Its home index is 190 mod 10=0. Slots 0 and 1 are occupied, and slot 2 is free, so its location is 2. **Answer: 2.** **Convention note:** The question is interpreted as asking where 190 would be inserted after the five listed keys.