Data Structure GATE Question Answers with Explanation.
Q1 – Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap? (GATE 2023)
Â
23, 17, 10, 6, 13, 14, 1, 5, 7, 12
23, 17, 14, 7, 13, 10, 1, 5, 6, 12
23, 17, 14, 6, 13, 10, 1, 5, 7, 15
23, 14, 17, 1, 10, 13, 16, 12, 7, 5
Ans – (2)
Explanation –
Q2 – 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)
Â
SLLdel is O(1) and DLLdel is O(n)
Both SLLdel and DLLdel are O(log(n))
Both SLLdel and DLLdel are O(1)
SLLdel is O(n) and DLLdel is O(1)
Ans – (4)
Explanation –
Q3 – 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 2023)
Ans – (8)
Explanation –Â