GATE CS 2024 Set 1 - W3Colleges

Question 11

MCQ · 1 mark · −0.33

Let \(f: \mathbb{R} \to \mathbb{R}\) be a function such that \(f(x) = \max\{x, x^{3}\}\), \(x \in \mathbb{R}\), where \(\mathbb{R}\) is the set of all real numbers. The set of all points where \(f(x)\) is NOT differentiable is

\(\{-1, 1, 2\}\) \(\{-2, -1, 1\}\) \(\{0, 1\}\) \(\{-1, 0, 1\}\)

Explanation

Answer: (D)

The curves \(y = x\) and \(y = x^{3}\) cross where \(x^{3} = x\), that is at \(x = -1, 0, 1\). Between these points the larger one switches:

for \(x \lt -1\) and \(0 \lt x \lt 1\): \(f(x) = x\), slope 1;
for \(-1 \lt x \lt 0\) and \(x \gt 1\): \(f(x) = x^{3}\), slope \(3x^{2}\).

At each crossing the slopes on the two sides differ: at \(x = \pm 1\) they are 1 and 3, and at \(x = 0\) they are 0 and 1. So the graph has a corner at each of these points, and \(f\) is not differentiable exactly on \(\{-1, 0, 1\}\). Elsewhere \(f\) equals a single polynomial near each point, so it is differentiable.

Answer: D

Question 12

MCQ · 1 mark · −0.33

The product of all eigenvalues of the matrix \(\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\) is

\(-1\) 0 1 2

Explanation

Answer: (B)

The product of all eigenvalues of a square matrix equals its determinant.

Here the rows are linearly dependent: each row exceeds the previous one by \((3, 3, 3)\), so \(R_{1} + R_{3} = 2R_{2}\). A matrix with dependent rows has determinant 0:

\[\det\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} = 0.\]

So 0 is one of the eigenvalues, and the product of all the eigenvalues is 0, whatever the other two are.

Answer: B

Question 13

MCQ · 1 mark · −0.33

Consider a system that uses 5 bits for representing signed integers in 2’s complement format. In this system, two integers \(A\) and \(B\) are represented as \(A\)=01010 and \(B\)=11010. Which one of the following operations will result in either an arithmetic overflow or an arithmetic underflow?

\(A + B\) \(A - B\) \(B - A\) \(2 * B\)

Explanation

Answer: (B)

With 5 bits, 2’s complement covers \(-16\) to \(+15\). Decode the operands: \(A = 01010 = +10\), and \(B = 11010 = -6\) (invert and add 1 to get \(00110 = 6\)).

\(A + B = 4\): in range.
\(A - B = 10 + 6 = 16\): above \(+15\), so it overflows; the 5-bit result 10000 would read as \(-16\).
\(B - A = -16\): exactly the most negative value, so it fits.
\(2 * B = -12\): in range.

Only \(A - B\) leaves the representable range.

Answer: B

Question 14

MCQ · 1 mark · −0.33

Consider a permutation sampled uniformly at random from the set of all permutations of \(\{1, 2, 3, \cdots, n\}\) for some \(n \geq 4\). Let \(X\) be the event that 1 occurs before 2 in the permutation, and \(Y\) the event that 3 occurs before 4. Which one of the following statements is TRUE?

The events \(X\) and \(Y\) are mutually exclusive The events \(X\) and \(Y\) are independent Either event \(X\) or \(Y\) must occur Event \(X\) is more likely than event \(Y\)

Explanation

Answer: (B)

By symmetry, 1 comes before 2 in exactly half of all permutations, so \(P(X) = \frac{1}{2}\); likewise \(P(Y) = \frac{1}{2}\).

The order inside the pair \(\{1, 2\}\) and the order inside the pair \(\{3, 4\}\) are each equally likely either way and do not influence each other, so \(P(X \cap Y) = \frac{1}{4} = P(X)\,P(Y)\). Hence \(X\) and \(Y\) are independent.

A fails: both events can happen together (probability \(\frac{1}{4}\)).
C fails: both can fail together, for example in 2, 1, 4, 3, ….
D fails: the two events are equally likely.

Answer: B

Question 15

MCQ · 1 mark · −0.33

Which one of the following statements is FALSE?

In the cycle stealing mode of DMA, one word of data is transferred between an I/O device and main memory in a stolen cycle For bulk data transfer, the burst mode of DMA has a higher throughput than the cycle stealing mode Programmed I/O mechanism has a better CPU utilization than the interrupt driven I/O mechanism The CPU can start executing an interrupt service routine faster with vectored interrupts than with non-vectored interrupts

Explanation

Answer: (C)

Statement C is false. In programmed I/O the CPU keeps polling the device status until it is ready, so its cycles are wasted in busy-waiting. Interrupt-driven I/O lets the CPU do other work and respond only when the device raises an interrupt, so it gives better CPU utilization, not worse.

The other statements are true:

A: in cycle stealing, the DMA controller takes the bus for one cycle and moves one word.
B: burst mode keeps the bus for the whole block, so bulk transfers finish sooner.
D: a vectored interrupt supplies the address of its service routine, so the CPU need not poll devices to find the source.

Answer: C

Question 16

MCQ · 1 mark · −0.33

A user starts browsing a webpage hosted at a remote server. The browser opens a single TCP connection to fetch the entire webpage from the server. The webpage consists of a top-level index page with multiple embedded image objects. Assume that all caches (e.g., DNS cache, browser cache) are all initially empty. The following packets leave the user’s computer in some order.

