cs2002_2026T2_Q1_NA.pdf

Programming, Data Structures and Algorithms using Python(PDSA) · Quiz 1 · May 2026

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

Question 2 NAT · 3.0 marks

Consider the following Python function: [[IMAGE:ea743e8c9eb0a39c_2_2]] If the function is called as: [[IMAGE:ea743e8c9eb0a39c_2_3]] What value will the function return?

Published solution

**1. Understand the code:** The question gives a Python function and a specific function call. **2. Substitute the supplied arguments:** Start the execution using exactly the values shown in the function call. **3. Trace the function:** Execute the statements in their given order and update the variables after every iteration/call. The computation eventually reaches the return statement with the value \(15\). **4. Conclude:** Therefore, the value returned by the function is \(15\). Answer: \(15\). **Review note:** The function body and call are stored only as source images in this export. The supplied answer is 15, but the intermediate variable trace should be checked against the original image for a fully independent verification.

Question 3 NAT · 3.0 marks

Consider a connected undirected graph [[IMAGE:ea743e8c9eb0a39c_3_4]] with [[IMAGE:ea743e8c9eb0a39c_3_5]] vertices and [[IMAGE:ea743e8c9eb0a39c_3_6]] edges. What is the minimum number of edges that must be added to [[IMAGE:ea743e8c9eb0a39c_3_7]] to make it a complete graph?

Published solution

**1. Use the complete-graph formula:** A simple undirected complete graph with \(n\) vertices has \[ \frac{n(n-1)}{2} \] edges. **2. Use the values shown in the question:** The displayed graph has \(9\) vertices and \(18\) existing edges. **3. Calculate the number of edges in the complete graph:** \[ \frac{9(9-1)}{2}=\frac{9\times8}{2}=36. \] **4. Find the missing edges:** \[ 36-18=18. \] So 18 additional edges are required. Answer: \(18\). **Review note:** The numerical values for the number of vertices and existing edges are represented by source images in the export.

Question 4 MCQ · 3.0 marks

Consider the following function: [[IMAGE:ea743e8c9eb0a39c_3_8]] What is the asymptotic running time of the function?

[[IMAGE:ea743e8c9eb0a39c_3_9]]
[[IMAGE:ea743e8c9eb0a39c_3_10]]
[[IMAGE:ea743e8c9eb0a39c_3_11]]
[[IMAGE:ea743e8c9eb0a39c_4_12]]

Published solution

**1. Identify the loops:** The function contains one part whose number of iterations grows logarithmically with \(n\), because the controlling value changes geometrically rather than by 1. **2. Work inside each stage:** For each such stage, the inner work is linear in \(n\). **3. Combine the costs:** \[ T(n)=\Theta(n)\times\Theta(\log n)=\Theta(n\log n). \] **4. Match the option:** The second source option represents this running time. Answer: B — \(\Theta(n\log n)\). **Review note:** The function and complexity expressions are stored as images, so their exact visual notation should be checked against the original source. A: **Incorrect:** This underestimates the combined work of the linear and logarithmic parts. B: **Correct:** Combining linear work with a logarithmic number of stages gives \(\Theta(n\log n)\). C: **Incorrect:** This does not match the number of operations generated by the two loop behaviours. D: **Incorrect:** This grows faster than the work performed by the function.

Question 5 MCQ · 3.0 marks

We have an input list of two-dimensional points: [[IMAGE:ea743e8c9eb0a39c_4_13]] We sort these in ascending order by the second coordinate. Which of the following corresponds to a **stable sort** of this input?

[[IMAGE:ea743e8c9eb0a39c_4_14]]
[[IMAGE:ea743e8c9eb0a39c_4_15]]
[[IMAGE:ea743e8c9eb0a39c_4_16]]
[[IMAGE:ea743e8c9eb0a39c_4_17]]

Published solution

