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 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 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 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 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)
GATE CSE 2023      Link List




There are 5 questions to complete.

Leave a Comment