All PYQs: Data Structures
44 real GATE CSE questions from 2012 to 2025, with the official answer key and a worked solution for each. Filter by year, topic, type, marks or keyword.
Questions belong to the GATE organising institutes; this copy is for personal study. Coverage varies by year: questions that need a figure I could not read, or whose answer I could not verify, were left out.
Showing 44 of 44 questions · 0 correct of 0 attempted · marks 0 / 68
GATE 2025 CS2 · Q13MCQ1 markTrees & Binary Search Trees
Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?
GATE 2025 CS1 · Q26MSQ1 markTrees & Binary Search Trees
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS2 · Q35NAT1 markTrees & Binary Search Trees
Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let T be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of T is ______.
GATE 2025 CS1 · Q35NAT1 markHeaps & Priority Queues
The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap T stores 32 keys. The height of T is ______.
GATE 2025 CS2 · Q38MCQ2 marksArrays, Stacks, Queues & Linked Lists
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly linked list with pointers to the head node and tail node of the list. Q: Min-heap implemented using an array. R: Binary Search Tree. Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size n of these data structures?
GATE 2025 CS2 · Q45MSQ2 marksArrays, Stacks, Queues & Linked Lists
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 O(1) 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 options may be correct. Select all that apply, then submit.
GATE 2025 CS1 · Q65NAT2 marksHashing
In a double hashing scheme, h1(k) = k mod 11 and h2(k) = 1 + (k mod 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 [h1(k) + i·h2(k)] mod m. The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is ______.
GATE 2024 CS2 · Q39MCQ2 marksTrees & Binary Search Trees
You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by one, starting with an empty tree. The tree T follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into T, and you do not have access to T. Which one of the following statements is TRUE?
GATE 2024 CS1 · Q41MCQ2 marksHeaps & Priority Queues
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?
GATE 2024 CS1 · Q43MCQ2 marksHeaps & Priority Queues
Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of k is
GATE 2024 CS2 · Q48MSQ2 marksArrays, Stacks, Queues & Linked Lists
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 (400 on top), whereas S2 is empty. 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 options may be correct. Select all that apply, then submit.
GATE 2023 · Q12MCQ1 markHeaps & Priority Queues
Which one of the following sequences when stored in an array at locations A[1], …, A[10] forms a max-heap?
GATE 2023 · Q13MCQ1 markArrays, Stacks, Queues & Linked Lists
Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
GATE 2023 · Q20MCQ1 markHashing
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?
GATE 2023 · Q46MCQ2 marksHeaps & Priority Queues
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A, key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations. When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
GATE 2023 · Q47MCQ2 marksTrees & Binary Search Trees
Consider the C function foo and the binary tree shown.
typedef struct node {
int val;
struct node *left, *right;
}
node;
int foo(node *p) {
int retval;
if (p == NULL) return 0;
else {
retval = p->val + foo(p->left) + foo(p->right);
printf("%d ", retval);
return retval;
}
} The tree: the root 10 has left child 5 and right child 11; node 5 has children 3 (left) and 8 (right); node 11 has only a right child 13. When foo is called with a pointer to the root node of the given binary tree, what will it print?GATE 2023 · Q59NAT2 marksArrays, Stacks, Queues & Linked Lists
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of which are initially empty. I: push the elements of a from a0 to a5 in that order into S. II: enqueue the elements of a from a0 to a5 in that order into Q. III: pop an element from S. IV: dequeue an element from Q. V: pop an element from S. VI: dequeue an element from Q. VII: dequeue an element from Q and push the same element into S. VIII: Repeat operation VII three times. IX: pop an element from S. X: pop an element from S. The top element of S after executing the above operations is ______.
GATE 2022 · Q15MCQ1 markArrays, Stacks, Queues & Linked Lists
Consider the problem of reversing a singly linked list (head → a → b → c → d → e becomes head → e → d → c → b → a). Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
GATE 2022 · Q16MCQ1 markHashing
Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?
GATE 2022 · Q28NAT1 markTrees & Binary Search Trees
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index ______.
GATE 2021 Set 1 · Q10MCQ1 markTrees & Binary Search Trees
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
GATE 2021 Set 1 · Q21NAT1 markArrays, Stacks, Queues & Linked Lists
Consider the following sequence of operations on an empty stack:
push(54); push(52); pop(); push(55); push(62);
s = pop(). Consider the following sequence of operations on an empty queue: enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32);q = dequeue(). The value of s + q is ______.
GATE 2021 Set 1 · Q47MSQ2 marksHashing
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. The state of the hash table: entry 00 is empty; entry 01 is a tree whose left child (3rd bit 0) is a single key and whose right child (3rd bit 1) is split on the 4th bit into two keys; entry 10 is a tree with one key on each side of the 3rd bit; entry 11 holds a single key. Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
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. The state of the hash table: entry 00 is empty; entry 01 is a tree whose left child (3rd bit 0) is a single key and whose right child (3rd bit 1) is split on the 4th bit into two keys; entry 10 is a tree with one key on each side of the 3rd bit; entry 11 holds a single key. 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 options may be correct. Select all that apply, then submit.
GATE 2020 · Q5MCQ1 markTrees & Binary Search Trees
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
GATE 2020 · Q6MCQ1 markTrees & Binary Search Trees
What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?
GATE 2020 · Q16MCQ1 markArrays, Stacks, Queues & Linked Lists
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
GATE 2020 · Q23NAT1 markHashing
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(k) = 1 + (k 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 is ______.
GATE 2020 · Q41MCQ2 marksTrees & Binary Search Trees
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.
GATE 2020 · Q47NAT2 marksHeaps & Priority Queues
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ______.
GATE 2019 Set 2 · Q46NAT2 marksTrees & Binary Search Trees
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ______.
GATE 2018 · Q3MCQ1 markArrays, Stacks, Queues & Linked Lists
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
GATE 2018 · Q20NAT1 markTrees & Binary Search Trees
The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.
GATE 2018 · Q46NAT2 marksHeaps & Priority Queues
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ______.
GATE 2017 Set 1 · Q6MCQ1 markTrees & Binary Search Trees
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are: (Note: the height of a tree with a single node is 0.)
GATE 2016 Set 1 · Q10MCQ1 markArrays, Stacks, Queues & Linked Lists
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
GATE 2016 Set 1 · Q34MCQ2 marksArrays, Stacks, Queues & Linked Lists
The following function computes the maximum value contained in an integer array p[] of size n (n ≥ 1).
int max(int *p, int n) {
int a = 0, b = n − 1;
while (__________) {
if (p[a] <= p[b]) {
a = a + 1;
} else {
b = b − 1;
}
}
return p[a];
} The missing loop condition isGATE 2016 Set 1 · Q37MCQ2 marksHeaps & Priority Queues
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
GATE 2016 Set 1 · Q41NAT2 marksArrays, Stacks, Queues & Linked Lists
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm: while Q is not Empty do { if S is Empty OR Top(S) ≤ Head(Q) then { x := Dequeue(Q); Push(S, x); } else { x := Pop(S); Enqueue(Q, x); } }. The maximum possible number of iterations of the while loop in the algorithm is ______.
GATE 2014 Set 1 · Q40MCQ2 marksHashing
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
GATE 2013 Code A · Q30MCQ2 marksHeaps & Priority Queues
The number of elements that can be sorted in Θ(log n) time using heap sort is
GATE 2013 Code A · Q43MCQ2 marksTrees & Binary Search Trees
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
GATE 2013 Code A · Q44MCQ2 marksArrays, Stacks, Queues & Linked Lists
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
MultiDequeue(Q) {
m = k;
while (Q is not empty) and (m > 0) {
Dequeue(Q);
m = m − 1;
}
} What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?GATE 2012 Code A · Q35MCQ2 marksArrays, Stacks, Queues & Linked Lists
Suppose a circular queue of capacity (n − 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
GATE 2012 Code A · Q47MCQ2 marksTrees & Binary Search Trees
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root.
int height(treeptr n) {
if (n == NULL) return −1;
if (n→left == NULL) if (n→right == NULL) return 0;
else return [Box 1];
else {
h1 = height(n→left);
if (n→right == NULL) return (1 + h1);
else {
h2 = height(n→right);
return [Box 2];
}
}
} The appropriate expressions for the two boxes B1 and B2 are