(i) HTTP GET request for the index page
(ii) DNS request to resolve the web server’s name to its IP address
(iii) HTTP GET request for an image object
(iv) TCP SYN to open a connection to the web server

Which one of the following is the CORRECT chronological order (earliest in time to latest) of the packets leaving the computer ?

(iv), (ii), (iii), (i) (ii), (iv), (iii), (i) (ii), (iv), (i), (iii) (iv), (ii), (i), (iii)

Explanation

Answer: (C)

Follow what the browser needs at each step:

(ii) It knows only the server’s name and the DNS cache is empty, so it must first send a DNS request for the IP address.
(iv) With the address known, it opens the TCP connection by sending a SYN.
(i) Over that connection it requests the index page.
(iii) Only after the index page arrives does the browser learn which images are embedded, so an image GET comes last.

So the order is (ii), (iv), (i), (iii). Options A and D send the SYN before the address is known, and option B requests an image before the index page.

Answer: C

Question 17

MCQ · 1 mark · −0.33

Given an integer array of size \(N\), we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is

both \(O(N)\) and \(\Omega(N)\) \(O(N)\) but not \(\Omega(N)\) \(\Omega(N)\) but not \(O(N)\) neither \(O(N)\) nor \(\Omega(N)\)

Explanation

Answer: (A)

The algorithm walks once through the array, comparing each adjacent pair \((a_{i}, a_{i+1})\), and stops as soon as a pair breaks the order. The worst case is an array that really is sorted (or breaks the order only at the very end): all \(N-1\) pairs must then be compared before the algorithm can answer.

So the worst-case time grows linearly with \(N\). It is \(\Theta(N)\), which means it is both \(O(N)\) and \(\Omega(N)\).

B fails because no method can do better: an element that is never examined could break the order, so the time is also \(\Omega(N)\). C and D fail because a single pass is \(O(N)\).

Answer: A

Question 18

MCQ · 1 mark · −0.33

Consider the following C program:

#include <stdio.h>
int main(){
   int a = 6;
   int b = 0;
   while(a < 10) {
      a = a / 12 + 1;
      a += b;}
   printf("%d", a);
   return 0;}

Which one of the following statements is CORRECT?

The program prints 9 as output The program prints 10 as output The program gets stuck in an infinite loop The program prints 6 as output

Explanation

Answer: (C)

Both operands of a / 12 are integers, so the division truncates. Starting from a = 6, the first pass gives \(6/12 = 0\), so a becomes \(0 + 1 = 1\), and a += b adds 0.

On every later pass a is 1: the test \(1 < 10\) holds, \(1/12 = 0\), and a is set to 1 again. Since b stays 0, nothing ever raises a to 10, so the condition never fails, the loop never exits and printf is never reached.

Options A, B and D all assume that the loop ends and something is printed.

Answer: C

Question 19

MCQ · 1 mark · −0.33

Consider the following C program:

#include <stdio.h>
void fX();
int main(){
   fX();
   return 0;}

void fX(){
 char a;
 if((a=getchar()) != '\n')
     fX();
 if(a != '\n')
     putchar(a);}

Assume that the input to the program from the command line is 1234 followed by a newline character. Which one of the following statements is CORRECT?

The program will not terminate The program will terminate with no output The program will terminate with 4321 as output The program will terminate with 1234 as output

Explanation

Answer: (C)

Each call of fX reads one character into its own local variable a. If that character is not a newline, the call recurses first and prints its own character only after the inner call returns, so characters come out in the reverse of the order they were read.

With the input 1234 and a newline, five nested calls read '1', '2', '3', '4' and '\n'. The fifth call neither recurses nor prints, and returns. The waiting calls then print 4, 3, 2 and 1 as they unwind, and main returns.

The newline ends the recursion, so the program terminates (not A) and prints 4321. Printing 1234 would need putchar before the recursive call.

Answer: C

Question 20

MCQ · 1 mark · −0.33

Let S be the specification: "Instructors teach courses. Students register for courses. Courses are allocated classrooms. Instructors guide students." Which one of the following ER diagrams CORRECTLY represents S?

ER diagrams (i) and (ii), with entity sets in rectangles and relationships in diamonds. In (i), Instructor–Teaches–Course and Classroom–Allocation–Course, a Registration rectangle is attached directly to Course, and a Student diamond joins Course to a Guides diamond that joins Instructor; in (ii), Instructor–Teaches–Course, Classroom–Allocation–Course, Course–Registration–Projects and Instructor–Guides–Projects.

ER diagrams (iii) and (iv), with entity sets in rectangles and relationships in diamonds. In (iii), Instructor–Teaches–Course, Course–Registration–Student and Instructor–Guides–Student, while Classroom is joined to Course by a plain line and the Allocation diamond hangs from Course alone; in (iv), Instructor–Teaches–Course, Classroom–Allocation–Course, Course–Registration–Student and Instructor–Guides–Student.

(i) (ii) (iii) (iv)

Explanation

Answer: (D)

The specification has four entity sets (Instructor, Course, Student and Classroom) and four relationships: Teaches (Instructor–Course), Registration (Student–Course), Allocation (Course–Classroom) and Guides (Instructor–Student). In an ER diagram entity sets are rectangles, relationships are diamonds, and two entity sets are linked only through a relationship.

(i) swaps the roles: Student is drawn as a relationship and Registration as an entity set.
(ii) has no Student entity set at all; Projects, which the specification never mentions, takes its place.
(iii) joins Classroom straight to Course with a plain line, and its Allocation diamond is connected to Course only.
(iv) shows exactly the four entity sets joined through the four relationships.

Answer: D

Computer Science and Information Technology