MSQ1 mark
Let be an odd number greater than 100. Consider a binary minheap with elements stored in an array whose index starts from 1.
Which of the following indices of do/does NOT correspond to any leaf node of the minheap?
One or more correct
MSQ1 mark
Consider a hash table that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is .
Consider the following sequence of insertions performed on :
Which of the following positions in the hash table is/are empty after these insertions are performed?
One or more correct
MSQ2 marks
Consider a binary search tree (BST) with leaf nodes (). Given any node , the key present in the node is denoted as . All the keys present in the given BST are distinct. The keys belong to the set of real numbers.
For a node , let denote the node that is its inorder successor. If a node does not have an inorder successor, then is . As there are no duplicates, if is not , then .
Corresponding to every leaf node that has a non-NULL , a new key with the following property is to be inserted into the BST.
Let represent the list of all such new keys to be inserted into the BST.
Which of the following statements is/are true?
One or more correct
MSQ2 marks
Consider a stack and a queue . Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in that order. When an element arrives, it is assigned either to (pushed on ) or to (enqueued to ). Once all the five elements are stored, the output is generated in two steps. First, stack is emptied by popping all elements. Then queue is emptied by dequeueing all elements. The output obtained by following this process is 4 3 1 2 5.
Given the output, the objective is to predict whether an element was assigned to or .
Which of the following options is/are possible valid assignment(s) of the elements?
*Note:* In the options, the notation denotes that element was assigned to and denotes that element was assigned to .
One or more correct
MSQ1 mark
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having distinct integers?
One or more correct
MSQ2 marks
Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct.
We wish to augment the stack data structure with an time MIN operation that returns a pointer to the record with smallest key present in the stack
1) without deleting the corresponding record, and
2) without increasing the complexities of the standard stack operations.
Which one or more of the following approach(es) can achieve it?
One or more correct
MSQ2 marks
Consider the following C function definition.
int f(int x, int y) {
for (int i=0; i<y; i++) {
x=x+x+y;
}
return x;
}One or more correct
MSQ1 mark
Consider the following C function definition.
int fX(char *a){
char *b = a;
while(*b)
b++;
return b - a;}One or more correct
MSQ2 marks
Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below.
Only the following three operations are available:
PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.
Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack.
Which of the following output sequences can be generated by using the above operations?
One or more correct
MSQ2 marks
Consider a *dynamic* hashing approach for 4-bit integer keys:
1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.
Consider the following state of the hash table (see figure).
Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
One or more correct
Answer key coming soon
Use ← → to move