Programming, Data Structures and Algorithms

Compute the home slot \(h(x) = 3x \bmod 10\) of each key in order, moving to the next index whenever a slot is taken.

• \(h(1) = 3\), \(h(4) = 12 \bmod 10 = 2\), \(h(5) = 15 \bmod 10 = 5\) and \(h(6) = 18 \bmod 10 = 8\). All four slots are free.
• \(h(14) = 42 \bmod 10 = 2\). Slot 2 holds 4 and slot 3 holds 1, so 14 goes to slot 4.
• \(h(15) = 45 \bmod 10 = 5\). Slot 5 holds 5, so 15 goes to slot 6.

Option A lists the home slots 2 and 5, which were already occupied when 14 and 15 arrived.

Answer: D

A.extend(B) adds each element of B to the end of A in place, so A becomes [1, 2, 3, 4, 5, 6].

• A.append(B) adds the whole list as a single element, giving [1, 2, 3, [4, 5, 6]].
• Lists have no update method (dictionaries and sets do), so option C raises AttributeError.
• insert needs two arguments, an index and a value, so A.insert(B) raises TypeError.

Answer: A

Binary search compares the target with the middle element and discards half of the remaining range. It needs two things to be correct and \(O(\log n)\):

• Sorted data. Discarding a half is justified only when the elements are in order. On unsorted input the search can throw away the half that holds the target, so binary search does not work for A or B.
• Constant-time access to the middle. A linked list must be walked node by node to reach its middle, costing \(\frac{n}{2} + \frac{n}{4} + \cdots = O(n)\) in total, so D is not \(O(\log n)\) even though the list is sorted.

Only the sorted array (C) meets both conditions.

Answer: C

Each swap in insertion sort exchanges two adjacent elements that are out of order, removing exactly one inversion. So the number of swaps equals the number of inversions.

Without \(x\), the only inversion is the pair (15, 13), so \(x\) must add exactly one more:

• \(x = 10\): only 11, placed before it, is larger. Total 2.
• \(x = 12\): no element is out of order with it. Total 1.
• \(x = 14\): only 13, placed after it, is smaller. Total 2.
• \(x = 16\): both 15 and 13, placed after it, are smaller. Total 3.

Answer: A, C

Each tuple assignment evaluates its whole right-hand side with the old sets before assigning anything.

• Pass 1, first if: A={"this"}, B={"that"}, C={"other"}.
• Pass 1, second if ("that" is in B): A={"other","this"}, B={"this","that"}, C={"that","other"}.
• Pass 2: "other" is still in C and "this" is in A, so A={"other"}, B={"this"}, C={"that"}. Now "that" is not in B, so the second if is skipped.

"other" is no longer in C, so the loop stops. Only B contains "this".

Answer: B

Each given shortest path has 3 edges, so in \(G\) the distances between \(a\) and \(d\), \(e\) and \(h\), and \(a\) and \(h\) are all exactly 3. An edge that would create a path of length 2 between one of these pairs cannot be in \(G\).

• \((b, d)\) would give \(a - b - d\), of length 2 between \(a\) and \(d\). Not an edge.
• \((b, h)\) would give \(a - b - h\), of length 2 between \(a\) and \(h\). Not an edge.
• \((e, g)\) would give \(e - g - h\), of length 2 between \(e\) and \(h\). Not an edge.
• \((b, g)\) shortens none of the three distances (for example, \(a - b - g - h\) still has length 3), so it may be an edge of \(G\).

Answer: A, C, D

From \(a = 15\), every value of \(a\) reached is odd until 0, so only return 2*f((a-1)/2,b) runs:

\[ f(15, 10) = 2f(7, 10) = 4f(3, 10) = 8f(1, 10) = 16f(0, 10) = 16 \times 10 = 160 \]

In Python 3, (a-1)/2 gives floats (7.0, 3.0, 1.0, 0.0), but the tests a%2==1 and a==0 behave just as they would for integers, and the result stays an integer because it is built from b = 10.

In general the function returns \((a + 1) \cdot b\), not \(a \cdot b\), so 150 is the tempting wrong answer.

Answer: 160

While flag is 0, each pass pushes the next value, so the stack grows to 0, 1, …, 8 (top 8). In the pass that pushes 8, x equals 8, so flag becomes 1 (for good) and the third block already runs in that same pass.

Each such pass pops the top into x and adds it to sum; if x is odd, the element below it is popped and thrown away:

• pop 8 (even): sum = 8
• pop 7, discard 6: sum = 15
• pop 5, discard 4: sum = 20
• pop 3, discard 2: sum = 23
• pop 1, discard 0: sum = 24

The stack is now empty, so the loop stops and 24 is output.

Answer: 24

Each vertex \(i\) has edges only to \(i + 2\) and \(i + 1\), listed in that order. So DFS from 0 always follows the \(+2\) edge first: 0, 2, 4, …, 100. Vertex 100 has no outgoing edges, so DFS backtracks to 98, whose second neighbour 99 is new; back at 96 it finds 97, and so on down to 1.

The discovery order is 0, 2, 4, …, 100, then 99, 97, …, 1. Vertex 50 is the 26th vertex discovered, so the other \(101 - 26 = 75\) vertices come after it: the 25 even vertices 52 to 100 and all 50 odd vertices.

Answer: 75

In a DFS of an undirected graph, every edge ends up as either a tree edge or a back edge. Cross (and forward) edges cannot occur: a vertex finishes only after all of its edges have been explored, so the far end of a newly explored edge is never already finished. Gray is the colour of a vertex that is discovered but not finished, not a kind of edge. So (B) and (D) are out.

The key reads "explored first in the direction from \(u\) to \(v\)" as the search moving from \(u\), the end nearer to \(s\), along this edge out to \(v\). DFS moves along an edge only to a vertex it has not discovered yet, so \(v\) is discovered through \((u, v)\) and the edge becomes a tree edge. A back edge, (C), would need \(v\) to be discovered already, and then the search does not move to \(v\) at all.

Answer: A