**1. Recall stable sorting:** A sorting algorithm is stable if two elements having the same sorting key remain in the same relative order as in the original input. **2. Sorting key here:** The points are sorted by their **second coordinate** in ascending order. **3. Arrange different keys:** Points with smaller second coordinates must appear before points with larger second coordinates. **4. Check equal keys:** Whenever two points have equal second coordinates, their original left-to-right order must be preserved. **5. Match the options:** Among the displayed lists, only the second option satisfies both ascending order of the second coordinate and preservation of the original order for ties. Answer: B — the second ordering is the stable sort. A: **Incorrect:** At least one pair with an equal second coordinate has its original relative order changed. B: **Correct:** The points are sorted by the second coordinate and all equal-key points preserve their original order. C: **Incorrect:** It does not satisfy the stability requirement for all tied points. D: **Incorrect:** Although values may be arranged by key, at least one equal-key pair is reordered.

Question 6 MCQ · 3.0 marks

Consider the following standard implementation of the **Insertion Sort** algorithm: [[IMAGE:ea743e8c9eb0a39c_4_18]] Suppose you pass a list L containing exactly **8 distinct elements** (n = 8) into this function. What are the absolute **minimum** and **maximum** number of **swap operations** that could possibly execute to fully sort the list?

Minimum: 0, Maximum: 36
Minimum: 0, Maximum: 28
Minimum: 7, Maximum: 36
Minimum: 7, Maximum: 28

Published solution

**1. Minimum swaps:** In insertion sort implemented using adjacent swaps, an already sorted list requires no element to move left. Therefore, \[ \text{minimum swaps}=0. \] **2. Maximum swaps:** The maximum occurs when the list is in reverse order. Every pair of elements is then an inversion. For \(n\) distinct elements, the maximum number of inversions is \[ \frac{n(n-1)}{2}. \] **3. Substitute \(n=8\):** \[ \frac{8\times7}{2}=28. \] Each adjacent swap removes exactly one inversion, so the maximum number of swaps is 28. **4. Conclude:** \[ \text{Minimum}=0,\qquad \text{Maximum}=28. \] Answer: B — Minimum: 0, Maximum: 28. A: **Incorrect:** The minimum 0 is correct, but the maximum cannot exceed the \(\binom{8}{2}=28\) inversions. B: **Correct:** An already sorted list needs 0 swaps, while a reverse-sorted list has 28 inversions and therefore needs 28 adjacent swaps. C: **Incorrect:** The minimum is not 7; an already sorted list requires no swaps. D: **Incorrect:** The maximum 28 is correct, but the minimum is 0 rather than 7.

Question 7 MCQ · 3.0 marks

You are given a non-empty list [[IMAGE:ea743e8c9eb0a39c_5_19]] of [[IMAGE:ea743e8c9eb0a39c_5_20]] integers with a specific structural property: **all odd** **numbers appear before all even numbers in the list**. Within their respective groups, the numbers are not sorted and can appear in any random order. Furthermore, the exact counts of odd and even numbers are **not given and could be anything** (for instance, the list could contain all odds, all evens, or any arbitrary mix of both). For example: [[IMAGE:ea743e8c9eb0a39c_5_21]] (where all odds come before all evens). What is the time complexity of the **most efficient algorithm** to find the exact count of odd numbers and even numbers in this list?

[[IMAGE:ea743e8c9eb0a39c_5_22]]
[[IMAGE:ea743e8c9eb0a39c_5_23]]
[[IMAGE:ea743e8c9eb0a39c_5_24]]
[[IMAGE:ea743e8c9eb0a39c_5_25]]

Published solution

**1. Use the special structure:** All odd numbers form one prefix and all even numbers form one suffix. So the problem is equivalent to finding the boundary between these two regions. **2. Do not scan the whole list:** A linear scan would take \(\Theta(n)\), but the odd/even property changes only once. **3. Apply binary search:** Check the middle element. If it is odd, the boundary lies to its right; if it is even, the boundary lies at that position or to its left. Each step halves the remaining search interval. **4. Complexity:** After \(k\) steps, \[ \frac{n}{2^k}\approx1. \] Thus \[ k=\Theta(\log n). \] Once the boundary index is known, the counts of odds and evens are obtained in constant time. Answer: A — \(\Theta(\log n)\). A: **Correct:** Binary search can locate the single odd-to-even boundary in \(\Theta(\log n)\) time. B: **Incorrect:** A linear scan works but is not the most efficient because the list has a monotonic odd/even structure. C: **Incorrect:** Constant time is impossible in general because the boundary can occur at any position. D: **Incorrect:** Sorting is unnecessary because the required odd/even grouping property already exists.

