GATE Computer Science Questions

Consider the following B+ tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the B+ tree. Which of the following options(s) is/are CORRECT?

Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown.

OSI Layers
(a) Network layer
(b) Transport layer
(c) Datalink layer

Functionalities
(I) Packet routing
(II) Framing and error handling
(III) Host to host communication

#include < stdio.h>  
void foo(int *p, int x){  
    *p=x;  
}  
int main(){  
    int *z;  
    int a = 20, b = 25;  
    z = &a;  
    foo(z,b);  
    printf("%d",a);  
    return 0;  
}  

The output of the given C program is ________. (Answer in integer)

Consider the following statements:

(i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address.
(ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S.

Which ONE of the following is CORRECT?

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is ______. (Answer in integer)

int main()  
{  
   int x=0, i=0;  
   scanf("%d",&x);  
   for(i=0; i<20; i++)  
   {  
       x = x+20;  
       printf("%d\n",x);  
   }  
   return 0;  
}   

Suppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/second) and the propagation delay between the two nodes is 100 milliseconds. Assume that the processing times at the source and destination are negligible. Also, assume that the size of the acknowledgement packet is negligible. Which ONE of the following most accurately gives the channel utilization for the above scenario in percentage?

A computer system supports a logical address space of $2^{32}$ bytes. It uses two-level hierarchical paging with a page size of $4096$ bytes. A logical address is divided into a $b$-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size.

The value of b is __________ . (Answer in integer)

Consider the database transactions $T_1$ and $T_2$, and data items $X$ and $Y$. Which of the schedule(s) is/are conflict serializable?

Transaction $T_1$

Transaction $T_2$

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the “hit rate” for L1 cache is 90% while the processor is accessing the data from L1 cache. Whereas, for the second level (L2) cache, the “hit rate” is 80% and the “miss penalty” for transferring data from L2 cache to L1 cache is 10 ns. The “miss penalty” for the data to be transferred from main memory to L2 cache is 100 ns.

Then the average memory access time in this system in nanoseconds is __________ . (rounded off to one decimal place)

A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store the immediate operand for the given instruction?

ADD R1, #25 // R1 = R1 + 25

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

Consider the following context-free grammar $G$, where $S$, $A$, and $B$ are the variables (non-terminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as:

$S\to aaB\mid Abb$

$A\to a\mid aA$

$B\to b\mid bB$

Which ONE of the languages $L(G)$ is accepted by $G$?

Consider the following recurrence relation:

$T(n)=2T(n-1)+n{2}^n$ for $n>0$, $T(0)=1$.

Which ONE of the following options is CORRECT?

The pseudocode of a function fun() is given below:

fun(int $A[0,\ldots,n-1]$) {  
    for i = 0 to n-2  
        for j = 0 to n-i-2  
            if ($A[j] > A[j+1]$)  
                then swap A[j] and A[j+1]   
}  

Let $A[0,\dots ,29]$ be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with $A[0,\dots ,29]$ as argument, is ________. (Answer in integer)

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.

Suppose a Min-Heap $T$ stores $32$ keys. The height of $T$ is ___________. (Answer in integer)

Which ONE of the following statements is FALSE regarding the symbol table?

A schedule of three database transactions $T_1$, $T_2$, and $T_3$ is shown. $R_i(A)$ and $W_i(A)$ denote read and write of data item A by transaction $T_i$, $i=1,2,3$. The transaction $T_1$ aborts at the end. Which other transaction(s) will be required to be rolled back?

$R_1(X)W_1(Y)R_2(X)R_2(Y)R_3(Y)ABORT(T_1)$

Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2, and P3, in order. Which of the following option(s) is/are TRUE with respect to TCP header flags that are set in the packets?

Let $X$ be a 3-variable Boolean function that produces output as 1' when at least two of the input variables are 1'. Which of the following statement(s) is/are CORRECT, where $a,b,c,d,e$ are Boolean variables?