# Data Structure

 Question 1
Consider a sequence $a$ of elements $a_0 = 1, a_1 = 5, a_2 = 7, a_3 = 8, a_4 = 9, \; and \; a_5 = 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 $a_0$ to $a_5$ in that order into $S$.
II: enqueue the elements of a from $a_0$ to $a_5$ 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 ___.
 A 7 B 8 C 9 D 2
GATE CSE 2023      Queue
Question 1 Explanation:
 Question 2
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
GATE CSE 2023      Binary Tree
Question 2 Explanation:

 Question 3
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)).
GATE CSE 2023      Heap Tree
Question 3 Explanation:
 Question 4
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 \gt 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) = \left \lfloor m(kA -\left \lfloor kA \right \rfloor ) \right \rfloor$, 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
GATE CSE 2023      Hashing
Question 4 Explanation:
 Question 5
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)