GATE CS question library

Consider a hash table of size seven, with starting index zero, and a hash function $(3x + 4)\mod 7$. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence $1, 3, 8, 10$ is inserted into the table using closed hashing? Note that − denotes an empty location in the table.

The inorder and preorder traversal of a binary tree are $\text{d b e a f c g}$ and $\text{a b d e c f g}$, respectively The postorder traversal of the binary tree is:

In an unweighted, undirected connected graph, the shortest path from a node $S$ to every other node is computed most efficiently, in terms of time complexity, by

Consider a pipelined processor with the following four stages: IF: Instruction Fetch ID: Instruction Decode and Operand Fetch EX: Execute WB: Write Back The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage depends on the instruction. The ADD and SUB instructions need $1$ clock cycle and …

The control signal functions of a $4$-$bit$ binary counter are given below (where $X$ is “don’t care”): …

In a look-ahead carry generator, the carry generate function $G_i$ and the carry propagate function $P_i$ for inputs $A_i$ and $B_i$ are given by: $$P_i = A_i \oplus B_i \text{ and }G_i = A_iB_i$$ The expressions for the sum bit $S_i$ and the carry bit $C_{i+1}$ of the look ahead carry adder are given by: …

Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of $n$ variables. What is the minimum size of the multiplexer needed?

Define the connective $*$ for the Boolean variables $X$ and $Y$ as: $$X * Y = XY + X'Y'.$$ Let $Z = X * Y$. Consider the following expressions $P$, $Q$ and $R$. $$P : X = Y * Z, \\ Q :Y = X * Z, \\ R : X *Y * Z = 1$$ Which of the following is TRUE?

Let $f(w, x, y, z) = \sum {\left(0,4,5,7,8,9,13,15\right)}$. Which of the following expressions are NOT equivalent to $f$? P: $x'y'z' + w'xy' + wy'z + xz$ Q: $w'y'z' + wx'y' + xz$ R: $w'y'z' + wx'y' + xyz+xy'z$ S: $x'y'z' + wx'y'+ w'y$

The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is:

Which of the following languages is regular?

A minimum state deterministic finite automaton accepting the language $L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has

Consider the set of (column) vectors defined by$$X = \left \{x \in R^3 \mid x_1 + x_2 + x_3 = 0, \text{ where } x^T = \left[x_1,x_2,x_3\right]^T\right \}$$.Which of the following is TRUE?

Consider the set $S =\{ a , b , c , d\}.$ Consider the following $4$ partitions $π_1,π_2,π_3,π_4$ on $S : π_1 =\{\overline{abcd}\},\quad π_2 =\{\overline{ab}, \overline{cd}\},$ $\quad π_3 = \{\overline{abc}, \overline{d}\},\quad π_4 =\{\bar{a}, \bar{b}, \bar{c}, \bar{d}\}$. Let $\prec$ be the partial order on the set of partitions …

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: