GATE Computer Science MCQ Questions

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

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 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 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

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$

Let $G(V,E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u,v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u,v)$, where $u,v\in V$ such that $u\ne v$, be 30. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $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?

Consider the following two languages over the alphabet $\{a,b,c\}$, where $m$ and $n$ are natural numbers.

$L_1=\{a^m{b}^m{c}^{m+n}\mid m,n\ge 1\}$

$L_2=\{a^m{b}^n{c}^{m+n}\mid m,n\ge 1\}$

Which ONE of the following statements is CORRECT?

$A=\{0,1,2,3,\dots \}$ is the set of non-negative integers. Let $F$ be the set of functions from $A$ to itself. For any two functions, $f_1,f_2\in F$, we define

$(f_1\odot f_2)(n)=f_1(n)+f_2(n)$

for every number $n$ in $A$. Which of the following is/are CORRECT about the mathematical structure $(F,\odot )$?

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 a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, $1K=2^{10}$, $1M=2^{20}$.]

Consider the following four variable Boolean function in sum-of-product form

$F(b_3,b_2,b_1,b_0)=\Sigma (0,2,4,8,10,11,12).$

where the value of the function is computed by considering $b_3{b}_2{b}_1{b}_0$ as a 4-bit binary number, where $b_3$ denotes the most significant bit and $b_0$ denotes the least significant bit. Note that there are no don't care terms. Which ONE of the following options is the CORRECT minimized Boolean expression for $F$?

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 two languages over the alphabet $\{a,b\}$:

$L_1=\{\alpha \beta \alpha \mid \alpha \in \{a,b{\}}^{+}\text{ AND }\beta \in \{a,b{\}}^{+}\}$

$L_2=\{\alpha \beta \alpha \mid \alpha \in \{a{\}}^{+}\text{ AND }\beta \in \{a,b{\}}^{+}\}$

Which ONE of the following statements is CORRECT?

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?

A computer has two processors, $M_1$ and $M_2$. Four processes $P_1,P_2,P_3,P_4$ with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:

$M_1$ uses priority of execution for the processes as, $P_1>P_3>P_2>P_4$, i.e., $P_1$ and $P_4$ have highest and lowest priorities, respectively.

$M_2$ uses priority of execution for the processes as, $P_2>P_3>P_4>P_1$, i.e., $P_2$ and $P_1$ have highest and lowest priorities, respectively.

A process $P_i$ is scheduled to a processor $M_k$, if the processor is free and no other process $P_j$ is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?

Consider two relations describing teams and players in a sports league:

• teams(tid, tname): tid, tname are team-id and team-name, respectively
• players(pid, pname, tid): pid, pname, and tid denote player-id, player-name and the team-id of the player, respectively

Which ONE of the following tuple relational calculus queries returns the name of the players who play for the team having tname as 'MI'?

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?

Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives:

(i) The processor saves the content of the program counter.
(ii) The program counter is loaded with the start address of the ISR.
(iii) The processor finishes the present instruction.

Which ONE of the following is the CORRECT sequence of steps?