Programming and Data Structures

GATE CS previous year questions · 27 questions

Topics

GATE CS 2025 Set 1 | Question 21

MSQ · 1 mark

Consider the following \(B^{+}\) tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the \(B^{+}\) tree. Which of the following option(s) is/are CORRECT?

B+ tree: root node with keys 6, 12, 19 and four full leaf nodes holding 1 4 3, 7 9 10, 13 15 17 and 20 21 22
Options for GATE CS 2025 Set 1 | Question 21

Explanation

Answer: (B), (D)

23 is larger than every key, so it belongs in the rightmost leaf (20, 21, 22). That leaf is full, and so are all the other leaves, so no key can be moved to a neighbour: the leaf must split, for example into (20, 21) and (22, 23), sending the separator 22 up to the root.

The root (6, 12, 19) is also full, so it splits too and a new root is created above the two halves. The tree grows from 2 levels to 3 and from 5 nodes to 8.

  • (A) False: the leaf and the root both split.
  • (B) True: each full node splits and its keys are shared between the two halves.
  • (C) False: three nodes are added (a new leaf, the second half of the old root, and the new root).
  • (D) True: the new root adds a level.

Answer: B, D

GATE CS 2025 Set 1 | Question 26

MSQ · 1 mark

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having \(n\) distinct integers?

Options for GATE CS 2025 Set 1 | Question 26

Explanation

Answer: (A), (B)

  • (A) True: a path from the root visits distinct nodes, so it has at most \(n - 1\) edges, and a skewed BST (keys inserted in sorted order) reaches exactly \(n - 1\).
  • (B) True: every left subtree holds smaller keys and every right subtree larger ones, so left–root–right order lists the keys in increasing order.
  • (C) False: a skewed BST has height \(n - 1\), so a search can take \(O(n)\) time; \(O(\log_{2} n)\) is guaranteed only for balanced trees.
  • (D) False: in a min-heap a parent is smaller than its children, but in a BST any left child is smaller than its parent.

Answer: A, B

GATE CS 2025 Set 1 | Question 34

NAT · 1 mark 
#include <stdio.h>
void foo(int *p, int x){
    *p=x;
}
int main(){
    int *z;
    int a = 20, b = 25;
    z = &a;
    foo(z,b);
    printf("%d",a);
    return 0;
}

The output of the given C program is __________. (Answer in integer)

Explanation

Answer: 25

In main, z = &a makes z hold the address of a. The call foo(z,b) copies that address into p and the value 25 into x.

Inside foo, *p=x stores 25 at the address held by p, which is the variable a itself. So a changes from 20 to 25, and printf prints 25.

Answer: 25

GATE CS 2025 Set 1 | Question 35

NAT · 1 mark

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.

Suppose a Min-Heap \(T\) stores 32 keys. The height of \(T\) is _____________. (Answer in integer)

Explanation

Answer: 5

A binary heap is always a complete binary tree: every level is full except possibly the last, which fills from the left. So its shape, and hence its height, depends only on the number of keys.

Levels 0 to 4 hold \(1 + 2 + 4 + 8 + 16 = 31\) keys, so the 32nd key starts level 5. The deepest leaf is therefore 5 edges below the root, matching \(\lfloor \log_2 n \rfloor = \lfloor \log_2 32 \rfloor = 5\).

Answer: 5

GATE CS 2025 Set 1 | Question 43

MCQ · 2 marks · −0.66

Let \(G(V, E)\) be an undirected and unweighted graph with 100 vertices. Let \(d(u, v)\) denote the number of edges in a shortest path between vertices \(u\) and \(v\) in \(V\). Let the maximum value of \(d(u, v),\ u, v \in V\) such that \(u \ne v\), be 30. Let \(T\) be any breadth-first-search tree of \(G\). Which ONE of the given options is CORRECT for every such graph \(G\)?

Options for GATE CS 2025 Set 1 | Question 43

Explanation

Answer: (C)

In a BFS tree rooted at \(r\), every vertex sits at depth equal to its shortest-path distance from \(r\), so the height of \(T\) is the largest distance from \(r\) to any vertex.

Take \(u, v\) with \(d(u, v) = 30\). For any root \(r\), \(30 = d(u, v) \le d(u, r) + d(r, v)\), so \(r\) is at distance at least 15 from \(u\) or from \(v\). Hence the height is always at least 15 (and never more than 30).

Both extremes occur: take a path of 31 vertices and attach the other 69 vertices to its middle vertex. BFS from the middle vertex gives height 15, and BFS from an end of the path gives height 30. So A, B and D can fail, and only C holds for every such graph.

Answer: C

GATE CS 2025 Set 1 | Question 61

NAT · 2 marks 
#include <stdio.h>
int foo(int S[],int size){
    if(size == 0) return 0;
    if(size == 1) return 1;
    if(S[0] != S[1]) return 1+foo(S+1,size-1);
    return foo(S+1,size-1);
}
int main(){
    int A[]={0,1,2,2,2,0,0,1,1};
    printf("%d",foo(A,9));
    return 0;
}

The value printed by the given C program is _______ . (Answer in integer)

Explanation

Answer: 5

