Data Structure Question Paper with Answer Pdf Free Download | Gate CSE Data Structure Practice Paper with Answers
GATE CSE 2024 SET-2
Q1): 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.
Stack S1
| 400 (Top) |
| 300 |
| 200 |
| 100 |
Stack S2
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?
- A) 100, 200, 400, 300
- B) 200, 300, 400, 100
- C) 400, 200, 100, 300
- D) 300, 200, 400, 100
Q2): 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?
- A) Inorder traversal of T can be determined from V
- B) Root node of T can be determined from V
- C) Preorder traversal of T can be determined from V
- D) Postorder traversal of T can be determined from V
Q3): Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in 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][2,5,3,1,4,2,6] is _____
GATE CSE 2024 SET-1
Q4): 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
- A) 53
- B) 52
- C) 27
- D) 1
Q5): An array [82,101,90,11,111,75,33,131,44,93][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?
- A) 82,90,101
- B) 82,11,93
- C) 131,11,93
- D)131,111,90
Q6): Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below.
| Operator | Precedence | Associativity |
|---|---|---|
| + | High | Left |
| − | High | Left |
| ∗ | Medium | Right |
| / | Low | Right |
The value of the expression 3+1+5∗2/7+2−4−7−6/23+1+5∗2/7+2−4−7−6/2 as per the above rules is _____
Q7): In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
- A) Only the root node
- B) All leaf nodes
- C) All internal nodes
- D) Only the leftmost leaf node
GATE CSE 2023
Q8): Consider a sequence aa 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 ___.
Q9): 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;
}
}
When foo is called with a pointer to the root node of the given binary tree, what will it print?
- A) 3 8 5 13 11 10
- B) 3 5 8 10 11 13
- C) 3 8 16 13 24 50
- D) 3 16 8 50 24 13
Q10): 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?
- A) Both Extract-Max(A) and Insert(A,key) run in O(1).
- B) Both Extract-Max(A) and Insert(A,key) run in O(log(n)).
- C) Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n).
- D) Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)).
Q11): 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?
- A) Division method, i.e., use the hash function h(k)=k mod m
- B) Multiplication method, i.e., use the hash function h(k)=⌊m(kA−⌊kA⌋)⌋, where A is a carefully chosen constant.
- C) Universal hashing method.
- D) If k is a prime number, use Division method. Otherwise, use Multiplication method
Q12): 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?
- A) SLLdel is O(1) and DLLdel is O(n)
- B) Both SLLdel and DLLdel are O(log(n))
- C) Both SLLdel and DLLdel are O(1)
- D) SLLdel is O(n) and DLLdel is O(1)
Q13): Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap?
- A) 23, 17, 10, 6, 13, 14, 1, 5, 7, 12
- B) 23, 17, 14, 7, 13, 10, 1, 5, 6, 12
- C) 23, 17, 14, 6, 13, 10, 1, 5, 7, 15
- D) 23, 14, 17, 1, 10, 13, 16, 12, 7, 5
More Practice: C Programming Gate Questions with Solutions Pdf Download