List of top Software Engineering Questions asked in GATE Computer Science and Information Technology

Consider the following C function definition: \begin{verbatim} int f(int x, int y) { for (int i = 0; i<y; i++) { x = x + x + y; } return x; } \end{verbatim} Which of the following statements is/are TRUE about the above function?

Consider the 5-state DFA \( M \) accepting the language \( L(M) \subseteq (0+1)^* \) shown below. For any string \( w \in (0+1)^* \), let \( n_0(w) \) be the number of \( 0 \)'s in \( w \) and \( n_1(w) \) be the number of \( 1 \)'s in \( w \). \begin{center} \includegraphics[width = 6cm]{50.png} \end{center} Which of the following statements is/are FALSE?

Let \( A \) be any \( n \times m \) matrix, where \( m>n \). Which of the following statements is/are TRUE about the system of linear equations \( Ax = 0 \)?

The symbol \( \rightarrow \) indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

Consider the following recurrence relation: \[ T(n) = \begin{cases} \sqrt{n}T(\sqrt{n}) + n & \text{for } n \geq 1,
1 & \text{for } n = 1. \end{cases} \] Which one of the following options is CORRECT?

Consider a Boolean expression given by \( F(X, Y, Z) = \Sigma(3, 5, 6, 7) \). Which of the following statements is/are CORRECT?

Consider a binary min-heap containing 105 distinct elements. Let \( k \) be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of \( k \) is:

Let \( G \) be a directed graph and \( T \) a depth first search (DFS) spanning tree in \( G \) that is rooted at a vertex \( v \). Suppose \( T \) is also a breadth first search (BFS) tree in \( G \), rooted at \( v \). Which of the following statements is/are TRUE for every such graph \( G \) and tree \( T \)?

Consider the following read-write schedule \( S \) over three transactions \( T_1, T_2, \text{and } T_3 \), where the subscripts in the schedule indicate transaction IDs: \[ S: r_1(z); w_1(z); r_2(x); r_3(y); w_3(y); r_2(y); w_2(x); w_2(y); \]
Which of the following transaction schedules is/are conflict equivalent to \( S \)?

An array \( [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] \) is heapified. Which one of the following options represents the first three elements in the heapified array?

Consider a 5-stage pipelined processor with Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Register Writeback (WB) stages. Which of the following statements about forwarding is/are CORRECT?

Consider the circuit shown below where the gates may have propagation delays. Assume that all signal transitions occur instantaneously and that wires have no delays. Which of the following statements about the circuit is/are CORRECT? \begin{center} \includegraphics[width=8cm]{28.png} \end{center}

Which of the following fields is/are modified in the IP header of a packet going out of a network address translation (NAT) device from an internal network to an external network?

Let \( A \) and \( B \) be two events in a probability space with \( P(A) = 0.3 \), \( P(B) = 0.5 \), and \( P(A \cap B) = 0.1 \). Which of the following statements is/are TRUE?

TCP client \( P \) successfully establishes a connection to TCP server \( Q \). Let \( N_P \) denote the sequence number in the SYN sent from \( P \) to \( Q \). Let \( N_Q \) denote the acknowledgement number in the SYN ACK from \( Q \) to \( P \). Which of the following statements is/are CORRECT?

A bag contains 10 red balls and 15 blue balls. Two balls are drawn randomly without replacement. Given that the first ball drawn is red, the probability (rounded off to 3 decimal places) that both balls drawn are red is \_\_\_\_.

Consider a digital logic circuit consisting of three 2-to-1 multiplexers \(M_1, M_2,\) and \(M_3\) as shown below. \(X_1\) and \(X_2\) are inputs of \(M_1\). \(X_3\) and \(X_4\) are inputs of \(M_2\). \(A, B,\) and \(C\) are select lines of \(M_1, M_2,\) and \(M_3,\) respectively. \begin{center} \includegraphics[width=6cm]{64.png} \end{center} For an instance of inputs \(X_1 = 1\), \(X_2 = 1\), \(X_3 = 0\), and \(X_4 = 0\), the number of combinations of \(A, B, C\) that give the output \(Y = 1\) is \_\_\_\_\_.

Consider sending an IP datagram of size 1420 bytes (including 20 bytes of IP header) from a sender to a receiver over a path of two links with a router between them. The first link (sender to router) has an MTU of 542 bytes, while the second link (router to receiver) has an MTU of 360 bytes. The number of fragments that would be delivered at the receiver is \_\_\_\_\_.

Consider the following two regular expressions over the alphabet \(\{0,1\}\): \[ r = 0^* + 1^* \quad \text{and} \quad s = 01^* + 10^*. \] The total number of strings of length less than or equal to 5, which are neither in \( r \) nor in \( s \), is \_\_\_\_\_\_.

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is \_\_\_\_\_.

Consider a 512 GB hard disk with 32 storage surfaces. There are 4096 sectors per track and each sector holds 1024 bytes of data. The number of cylinders in the hard disk is \_\_\_\_\_\ .

The baseline execution time of a program on a \( 2 \, \text{GHz} \) single core machine is \( 100 \, \text{ns} \). The code corresponding to \( 90\% \) of the execution time can be fully parallelized. The overhead for using an additional core is \( 10 \, \text{ns} \) when running on a multicore system. Assume that all cores in the multicore system run their share of the parallelized code for an equal amount of time. The number of cores that minimize the execution time of the program is \_\_\_\_\_.

A given program has \( 25\% \) load/store instructions. Suppose the ideal CPI (cycles per instruction) without any memory stalls is 2. The program exhibits \( 2\% \) miss rate on instruction cache and \( 8\% \) miss rate on data cache. The miss penalty is \( 100 \) cycles. The speedup (rounded off to two decimal places) achieved with a perfect cache (i.e., with NO data or instruction cache misses) is \_\_\_\_\_.

Consider the following code snippet using the \texttt{fork() and \texttt{wait()} system calls. Assume that the code compiles and runs correctly, and that the system calls run successfully without any errors.} \begin{verbatim} int x = 3; while (x>0) { fork(); printf("hello"); wait(NULL); x--; } \end{verbatim} The total number of times the \texttt{printf} statement is executed is \_\_\_\_\_.

Consider the entries shown below in the forwarding table of an IP router. Each entry consists of an IP prefix and the corresponding next hop router for packets whose destination IP address matches the prefix. The notation “/N” in a prefix indicates a subnet mask with the most significant \( N \) bits set to 1. \begin{center} \begin{tabular}{|c|c|} \hline Prefix & Next hop router
\hline 10.1.1.0/24 & R1
10.1.1.128/25 & R2
10.1.1.64/26 & R3
10.1.1.192/26 & R4
\hline \end{tabular} \end{center} This router forwards 20 packets each to 5 hosts. The IP addresses of the hosts are \( 10.1.1.16 \), \( 10.1.1.72 \), \( 10.1.1.132 \), \( 10.1.1.191 \), and \( 10.1.1.205 \). The number of packets forwarded via the next hop router \( R2 \) is \_\_\_\_\_.