GATE CS question library

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is $4$ bytes in size. Given a $100 \times 10^6$ bytes disk on which the file system is stored and data block size is $10^3$ bytes, the maximum size of a file that can be stored on this disk in units of $10^6$ bytes is _________.

Which one of the following is TRUE?

Which one of the following is NOT performed during compilation?

Consider the grammar defined by the following production rules, with two operators $∗$ and $+$ $S\:\to\:T∗P$ $T\:\to\:U\mid T∗U$ $P\:\to\:Q+P\mid Q$ $Q\:\to Id$ $U\:\to Id$ Which one of the following is TRUE?

Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$. Which one of the following is FALSE?

If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language $L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$ Which one of the following is CORRECT?

Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing

A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

Suppose $n$ and $p$ are unsigned int variables in a C program. We wish to set $p$ to $^nC_3$. If $n$ is large, which one of the following statements is most likely to set $p$ correctly?

Which one of the following correctly determines the solution of the recurrence relation with $T(1) = 1$? $$T(n)= 2T\left(\frac {n} {2}\right) + \log n$$

Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num>>= 1; } return (count); } The value returned by func($435$) is ________

A $4$-way set-associative cache memory unit with a capacity of $16$ KB is built using a block size of $8$ words. The word length is $32$ bits. The size of the physical address space is $4$ GB. The number of bits for the TAG field is ____

Let $k=2^n$. A circuit is built by giving the output of an $n$-bit binary counter as input to an $n\text{-to-}2^n$ bit decoder. This circuit is equivalent to a

Consider the equation $(123)_5=(x8)_y$ with $x$ and $y$ as unknown. The number of possible solutions is _____ .

The dual of a Boolean function $F(x_1,x_2,\dots,x_n,+, .,')$, written as $F^D$ is the same expression as that of $F$ with $+$ and $⋅$ swapped. $F$ is said to be self-dual if $F = F^D$. The number of self-dual functions with $n$ Boolean variables is

A non-zero polynomial $f(x)$ of degree 3 has roots at $x=1$, $x=2$ and $x=3$. Which one of the following must be TRUE?

If the matrix $A$ is such that $$A= \begin{bmatrix} 2\\ −4\\7\end{bmatrix}\begin{bmatrix}1& 9& 5\end{bmatrix}$$ then the determinant of $A$ is equal to ______.

The maximum number of edges in a bipartite graph on $12$ vertices is____

Each of the nine words in the sentence $\text{"The quick brown fox jumps over the lazy dog”}$ is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The $\text{expected}$ length of the word drawn is _____________. (The answer should be rounded to one decimal place.)

The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students doubled in $2009$, by what percent did the number of male students increase in $2009$?