GATE CS Searching, Sorting, Hashing questions

Let $n$ be an odd number greater than $100$. Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from $1$. Which of the following indices of $P$ do/does NOT correspond to any leaf node of the minheap?

Consider a hash table $P[0,1, \ldots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x)=(x+7) \bmod 11$. Consider the following sequence of insertions performed on $P$ : $$\text{ 1,13, 22, 15, 11, } 24$$ Which of the following positions in the hash table is/are empty …

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with $23$ nodes is $\_\_\_\_$.(answer in integer)

Let $P$ be the set of all integers from $1$ to $15$. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?

The following sequence corresponds to the preorder traversal of a binary search tree $T$ : $$50,25,13,40,30,47,75,60,70,80,77$$ The position of the element $60$ in the postorder traversal of $T$ is $\_\_\_\_$ . (answer in integer) Note: The position begins with $1$.

The keys $5,28,19,15,26,33,12,17,10$ are inserted into a hash table using the hash function $h(k)=k \bmod 9$. The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is $\_\_\_\_$. (answer in integer)

Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will carry out a total of $7$ merge operations. A merge operation on sorted left array $L$ and sorted right array $R$ is said to be void if the output of the merge operation is the …

Consider a binary search tree (BST) with $n$ leaf nodes $(n>0)$. Given any node $V$, the key present in the node is denoted as $\operatorname{Val}(V)$. All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node $V$, let $\operatorname{Suc}(V)$ denote the node that is its inorder successor. If a …

The pseudocode of a function $\text{fun ()}$ is given below: fun(int A[0,....,n-1]) { for i=0 to n-2 for j=0 to n-i-2 if (A[j]>A[j+1]) then swap A[j] and A[j+1] } Let $A[0, \ldots, 29]$ be an array storing $30$ distinct integers in descending order. The number of swap operations that will be performed, if the function $\text{fun ()}$ is called …

In a double hashing scheme, $h_{1}(k)=k \bmod 11$ and $h_{2}(k)=1+(k \bmod 7)$ are the auxiliary hash functions. The size $m$ of the hash table is $11$. The hash function for the $i$-th probe in the open address table is $\left[h_{1}(k)+i h_{2}(k)\right] \bmod m$. The following keys are inserted in the given order: $63,50,25,79,67,24$. The slot …

​​​​Consider an unorders list of $N$ distinct integers. What is the minimum number of element comaparisons required to find an integer in the list that is NOT the largest in the list?

​​An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1 \leq i \leq n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 \ldots n]$ is sorted in the non-increasing order. Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons …

​​​​​An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?

Let $\text{A}$ be an array containing integer values. The distance of $\text{A}$ is defined as the minimum number of elements in $\text{A}$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array $[2,5,3,1,4,2,6]$ is ___________.

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k>m$. Which one of the following is the best hashing strategy to counteract the adversary?

​​​Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_{1}$ and $h_{2}.$ Further suppose our hashing scheme uses $h_{1}$ for the odd keys and $h_{2}$ for the even keys. What is the expected number of keys in a slot?

Consider the following array.$$\begin{array}{|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array}$$ Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys: There is a main hash table of size $4$. The $2$ least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to …

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?

Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ …