GATE CS question library

Consider a computer system with $40$-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires $48$ bits, then the size of the per-process page table is __________ megabytes.

Consider a carry look ahead adder for adding two $n$-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is

Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? $P$: Minimum spanning tree of $G$ does not change. $Q$: Shortest path between any pair of vertices does not change.

Consider the following code segment. x = u - t; y = x * v; x = y + w; y = t - z; y = x * y; The minimum number of total variables required to convert the above code segment to static single assignment form is __________.

Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $Top(S)$ returns the element at the top of $S$ without removing it from $S$. Consider the algorithm given below. while Q is not Empty do if S is Empty OR Top(S) ≤ Head …

We want to design a synchronous counter that counts the sequence $0-1-0-2-0-3$ and then repeats. The minimum number of $\text{J-K}$ flip-flops required to implement this counter is _____________.

Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ($n$ refers to the number of items in the queue) ?

Let $p, q, r, s$ represents the following propositions. $p:x\in\left\{8, 9, 10, 11, 12\right\}$ $q:$ $x$ is a composite number. $r:$ $x$ is a perfect square. $s:$ $x$ is a prime number. The integer $x\geq2$ which satisfies $\neg\left(\left(p\Rightarrow q\right) \wedge \left(\neg r \vee \neg s\right)\right)$ is ____________.

A probability density function on the interval $[a, 1]$ is given by $1/x^{2}$ and outside this interval the value of the function is zero. The value of $a$ is _________.

The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are:

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

Which of the following decision problems are undecidable? Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$ Given a CFG $G = (N,\Sigma,P,S)$ and a string $x \in \Sigma^{*}$, does $x \in L(G)$} ? Given CFGs $G_1$ and $G_2$, is $L (G_1) = L(G_2)$? Given a TM $M$, is $L(M)=\Phi$ ?

The $16\text{-bit}\;2's$ complement representation of an integer is $1111 \quad 1111 \quad 1111 \quad 0101;$ its decimal representation is ____________

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $0$'s and two consecutive $1$'s?

Which one of the following is NOT a part of the ACID properties of database transactions?

Consider the following C program. # include <stdio.h> void mystery (int *ptra, int *ptrb) { int *temp; temp = ptrb; ptrb =ptra; ptra = temp; } int main () { int a = 2016, b=0, c= 4, d = 42; mystery (&a, &b); if (a < c) mystery (&c, &a); mystery (&a, &d); printf("%d\n", a); } The output of the program is _________.

Which of the following languages is generated by the given grammar? $$S \rightarrow aS \mid bS \mid \varepsilon$$

Which one of the following protocols is NOT used to resolve one form of address to another one?

Consider the following "C" program. void f(int, short); void main() { int i = 100; short s = 12; short *p = &s; ____________; // call to f() } Which one of the following expressions , when placed in the blank above, will NOT result in a type checking error?