GATE CS question library

Consider a processor that has $16$ general purpose registers and it uses $2$-byte instruction format for all its instructions. Variable-sized opcodes are permitted. There are three different types of instructions; M-type, R-type, and C-type. Each M-type instruction has $2$ register operands and a $6$-bit immediate operand. Each Rtype instruction has …

An index in a DBMS is said to be dense if an index entry appears for every search-key value in the indexed file. Otherwise it is called a sparse index. Consider the following two statements. $\text{S1}$: A hash index must be a dense index $\text{S1}$: A $B^{+}$ tree index can be a sparse index Which one of the following options is correct?

Consider the following two finite automata $D_{1}$ and $D_{2}$. Which of the following statements is/are true?

Consider a binary search tree (BST) with $n$ leaf nodes $(n>0)$. Given any node $V$, the key present in the node is denoted as $\operatorname{Val}(V)$. All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node $V$, let $\operatorname{Suc}(V)$ denote the node that is its inorder successor. If a …

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^{i} b^{j} c^{k} d^{\ell} \mid i, j, k, \ell \geq 0\right\}$. Which of the following constraints ensure(s) that the language $L$ is context-free?

Consider a stack $S$ and a queue $Q$. Both of them are initially empty and have the capacity to store ten elements each. The elements $1,2,3,4$, and $5$ arrive one by one, in that order. When an element arrives, it is assigned either to $S$ (pushed on $S$ ) or to $Q$ (enqueued to $Q$ ). Once all the five elements are stored, the output is …

Consider three processes $\text{P1, P2}$, and $\text{P3}$ running identical code, as shown in the pseudocode below. $\text{A}$ and $\text{B}$ are two binary semaphores initialized to $1$ and $0$, respectively. $\text{X}$ is a shared variable initialized to $0$. Each line in the pseudocode is executed atomically. Pseudocode of P1, P2, and P3 …

Consider a system with a processor and a $4$ KB direct mapped cache with block size of $16$ bytes. The system has a $16$ MB physical memory. Four words $\mathrm{P}, \mathrm{Q}, \mathrm{R}$, and S are accessed by the processor in the same order $10$ times. That is, there are a total of $40$ memory references in the sequence …

To keep track of free blocks in a file system, one of the two approaches is generally used - using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is $16$ GB , block size is $2$ KB , and block numbers used are $32$-bit long. A single …

A system has a Translation Lookaside Buffer (TLB) that has a reach of $1$ MB. TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entries. The paging system uses pages of size $4$ KB. The virtual address space is $64$ GB and physical address space is $1$ GB. If each TLB entry stores a $4$-bit process id, …

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are $8$ holes in the memory of sizes $20 \mathrm{KB}, 4 \mathrm{~KB}$, $25 \mathrm{~KB}, 18 \mathrm{~KB}, 7 \mathrm{~KB}, 9 \mathrm{~KB}, 15 \mathrm{~KB}$, and $12$ KB. Assume that no two holes are adjacent. Two processes $\text{P1}$ of …

A non-pipelined instruction execution unit that operates at $1.6$ GHz clock takes an average of $5$ clock cycles to complete the execution of an instruction. To improve the performance, the system was pipelined with a goal of achieving an average throughput of one instruction per clock cycle. However, it could operate only at $1.2$ GHz due to pipeline …

Consider a system with $1$ MB physical memory and a word length of $1$ byte. The system uses a direct mapped cache, with block numbers starting from $0$. The word with physical address $\text{0xA2C28}$ is mapped to the cache block number $17610$. The maximum possible size of the cache (in KB ) for this configuration is $\_\_\_\_\_\_\_$. (answer …

Consider a new TCP connection between a sender and a receiver. The receiver advertised window is constant at $48$ KB, the maximum segment size (MSS) is $2$ KB, and the slow start threshold for TCP congestion control is $16$ KB. Assume that there are no timeouts or duplicate acknowledgements. The number of rounds of transmission required for the …

Consider the digital circuit shown below with two input lines $\text{A}$ and $\text{B}$, two select lines $\text{S0}$ and $\text{S1}$, and an output line $\text{Y}$. The blocks $\text{Q}$ and $\text{M}$ represent active high $2:4$ decoder and $4$-to-$1$ multiplexer, respectively. Out of $16$ possible input combinations, the number of …

Consider the following ANSI-C program. #include <stdio.h> int main(){ int *ptr, a, b, c; a=5; b=11; c=20; ptr=&a; *ptr=c; ptr=&c; a=*(&b); c=*ptr-a; printf("%d",c); return(0); } The output of this program is $\_\_\_\_$ . (answer in integer) Note: Assume that the program compiles and runs successfully.

Consider the following ANSI-C function. int func(int start, int end){ int length=end+1-start; if((length<1)||(start<0)||(end<0)){ return(0); } if(length%3==0){ return(func(start+1, end)); }else if(length%3==1){ return(1+func(start, end-1)); }else { return(func(start+2, end)); } } The maximum possible value that can be returned from this function is …

The determinant of a $4 \times 4$ matrix $A$ is $3$. The value of the determinant of $2 A$ is $\_\_\_\_$. (answer in integer)

Suppose an unbiased coin is tossed $6$ times. Each coin toss is independent of all previous coin tosses. Let $E_{1}$ be the event that among the second, fourth, and sixth coin tosses, there are at least two heads. Let $E_{2}$ be the event that among the first, second, third, and fifth coin tosses, there are equal number of heads and tails. The …

Consider a function $f:(0,1) \rightarrow\{0,1\}$ defined as follows. For a real number $r \in(0,1), f(r)=1$ if the second digit after the decimal point in $r$ is one of the four digits $2,3,6$ and $7$. Otherwise, $f(r)$ is equal to $0$. The number of points in $(0,1)$ at which $f$ is discontinuous is $\_\_\_\_\_\_$. (answer in integer)