GATE DA Programming, Data Structures and Algorithms Previous Year Questions

GATE DA 2024 | Question 16

MCQ · 1 mark · −0.33

Match the items in Column 1 with the items in Column 2 in the following table:

Column 1	Column 2
(p) First In First Out	(i) Stacks
(q) Lookup Operation	(ii) Queues
(r) Last In First Out	(iii) Hash Tables

(p) − (ii), (q) − (iii), (r) − (i) (p) − (ii), (q) − (i), (r) − (iii) (p) − (i), (q) − (ii), (r) − (iii) (p) − (i), (q) − (iii), (r) − (ii)

Explanation

Answer: (A)

Each phrase in Column 1 is the defining behaviour of one structure:

(p) First In First Out: a queue removes items in the order they arrived, like a line at a counter, so (p) − (ii).
(q) Lookup: a hash table exists to find a value by its key in expected constant time, so (q) − (iii).
(r) Last In First Out: a stack always removes the most recently added item, like a pile of plates, so (r) − (i).

Only option (A) has all three pairs; (C) and (D) pair FIFO with stacks, and (B) pairs lookup with stacks.

Answer: A

Consider performing uniform hashing on an open address hash table with load factor \(\alpha = \frac{n}{m} < 1\), where \(n\) elements are stored in the table with \(m\) slots. The expected number of probes in an unsuccessful search is at most \(\frac{1}{1-\alpha}\).

Inserting an element in this hash table requires at most ______ probes, on average.

\(\ln\left(\dfrac{1}{1-\alpha}\right)\) \(\dfrac{1}{1-\alpha}\) \(1+\dfrac{\alpha}{2}\) \(\dfrac{1}{1+\alpha}\)

Explanation

Answer: (B)

To insert a key with open addressing, we follow the key's probe sequence until we reach an empty slot and store the key there. An unsuccessful search for the same key follows the same sequence and also stops at the first empty slot, so an insertion makes exactly the probes of an unsuccessful search. Its average cost therefore has the same bound, at most \(\frac{1}{1-\alpha}\) probes.

Options A and C are smaller than this bound for every \(0 < \alpha < 1\), so they understate the cost; they resemble formulas for successful searches. Option D is even below 1, although every insertion probes at least one slot.

Answer: B

GATE DA 2024 | Question 28

MSQ · 1 mark

Consider the following tree traversals on a full binary tree:

(i) Preorder
(ii) Inorder
(iii) Postorder

Which of the following traversal options is/are sufficient to uniquely reconstruct the full binary tree?

(i) and (ii) (ii) and (iii) (i) and (iii) (ii) only

Explanation

Answer: (A), (B), (C)

Take the node labels to be distinct. In a full binary tree every node has 0 or 2 children.

With inorder (A, B): the root is the first node in preorder or the last in postorder, and its position in inorder splits the other nodes into the left and right subtrees. Repeating this rebuilds any binary tree.
Preorder and postorder (C): for general trees a lone child could be left or right, but here an internal node always has two children. The node after the root in preorder is the left child, and its place in postorder marks where the left subtree ends, so the split is again unique.
Inorder only (D): the full trees with root 2 (children 1 and 4, where 4 has children 3 and 5) and root 4 (children 2 and 5, where 2 has children 1 and 3) both give 1 2 3 4 5.

Answer: A, B, C

GATE DA 2024 | Question 30

NAT · 1 mark

Consider sorting the following array of integers in ascending order using an in-place Quicksort algorithm that uses the last element as the pivot.

60

70

80

90

100

The minimum number of swaps performed during this Quicksort is ______.

Your answer

Explanation

Answer: 0

The array is already sorted. In the first partition the pivot is 100 and every other element is smaller, so they all already sit on the left side and the pivot is already in its final place. Each later call looks the same: on 60 70 80 90 the pivot 90 is the largest, then 80, then 70.

A Lomuto-style partition would only ever swap an element with itself here, because its two indices are always equal, and such a step moves nothing and can be skipped. No element ever has to change place, so the minimum number of swaps is 0.

Answer: 0

GATE DA 2024 | Question 32

NAT · 1 mark

The fundamental operations in a double-ended queue D are:

insertFirst(e) – Insert a new element e at the beginning of D.
insertLast(e) – Insert a new element e at the end of D.
removeFirst() – Remove and return the first element of D.
removeLast() – Remove and return the last element of D.

In an empty double-ended queue, the following operations are performed:

insertFirst(10)

insertLast(32)

a ←removeFirst()

insertLast(28)

insertLast(17)

a ←removeFirst()

a ← removeLast()

The value of a is ______.

Your answer

Explanation

Answer: 17

Trace the deque, writing its front on the left:

insertFirst(10): [10]
insertLast(32): [10, 32]
removeFirst() returns 10, so a = 10: [32]
insertLast(28) and insertLast(17): [32, 28, 17]
removeFirst() returns 32, so a = 32: [28, 17]
removeLast() returns 17, so a = 17: [28]

Each assignment overwrites a, so its final value is 17. The 28 is still in the deque and is never assigned.

Answer: 17

GATE DA 2024 | Question 38

MCQ · 2 marks · −0.66

Consider the following Python code:

def count(child_dict, i):
    if i not in child_dict.keys():
         return 1
    ans = 1
    for j in child_dict[i]:
        ans += count(child_dict, j)
    return ans

child_dict = dict()
child_dict[0] = [1,2]
child_dict[1] = [3,4,5]
child_dict[2] = [6,7,8]
print(count(child_dict,0))

Which ONE of the following is the output of this code?

6 1 8 9

Explanation

Answer: (D)

