Programming, Data Structures and Algorithms using Python Quiz 1: 19 July 2026 (May 2026 term)

Consider the following Python function:

If the function is called as: What value will the function return?

Inscript Consider a connected undirected graph with vertices and edges. What is the minimum number of edges that must be added to to make it a complete graph?

Consider the following function:

What is the asymptotic running time of the function?

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

Consider the following standard implementation of the Insertion Sort algorithm:

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?

You are given a non-empty list of 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: (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?

Consider the following partition algorithm used in Quicksort. The algorithm takes a list and two 0-based indices, and , and uses the first element as the pivot.

Suppose the partition algorithm is called as:

After one complete execution of , what will be the state of the list ?

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:

After performing the given sequence of operations, what will be the front and rear elements of queue Q?

Consider the following Python function for cycle detection in an undirected graph represented using an adjacency list.

The function parameters have the following meanings: is the adjacency list representation of an undirected graph with vertices numbered from to . • is the starting vertex from which the function is invoked.• is if vertex has already been visited during the current traversal; otherwise it is . • stores the vertex from which the current vertex was reached during the traversal. For the initial call, may be set to or . • Assume that: The graph may contain one or more connected components.1. The function is called exactly once from a single starting vertex .2. There is no outer loop that invokes the function on other unvisited vertices.3. 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?

Consider a connected, directed graph on which Depth First Search (DFS) is executed. For an edge in , let the following be the pre and post numbers computed by DFS. Which of the following options is correct for edge ?

Consider the following functions: • • • Which of the following is/are True?

Consider the following linked list structure, where each node is an object of the given class and it has a pointer that points to the first node of the linked list and a pointer that points to the last node of the linked list.

Which of the following operations can be completed in O(1) (constant) time.

Let be a connected, undirected graph, and let be a Breadth-First Search (BFS) tree generated by running BFS on starting from a source vertex . Let denote the shortest path distance (number of edges) from the source vertex to any vertex . If is an edge in the original graph that does NOT belong to the BFS tree (i.e., a cross- edge), which of the following statements regarding their distances from the source vertex are TRUE? (Select all that apply)

Consider the following Directed Acyclic Graph(DAG):

Identify the valid topological ordering(s)

Consider the following implementation of the function, which merges two sorted lists into a single sorted list:

Let four sorted lists and , each containing 5 elements, are merged into a single sorted list using the following two-way merge strategy using above function: Merge and to obtain . • Merge and to obtain . • Merge and to obtain the final sorted list . • What is the maximum number of element comparisons performed by the function during the entire process?

A hash table with 8 slots (indexed to ) uses open addressing with linear probing ( ). After inserting 5 keys, the current state of the table is shown below:

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?