Each call compares the first two elements and then moves one place to the right. It adds 1 whenever the two neighbours differ, and the last single element adds 1 more (the size 1 case). So foo returns the number of unequal neighbour pairs plus 1, which is the number of runs of equal values.

In 0, 1, 2, 2, 2, 0, 0, 1, 1 there are 4 unequal pairs: (0, 1), (1, 2), (2, 0) and (0, 1). They split the array into the runs 0 | 1 | 2 2 2 | 0 0 | 1 1.

Value printed \(= 4 + 1 = 5\).

Answer: 5

GATE CS 2025 Set 1 | Question 62

NAT · 2 marks

Let LIST be a datatype for an implementation of linked list defined as follows:

typedef struct list {
    int data;
    struct list *next;
} LIST;

Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.

Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is ________ . (Answer in integer)

L1: 1, 7, 12, 3, 9, 5, 11, 15, 8 and L2: 1, 11, 6, 9, 15, 12, 4, each ending in NULL
int find (int query, LIST *list) {
    while (list != NULL){
        if(list->data == query) return 1;
        list = list->next;
    }
    return 0;
}
int main () {
      … … …
    ptr1=L1; ptr2=L2;
    while (ptr1->next != NULL){
        query = ptr1->next->data;
        if (find (query, L2))
            ptr1->next = ptr1->next->next;
        else ptr1 = ptr1->next;
    }
      … … …
    return 0;
}

Explanation

Answer: 5

The loop always tests the node after ptr1, so the head of L1 is never examined. If that next value is in L2, the node is unlinked and ptr1 stays where it is; otherwise ptr1 moves forward.

L2 holds {1, 11, 6, 9, 15, 12, 4}. Going through L1 after the head: 7 kept, 12 removed, 3 kept, 9 removed, 5 kept, 11 removed, 15 removed, 8 kept.

L1 becomes 1 → 7 → 3 → 5 → 8. The head node 1 stays even though 1 is also in L2.

Answer: 5

GATE CS 2025 Set 1 | Question 63

NAT · 2 marks

Consider the following C program:

#include <stdio.h>
int gate (int n) {
    int d, t, newnum, turn;
    newnum = turn = 0; t=1;
    while (n>=t) t *= 10;
    t /=10;
    while (t>0) {
        d = n/t;
        n = n%t;
        t /= 10;
        if (turn) newnum = 10*newnum + d;
        turn = (turn + 1) % 2;
    }
    return newnum;
}
int main () {
    printf ("%d", gate(14362));
    return 0;
}

The value printed by the given C program is _______ . (Answer in integer)

Explanation

Answer: 46

The first loop multiplies t by 10 until it exceeds n, ending at \(t = 100000\); then t /= 10 gives \(t = 10000\), the place value of the leading digit. The second loop reads the digits of 14362 from left to right: 1, 4, 3, 6, 2.

turn starts at 0 and flips after every digit, so only the 2nd and 4th digits are appended: newnum becomes 4 and then \(10 \times 4 + 6 = 46\). The digits 1, 3 and 2 are skipped.

Answer: 46

GATE CS 2025 Set 1 | Question 65

NAT · 2 marks

In a double hashing scheme, \(h_1(k) = k \bmod 11\) and \(h_2(k) = 1 + (k \bmod 7)\) are the auxiliary hash functions. The size \(m\) of the hash table is 11. The hash function for the \(i\)-th probe in the open address table is \([h_1(k) + i\,h_2(k)] \bmod m\). The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24.

The slot at which key 24 gets stored is ___________. (Answer in integer)

Explanation

Answer: 10 to 11

The first five keys go to their home slots \(h_1(k)\) with no collision: 63 → 8, 50 → 6, 25 → 3, 79 → 2, 67 → 1.

For 24: \(h_1(24) = 2\), which is taken by 79, and \(h_2(24) = 1 + (24 \bmod 7) = 4\).

  • \(i = 1\): \((2 + 4) \bmod 11 = 6\), taken by 50.
  • \(i = 2\): \((2 + 8) \bmod 11 = 10\), free.

So 24 is stored in slot 10, with slots numbered 0 to 10. The key also accepts 11, the same slot counted from 1.

Answer: 10

GATE CS 2025 Set 2 | Question 13

MCQ · 1 mark · −0.33

Consider a binary tree \(T\) in which every node has either zero or two children. Let \(n \gt 0\) be the number of nodes in \(T\).

Which ONE of the following is the number of nodes in \(T\) that have exactly two children?

Options for GATE CS 2025 Set 2 | Question 13

Explanation

Answer: (B)

Let \(k\) be the number of nodes with two children; all other nodes are leaves. Count the edges in two ways:

  • each of the \(k\) internal nodes has 2 child edges, giving \(2k\) edges;
  • every node except the root has exactly one edge to its parent, giving \(n - 1\) edges.

So \(2k = n - 1\), that is, \(k = \frac{n-1}{2}\). For example, a root with two leaf children has \(n = 3\) and \(k = 1\). Such a tree always has an odd number of nodes, so \(\frac{n}{2}\) and \(\frac{n-2}{2}\) are not even whole numbers, while \(\frac{n+1}{2}\) counts the leaves.

Answer: B