child_dict describes a tree: node 0 has children 1 and 2, node 1 has children 3, 4, 5, and node 2 has children 6, 7, 8. A node that is not a key (3 to 8) is a leaf and returns 1. Any other node returns 1 for itself plus the counts of its children, so count counts every node in the subtree.

count(child_dict, 1) \(= 1 + 3 = 4\), and likewise count(child_dict, 2) \(= 4\).
count(child_dict, 0) \(= 1 + 4 + 4 = 9\).

The tree has the nine nodes 0 to 8. Option A (6) counts only the leaves, and option C (8) leaves out the root.

Answer: D

GATE DA 2024 | Question 39

MCQ · 2 marks · −0.66

Consider the function computeS(X) whose pseudocode is given below:

computeS(X)
S[1] ← 1
for i ←2 to length(X)
  S[i] ← 1
  if X[i - 1] ≤ X[i]
      S[i] ← S[i] + S[i - 1]
  end if
end for
return S

Which ONE of the following values is returned by the function computeS(X) for \(X = [6, 3, 5, 4, 10]\)?

[1, 1, 2, 3, 4] [1, 1, 2, 3, 3] [1, 1, 2, 1, 2] [1, 1, 2, 1, 5]

Explanation

Answer: (C)

\(S[i]\) is the length of the non-decreasing run that ends at position \(i\): it restarts at 1 and adds \(S[i-1]\) only when \(X[i-1] \le X[i]\). With \(X = [6, 3, 5, 4, 10]\), indexed from 1:

\(S[1] = 1\).
\(i = 2\): \(6 \le 3\) is false, so \(S[2] = 1\).
\(i = 3\): \(3 \le 5\), so \(S[3] = 1 + S[2] = 2\).
\(i = 4\): \(5 \le 4\) is false, so \(S[4] = 1\).
\(i = 5\): \(4 \le 10\), so \(S[5] = 1 + S[4] = 2\).

Options A and B miss the restart at the drop from 5 to 4; option D restarts there but then overstates \(S[5]\).

Answer: C

GATE DA 2024 | Question 40

MCQ · 2 marks · −0.66

Let \(F(n)\) denote the maximum number of comparisons made while searching for an entry in a sorted array of size \(n\) using binary search.

Which ONE of the following options is TRUE?

\(F(n) = F(\lfloor n/2 \rfloor) + 1\) \(F(n) = F(\lfloor n/2 \rfloor) + F(\lceil n/2 \rceil)\) \(F(n) = F(\lfloor n/2 \rfloor)\) \(F(n) = F(n - 1) + 1\)

Explanation

Answer: (A)

Binary search compares the target with the middle element. Either it matches, or the search continues in just one of the two parts left after removing the middle. With \(n\) elements the larger part has \(\lfloor n/2 \rfloor\) elements, so in the worst case one comparison is followed by a search of size \(\lfloor n/2 \rfloor\):

\[F(n) = F(\lfloor n/2 \rfloor) + 1, \quad F(1) = 1,\]

which solves to \(F(n) = \lfloor \log_{2} n \rfloor + 1\).

Option B searches both halves, C forgets the comparison just made (so \(F\) would never grow), and D discards only one element per step, which describes linear search.

Answer: A

GATE DA 2024 | Question 41

MCQ · 2 marks · −0.66

Consider the following Python function:

def fun(D, s1, s2):
       if s1 < s2:
          D[s1], D[s2] = D[s2], D[s1]
          fun(D, s1+1, s2-1)

What does this Python function fun() do? Select the ONE appropriate option below.

It finds the smallest element in D from index s1 to s2, both inclusive. It performs a merge sort in-place on this list D between indices s1 and s2, both inclusive. It reverses the list D between indices s1 and s2, both inclusive. It swaps the elements in D at indices s1 and s2, and leaves the remaining elements unchanged.

Explanation

Answer: (C)

Each call swaps the two outer elements D[s1] and D[s2], then recurses on the next pair inward, s1+1 and s2-1. It stops when the indices meet or cross, so the middle element of an odd-length range stays where it is.

For example, with D = [1, 2, 3, 4, 5], fun(D, 0, 4) swaps 1 and 5, then 2 and 4, giving [5, 4, 3, 2, 1]: the segment from s1 to s2 is reversed in place.

Option D describes only the first call, but the recursion keeps swapping the inner pairs. The function never compares values, so it cannot find a minimum (A) or sort (B).

Answer: C

GATE DA 2024 | Question 45

MCQ · 2 marks · −0.66

Consider the following sorting algorithms:

(i) Bubble sort
(ii) Insertion sort
(iii) Selection sort

Which ONE among the following choices of sorting algorithms sorts the numbers in the array [4, 3, 2, 1, 5] in increasing order after exactly two passes over the array?

(i) only (iii) only (i) and (iii) only (ii) and (iii) only

Explanation

Answer: (B)

Trace two passes of each algorithm on [4, 3, 2, 1, 5]:

Bubble sort: pass 1 carries 4 to its place, giving [3, 2, 1, 4, 5]; pass 2 carries 3, giving [2, 1, 3, 4, 5]. Not yet sorted.
Insertion sort: pass 1 inserts 3, giving [3, 4, 2, 1, 5]; pass 2 inserts 2, giving [2, 3, 4, 1, 5]. Not yet sorted.
Selection sort: pass 1 swaps the minimum 1 into the first position, giving [1, 3, 2, 4, 5]; pass 2 swaps 2 into the second position, giving [1, 2, 3, 4, 5]. Sorted.

Only selection sort is done, because its two swaps happen to fix every misplaced element; bubble sort and insertion sort each need a third pass.

Answer: B