GATE CS question library

The above synchronous sequential circuit built using JK flip-flops is initialized with $Q_2Q_1Q_0 = 000$. The state sequence for this circuit for the next $3$ clock cycles is

The memory access time is $1$ nanosecond for a read operation with a hit in cache, $5$ nanoseconds for a read operation with a miss in cache, $2$ nanoseconds for a write operation with a hit in cache and $10$ nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves $100$ instruction fetch operations, …

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies $1$ ns, $2.2$ ns, $2$ ns, $1$ ns, and $0.75$ ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the …

Consider the C function given below. Assume that the array $listA$ contains $n (>0)$ elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return(k); else return -1; } Which …

Consider the pseudocode given below. The function $DoSomething()$ takes as argument a pointer to the root of an arbitrary tree represented by the $leftMostChild-rightSibling$ representation. Each node of the tree is of type $treeNode$. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr …

Consider a hash table with $100$ slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first $3$ slots are unfilled after the first $3$ insertions?

Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of …

Consider the decision problem $2CNFSAT$ defined as follows: $$\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}$$ For example, $\phi = (x1 \vee x2) \wedge (x1 \vee \bar{x3}) \wedge (x2 \vee x4)$ is a Boolean formula and it is in $2CNFSAT$. The decision problem $2CNFSAT$ is

Suppose you want to move from $0$ to $100$ on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers $i,\:j \:\text{with}\: i <j$. Given a shortcut $(i,j)$, if you are at position $i$ on the number line, you may directly move to $j$. Suppose $T(k)$ …

Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ $L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}$ Here, $w^r$ is the reverse of the string $w$. Which of these languages are deterministic Context-free languages?

Which one of the following problems is undecidable?

Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

Consider a paging hardware with a $TLB$. Assume that the entire page table and all the pages are in the physical memory. It takes $10$ milliseconds to search the $TLB$ and $80$ milliseconds to access the physical memory. If the $TLB$ hit ratio is $0.6$, the effective memory access time (in milliseconds) is _________.

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): …

A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.

Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation. employee (empId, empName, empAge) dependent (depId, eId, depName, depAge) Consider the following relational algebra query: …

Consider the transactions $T1, T2, \:\text{and} \:T3$ and the schedules $S1 \:\text{and} \:S2$ given below. $T1: r1(X); r1(Z); w1(X); w1(Z)$ $T2: r2(Y); r2(Z); w2(Z)$ $T3: r3(Y); r3(X); w3(Y)$ $S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)$ $S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)$ …

An $IP$ router with a $\text{Maximum Transmission Unit (MTU)}$ of $1500$ bytes has received an $IP$ packet of size $4404\text{ bytes}$ with an $IP$ header of length $20\text{ bytes}$. The values of the relevant fields in the header of the third $IP$ fragment generated by the router for this packet are:

Every host in an $\textsf{IPv4}$ network has a $1\text{-second}$ resolution real-time clock with battery backup. Each host needs to generate up to $1000$ unique identifiers per second. Assume that each host has a globally unique $\textsf{IPv4}$ address. Design a $50\text{-bit}$ globally unique ID for this purpose. After what period (in seconds) …

An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address $131.23.151.76$. The router's routing table has the following entries: …