GATE CS question library

Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?

Which one of the following is a top-down parser?

Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2. …

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height $h$ is:

Which of the following sorting algorithms has the lowest worse-case complexity?

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Consider a disk pack with $16$ surfaces, $128$ tracks per surface and $256$ sectors per track. $512$ bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:

Consider a $4$-way set associative cache consisting of $128$ lines with a line size of $64$ words. The CPU generates a $20-bit$ address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:

Consider the following Boolean function of four variables: $$f(w, x, y, z) = \Sigma(1, 3, 4, 6, 9, 11, 12, 14)$$ The function is

How many $3$-to-$8$ line decoders with an enable input are needed to construct a $6$-to-$64$ line decoder without using any other logic gates?

Which of the following is TRUE?

Which of the following problems is undecidable?

Let $G$ be the non-planar graph with the minimum possible number of edges. Then $G$ has

What is the maximum number of different Boolean functions involving $n$ Boolean variables?

Let $S$ be a set of $n$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are:

Consider the following two statements about the function $f(x)=\left\vert x\right\vert$: P. $f(x)$ is continuous for all real values of $x$. Q. $f(x)$ is differentiable for all real values of $x$ . Which of the following is TRUE?

Let A be a $4 \times 4$ matrix with eigen values -5,-2,1,4. Which of the following is an eigen value of the matrix$\begin{bmatrix} A & I \\ I & A \end{bmatrix}$, where $I$ is the $4 \times 4$ identity matrix?

The grammar $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \epsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$ generates the language $L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In this grammar what is the length of the derivation (number of steps starting from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$

Statement for Linked Answer Questions 76 & 77: A $3$-ary max heap is like a binary max heap, but instead of $2$ children, nodes have $3$ children. A $3$-ary heap can be represented by an array as follows: The root is stored in the first location, $a[0]$, nodes in the next level, from left to right, is stored from $a[1]$ to $a[3]$. The nodes …

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the …