GATE CS Programming and Data Structures Previous Year Questions

GATE CS 2025 Set 2 | Question 19

MCQ · 1 mark · −0.33

Consider the following C program:

#include <stdio.h>
void stringcopy(char *, char *);
int main(){
    char a[30] = "@#Hello World!";
    stringcopy(a, a + 2);
    printf("%s\n", a);
    return 0;
}
void stringcopy(char *s, char *t) {
    while(*t)
        *s++ = *t++;
}

Which ONE of the following will be the output of the program?

@#Hello World! Hello World! ello World! Hello World!d!

Explanation

Answer: (D)

The array holds the 14 characters @#Hello World! at indices 0 to 13, followed by '\0' at index 14.

stringcopy(a, a + 2) copies one character at a time from t to s, with t always two places ahead of s. Every character is therefore read before it can be overwritten, and the 12 characters Hello World! land in indices 0 to 11.

The loop stops as soon as *t is '\0', so the terminator is never copied. Indices 12 and 13 keep their old characters d!, and the string still ends at index 14, so printf prints Hello World!d!.

Answer: D

GATE CS 2025 Set 2 | Question 33

NAT · 1 mark

int x=126,y=105;
do {
    if(x>y) x=x-y;
    else y=y-x;
} while(x!=y);

printf("%d",x);

The output of the given C code segment is ________. (Answer in integer)

Your answer

Explanation

Answer: 21

The loop is the subtraction form of Euclid’s algorithm. Replacing the larger number by the difference of the two never changes their greatest common divisor, and the values keep shrinking until they are equal, so both end up as \(\gcd(126, 105)\).

Trace of \((x, y)\): \((126, 105) \to (21, 105) \to (21, 84) \to (21, 63) \to (21, 42) \to (21, 21)\). Now x!=y is false, the do-while loop exits and 21 is printed.

Answer: 21

GATE CS 2025 Set 2 | Question 35

NAT · 1 mark

Suppose the values \(10, -4, 15, 30, 20, 5, 60, 19\) are inserted in that order into an initially empty binary search tree. Let \(T\) be the resulting binary search tree. The number of edges in the path from the node containing \(19\) to the root node of \(T\) is ___________. (Answer in integer)

Your answer

Explanation

Answer: 4

Insert the keys in order, going left for a smaller key and right for a larger one:

10 is the root; \(-4\) goes left of 10 and 15 right of 10.
30 goes right of 15, and 20 goes left of 30.
5 goes right of \(-4\), and 60 goes right of 30.
19 is larger than 10 and 15 but smaller than 30 and 20, so it becomes the left child of 20.

The path from 19 up to the root is \(19 \to 20 \to 30 \to 15 \to 10\): 4 edges, i.e. 19 sits at depth 4.

Answer: 4

GATE CS 2025 Set 2 | Question 45

MSQ · 2 marks

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct.

We wish to augment the stack data structure with an \(O(1)\) time MIN operation that returns a pointer to the record with smallest key present in the stack

without deleting the corresponding record, and
without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

Keep with every record in the stack, a pointer to the record with the smallest key below it. Keep a pointer to the record with the smallest key in the stack. Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order. Keep a Min-Heap in which the key values of the records in the stack are maintained.

Explanation

Answer: (A)

A works. On PUSH, the new record stores a pointer to the minimum of the records below it: the smaller of the old top and the record the old top points to, found in \(O(1)\). MIN compares the top with the record its pointer names, also \(O(1)\). POP just removes the top, and the pointers in the records left behind are still correct.
B fails. Once the minimum is popped, finding the new minimum needs an \(O(n)\) scan, so POP gets slower.
C fails. Keeping an array sorted costs \(O(n)\) shifting on each PUSH and POP.
D fails. Heap insertion and deletion take \(O(\log n)\), so PUSH and POP are no longer \(O(1)\).

Answer: A

GATE CS 2025 Set 2 | Question 62

NAT · 2 marks

Consider the following C program:

#include <stdio.h>
int main(){
    int a;
    int arr[5] = {30,50,10};
    int *ptr;
    ptr = &arr[0] + 1;
    a = *ptr;
    (*ptr)++;
    ptr++;
    printf("%d", a + (*ptr) + arr[1]);
    return 0;
}

The output of the above program is ___________. (Answer in integer)

Your answer

Explanation

Answer: 111

The array holds {30, 50, 10, 0, 0}: elements without an initialiser become 0.
ptr = &arr[0] + 1 points to arr[1], so a = 50.
(*ptr)++ increments the element, not the pointer, so arr[1] becomes 51. The copy in a stays 50.
ptr++ moves the pointer to arr[2], so *ptr is 10.

