GATE CS question library

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?

A block-set associative cache memory consists of $128$ blocks divided into four block sets. The main memory consists of $16, 384$ blocks and each block contains $256$ eight bit words. How many bits are required for addressing the main memory? How many bits are needed to represent the TAG, SET and WORD fields?

State whether the following statements are TRUE or FALSE with reason: The Link-load-and-go loading scheme required less storage space than the link-and-go loading scheme.

State whether the following statements are TRUE or FALSE with reason: The flags are affected when conditional CALL or JUMP instructions are executed.

State whether the following statements are TRUE or FALSE with reason: The data transfer between memory and I/O devices using programmed I/O is faster than interrupt-driven I/O.

State whether the following statements are TRUE or FALSE with reason: RAM is a combinational circuit and PLA is a sequential circuit.

A graph is planar if and only if,

Indicate which of the following well-formed formulae are valid:

The number of ways in which $5\; A's, 5\; B's$ and $5\; C's$ can be arranged in a row is:

Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:

It is undecidable whether:

Recursive languages are:

The complexity of comparison based sorting algorithms is:

The total external path length, $\text{EPL},$ of a binary tree with $n$ external nodes is, $\text{EPL}= \displaystyle \sum_{w} I_w$, where $I_{w}$ is the path length of external node $w$),

The number of rooted binary trees with $n$ nodes is,

Indicate which of the following statements are true: A relational database which is in $3$NF may still have undesirable data redundancy because there may exist:

Choose the correct alternatives (More than one may be correct). Two NAND gates having open collector outputs are tied together as shown in below figure. The logic function $Y,$ implemented by the circuit is,