cs2002_2026T2_Q1_NA.pdf
Programming, Data Structures and Algorithms using Python · Quiz 1 · May 2026
← Course papers · Start practice / exam
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?
A published solution is not available for this question yet.
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?
A published solution is not available for this question yet.
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]]
A published solution is not available for this question yet.
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]]
A published solution is not available for this question yet.
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
A published solution is not available for this question yet.
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]]
A published solution is not available for this question yet.
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]]
A published solution is not available for this question yet.
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
A published solution is not available for this question yet.
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.
A published solution is not available for this question yet.
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.
A published solution is not available for this question yet.
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]]
A published solution is not available for this question yet.
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.
A published solution is not available for this question yet.
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]]
A published solution is not available for this question yet.
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
A published solution is not available for this question yet.
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?
A published solution is not available for this question yet.
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?
A published solution is not available for this question yet.