The program prints \(50 + 10 + 51 = 111\).

Answer: 111

GATE CS 2025 Set 2 | Question 63

NAT · 2 marks

Consider the following C program:

#include <stdio.h>

int g(int n) {
    return (n+10);
}

int f(int n) {
    return g(n*2);
}

int main() {
    int sum, n;
    sum=0;
    for (n=1; n<3; n++)
        sum += g(f(n));
    printf ("%d", sum);
    return 0;

}

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

Your answer

Explanation

Answer: 46

Compose the two functions: \(f(n) = g(2n) = 2n + 10\), so \(g(f(n)) = 2n + 20\).

The loop runs only for \(n = 1\) and \(n = 2\), because the condition is \(n < 3\):

\(n = 1\): \(f(1) = 12\) and \(g(12) = 22\).
\(n = 2\): \(f(2) = 14\) and \(g(14) = 24\).

So sum ends at \(22 + 24 = 46\). Running the loop for \(n = 3\) as well would wrongly add 26.

Answer: 46

GATE CS 2024 Set 1 | Question 18

MCQ · 1 mark · −0.33

Consider the following C program:

#include <stdio.h>
int main(){
   int a = 6;
   int b = 0;
   while(a < 10) {
      a = a / 12 + 1;
      a += b;}
   printf("%d", a);
   return 0;}

Which one of the following statements is CORRECT?

The program prints 9 as output The program prints 10 as output The program gets stuck in an infinite loop The program prints 6 as output

Explanation

Answer: (C)

Both operands of a / 12 are integers, so the division truncates. Starting from a = 6, the first pass gives \(6/12 = 0\), so a becomes \(0 + 1 = 1\), and a += b adds 0.

On every later pass a is 1: the test \(1 < 10\) holds, \(1/12 = 0\), and a is set to 1 again. Since b stays 0, nothing ever raises a to 10, so the condition never fails, the loop never exits and printf is never reached.

Options A, B and D all assume that the loop ends and something is printed.

Answer: C

GATE CS 2024 Set 1 | Question 19

MCQ · 1 mark · −0.33

Consider the following C program:

#include <stdio.h>
void fX();
int main(){
   fX();
   return 0;}

void fX(){
 char a;
 if((a=getchar()) != '\n')
     fX();
 if(a != '\n')
     putchar(a);}

Assume that the input to the program from the command line is 1234 followed by a newline character. Which one of the following statements is CORRECT?

The program will not terminate The program will terminate with no output The program will terminate with 4321 as output The program will terminate with 1234 as output

Explanation

Answer: (C)

Each call of fX reads one character into its own local variable a. If that character is not a newline, the call recurses first and prints its own character only after the inner call returns, so characters come out in the reverse of the order they were read.

With the input 1234 and a newline, five nested calls read '1', '2', '3', '4' and '\n'. The fifth call neither recurses nor prints, and returns. The waiting calls then print 4, 3, 2 and 1 as they unwind, and main returns.

The newline ends the recursion, so the program terminates (not A) and prints 4321. Printing 1234 would need putchar before the recursive call.

Answer: C

GATE CS 2024 Set 1 | Question 41

MCQ · 2 marks · −0.66

An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?

82, 90, 101 82, 11, 93 131, 11, 93 131, 111, 90

Explanation

Answer: (D)

No option starts with the smallest key, 11, so the heap meant is a max-heap. Build it bottom-up, sifting down from the last internal node (position 5) back to the root:

111 is already larger than its child 93; 11 swaps with its larger child 131; 90 stays above 75 and 33.
101 swaps with its larger child, now 131.
At the root, 82 swaps with 131, then with 111, then with 93.

The heap is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82], and inserting the keys one at a time gives the same first three. Option C is impossible because 11, the smallest key, cannot have children in a max-heap; A and B do not start with the maximum, 131.

Answer: D

GATE CS 2024 Set 1 | Question 43

MCQ · 2 marks · −0.66

Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of \(k\) is

53 52 27 1

Explanation

Answer: (A)

In a min-heap every parent is smaller than its children, so the maximum element cannot have a child: it must be a leaf. With the 105 elements at indices 1 to 105, the nodes with children are indices 1 to \(\lfloor 105/2 \rfloor = 52\), and the leaves are indices 53 to 105, which is \(105 - 52 = 53\) positions.

Every leaf is possible: put the maximum at any chosen leaf and fill the other positions with the remaining elements in increasing order of index; each parent is still smaller than its children. So \(k\) has 53 possible values (indices 52 to 104 with 0-based indexing, still 53).

Answer: A