Recent questions tagged python-&-dsa

A function $\texttt{shuffle(s)}$ takes a sequence $\texttt{s}$ with an even number of elements. It returns a new list by interleaving the first half of $\texttt{s}$ with ...

Consider the following Python code:s = [3] s.extend([4, 5]) s.extend([s.append(9), s.append(10)]) print(s)What is the output of the code above?[3, 4, 5, 9, 10][3, 4, 5, N...

Consider the following Python code:s = [9, 7, 8] a, b = s, s[:] print(a is s, b == s, b is s) print(a.pop()) print(a + b)What is the output of the code above?True True Tr...

Consider the following Python code:s = [6, 7, 8] print(s.append(6)) s.insert(0, 9) x = s.pop(1) s.remove(x) print(s)What is the output of the code above?None [9, 7, 8]Non...

Suppose we convert a balanced Binary Search Tree (BST) containing $n$ elements into a Sorted Doubly Linked List (DLL) in-place (without using extra memory for new nodes)....

A hash table of size $M=11$ uses the hash function $h(k)=k \bmod 11$. QUADRATIC PROBING is used for collision resolution with the probing function $h(k, i)=\left(h(k)+i^2...

Let $G=(V, E)$ be a directed graph with source vertex $s$. We run DIJKSTRA'S ALGORITHM to find the shortest paths. During the execution, the "Relaxation" step is performe...

Consider the QUICKSORT algorithm applied to an array of $n$ distinct elements. Let the pivot always be chosen as the MEDIAN of the array. What is the recurrence relation ...

A double-ended queue (DEQUE) supports insertion and deletion at both ends $(f$ for front, $r$ for rear$)$. If we want to implement a STACK using this DEQUE, which of the ...

When performing an In-order traversal on a Binary Search Tree (BST) containing $n$ distinct elements, what is the specific property of the resulting sequence?The first el...

Consider a Directed Acyclic Graph (DAG). We want to find the shortest path from a source vertex $S$ to all other vertices. Since the graph is a DAG, which approach provid...

In a hash table with $10$ slots and collisions resolved by chaining, the following keys are inserted: $5,25,19,15,20,33,12,17,10$. If the hash function is $h(k)=k \% 10$,...

A circular queue is implemented using an array of size $M$. If 'front' points to the index of the first element and 'rear' points to the index of the last element, what i...

Suppose we are sorting an array of $n$ elements using Quicksort. In the worst-case scenario, the partitioning process always picks the smallest or largest element as the ...

Consider a simple, weighted, directed graph $G=(V, E)$ with $n$ vertices and $m$ edges. Let $w(u, v)$ be the weight of the edge from $u$ to $v$. Which of the following st...

Consider a Binary Search Tree (BST) where the post-order traversal is $2,4,3,7,9,8,5$. What is the pre-order traversal of this tree?$5,3,2,4,8,7,9$ $2,3,4,5,7,8,9$ $5,8,9...

What is the worst-case time complexity of the QuickSort algorithm when the pivot is always chosen as the middle element and the input array is already sorted in ascending...

Which of the following properties is/are TRUE for a Simple Undirected Graph $G$ with $n$ vertices and $k$ connected components?DIJKSTRA'S ALGORITHM CAN BE USED TO FIND TH...

In Python, consider a list $\verb|L|$ being used to implement a stack. If we perform $n$ $\verb|append()|$ operations starting from an empty list, what is the amortized t...

An array of $n$ elements is sorted. We want to search for an element using Binary Search. If we modified the algorithm to split the array into three equal parts instead o...

Which of the following statements is TRUE regarding Breadth-First Search (BFS) and Depth-First Search (DFS) on an unweighted, connected graph?BFS finds the shortest path ...

Consider a hash table with $10$ slots using open addressing with linear probing. The hash function is $h(k)=k \text{(mod 10)}$. After inserting the keys $42,52,62$, and $...

During the execution of Quicksort on an array of $n$ distinct elements, if the pivot is always chosen such that it is the third smallest element in the current sub-array,...

A complete binary tree with $n$ nodes is represented in an array starting from index $1$. For a node located at index $i$, what is the index of its right child, and what ...

Consider the Merge Sort algorithm being applied to an array of $n$ elements. Which of the following statements is/are TRUE regarding its operational characteristics?Merge...

What is the output of the following Python code snippet?def modify_list(lst): lst.append([3, 4]) lst = [7, 8] return lst my_list = [1, 2] new_list = modif...

Consider a Directed Acyclic Graph (DAG). If you perform a Depth First Search (DFS) on this graph and record the "finish times" of each vertex (the time at which the recur...

Suppose you are searching for the value $X=35$ in a sorted array $A= [10,20,30,40,50,60,70]$ using the Binary Search algorithm. If the algorithm uses the formula mid $=l ...

Consider a scenario where you are given a stack $S$ and an empty queue $Q$. You perform the following sequence of operations:Push elements $10,20,30,40$ into $S$ in that ...

Consider the Merge Sort algorithm applied to an array $A$ of $n$ distinct integers. During the Merge step, we maintain two pointers for the sorted subarrays $L$ and $R$. ...