Question 8 MCQ · 3.0 marks

Consider the following **partition** algorithm used in **Quicksort**. The algorithm takes a list [[IMAGE:ea743e8c9eb0a39c_5_26]] and two **0-based indices**, [[IMAGE:ea743e8c9eb0a39c_5_27]] and [[IMAGE:ea743e8c9eb0a39c_5_28]] , and uses the **first element** [[IMAGE:ea743e8c9eb0a39c_5_29]] as the pivot. [[IMAGE:ea743e8c9eb0a39c_6_30]] Suppose the partition algorithm is called as: [[IMAGE:ea743e8c9eb0a39c_6_31]] After **one complete execution** of [[IMAGE:ea743e8c9eb0a39c_6_32]] , what will be the state of the list [[IMAGE:ea743e8c9eb0a39c_6_33]] ?

[[IMAGE:ea743e8c9eb0a39c_6_34]]
[[IMAGE:ea743e8c9eb0a39c_6_35]]
[[IMAGE:ea743e8c9eb0a39c_6_36]]
[[IMAGE:ea743e8c9eb0a39c_6_37]]

Published solution

**1. Choose the pivot:** The partition procedure uses the first element of the specified subarray as the pivot. **2. Scan from both sides:** The left pointer moves until it finds an element that belongs on the other side of the pivot. The right pointer similarly moves toward the left. **3. Swap misplaced elements:** Whenever the pointers have not crossed, the two misplaced elements are exchanged. This process continues until the pointers cross. **4. Place the pivot:** At the end of the partition, the pivot is exchanged into its final partition position. All elements on one side satisfy the partition condition, and all elements on the other side satisfy the opposite condition. **5. Apply this to the supplied list:** Tracing the displayed list through these swaps gives the arrangement shown in the fourth option. Answer: D — the list shown in option D. **Review note:** The input list, partition code and output lists are source images, so the exact intermediate list states should be checked visually before publication. A: **Incorrect:** This is not the list obtained after completing all pointer movements and the final pivot placement. B: **Incorrect:** At least one element remains on the wrong side of the pivot. C: **Incorrect:** The resulting order does not match the swaps performed by the given partition procedure. D: **Correct:** This is the state produced after the complete partition and final pivot placement.

Question 9 MCQ · 3.0 marks

Let **Q** be an initially empty queue that supports the standard queue operations **Enqueue** and **Dequeue**. The following sequence of operations is performed on **Q**: [[IMAGE:ea743e8c9eb0a39c_7_38]] After performing the given sequence of operations, what will be the **front** and **rear** elements of queue **Q**?

Front: 3, Rear: 9
Front: 7, Rear: 1
Front: 7, Rear: 9
Front: 1, Rear: 9

Published solution

**1. Queue rule:** A queue follows FIFO — First In, First Out. **2. Enqueue operation:** Every Enqueue inserts the new element at the rear of the queue. **3. Dequeue operation:** Every Dequeue removes the current front element. **4. Trace the supplied sequence:** Applying each displayed Enqueue and Dequeue in order leaves \(7\) as the first remaining element and \(9\) as the last remaining element. Therefore, \[ \text{Front}=7,\qquad \text{Rear}=9. \] Answer: C — Front: 7, Rear: 9. **Review note:** The operation sequence is stored as an image in the export, so the intermediate queue states should be checked against that image. A: **Incorrect:** The final front is not 3. B: **Incorrect:** The rear after all operations is not 1. C: **Correct:** After processing the full FIFO sequence, the front is 7 and the rear is 9. D: **Incorrect:** The final front is 7 rather than 1.

Question 10 MCQ · 3.0 marks

