GATE CS question library

Suppose we uniformly and randomly select a permutation from the $20 !$ permutations of $1, 2, 3\ldots ,20.$ What is the probability that $2$ appears at an earlier position than any other even number in the selected permutation?

Which of the following graphs has an Eulerian circuit?

Let $\text{ Graph}(x)$ be a predicate which denotes that $x$ is a graph. Let $\text{ Connected}(x)$ be a predicate which denotes that $x$ is connected. Which of the following first order logic sentences DOES NOT represent the statement: $\qquad\text{“Not every graph is connected"}$

How many different non-isomorphic Abelian groups of order $4$ are there?

Which one of the following uses UDP as the transport protocol?

In Ethernet when Manchester encoding is used, the bit rate is:

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?