List of top Questions asked in GATE CS

Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?

Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.

Let \[ A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{bmatrix} \] Let det(A) and det(B) denote the determinants of the matrices A and B, respectively.
Which one of the options given below is TRUE?

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: \[ \text{letter} \;\;\rightarrow\;\; [A\!-\!Za\!-\!z] \] \[ \text{digit} \;\;\rightarrow\;\; [0\!-\!9] \] \[ \text{id} \;\;\rightarrow\;\; \text{letter (letter | digit)}^* \] Which one of the following Non-deterministic Finite-state Automata with $\epsilon$-transitions accepts the set of valid identifiers? (A double-circle denotes a final state).

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k>m$. Which one of the following is the best hashing strategy to counteract the adversary?

The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure. Match the functional equivalence of this circuit to one of the following options.

Which one or more of the following need to be saved on a context switch from one thread (T1) of a process to another thread (T2) of the same process?

Which of the following statements is/are CORRECT?

Geetha has a conjecture about integers, of the form \[ \forall x \big(P(x) \Rightarrow \exists y \, Q(x,y)\big) \] where $P$ is a statement about integers and $Q$ is a statement about pairs of integers. Which of the following option(s) would imply Geetha's conjecture?

Which one or more of the following CPU scheduling algorithms can potentially cause starvation?

Let \[ f(x) = x^3 + 15x^2 - 33x - 36 \] be a real-valued function. Which of the following statements is/are TRUE?

Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^2$. Which of the following statements is/are TRUE?

Let $A$ be the adjacency matrix of the given graph with vertices $\{1,2,3,4,5\}$.

Let $\lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5$ be the eigenvalues of $A$ (not necessarily distinct). Find: \[ \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_5 \;=\; \_\_\_\_\_\_ . \]

The value of the definite integral $\displaystyle \int_{-3}^{3}\int_{-2}^{2}\int_{-1}^{1}\big(4x^{2}y - z^{3}\big)\,dz\,dy\,dx$ is ________. (Rounded off to the nearest integer)

A particular number is written as $132$ in radix-$4$ representation. The same number in radix-$5$ representation is ________

Consider a 3-stage pipelined processor having a delay of 10 ns, 20 ns, and 14 ns for the first, second, and third stages, respectively. Assume that there is no other delay and the processor does not suffer from any pipeline hazards. Also assume that one instruction is fetched every cycle.
The total execution time for executing 100 instructions on this processor is ________ ns.

A keyboard connected to a computer is used at a rate of 1 keystroke per second. The computer polls the keyboard every 10 ms, each poll takes 100 $\mu s$. If a key is detected, an additional 200 $\mu s$ is used for processing. Let $T_1$ be the fraction of a second spent in polling and processing a keystroke. In an alternative implementation with interrupts, each keystroke requires 1 ms to service and process. Let $T_2$ be the fraction of a second in the interrupt method. Find the ratio $T_1/T_2$.

The integer value printed by the ANSI-C program given below is ________.


int funcp(){
    static int x = 1;
    x++;
    return x;
}

int main(){
    int x,y;
    x = funcp();
    y = funcp() + x;
    printf("%d\n", (x+y));
    return 0;
}

Consider the following program:

int main() {
    f1();
    f2(2);
    f3();
    return(0);
}

int f1() {
    f1();
    return(1);
}

int f2(int X) {
    f3();
    if (X==1)
        return f1();
    else
        return (X * f2(X-1));
}

int f3() {
    return(5);
}

Which one of the following options represents the activation tree corresponding to the main function?

Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?

Consider the two functions incr and decr below. Five threads each call incr once and three threads each call decr once on the same shared variable $X$ (initially $10$). There are two semaphore implementations:

I-1: $s$ is a binary semaphore initialized to $1$.
I-2: $s$ is a counting semaphore initialized to $2$.

Let $V_1, V_2$ be the values of $X$ at the end of all threads for I-1 and I-2, respectively. Which choice gives the minimum possible values of $V_1, V_2$?

incr(){              
  wait(s);           
  X = X + 1;         
  signal(s);         
}

decr(){
  wait(s);
  X = X - 1;
  signal(s);
}

Consider the context-free grammar $G$ below: \[ S \;\to\; aSb \;|\; X \] \[ X \;\to\; aX \;|\; Xb \;|\; a \;|\; b \] where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non-terminal is $S$. Which one of the following statements is CORRECT?

Consider the pushdown automaton (PDA) $P$ over input alphabet $\{a,b\}$ and stack alphabet $\{\perp, A\}$ with start state $s$ and acceptance by empty stack.
The transition sketch shows:
- In $s$ on each $a$ it pushes one $A$ (i.e., $a/\perp \to A\perp$ and $a/A \to AA$).
- On the first $b$ it goes to $p$ with $b/A \to \epsilon$ and stays in $p$ popping one $A$ per $b$ ($b/A \to \epsilon$).
- From $p$ it may go to $q$ by $\epsilon/A \to \epsilon$, and in $q$ it can keep popping $A$’s and finally pop $\perp$ by $\epsilon/\perp \to \epsilon$.
Question: Which option describes $L(P)$? IMAGE8

Consider the given C-code and its corresponding assembly code, with a few operands U1–U4 being unknown. Some useful information as well as the semantics of each unique assembly instruction is annotated as inline comments in the code. The memory is byte-addressable.

A 4 KB byte-addressable memory is built using four 1 KB memory blocks. IA4 and IA3 feed a decoder that drives the active-high CS of the four blocks; the remaining ten address lines (all except IA4, IA3) go to the Addr inputs of each block. For each block, let $X_1,X_2,X_3,X_4$ be the input memory address (IA11–IA0), in decimal, of its starting location (Addr $=0$). Which option is correct?