List of top Questions asked in GATE CS

Let $A$ be a $2 \times 2$ matrix as given:

A = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}

What are the eigenvalues of the matrix $A^{13}$ ?

A packet with the destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to?

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

teams(tid, tname): tid and 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'?

Given Data:
- Two processors:

M_1

and

M_2

- Four processes:

P_1, P_2, P_3, P_4

- CPU bursts:

P_1 = 20

,

P_2 = 16

,

P_3 = 25

,

P_4 = 10

- Priority order for

M_1

:

P_1 > P_3 > P_2 > P_4

- Priority order for

M_2

:

P_2 > P_3 > P_4 > P_1

- Scheduling: Non-preemptive priority scheduling

Step 1: Assigning Processes to Processors
At

t = 0

, both processors are free. The highest-priority process for each processor is scheduled:
-

M_1

gets

P_1

(highest priority on

M_1

, burst = 20 ms).
-

M_2

gets

P_2

(highest priority on

M_2

, burst = 16 ms).

Step 2: Scheduling Remaining Processes
-

P_2

finishes at

t = 16

, so

M_2

picks the next highest-priority process,

P_3

(burst = 25 ms).
-

P_1

finishes at

t = 20

, so

M_1

picks

P_4

(burst = 10 ms).
-

P_4

finishes at

t = 30

, and

P_3

finishes at

t = 41

.

Step 3: Calculate Waiting Times
-

P_1

starts at 0, so waiting time =

0

ms.
-

P_2

starts at 0, so waiting time =

0

ms.
-

P_3

starts at 16, so waiting time =

16

ms.
-

P_4

starts at 20, so waiting time =

20

ms.

Step 4: Compute Average Waiting Time

\text{Average waiting time} = \frac{(0 + 0 + 16 + 20)}{4} = \frac{36}{4} = 9 \text{ ms}.

Final Answer: The average waiting time of the processes is

9

milliseconds.

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?

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates a 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}$ .]

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

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

\text{fun(int A[0, \ldots, n-1])} \{

\text{for } i = 0 \text{ to } n-2

\text{for } j = 0 \text{ to } n - i - 2

\text{if } (A[j] > A[j+1]) \text{ then swap } A[j] \text{ and } A[j+1]

\}

Let $A[0, \ldots, 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, \ldots, 29]

as argument, is ______ (Answer in integer).

A box contains 5 coins: 4 regular coins and 1 fake coin.

- When a regular coin is tossed, the probability

P(\text{head}) = 0.5

.
- For a fake coin,

P(\text{head}) = 1

.

You pick a coin at random and toss it twice, and get two heads. The probability that the coin you have chosen is the fake coin is ______.

Consider the given function $f(x)$ .

f(x) = \begin{cases} ax + b & \text{for } x < 1 \\ x^3 + x^2 + 1 & \text{for } x \geq 1 \end{cases}

If the function is differentiable everywhere, the value of $b$ must be ________ (rounded off to one decimal place).

Let $S$ be the set of all ternary strings defined over the alphabet $\{a, b, c\}$ . Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that is, "aa", "bb", or "cc". The number of such strings of length 5 that are possible is _________.

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?

A partial data path of a processor is given in the figure, where RA, RB, and RZ are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data path as shown?

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?

The number $-6$ can be represented as $1010$ in 4-bit 2’s complement representation. Which of the following is/are CORRECT 2’s complement representation(s) of $-6$ ?

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?

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?

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?

Consider the following recurrence relation:

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

Which ONE of the following options is CORRECT?

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 AaA

B \to b \mid bB

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

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let $d_1(u, v)$ and $d_2(u, v)$ be the shortest distances between u and v in G and T, respectively. Which ONE of the following options is CORRECT for all possible G, T, u, and v?

g(periodcentered) is a function from A to B, f(periodcentered) is a function from B to C, and their composition defined as f(g(periodcentered)) is a mapping from A to C. If f(periodcentered) and f(g(periodcentered)) are onto (surjective) functions, which ONE of the following is TRUE about the function g(periodcentered)?

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

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?

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?