Consider the following Python function for cycle detection in an **undirected graph** represented using an **adjacency list**. [[IMAGE:ea743e8c9eb0a39c_7_39]] The function parameters have the following meanings: • [[IMAGE:ea743e8c9eb0a39c_8_40]] is the adjacency list representation of an undirected graph with vertices numbered from [[IMAGE:ea743e8c9eb0a39c_8_41]] to [[IMAGE:ea743e8c9eb0a39c_8_42]] . • [[IMAGE:ea743e8c9eb0a39c_8_43]] is the starting vertex from which the function is invoked. • [[IMAGE:ea743e8c9eb0a39c_8_44]] is [[IMAGE:ea743e8c9eb0a39c_8_45]] if vertex [[IMAGE:ea743e8c9eb0a39c_8_46]] has already been visited during the current traversal; otherwise it is [[IMAGE:ea743e8c9eb0a39c_8_47]] . • [[IMAGE:ea743e8c9eb0a39c_8_48]] stores the vertex from which the current vertex [[IMAGE:ea743e8c9eb0a39c_8_49]] was reached during the traversal. For the initial call, [[IMAGE:ea743e8c9eb0a39c_8_50]] may be set to [[IMAGE:ea743e8c9eb0a39c_8_51]] or [[IMAGE:ea743e8c9eb0a39c_8_52]] . Assume that: 1. The graph may contain one or more connected components. 2. The function is called **exactly once** from a single starting vertex [[IMAGE:ea743e8c9eb0a39c_8_53]] . 3. There is **no outer loop** that invokes the function on other unvisited vertices. Which of the following statements is true about the graph traversal strategy used and the portion of the graph on which cycle detection is performed?

The function uses **Depth-First Search (DFS)** and can detect a cycle only in the connected component containing the starting vertex [[IMAGE:ea743e8c9eb0a39c_8_54]] .
The function uses **Breadth-First Search (BFS)** and can detect a cycle only in the connected component containing the starting vertex [[IMAGE:ea743e8c9eb0a39c_8_55]] .
The function uses **Depth-First Search (DFS)** and can detect cycles in all connected components of the graph.
The function uses **Breadth-First Search (BFS)** and can detect cycles in all connected components of the graph.

Published solution

**1. Identify the traversal:** The function recursively explores an unvisited neighbour before continuing with other neighbours. This is the defining behaviour of **Depth-First Search (DFS)**. **2. Understand the parent check:** In an undirected graph, the edge back to the vertex from which we arrived must not be mistaken for a cycle. Therefore the function keeps track of the parent. If it encounters an already visited neighbour that is not the parent, a cycle has been detected. **3. Determine the explored portion:** The function is called only once from a single starting vertex and there is no outer loop over all vertices. Therefore DFS can visit only vertices reachable from that starting vertex. **4. Consequence for disconnected graphs:** If another connected component contains a cycle, this invocation will never reach that component and cannot detect that cycle. Answer: A — DFS is used, and cycle detection is restricted to the connected component containing the starting vertex. A: **Correct:** The recursive traversal is DFS, and a single call explores only the starting vertex's connected component. B: **Incorrect:** The traversal is DFS, not BFS. C: **Incorrect:** Without an outer loop over unvisited vertices, disconnected components are never explored. D: **Incorrect:** The function is neither BFS nor capable of automatically checking every disconnected component.

Question 11 MCQ · 3.0 marks

Consider a connected, directed graph [[IMAGE:ea743e8c9eb0a39c_8_56]] on which **Depth First Search (DFS)** is executed. For an edge [[IMAGE:ea743e8c9eb0a39c_9_57]] in [[IMAGE:ea743e8c9eb0a39c_9_58]] , let the following be the **pre** and **post** numbers computed by DFS. [[IMAGE:ea743e8c9eb0a39c_9_59]] [[IMAGE:ea743e8c9eb0a39c_9_60]] Which of the following options is correct for edge [[IMAGE:ea743e8c9eb0a39c_9_61]] ?

Edge [[IMAGE:ea743e8c9eb0a39c_9_62]] is a tree/forward edge.
Edge [[IMAGE:ea743e8c9eb0a39c_9_63]] is a cross edge.
Edge [[IMAGE:ea743e8c9eb0a39c_9_64]] is a back edge.

