List of top Computer Science and IT Engineering Questions

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.

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).

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet $\{0, 1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state.

Which one of the following regular expressions correctly describes the language accepted by A?

Which one of the options best describes the transformation of the 2-dimensional figure P to Q, and then to R, as shown?

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$?

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.

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:

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 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 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$.

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?

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 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?

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?

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?

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

Consider the IEEE-754 single precision floating point numbers $P=0xC1800000$ and $Q=0x3F5C2EF4$. Which one of the following corresponds to the product $P \times Q$, represented in IEEE-754 single precision format?

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 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 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 particular number is written as $132$ in radix-$4$ representation. The same number in radix-$5$ representation is ________

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

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$.