GATE CS question library

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of the vertex $v \in V$. …

Let $L_{1}$ and $L_{2}$ be two languages over a finite alphabet, such that $L_{1} \cap L_{2}$ and $L_{2}$ are regular languages. Which of the following statements is/are always true?

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 …

Consider the following two syntax-directed definitions $\text{SDD1}$ and $\text{SDD2}$ for type declarations. …

Consider the following context-free grammar $G$. $$\begin{array}{l} S \rightarrow a b a A B A b b a \\ A \rightarrow a a B B A b \mid b B a b a a \\ B \rightarrow a B b \mid a b \end{array}$$ In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols. Let $L(G)$ be the language …

An undirected, unweighted, simple graph $G(V, E)$ is said to be $2$-colorable if there exists a function $c: V \rightarrow\{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$ be an undirected graph, which is a path on $8$ vertices. The number of matchings in $G$ is $\_\_\_\_$. (answer in integer)

An ISP having an address block $202.16.0.0/15$ assigns a block of $6000$ IP addresses to a client, using the classless internet domain routing (CIDR) super-netting approach. Which of the following address blocks can be assigned by the ISP?

Let $X$ be a random variable which takes values in the set $\{1,2,3,4,5,6,7,8\}$. Further, $\operatorname{Pr}(X=1)=\operatorname{Pr}(X=2)=\operatorname{Pr}(X=5)=\operatorname{Pr}(X=7)=\frac{1}{6}$ and $\operatorname{Pr}(X=3)=\operatorname{Pr}(X=4)=\operatorname{Pr}(X=6)=\operatorname{Pr}(X=8)=\frac{1}{12}$. The expected value of $X$, denoted by …

Consider a hard disk with a rotational speed of $15000$ rpm. The time to move the read/write head from a track to its adjacent track is $1$ millisecond. Initially, the head is on track $0$. The number of sectors per track is $400$. The sector size is $1024$ bytes. It is necessary to transfer data from $10$ randomly located sectors in each of the …

The EX stage of a pipelined processor performs the memory read operations for LOAD instructions, and the operations for the arithmetic and logic instructions. Let $t_{E X}$ denote the time taken by the EX stage to perform the operation for an instruction. For each instruction type, the values of $t_{E X}$ and $M$ (the number of instructions of that …

Consider the recursive functions represented by the following code segment: 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 $\mathrm{f} \circ \circ(\mathrm{n})$ returns $5$ is $\_\_\_\_$. (answer in integer) Note: Ignore …

The following sequence corresponds to the preorder traversal of a binary search tree $T$ : $$50,25,13,40,30,47,75,60,70,80,77$$ The position of the element $60$ in the postorder traversal of $T$ is $\_\_\_\_$ . (answer in integer) Note: The position begins with $1$.

Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process. int main () { int i; for (i = 0; i < 3; i++) { if (fork() == 0) { continue; } break; } printf("Hello!"); return 0; } The total number of times that the printf statement gets …

Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of $6$ seconds. The second type, Controllers (C), requires a CPU burst of $8$ seconds. A new process of type A arrives at time $t=10$, $20, 30, 40$, and $50$ (in seconds). Similarly, a new process of type C arrives at time $t=$ …

Consider a relational database schema with a relation $R(A, B, C, D)$. If $\{A, B\}$ and $\{A, C\}$ are the only two candidate keys of the relation $R$, then the number of superkeys of relation $R$ is $\_\_\_\_$. (answer in integer)

Expedite, Hasten, Hurry, $\_\_\_\_$ Fill the blank by choosing a word with a meaning similar to that of the words given above.

A black square PQRS has been cut into two parts. One part of it is shown in Panel $\text{I}.$ Which one of the shapes in Panel $\text{II}$ is the other part?

A day can only be cloudy or sunny. The probability of a day being cloudy is $0.5$, independent of the condition on other days. What is the probability that in any given four days, there will be three cloudy days and one sunny day?

The values of Stock $\text{A}$ and Stock $\text{B}$ on a particular day are Rs. $50$ and Rs. $80$, respectively. An investor invests Rs. $100$ in Stock $\text{A}$ and Rs. $80$ in Stock $\text{B}$. He sells all the stocks the next day when the value of Stock $\text{A}$ is Rs. $55$ and Stock $\text{B}$ is Rs. $70$. The profit made by …