List of top Questions asked in GATE CS- 2026

int bar(int n){
     if (n == 1) return 0;
     else return 1 + bar(n/2);
}
int foo(int n){
     if (n == 1) return 1;
     else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______.

Note: Ignore syntax errors (if any) in the function.

Consider a system that has a cache memory unit and a memory management unit (MMU). The address input to the cache memory is a physical address. The MMU has a translation lookaside buffer (TLB). Assume that when a page is evicted from the main memory, the corresponding blocks in the cache are marked as invalid.
For a given memory reference, which of the following sequences of events can NEVER happen?

Consider a hash table \( P[0,1,\ldots,10] \) that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is \( h(x) = (x+7) \bmod 11 \).

Consider the following sequence of insertions performed on \( P \):

\[ 1, 13, 22, 15, 11, 24 \]

Which of the following positions in the hash table is/are empty after these insertions are performed?

Let \(P\) be the set of all integers from 1 to 15. Consider any order of insertion of the elements of \(P\) into a binary search tree that creates a complete binary tree.

Which one of the following elements can NEVER be the third element that is inserted?

Consider the 8-bit signed integers \( X, Y \) and \( Z \) represented using the sign-magnitude form. The binary representations of \( X \) and \( Y \) are as follows:

\[ X: 10110100 \qquad Y: 01001100 \]

Which of the following operations to compute \( Z \) result(s) in an arithmetic overflow?

Consider the following program in C:

#include <stdio.h>

void func(int i, int j) {
  if (i < j) {
    int i = 0;
    while (i < 10) {
      j += 2;
      i++;
    }
  }
  printf("%d", i);
}

int main() {
  int i = 9, j = 10;
  func(i, j);
  return 0;
}

The output of the program is __________. (answer in integer)

Note: Assume that the program compiles and runs successfully.

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
  int elt;
  struct node *next;
};

int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

Consider a processor P whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destination operand.
Which one of the following sequences of instructions corresponds to the high-level language statement \(Z = X + Y\)?
Note: X, Y, and Z are memory operands. R0, R1, and R2 are registers.

Let \( n \) be an odd number greater than 100. Consider a binary minheap with \( n \) elements stored in an array \( P \) whose index starts from 1.

Which of the following indices of \( P \) do/does NOT correspond to any leaf node of the minheap?

Let \(X\) be a random variable which takes values in the set \(\{1, 2, 3, 4, 5, 6, 7, 8\}\).
Further, \(\Pr(X=1) = \Pr(X=2) = \Pr(X=5) = \Pr(X=7) = \frac{1}{6}\) and \(\Pr(X=3) = \Pr(X=4) = \Pr(X=6) = \Pr(X=8) = \frac{1}{12}\).
The expected value of \(X\), denoted by \(E[X]\), is equal to ___________. (rounded off to two decimal places)

The size of the physical address space of a processor is \(2^{32}\) bytes. The capacity of a cache memory unit is \(2^{23}\) bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a \(K\)-way set-associative cache, where \(K = 2^{L}\) and \(L \in \{1,2,3\}\). Let the length of the TAG field be \(M\) bits for the direct mapped cache, and \(N\) bits for the set-associative cache.

Which one of the following options is true?

The figure shows two 4-tile patterns.

Either one or both of the patterns can be used any number of times and in any orientation to construct a new pattern. Which one of the options below cannot be constructed by using only these two 4-tile patterns assuming there are no overlaps among them?

An undirected, unweighted, simple graph \(G(V,E)\) is said to be 2-colorable if there exists a function \(c: V \to \{0,1\}\) such that for every \((u,v) \in E\), \(c(u) \neq c(v)\).
Which of the following statements about 2-colorable graphs is/are true?

Let \(G(V,E)\) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let \(s \in V\) be a vertex in \(G\). For every \(u \in V\) and for every \(k \geq 0\), let \(d_k(u)\) denote the weight of a shortest path (in terms of weight) from \(s\) to \(u\) of length at most \(k\). If there is no path from \(s\) to \(u\) of length at most \(k\), then \(d_k(u) = \infty\).

Consider the statements:

S1: For every \(k \geq 0\) and \(u \in V\), \(d_{k+1}(u) \leq d_k(u)\).

S2: For every \((u,v) \in E\), if \((u,v)\) is part of a shortest path (in terms of weight) from \(s\) to \(v\), then for every \(k \geq 0\), \(d_k(u) \leq d_k(v)\).

Which one of the following options is correct?

An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice in succession and the number on the top face is recorded each time. The probability that the number appearing in the second roll is an integer multiple of the number appearing in the first roll is ______.

Let \(G(V, E)\) be a simple, undirected graph. A vertex cover of \(G\) is a subset \(V' \subseteq V\) such that for every \((u, v) \in E\), \(u \in V'\) or \(v \in V'\). Let the size of the smallest vertex cover in \(G\) be \(k\). Let \(S\) be any vertex cover of size \(k\).
For a vertex \(v \in V\), which of the following constraints will always ensure that \(v \in S\)?