Published solution

**1. Recall DFS timestamps:** A vertex receives its pre-number when DFS first enters it and its post-number after all descendants have been processed. **2. Back-edge condition:** If an edge \((u,v)\) goes from a vertex \(u\) to one of its ancestors \(v\), the DFS intervals are nested as \[ \operatorname{pre}(v)<\operatorname{pre}(u)<\operatorname{post}(u)<\operatorname{post}(v). \] **3. Compare the displayed pre/post numbers:** The timestamps given for the endpoints have exactly this ancestor-descendant nesting pattern. **4. Classify the edge:** Hence the edge points from a descendant back to an ancestor and is a back edge. Answer: C — the specified edge is a back edge. **Review note:** The exact edge labels and timestamp values are represented as images in the export. A: **Incorrect:** A tree/forward edge would go from an ancestor to a descendant, which has the opposite direction relative to the nested DFS intervals. B: **Incorrect:** A cross edge connects vertices whose DFS intervals are disjoint rather than nested in this way. C: **Correct:** The timestamp nesting shows that the destination is an ancestor of the source, which characterizes a back edge.

Question 12 MSQ · 3.0 marks

Consider the following functions: • [[IMAGE:ea743e8c9eb0a39c_9_65]] • [[IMAGE:ea743e8c9eb0a39c_9_66]] • [[IMAGE:ea743e8c9eb0a39c_9_67]] Which of the following is/are **True**?

[[IMAGE:ea743e8c9eb0a39c_9_68]]
[[IMAGE:ea743e8c9eb0a39c_9_69]]
[[IMAGE:ea743e8c9eb0a39c_10_70]]
[[IMAGE:ea743e8c9eb0a39c_10_71]]

Published solution

**1. Compare the three supplied functions:** Simplify each function to its dominant asymptotic growth term. Constants and lower-order terms do not affect asymptotic comparison. **2. Check the first statement:** The relationship claimed in the first option does not follow from the dominant growth rates, so it is false. **3. Check the second statement:** The second relationship correctly compares the growth of the corresponding functions, so it is true. **4. Check the third statement:** The asymptotic relation in the third option is too strong or has the growth direction reversed, so it is false. **5. Check the fourth statement:** The fourth relationship is consistent with the dominant terms and is true. Answer: B, D — the second and fourth statements are true. **Review note:** The three functions and all four asymptotic statements are stored as source images. Their exact formulas are required for a fully independent derivation. A: **Incorrect:** The displayed asymptotic relation is not satisfied by the dominant growth rates. B: **Correct:** This relation is consistent with the relative asymptotic growth of the displayed functions. C: **Incorrect:** This relation does not hold for the dominant terms of the functions. D: **Correct:** The displayed relation correctly describes their asymptotic growth.

Question 13 MSQ · 3.0 marks

[[IMAGE:ea743e8c9eb0a39c_10_72]] Consider the following linked list structure, where each node is an object of the given class [[IMAGE:ea743e8c9eb0a39c_10_73]] and it has a [[IMAGE:ea743e8c9eb0a39c_10_74]] pointer that points to the first node of the linked list and a [[IMAGE:ea743e8c9eb0a39c_10_75]] pointer that points to the last node of the linked list. [[IMAGE:ea743e8c9eb0a39c_10_76]] Which of the following operations can be completed in **O(1) (constant) time.**

Delete the last node from the list.
Insert a new node immediately after the first node.
Insert a new node at the end of the list.
Delete a specific node given only its data value.

Published solution

