**1. Trace the accessed indices:** The index starts at 1 and doubles to 2,4,8,… while it is less than n. It therefore executes only logarithmically many iterations.
**2. State the tight bound:** Under constant-cost indexing and output per item, the time is \(\Theta(\log n)\), so the intended tight option is O(log n).
**Answer: B — O(log n).**
**Convention note:** The question uses O notation as a tight-growth classification. Literally the slower-growing logarithmic time also belongs to the other larger O classes. Output is treated as constant cost per list element.
A: **Incorrect:** It is a looser upper bound than the actual logarithmic growth.
B: **Correct:** It matches the number of index doublings.
C: **Incorrect:** It is also a loose upper bound, not the tight rate.
D: **Incorrect:** It adds unnecessary linear growth.
**1. Use standard growth comparisons:** Every fixed power of log n is smaller asymptotically than every positive power of n, while any fixed polynomial times logarithms is smaller than \(2^n\). Thus f₅ is first and f₃ last.
**2. Compare the middle terms:** \(f_2/f_4=(\log n)^2/\sqrt n\to0\), and \(f_4/f_1=1/(\sqrt n\log n)\to0\). Hence the order is \(f_5,f_2,f_4,f_1,f_3\).
**Answer: B — f₅,f₂,f₄,f₁,f₃.**
A: **Incorrect:** It incorrectly puts exponential growth first and polylogarithmic growth last.
B: **Correct:** It has every consecutive asymptotic comparison in the correct direction.
C: **Incorrect:** It places the exponential before several slower functions.
D: **Incorrect:** It begins with a larger polynomial instead of the smallest polylogarithm.
**1. Start with indices 0 through 16:** The floor midpoint is 8, containing 35. Since 47>35, keep indices 9…16; midpoint 12 contains 51, so keep 9…11.
**2. Finish the search:** Midpoint 10 contains 43, so keep index 11, containing 47. The comparisons are 35,51,43,47.
**Answer: C — 35, 51, 43, 47.**
A: **Incorrect:** It uses 39 instead of the required midpoint value 43.
B: **Incorrect:** It skips the midpoint at index 10.
C: **Correct:** It follows all four floor-midpoint comparisons.
D: **Incorrect:** It uses the wrong second midpoint 55.
E: **Incorrect:** C supplies the actual sequence.
**1. Insert 2 into the sorted prefix:** Starting [3,4,2,1,5], move 2 left past 4 and 3 through two adjacent swaps, producing [2,3,4,1,5].
**2. Insert 1 and finish:** Move 1 left past 4,3,2 through three swaps, obtaining [1,2,3,4,5]. The final 5 needs no swap. Total=2+3=5.
**Answer: D — 5.**
A: **Incorrect:** It counts only the insertion of 2.
B: **Incorrect:** It counts only the insertion of 1.
C: **Incorrect:** It misses one of the five inversions.
D: **Correct:** Five adjacent swaps remove the five input inversions.
**1. Count merge-sort comparisons:** A balanced merge-sort recursion has \(O(\log n)\) levels and \(O(n)\) element comparisons per level, for \(O(n\log n)\) string comparisons.
**2. Charge for a string comparison:** Comparing two length-k strings may inspect k characters, costing O(k). Multiplication gives \(O(kn\log n)\) in the worst case under the stated comparison model.
**Answer: B — O(kn log n).**
A: **Incorrect:** It omits the recursion-level factor log n.
B: **Correct:** It multiplies the comparison count by the per-comparison string cost.
C: **Incorrect:** The recursion depth depends on the number of strings n, not their length k.
D: **Incorrect:** It has an unsupported quadratic factor in n and omits the proper character cost.
**1. Analyze balanced partitions:** When pivots split the remaining elements roughly equally, \(T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)\), the best usual quicksort case.
**2. Analyze sorted input with first-element pivot:** On increasing input, the first element is always the smallest, producing subproblem sizes 0 and n−1. This yields \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\), not the best case. Therefore statement 1 alone is true.
**Answer: A — Only Statement 1.**
A: **Correct:** Only the balanced-partition best-case statement is true.
B: **Incorrect:** First-element pivot on sorted distinct input creates the worst imbalance.
C: **Incorrect:** Equal halves do not give the quadratic worst case.
D: **Incorrect:** Statement 2 is false.
E: **Incorrect:** Both statements 2 and 3 are false.
**1. Trace the recursive removals:** The initial bottom-to-top stack is [1,2,3]. Calls pop 3, then 2, then 1, reaching an empty stack. Each call remembers its own x.
**2. Trace unwinding:** The x=1 call pushes 2 then 1, giving [2,1]. The x=2 call appends 4 then 2, giving [2,1,4,2]. Finally x=3 appends 6 then 3.
**3. Read bottom to top:** The final stack is [2,1,4,2,6,3]. The original and doubled copies are interleaved according to the unwind order.
**Answer: C — [2,1,4,2,6,3].**
A: **Incorrect:** It incorrectly groups all originals before all doubled values.
B: **Incorrect:** It does not follow the bottom-up unwind sequence.
C: **Correct:** It matches all six push operations in order.
D: **Incorrect:** It reverses the grouping and does not reflect the recursive pushes.
**1. Use the rear pointer for enqueue:** Link the new node after rear and update rear. The empty-queue case additionally sets head; all require a fixed number of pointer changes.
**2. Use the head pointer for dequeue:** Read/remove head and replace it by head.next; if the queue becomes empty, clear rear too. No traversal is needed. Both operations take constant time.
**Answer: A — enqueue O(1), dequeue O(1).**
A: **Correct:** Both endpoints are directly available, making both operations O(1).
B: **Incorrect:** Removing the first node does not require a linear scan.
C: **Incorrect:** The rear pointer avoids scanning for the end.
D: **Incorrect:** Neither operation needs a full traversal.
**1. Match the operational policies:** Undo reverses the most recent action, so use a stack (b). Ordinary print scheduling serves the earliest submitted job first, so use a queue (a).
**2. Match lookup and connectivity:** A hash table (d) supports records indexed by book ID. A graph (c) represents cities and routes for shortest-path algorithms. The mapping is 1-b,2-a,3-d,4-c.
**Answer: B — 1-b, 2-a, 3-d, 4-c.**
A: **Incorrect:** It reverses stack/queue roles and gives unsuitable structures for lookup and paths.
B: **Correct:** It matches all four applications.
C: **Incorrect:** It has correct lookup/path choices but reverses undo and printing.
D: **Incorrect:** It misassigns undo, print scheduling, lookup and routes.
**1. Extract the DAG constraints:** The edges are 1→2,1→3,2→4,3→4,4→5 and 3→6. A topological order must put every source before its target.
**2. Test the requested NOT-orders:** B=[1,3,4,2,5,6] violates 2→4. E=[1,2,4,3,5,6] violates 3→4. A,C,D satisfy all constraints, even though they may order unrelated 5 and 6 differently.
**Answer: B, E — B and E — the invalid topological orders.**
A: **Incorrect:** Not selected: it satisfies every edge constraint.
B: **Correct:** Selected: it puts 4 before prerequisite 2.
C: **Incorrect:** Not selected: both 2 and 3 precede 4.
D: **Incorrect:** Not selected: it is a valid topological ordering.
E: **Correct:** Selected: it puts 4 before prerequisite 3.
Consider a **connected, undirected graph G** with **n** vertices. A **Breadth-First Search (BFS)**
traversal is performed starting from a source vertex **s**. Let **d(s, v)** denote the shortest distance (in
terms of number of edges) from **s** to vertex **v**.
Which of the following statements is **true** about the BFS traversal?
6406535115350.
All vertices at distance **k** from **s** are visited before any vertex at distance **k + 1**
from **s.**
6406535115351.
Once a vertex is visited, it is never visited again during the traversal.
6406535115352.
BFS may fail to visit some vertices, even if the graph is connected.
6406535115353.
The time complexity of BFS using an adjacency list representation is **O(n**\(^{2}\)**).**
A published solution is not available for this question yet.
**1. Identify the counted property:** The function increments only when i divides n and i is even, so it counts positive even divisors.
**2. Enumerate both lists:** Even divisors of 48 are 2,4,6,8,12,16,24,48, giving 8. Even divisors of 36 are 2,4,6,12,18,36, giving 6. Hence g(48)−g(36)=8−6=2.
**Answer: 2.**
**1. Count invocations, not returned values:** Although every leaf returns zero, both recursive branches are still evaluated. Let C(n) count all invocations including the current call. Then C(0)=C(1)=1 and \(C(n)=1+C(n-1)+C(n-2)\).
**2. Evaluate the recurrence:** C(2)=3, C(3)=5, C(4)=9, C(5)=15 and C(6)=25.
**3. Exclude the initial call:** The question excludes the original fun(6), so recursive calls=25−1=24. Repeated calls with the same argument are counted separately because there is no memoization.
**Answer: 24.**
**1. Insert the existing keys:** Modulo 8 gives 10→2, 3→3. Key 18 starts at 2, passes occupied 2 and 3, and lands at 4. Key 25 lands at 1. Key 33 starts at 1 and passes 1,2,3,4 before landing at 5.
**2. Insert 42:** Its home slot is 42 mod 8=2. Slots 2,3,4,5 are occupied, and slot 6 is the first free one. Therefore its insertion index is 6.
**Answer: 6.**
**1. Use one edge per unordered vertex pair:** For a simple undirected graph, the maximum is attained by the complete graph \(K_{20}\).
**2. Count pairs:** \(\binom{20}{2}=20(19)/2=190\). A complete graph is connected, so connectedness does not reduce this maximum.
**Answer: 190.**
**Convention note:** The usual simple-graph convention is assumed. Parallel edges would remove any finite upper bound.
**1. Read node 5’s neighbors:** Its list is [3,6], so its degree x is 2. Undirected adjacency lists list both directions, but a vertex’s degree is just its own neighbor count.
**2. Find connected components:** Vertices {1,2,3,4,5,6} form one component, and {7,8,9} form another, so y=2. Thus x+y=2+2=4.
**Answer: 4.**
