GATE CS question library

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 ______