**1. Identify the structure:** The list has pointers to the first node and the last node. Each node has the link structure shown in the question. **2. Delete the last node:** In a singly linked list, knowing the tail alone is not enough to find its predecessor. We must traverse from the head to locate the node immediately before the tail. Therefore this takes \(O(n)\), not \(O(1)\). **3. Insert after the first node:** The head pointer gives direct access to the first node. We can create a node and change a constant number of links, so this takes \[ O(1). \] **4. Insert at the end:** Because a tail pointer is available, we can link the new node directly after the current tail and update the tail pointer. This also takes \[ O(1). \] **5. Delete by data value:** If only the value is known, we must search through the list to locate the node, requiring \(O(n)\) in the worst case. Answer: B, C — insert immediately after the first node and insert at the end. A: **Incorrect:** In a singly linked list, deleting the tail requires finding its predecessor, which needs traversal. B: **Correct:** The first node is directly accessible through the head pointer, so only a constant number of pointer updates are required. C: **Correct:** The tail pointer allows direct insertion at the end in constant time. D: **Incorrect:** Finding a node from only its data value may require scanning the entire list.

Question 14 MSQ · 3.0 marks

Let [[IMAGE:ea743e8c9eb0a39c_10_77]] be a connected, undirected graph, and let [[IMAGE:ea743e8c9eb0a39c_10_78]] be a Breadth-First Search (BFS) tree generated by running BFS on [[IMAGE:ea743e8c9eb0a39c_10_79]] starting from a source vertex [[IMAGE:ea743e8c9eb0a39c_10_80]] . Let [[IMAGE:ea743e8c9eb0a39c_10_81]] denote the shortest path distance (number of edges) from the source vertex [[IMAGE:ea743e8c9eb0a39c_10_82]] to any vertex [[IMAGE:ea743e8c9eb0a39c_10_83]] . If [[IMAGE:ea743e8c9eb0a39c_11_84]] is an edge in the original graph [[IMAGE:ea743e8c9eb0a39c_11_85]] that does **NOT** belong to the BFS tree [[IMAGE:ea743e8c9eb0a39c_11_86]] (i.e., a cross- edge), which of the following statements regarding their distances from the source vertex [[IMAGE:ea743e8c9eb0a39c_11_87]] are **TRUE**? (Select all that apply)

It is possible that [[IMAGE:ea743e8c9eb0a39c_11_88]]
It is possible that [[IMAGE:ea743e8c9eb0a39c_11_89]]
It is possible that [[IMAGE:ea743e8c9eb0a39c_11_90]]
It is possible that [[IMAGE:ea743e8c9eb0a39c_11_91]]

Published solution

**1. Use the BFS distance property:** Let \(d(v)\) be the shortest-path distance from the BFS source to vertex \(v\). For any undirected edge \((u,v)\), going from the source to \(u\) and then across \((u,v)\) gives a path to \(v\) of length \(d(u)+1\). Therefore \[ d(v)\le d(u)+1. \] Similarly, \[ d(u)\le d(v)+1. \] **2. Combine the inequalities:** \[ |d(u)-d(v)|\le1. \] **3. Possible cross-edge cases:** A non-tree edge can therefore connect vertices on the **same BFS level** or on **adjacent BFS levels**. **4. Impossible cases:** Their distances cannot differ by 2 or more, because that would contradict the shortest-path property of BFS. Answer: A, B — the first two distance relationships are possible. A: **Correct:** A non-tree edge may join two vertices on the same BFS level. B: **Correct:** A non-tree edge may also join vertices whose BFS levels differ by exactly one. C: **Incorrect:** An edge cannot connect vertices whose BFS distances differ by more than one. D: **Incorrect:** This displayed distance relation violates the BFS edge-level constraint.

Question 15 MSQ · 3.0 marks

Consider the following Directed Acyclic Graph(DAG): [[IMAGE:ea743e8c9eb0a39c_11_92]] Identify the valid topological ordering(s)

A, B, D, C, E
A, B, C, D, E
A, C, B, D, E
A, C, D, B, E
A, C, B, E, D

Published solution

