GATE CS question library

​​​​​An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?

Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text{ for } n \geq 1, \\ 1 \quad \text{ for } n=1\end{array}\right.$ Which one of the following options is CORRECT?

Consider a binary min-heap containing $105$ distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of $k$ is

​The symbol $\rightarrow$ indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

​​​​Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$, rooted at $v$. Which of the following statements is/are TRUE for every such graph $G$ and tree $T$?

​​​​Consider the following read-write schedule $\text{S}$ over three transactions $T_{1}, T_{2}$, and $T_{3}$, where the subscripts in the schedule indicate transaction IDs: $S: r_{1}(z) ; w_{1}(z) ; r_{2}(x) ; r_{3}(y) ; w_{3}(y) ; r_{2}(y) ; w_{2}(x) ; w_{2}(y) ;$ Which of the following transaction schedules is/are conflict equivalent to …

Consider a Boolean expression given by $\text{F(X, Y, Z)}=\sum(3,5,6,7)$. Which of the following statements is/are CORRECT?

​​Consider the following $\mathrm{C}$ function definition. int f (int x, int y){ for (int i=0 ; i<y ; i++ ) { x= x + x + y; } return x; } Which of the following statements is/are TRUE about the above function?

​​Let $A$ be any $n \times m$ matrix, where $m>n$. Which of the following statements is/are TRUE about the system of linear equations $Ax=0$?

​Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. Which of the following statements is/are FALSE?

​​​The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE?

Consider the operators $\diamond$ and $\square$ defined by $a \diamond b=a+2 b, a \square b=a b$, for positive integers. Which of the following statements is/are TRUE?

​​​​Consider two set-associative cache memory architectures: $\text{WBC}$, which uses the write back policy, and $\text{WTC}$, which uses the write through policy. Both of them use the $\text{LRU}$ (Least Recently Used) block replacement policy. The cache memory is connected to the main memory. Which of the following statements is/are TRUE?

Consider a $512$ GB hard disk with $32$ storage surfaces. There are $4096$ sectors per track and each sector holds $1024$ bytes of data. The number of cylinders in the hard disk is _________.

Consider the following code snippet using the fork () and wait () system calls. Assume that the code compiles and runs correctly, and that the system calls run successfully without any errors. int x=3; while (x>0){ fork (); printf("hello"); wait (NULL) ; X-- ; } The total number of times the printf statement is executed is __________.

A given program has $25 \%$ load/store instructions. Suppose the ideal $\text{CPI}$ (cycles per instruction) without any memory stalls is $2$. The program exhibits $2 \%$ miss rate on instruction cache and $8 \%$ miss rate on data cache. The miss penalty is $100$ cycles. The speedup (rounded off to two decimal places) achieved with a perfect …

The baseline execution time of a program on a $2 \mathrm{GHz}$ single core machine is $100$ nanoseconds ( $n s)$. The code corresponding to $90 \%$ of the execution time can be fully parallelized. The overhead for using an additional core is $10 ~ns$ when running on a multicore system. Assume that all cores in the multicore system run their share …

Let $G=(V, \Sigma, S, P)$ be a context-free grammar in Chomsky Normal Form with $\Sigma=\{a, b, c\}$ and $V$ containing $10$ variable symbols including the start symbol $S$. The string $w=a^{30} b^{30} c^{30}$ is derivable from $S$. The number of steps (application of rules) in the derivation $S \rightarrow^* w$ is __________.

Consider the entries shown below in the forwarding table of an $\text{IP}$ router. Each entry consists of an $\text{IP}$ prefix and the corresponding next hop router for packets whose destination $\text{IP}$ address matches the prefix. The notation " /$\mathrm{N}$ " in a prefix indicates a subnet mask with the most significant $\mathrm{N}$ bits set …

The number of edges present in the forest generated by the $\text{DFS}$ traversal of an undirected graph $G$ with $100$ vertices is $40$. The number of connected components in $G$ is __________.