GATE CS 1987 Q1-xviii — Searching, Sorting, Hashing

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)