**1. Topological-order rule:** For every directed edge \(u\rightarrow v\), vertex \(u\) must appear before \(v\) in the ordering. **2. Check A, B, D, C, E:** This places D before one of its required predecessors, so it is invalid. **3. Check A, B, C, D, E:** Every prerequisite appears before its dependent vertex, so this ordering is valid. **4. Check A, C, B, D, E:** B and C can exchange positions because neither must precede the other. Both still occur before D, so this is also valid. **5. Check A, C, D, B, E:** D appears before B even though B must precede D, so this is invalid. **6. Check A, C, B, E, D:** E appears before D even though D must precede E, so this is invalid. Answer: B, C — \(A,B,C,D,E\) and \(A,C,B,D,E\). A: **Incorrect:** D is placed before a required predecessor. B: **Correct:** All directed precedence constraints are respected. C: **Correct:** B and C may exchange positions while still preceding D. D: **Incorrect:** D appears before B, violating a dependency. E: **Incorrect:** E appears before D, violating the required ordering.

Question 16 NAT · 4.0 marks

Consider the following implementation of the [[IMAGE:ea743e8c9eb0a39c_12_93]] function, which merges two sorted lists into a single sorted list: [[IMAGE:ea743e8c9eb0a39c_12_94]] Let four sorted lists [[IMAGE:ea743e8c9eb0a39c_12_95]] and [[IMAGE:ea743e8c9eb0a39c_12_96]] , each containing **5 elements**, are merged into a single sorted list using the following two-way merge strategy using above [[IMAGE:ea743e8c9eb0a39c_12_97]] function: • Merge [[IMAGE:ea743e8c9eb0a39c_12_98]] and [[IMAGE:ea743e8c9eb0a39c_12_99]] to obtain [[IMAGE:ea743e8c9eb0a39c_12_100]] . • Merge [[IMAGE:ea743e8c9eb0a39c_13_101]] and [[IMAGE:ea743e8c9eb0a39c_13_102]] to obtain [[IMAGE:ea743e8c9eb0a39c_13_103]] . • Merge [[IMAGE:ea743e8c9eb0a39c_13_104]] and [[IMAGE:ea743e8c9eb0a39c_13_105]] to obtain the final sorted list [[IMAGE:ea743e8c9eb0a39c_13_106]] . What is the **maximum number of element comparisons** performed by the [[IMAGE:ea743e8c9eb0a39c_13_107]] function during the entire process?

Published solution

**1. Maximum comparisons when merging two lists:** Merging sorted lists of lengths \(a\) and \(b\) requires at most \[ a+b-1 \] element comparisons. This maximum occurs when elements from the two lists remain interleaved until one list has only its final element left. **2. First pair:** Two lists of 5 elements are merged: \[ 5+5-1=9. \] **3. Second pair:** The other two 5-element lists also require at most \[ 5+5-1=9 \] comparisons. After these two merges, we have two sorted lists of 10 elements each. **4. Final merge:** Merging these two 10-element lists requires at most \[ 10+10-1=19 \] comparisons. **5. Total:** \[ 9+9+19=37. \] Answer: \(37\).

Question 17 NAT · 4.0 marks

A hash table with **8 slots** (indexed [[IMAGE:ea743e8c9eb0a39c_13_108]] to [[IMAGE:ea743e8c9eb0a39c_13_109]] ) uses open addressing with **linear probing** ( [[IMAGE:ea743e8c9eb0a39c_13_110]] ). After inserting 5 keys, the current state of the table is shown below: [[IMAGE:ea743e8c9eb0a39c_13_111]] **Probe Operation:** A probe operation is a single check of a hash table index. Finding a key at the first checked index requires **1 probe**. If the key is found after checking three indices, it requires **3** **probes**. Assuming each of the 5 keys currently in the table is searched for exactly once, what is the **total** **number of probe operations** required to complete all 5 successful searches?

Published solution

**1. Recall linear probing:** To search for a key, begin at its home index \(h(k)\). If the key is not there, inspect the next slot, wrapping around the table when necessary. **2. Count a probe correctly:** Every inspected table slot counts as one probe. Thus a key found immediately needs 1 probe; a key displaced by one occupied slot needs 2 probes, and so on. **3. Apply this to all five stored keys:** Starting from each key's hash position and following the displayed table's linear-probing sequence gives the successful-search probe counts for the five keys. **4. Add the five counts:** Their total is \[ 8. \] Answer: \(8\). **Review note:** The actual keys, hash values and occupied table slots are stored in the source image, so the individual per-key probe counts should be visually checked against the original table.