GATE CS Programming and Data Structures Previous Year Questions

GATE CS 2024 Set 1 | Question 48

MSQ · 2 marks

Consider the following C function definition.

int f(int x, int y) {
  for (int i=0; i<y; i++) {
    x=x+x+y;
  }
  return x;
}

Which of the following statements is/are TRUE about the above function?

If the inputs are x=20, y=10, then the return value is greater than \(2^{20}\) If the inputs are x=20, y=20, then the return value is greater than \(2^{20}\) If the inputs are x=20, y=10, then the return value is less than \(2^{10}\) If the inputs are x=10, y=20, then the return value is greater than \(2^{20}\)

Explanation

Answer: (B), (D)

Each iteration sets \(x \leftarrow 2x + y\), and the loop runs \(y\) times. Adding \(y\) to both sides shows that \(x + y\) doubles on every iteration, so the function returns \(2^{y}(x + y) - y\).

x=20, y=10: \(2^{10} \cdot 30 - 10 = 30710\). That is below \(2^{20} = 1048576\) but above \(2^{10} = 1024\), so A and C are false.
x=20, y=20: \(2^{20} \cdot 40 - 20 = 41943020 \gt 2^{20}\), so B is true.
x=10, y=20: \(2^{20} \cdot 30 - 20 = 31457260 \gt 2^{20}\), so D is true.

Both large results are below \(2^{31} - 1\), so int does not overflow.

Answer: B, D

GATE CS 2024 Set 2 | Question 13

MCQ · 1 mark · −0.33

Consider the following C program. Assume parameters to a function are evaluated from right to left.

#include <stdio.h>

int g(int p) { printf("%d", p); return p; }
int h(int q) { printf("%d", q); return q; }

void f(int x, int y) {
  g(x);
  h(y);
}

int main() {
  f(g(10),h(20));
}

Which one of the following options is the CORRECT output of the above C program?

20101020 10202010 20102010 10201020

Explanation

Answer: (A)

Follow the calls in order.

In main, the arguments of f are evaluated right to left: h(20) runs first and prints 20, then g(10) prints 10.
f(10, 20) then runs its body in order: g(x) prints 10 and h(y) prints 20.

Nothing separates the numbers, so the output is 20101020. Left-to-right evaluation would print 10, 20, 10, 20 instead, which is option D. Standard C leaves the order of argument evaluation unspecified, which is why the question fixes it.

Answer: A

GATE CS 2024 Set 2 | Question 33

MSQ · 1 mark

Consider the following C function definition.

int fX(char *a){
    char *b = a;
    while(*b)
        b++;
    return b - a;}

Which of the following statements is/are TRUE?

The function call fX("abcd") will always return a value Assuming a character array c is declared as char c[] = "abcd" in main(), the function call fX(c) will always return a value The code of the function will not compile Assuming a character pointer c is declared as char *c = "abcd" in main(), the function call fX(c) will always return a value

Explanation

Answer: (A), (B), (D)

fX moves the pointer b forward until it reaches the terminating '\0' and returns b - a, the number of characters before it: the length of the string. The pointer difference is converted to int on return, so the function is valid C and (C) is false.

(A) A string literal is always stored with a terminating null character, so the call returns 4.
(B) char c[] = "abcd" creates a 5-element array whose last element is '\0', so the call returns 4.
(D) c points to the literal itself, which also ends in '\0', so the call returns 4.

The loop stops in every case, so all three calls return a value.

Answer: A, B, D

GATE CS 2024 Set 2 | Question 36

MCQ · 2 marks · −0.66

What is the output of the following C program?

#include <stdio.h>
int main() {
    double a[2]={20.0, 25.0}, *p, *q;
    p = a;
    q = p + 1;
    printf("%d,%d", (int)(q - p), (int)(*q - *p));
    return 0;}

4,8 1,5 8,5 1,8

Explanation

Answer: (B)

p points to a[0], and q = p + 1 points to the next element, a[1].

