GATE CS question library

Six students $\text{P, Q, R, S, T and U}$, with distinct heights, compare their heights and make the following observations. $\text{Observation I}$: $\text{S}$ is taller than $\text{R}$. $\text{Observation II}$: $\text{Q}$ is the shortest of all. $\text{Observation III}$: $\text{U}$ is taller than only one student. $\text{Observation IV}$: …

Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$. $S_2$: If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning tree. Which one of the following options is correct?

​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$?

The format of the single-precision floating point representation of a real number as per the $\text{IEEE 754}$ standard is as follows: $$\begin{array}{|c|c|c|} \hline \text{sign} & \text{exponent} & \text{mantissa} \\ \hline \end{array}$$ Which one of the following choices is correct with respect to the smallest normalized positive number …

Consider the following $\text{ANSI C}$ program: int main () { Integer x; return 0; } Which one of the following phases in a seven-phase $C$ compiler will throw an error?

Consider the following statements $S1$ and $S2$ about the relational data model: $S1$: A relation scheme can have at most one foreign key. $S2$: A foreign key in a relation scheme $R$ cannot be used to refer to tuples of $R.$ Which one of the following choices is correct?

Which one of the following circuits implements the Boolean function given below? $f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6$, where $m_i$ is the $i^{\text{th}}$ minterm.

Consider the three-way handshake mechanism followed during $\text{TCP}$ connection establishment between hosts $P$ and $Q$. Let $X$ and $Y$ be two random $32$-bit starting sequence numbers chosen by $P$ and $Q$ respectively. Suppose $P$ sends a $\text{TCP}$ connection request message to $Q$ with a $\text{TCP}$ segment having …

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?

Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal $\text{DFA}$ with $k$ states. Which one of the following languages must necessarily be accepted by a minimal $\text{DFA}$ with $k$ states?

Consider the following $\text{ANSI C}$ program. #include <stdio.h> int main() { int arr[4][5]; int i, j; for (i=0; i<4; i++) ​​​​​​{ for (j=0; j<5; j++) { arr[i][j] = 10 * i + j; } } printf(“%d”, *(arr[1]+9)); return 0; } What is the output of the above program?

Consider the following sets, where $n \geq 2$: $S_1$: Set of all $n \times n$ matrices with entries from the set $\{ a, b, c\}$ $S_2$: Set of all functions from the set $\{0,1,2, \dots, n^2-1\}$ to the set $\{0, 1, 2\}$ Which of the following choice(s) is/are correct?

Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?

In the context of compilers, which of the following is/are $\text{NOT}$ an intermediate representation of the source program?

Which of the following statement(s) is/are correct in the context of $\text{CPU}$ scheduling?

Choose the correct choice(s) regarding the following proportional logic assertion $S$: $$S: (( P \wedge Q) \rightarrow R) \rightarrow (( P \wedge Q) \rightarrow (Q \rightarrow R))$$

Consider a complete binary tree with $7$ nodes. Let $A$ denote the set of first $3$ elements obtained by performing Breadth-First Search $\text{(BFS)}$ starting from the root. Let $B$ denote the set of first $3$ elements obtained by performing Depth-First Search $\text{(DFS)}$ starting from the root. The value of $\mid A-B \mid$ is …

Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________

If $x$ and $y$ are two decimal digits and $(0.1101)_2 = (0.8xy5)_{10}$, the decimal value of $x+y$ is ___________

Consider a set-associative cache of size $\text{2KB (1KB} =2^{10}$ bytes$\text{)}$ with cache block size of $64$ bytes. Assume that the cache is byte-addressable and a $32$ -bit address is used for accessing the cache. If the width of the tag field is $22$ bits, the associativity of the cache is _________