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

**Step 1:** Sequential operations add their running times: \(O(n\log n)+O(n)+O(\log n)\). **Step 2:** The dominant term is \(n\log n\), giving the tightest listed bound \(O(n\log n)\). **Answer: C — \(O(n\log n)\).** **Convention note:** As usual for this single-answer complexity question, choose the tightest listed bound. Big-O alone denotes an upper bound; the quadratic option is also a loose upper bound. A: **Incorrect:** Linear growth does not cover the dominant \(n\log n\) term. B: **Incorrect:** This covers only the smallest operation. C: **Correct:** The sum is bounded by a constant multiple of \(n\log n\). D: **Incorrect:** Quadratic growth is a valid looser upper bound, but is not the tightest listed bound.

**Step 1:** The outer loop uses \(i=1,2,4,\ldots,2^k\), where \(k=\lfloor\log_2 n\rfloor\). The inner loop performs exactly i increments at each stage. **Step 2:** Total increments are \(1+2+\cdots+2^k=2^{k+1}-1\). This lies between n and 2n for positive integer n, so the running time is \(\Theta(n)\). **Answer: C — \(O(n)\).** **Convention note:** The intended answer is the tightest bound, under unit-cost arithmetic; the larger Big-O bounds are technically also upper bounds. A: **Incorrect:** This is a loose upper bound; multiplying n by the number of outer iterations overcounts the shrinking inner-loop lengths. B: **Incorrect:** This is a loose bound, not the tight growth. C: **Correct:** The geometric sum grows linearly. D: **Incorrect:** The outer loop alone is logarithmic, but all inner iterations total linear work.

**Step 1:** Counting one midpoint probe as one comparison, the worst-case number is \(C(n)=\lfloor\log_2 n\rfloor+1\) for n at least 1. **Step 2:** Doubling gives \(C(2n)=\lfloor\log_2 n+1\rfloor+1=C(n)+1\). One extra halving is needed. **Answer: D — It increases by 1.** **Convention note:** This counts comparisons with a midpoint as one logical probe. Counting individual Python equality and inequality tests can change the constant number of primitive comparisons per probe. A: **Incorrect:** Doubling the input does not double a logarithmic search depth. B: **Incorrect:** The worst-case depth increases by one. C: **Incorrect:** A larger search space cannot halve the worst-case depth. D: **Correct:** One additional midpoint probe is required.

**Step 1:** In descending order, the element at index i is smaller than every element in the sorted prefix, so it crosses all i preceding elements. **Step 2:** Total adjacent swaps are \(1+2+\cdots+(n-1)=n(n-1)/2\), yielding quadratic worst-case time. **Answer: B — When the input array is sorted in reverse (descending) order; each element .** A: **Incorrect:** Already ascending input needs no swaps and only linear checks. B: **Correct:** Every insertion travels across its entire sorted prefix. C: **Incorrect:** Equal elements do not move past one another under the strict less-than test. D: **Incorrect:** Random order has quadratic average time, but need not attain the maximum number of inversions.

**Step 1:** A stable sort preserves the original order of records with equal keys. Every record in the left half originally preceded every record in the right half. **Step 2:** When the compared keys tie during merging, copy the left record first. Recursively stable halves and this tie rule preserve order throughout the result. **Answer: D — Choose the left-subarray element first on equal keys.** A: **Incorrect:** Divide and conquer does not by itself specify how ties are handled. B: **Incorrect:** A secondary key can change the original order; it is not the usual stability rule. C: **Incorrect:** Taking the right record first reverses a pair of equal records from opposite halves. D: **Correct:** Taking the left record first preserves the original relative order.

**Step 1:** An extreme pivot leaves subproblems of sizes 0 and n−1, while partitioning still costs \(\Theta(n)\). **Step 2:** Repeating this gives \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\). **Answer: B — Choosing either the smallest or the largest element as the pivot at each .** A: **Incorrect:** Median pivots produce balanced partitions and logarithmic depth. B: **Correct:** A minimum or maximum pivot repeatedly produces the most unbalanced split. C: **Incorrect:** First or last position need not contain an extreme value; the input order matters. D: **Incorrect:** Roughly equal halves give the usual n log n behavior.

**Step 1:** A singly linked node exposes its own data and its successor, but no reference to its predecessor. **Step 2:** Thus its data can be modified, its successor bypassed, or a new successor linked directly. Accessing the preceding node requires another reference or traversal from the head. **Answer: D — Modify the immediately preceding node’s data.** A: **Incorrect:** Its data field is directly accessible, so this is possible. B: **Incorrect:** Set current.next to current.next.next, with the stated non-tail assumption. C: **Incorrect:** Link the new node to current.next and then set current.next to the new node. D: **Correct:** There is no backward link from the current node to its predecessor.

