GATE CS question library

In an $11$-bit computer instruction format, the size of address field is $4$-bits. The computer uses expanding OP code technique and has $5$ two-address instructions and $32$ one-address instructions. The number of zero-address instructions it can support is ________

Consider a $3$-bit error detection and $1$-bit error correction hamming code for $4$-bit data. The extra parity bits required would be _____ and the $3$-bit error detection is possible because the code has a minimum distance of _______.

Which of the following predicate calculus statements is/are valid?

Find the maximum clock frequency at which the counter in the figure below can be operated. Assume that the propagation delay through each flip flop and each AND gate is $10\;\text{ns}$. Also, assume that the setup time for the $JK$ inputs of the flip flops is negligible.

Which of the following is the strongest correct statement about a finite language over some finite alphabet $\Sigma?$

Let $r=1(1+0)^*, s=11^*0 \text{ and } t=1^*0$ be three regular expressions. Which one of the following is true?

Indicate all the false statements from the statements given below:

If $F_1$, $F_2$ and $F_3$ are propositional formulae such that $F_1 \land F_2 \rightarrow F_3$ and $F_1 \land F_2 \rightarrow \sim F_3$ are both tautologies, then which of the following is true:

Indicate all the true statements from the following:

Consider the following Pascal function: Function X(M:integer):integer; Var i:integer; Begin i := 0; while i*i < M do i:= i+1 X := i end The function call $X(N)$, if $N$ is positive, will return

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph $G$ with $n$ vertices and $m$ edges has the time complexity of:

The following sequence of operations is performed on a stack: $PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POP$ The sequence of values popped out is

A “link editor” is a program that:

The total size of address space in a virtual memory system is limited by:

Advantage of synchronous sequential circuits over asynchronous ones is:

Consider the following recursive definition of $fib$: fib(n) := if n = 0 then 1 else if n = 1 then 1 else fib(n-1) + fib(n-2) The number of times $fib$ is called (including the first call) for evaluation of $fib(7)$ is___________.

The weighted external path length of the binary tree in figure is ______

The minimum number of comparisons required to sort $5$ elements is ______

Consider the number given by the decimal expression: $$16^3*9 + 16^2*7 + 16*5+3$$ The number of $1’s$ in the unsigned binary representation of the number is ______

In a two-level virtual memory, the memory access time for main memory, $t_{M}=10^{-8}$ sec, and the memory access time for the secondary memory, $t_D=10^{-3}$ sec. What must be the hit ratio, $H$ such that the access efficiency is within $80$ percent of its maximum value?