Subtracting two pointers into the same array counts elements, not bytes, so q - p is 1, even though a double usually takes 8 bytes.
*q - *p subtracts the stored values: \(25.0 - 20.0 = 5.0\), which the cast turns into the int 5.

So the program prints 1,5. Option (C) reports the pointer gap in bytes instead of elements, and the 4 and 8 in (A) and (D) match neither expression.

Answer: B

GATE CS 2024 Set 2 | Question 39

MCQ · 2 marks · −0.66

You are given a set \(V\) of distinct integers. A binary search tree \(T\) is created by inserting all elements of \(V\) one by one, starting with an empty tree. The tree \(T\) follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into \(T\), and you do not have access to \(T\).

Which one of the following statements is TRUE?

Inorder traversal of \(T\) can be determined from \(V\) Root node of \(T\) can be determined from \(V\) Preorder traversal of \(T\) can be determined from \(V\) Postorder traversal of \(T\) can be determined from \(V\)

Explanation

Answer: (A)

An inorder traversal visits the left subtree, then the node, then the right subtree. In a binary search tree with smaller values on the left, this always lists the keys in increasing order, whatever the shape of the tree. So sorting \(V\) gives the inorder traversal of \(T\).

The other three depend on the insertion order. The root is simply the first value inserted: inserting 1, 2, 3 gives root 1 with a chain to the right, while 2, 1, 3 gives root 2 with two children. These two trees also differ in preorder (1, 2, 3 against 2, 1, 3) and postorder (3, 2, 1 against 1, 3, 2), so none of them can be found from \(V\) alone.

Answer: A

GATE CS 2024 Set 2 | Question 42

MCQ · 2 marks · −0.66

Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices.

The C code snippet given below has been written to compute the length of the longest subarray of X that contains at most two distinct integers. The code has two missing expressions labelled \((P)\) and \((Q)\).

int first=0, second=0, len1=0, len2=0, maxlen=0;
for (int i=0; i < n; i++) {
  if (X[i] == first) {
    len2++; len1++;
  } else if (X[i] == second) {
    len2++;
    len1 = ___(P)___;
    second = first;
  } else {
    len2 = ___(Q)___;
    len1 = 1; second = first;
  }
  if (len2 > maxlen) {
    maxlen = len2;
  }
  first = X[i];
}

Which one of the following options gives the CORRECT missing expressions?

(Hint: At the end of the i-th iteration, the value of len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)

\((P)\) len1+1 \((Q)\) len2+1 \((P)\) 1 \((Q)\) len1+1 \((P)\) 1 \((Q)\) len2+1 \((P)\) len2+1 \((Q)\) len1+1

Explanation

Answer: (B)

During iteration i, first holds the previous element and second the other value in the current two-value window.

X[i] == second: the window still has only two values, so len2 grows by 1. But X[i] differs from the previous element, so the run of equal values ending at X[i] starts again: (P) is 1.
A new value: the window must drop second. The longest valid subarray ending at X[i] is the final run of first values, of length len1, plus X[i]: (Q) is len1+1.

For example, for 1, 2, 1, 3 the correct value at 3 is 2 (the subarray 1, 3), which len1+1 gives, while len2+1 would give 4.

Answer: B

GATE CS 2024 Set 2 | Question 48

MSQ · 2 marks

Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below.

Stack `S1`
400 (Top)
300
200
100

Stack `S2`

Only the following three operations are available:
PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.

Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack.

Which of the following output sequences can be generated by using the above operations?

100, 200, 400, 300 200, 300, 400, 100 400, 200, 100, 300 300, 200, 400, 100

Explanation

Answer: (B), (C), (D)

Only S1 can output, and S2 can park at most two elements taken from the top of S1.

(A) Impossible: to output 100 first, the three elements above it (400, 300 and 200) must all be parked, but S2 holds only two.
(B) Park 400 and 300, output 200, move 300 back and output it, move 400 back and output it, then output 100.
(C) Output 400, park 300, output 200 and 100, then move 300 back and output it.
(D) Park 400, output 300 and 200, move 400 back and output it, then output 100.

Answer: B, C, D