**Step 1:** For every undirected edge (u,v), a shortest path to u followed by that edge gives \(d(v)\le d(u)+1\). Reversing the roles gives \(d(u)\le d(v)+1\). **Step 2:** Therefore \(|d(u)-d(v)|\le1\), including non-tree edges. Their endpoints may be in the same or adjacent BFS levels. **Answer: A — Levels are equal or differ by exactly 1.** A: **Correct:** This follows from the two shortest-path inequalities. B: **Incorrect:** Non-tree edges are not restricted to the source and level 1. C: **Incorrect:** A gap above one would give a shorter route to the deeper endpoint. D: **Incorrect:** Same-level endpoints are possible but not mandatory; different parents are not mandatory either.

**Step 1:** Insert the stated keys: 12→2, 42→3 after a collision, 35→5, 28→8, 63→4 after probing 3, and 55→6 after probing 5. **Step 2:** If 23 is inserted next, its home slot is 3. Slots 3, 4, 5 and 6 are occupied, so it enters slot 7. **Answer: D — 7.** **Convention note:** The listed insertion sequence omits 23. Literally, 23 is not yet stored anywhere. The answer 7 follows the intended interpretation: insert 23 after the six listed keys. A: **Incorrect:** Slot 3 already contains 42. B: **Incorrect:** Slot 4 already contains 63. C: **Incorrect:** Slot 6 already contains 55. D: **Correct:** Slot 7 is the first free location reached from home slot 3.

**Step 1:** Each completed selection-sort pass selects the smallest remaining element and puts it at the next position of the prefix. **Step 2:** After k passes, the first k positions contain the k smallest elements in final sorted order. The remaining positions contain the other n−k largest elements, without a guarantee of internal order. **Answer: C, D — First k elements are final; the suffix contains the remaining largest elements.** A: **Incorrect:** The prefix does contain the k smallest elements; the qualification claiming otherwise is false. B: **Incorrect:** Index k is still in the unsorted suffix and need not contain the next smallest element. C: **Correct:** This is precisely the selection-sort invariant. D: **Correct:** Removing the k smallest leaves the n−k largest, whose order is unrestricted.

**Step 1:** A connected undirected graph is a tree exactly when it has n−1 edges. A forest with c components has \(n-c\) edges. **Step 2:** Every nonempty finite forest has a vertex of degree at most 1, so minimum degree at least 2 forces a cycle. A tree has one simple path between every pair of distinct vertices. **Answer: A, C, E — Connected n−1 edges implies tree; minimum degree 2 implies a cycle; tree paths are unique.** A: **Correct:** Connectedness plus n−1 edges characterizes a tree. B: **Incorrect:** A triangle and an isolated vertex have n=4 and 3 edges but are disconnected. C: **Correct:** A finite acyclic graph cannot have minimum degree at least 2. D: **Incorrect:** A disconnected forest has fewer than n−1 edges. E: **Correct:** Two different simple paths between the same vertices would create a cycle.

**Step 1:** BFS from 0 discovers 1 and 2, creating edges (0,1),(0,2). Processing 1 discovers 4 and 5, creating (1,4),(1,5). The queue is then [2,4,5]. **Step 2:** Processing 2 adds nobody. Processing 4 discovers 3, creating (4,3); by then 5 is already discovered. The non-tree edges among the choices are (2,4),(3,5),(4,5). **Answer: B, D, E — (2,4); (3,5); (4,5).** A: **Incorrect:** Vertex 1 first discovers 4, so this is a tree edge. B: **Correct:** Vertex 4 was already discovered by 1 when 2 is processed. C: **Incorrect:** Vertex 4 first discovers 3, so this is a tree edge. D: **Correct:** Vertex 3 is discovered by 4, not 5. E: **Correct:** Both endpoints are already discovered when this edge is scanned. F: **Incorrect:** Vertex 1 first discovers 5, so this is a tree edge.

**Step 1:** Let C(n) count all invocations, including the current one. Then \(C(0)=C(1)=1\), and \(C(n)=1+C(n-1)+C(n-2)\). **Step 2:** Thus C(2)=3, C(3)=5 and C(4)=9. Excluding the original fun(4) leaves \(9-1=8\) recursive calls. **Answer: 8.**

**Step 1:** Interpret the complete directed graph as having both directed arcs between each pair of distinct vertices, with no loops. DFS can descend through all five vertices in one chain. **Step 2:** Each vertex has a back arc to every earlier vertex on that chain. Their counts are 0, 1, 2, 3 and 4, totaling 10. No pair can contribute more than one descendant-to-ancestor back arc. **Answer: 10.** **Convention note:** The wording “unique edge” resembles undirected K5, but the question explicitly says directed and defines directed back edges. The answer 10 uses a complete bidirected graph. For undirected K5, counting each non-tree edge once would instead give 10−4=6.

**Step 1:** The arrows force 0 before both 1 and 2; both 1 and 2 before 4; then 4 before 3, and 3 before 5. **Step 2:** Only 1 and 2 can exchange positions. The orders are (0,1,2,4,3,5) and (0,2,1,4,3,5), giving two. **Answer: 2.**