List of top Questions asked in GATE CS

In an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted.
- If the first question is answered wrong, the student gets zero marks.
- If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question.
- If both the questions are answered correctly, the student gets the sum of the marks of the two questions.
The following table shows the probability of correctly answering a question and the marks of the question respectively.
\[ \begin{array}{c|c|c} \text{Question} & \text{Probability of answering correctly} & \text{Marks}
\hline \text{QuesA} & 0.8 & 10
\text{QuesB} & 0.5 & 20
\end{array} \] Assuming that the student always wants to maximize her expected marks in the examination, in which order should she attempt the questions and what is the expected marks for that order (assume that the questions are independent)?

Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements:
\[ S_1:\ \text{Read misses in a write-through L1 cache do not result in writebacks of dirty lines to the L2.} \] \[ S_2:\ \text{Write allocate policy must be used in conjunction with write-through caches and no-write allocate policy is used with writeback caches.} \] Which of the following statements is correct?

For a biased coin, the probability of head is 0.4.
The coin is tossed 1000 times. The standard deviation of the number of heads (rounded to 2 decimal places) is \(\underline{\hspace{2cm}}\).

Consider a computer system with DMA support.
The DMA module transfers one 8-bit character in one CPU cycle using cycle stealing. The processor speed is 2 MHz and 0.5% of processor cycles are used for DMA. The data transfer rate of the device is \(\underline{\hspace{2cm}}\) bits per second.

A data file with 1,50,000 student records is stored on disk with block size 4096 bytes.
Each index record consists of an ANum field of size 12 bytes and a record pointer of size 7 bytes. The number of blocks in the index file is \(\underline{\hspace{2cm}}\).

Choose the correct choice(s) regarding the following propositional logic assertion $S$: \[ S : \big((P \land Q) \rightarrow R\big) \rightarrow \big((P \land Q) \rightarrow (Q \rightarrow R)\big) \]

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size \(n\)?

Let \(L \subseteq \{0,1\}^*\) be an arbitrary regular language accepted by a minimal DFA with \(k\) states. Which one of the following languages must necessarily be accepted by a minimal DFA with \(k\) states?

Consider the following sets, where \( n \geq 2 \):
\[ S_1:\ \text{Set of all } n \times n \text{ matrices with entries from the set } \{a,b,c\} \] \[ S_2:\ \text{Set of all functions from the set } \{0,1,2,\ldots,n^2-1\} \text{ to the set } \{0,1,2\} \] Which of the following choice(s) is/are correct?

Consider the following statements S1 and S2 about the relational data model:
S1: A relation scheme can have at most one foreign key.
S2: A foreign key in a relation scheme $R$ cannot be used to refer to tuples of $R$.
Which one of the following choices is correct?

Consider the three-way handshake mechanism followed during TCP connection establishment between hosts $P$ and $Q$. Let $X$ and $Y$ be two random 32-bit starting sequence numbers chosen by $P$ and $Q$ respectively. Suppose $P$ sends a TCP connection request message to $Q$ with a TCP segment having SYN bit = 1, SEQ number = $X$, and ACK bit = 0. Suppose $Q$ accepts the connection request. Which one of the following choices represents the information present in the TCP segment header that is sent by $Q$ to $P$?

The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year 3 was ₹1, which was half the cost/unit in Year 2. The cost/unit in Year 3 was one-third of the cost/unit in Year 1. Taxes were paid on the selling price at 10%, 13% and 15% respectively for the three years. Net profit is calculated as the difference between the selling price and the sum of cost and taxes paid in that year. The ratio of the selling price in Year 2 to the selling price in Year 3 is \(\underline{\hspace{1cm}}\).
\includegraphics[width=0.75\linewidth]{image9.png}

Six students P, Q, R, S, T and U, with distinct heights, compare their heights and make the following observations.
Observation I: S is taller than R.
Observation II: Q is the shortest of all.
Observation III: U is taller than only one student.
Observation IV: T is taller than S but is not the tallest.
The number of students that are taller than R is the same as the number of students shorter than \(\underline{\hspace{2cm}.}\)

Let \(G\) be a connected undirected weighted graph. Consider the following two statements:
\(S_1:\) There exists a minimum weight edge in \(G\) which is present in every minimum spanning tree of \(G\).
\(S_2:\) If every edge in \(G\) has distinct weight, then \(G\) has a unique minimum spanning tree.
Which one of the following options is correct?

Let \(H\) be a binary min-heap consisting of \(n\) elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in \(H\)?

A jigsaw puzzle has 2 pieces. One of the pieces is shown above. Which one of the given options for the missing piece, when assembled, will form a rectangle?
The piece can be moved, rotated or flipped to assemble with the above piece. \includegraphics[width=0.152\linewidth]{image7.png} \includegraphics[width=0.85\linewidth]{image07.png}

The number of students in three classes is in the ratio \(3:13:6\). If 18 students are added to each class, the ratio changes to \(15:35:21\).
The total number of students in all the three classes in the beginning was:

If $\left(x-\dfrac{1}{2}\right)^2 - \left(x-\dfrac{3}{2}\right)^2 = x + 2$, then the value of $x$ is: