List of top Computer Science and IT Engineering Questions asked in GATE CS

Consider the C function foo and the binary tree shown. When foo is called with a pointer to the root node of the given binary tree, what will it print?

typedef struct node {
    int val;
    struct node *left, *right;
} node;

int foo(node *p) {
    int retval;
    if (p == NULL)
        return 0;
    else {
        retval = p→val + foo(p→left) + foo(p→right);
        printf("%d ", retval);
        return retval;
    }
}

Binary tree structure:

Let $f:A\to B$ be an onto (surjective) function, where $A$ and $B$ are nonempty sets. Define an equivalence relation $\sim$ on $A$ by $a_1\sim a_2$ iff $f(a_1)=f(a_2)$. Let $\mathcal{E=\{[x]:x\in A\}$ be the set of all equivalence classes under $\sim$. Define $F:\mathcal{E}\to B$ by $F([x])=f(x)$ for all classes $[x]\in\mathcal{E}$. Which of the following statements is/are TRUE?}

A new reliable byte-stream protocol (myTCP) runs over a 100 Mbps network with RTT = 150 ms and maximum segment lifetime (MSL) = 2 minutes. Which of the following are valid sequence number field lengths?

Let $X$ be a set and $2^{X}$ denote the power set of $X$. Define a binary operation $\,\Delta\,$ on $2^{X}$ by $A \Delta B = (A-B)\cup(B-A)$ (symmetric difference). Let $H=(2^{X},\Delta)$. Which of the following statements about $H$ is/are correct?

Suppose in a web browser you click on www.gate-2023.in. The browser cache is empty. The DNS address is not cached, so an iterative DNS lookup across 3 tiers is required. Let RTT denote the round trip time between your host and either a DNS server or the web server. RTT between local host and web server is also equal to RTT. The HTML page is very small and references 10 small objects from the same server. Neglect transmission and rendering time. Which of the following statements is/are CORRECT about the minimum elapsed time between clicking the URL and full rendering?

Consider a random experiment where two fair coins are tossed. Let $A$ be the event that denotes HEAD on both throws, $B$ the event that denotes HEAD on the first throw, and $C$ the event that denotes HEAD on the second throw. Which of the following statements is/are TRUE?

Consider functions Function_1 and Function_2 as follows. Let $f_1(n)$ and $f_2(n)$ be the number of times the statement $x = x + 1$ executes in Function_1 and Function_2, respectively. Which statements are TRUE?

Function_1                          Function_2
while n>1 do                      for i = 1 to 100 * n do
  for i = 1 to n do                   x = x + 1;
    x = x + 1;                      end for
  end for
  n = floor(n/2);
end while

Let $G$ be a simple, finite, undirected graph with vertex set $\{v_1, \ldots, v_n\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2,\ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i = 1, \ldots, n$, \[ \text{color}(v_i) \leftarrow \min\{j \in \mathbb{N} : \ \text{no neighbour of } v_i \text{ is colored } j\}. \] Which of the following statements is/are TRUE?

Let $U = \{1,2,3\}$. Let $2^U$ denote the power set of $U$. Consider an undirected graph $G$ whose vertex set is $2^U$. For any $A,B \in 2^U$, $(A,B)$ is an edge in $G$ iff (i) $A \neq B$, and (ii) either $A \subset B$ or $B \subset A$. For any vertex $A$ in $G$, the set of all possible orderings in which the vertices of $G$ can be visited in a BFS starting from $A$ is denoted by $\mathcal{B}(A)$. If $\varnothing$ denotes the empty set, find $|\mathcal{B}(\varnothing)|$.

Consider the two-dimensional array D[128][128] in C, stored in row-major order. Each physical page frame holds 512 elements of D. There are 30 physical page frames. The following code executes:

for (int i = 0; i<128; i++)
    for (int j = 0; j<128; j++)
        D[j][i] *= 10;

The number of page faults generated during this execution is:

A computer uses 57-bit virtual addresses with multi-level tree-structured page tables (L levels). Page size = 4 KB and each page-table entry (PTE) = 8 bytes. Find $L$.

Consider a sequence $a$ of elements $a_0=1,\,a_1=5,\,a_2=7,\,a_3=8,\,a_4=9,\,a_5=2$. The following operations are performed on a stack $S$ and a queue $Q$, both initially empty. [I:] push the elements of $a$ from $a_0$ to $a_5$ (in that order) into $S$.
[II:] enqueue the elements of $a$ from $a_0$ to $a_5$ (in that order) into $Q$.
[III:] pop an element from $S$.
[IV:] dequeue an element from $Q$.
[V:] pop an element from $S$.
[VI:] dequeue an element from $Q$.
[VII:] dequeue an element from $Q$ and push the same element into $S$.
[VIII:] Repeat operation VII three times.
[IX:] pop an element from $S$.
[X:] pop an element from $S$.

Consider the syntax-directed translation with non-terminals N, I, F, B and the rules:

\[ \begin{aligned} N &\to I\ \#\ F \qquad && N.val = I.val + F.val \\ I &\to I_1\ B \qquad && I.val = 2 \times I_1.val + B.val \\ I &\to B \qquad && I.val = B.val \\ F &\to B\ F_1 \qquad && F.val = \tfrac12 \big(B.val + F_1.val\big) \\ F &\to B \qquad && F.val = \tfrac12 B.val \\ B &\to 0 \qquad && B.val = 0 \\ B &\to 1 \qquad && B.val = 1 \end{aligned} \] Find the value computed for the input string 10#011 (rounded to three decimals).

Consider the table Student with attributes (rollNum, name, gender, marks). The primary key is rollNum. The SQL query is:

SELECT *
FROM Student
WHERE gender = 'F' AND marks > 65;

The number of rows returned by this query is:

A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of $b$ blocks needs $\lceil \log_2 b \rceil$ block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.

Consider the language $L$ over the alphabet $\{0,1\}$: \[ L = \{\, w \in \{0,1\}^* \;\mid\; \text{$w$ does not contain three or more consecutive $1$'s}\,\}. \] The minimum number of states in a Deterministic Finite-State Automaton (DFA) for $L$ is ________.

An 8-way set associative cache of size 64 KB (1 KB = 1024 bytes) is used in a system with a 32-bit address. The address is sub-divided into TAG, INDEX, and BLOCK OFFSET. Find the number of bits in the TAG.

The forwarding table of a router is shown below. A packet addressed to a destination address 200.150.68.118 arrives at the router. It will be forwarded to the interface with ID

Let $U = \{1,2,\ldots,n\}$ with $n > 1000$. Let $k < n$ be a positive integer. Let $A,B \subseteq U$ with $|A| = |B| = k$ and $A \cap B = \varnothing$. A permutation of $U$ separates $A$ from $B$ if either all members of $A$ appear before any member of $B$, or all members of $B$ appear before any member of $A$.

How many permutations of $U$ separate $A$ from $B$?

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;
}