GATE CS 2024 Set 2 - W3Colleges

Question 31

MSQ · 1 mark

An instruction format has the following structure:

Instruction Number: Opcode destination reg, source reg-1, source reg-2

Consider the following sequence of instructions to be executed in a pipelined processor:

I1: DIV R3, R1, R2
I2: SUB R5, R3, R4
I3: ADD R3, R5, R6
I4: MUL R7, R3, R8

Which of the following statements is/are TRUE?

There is a RAW dependency on R3 between I1 and I2 There is a WAR dependency on R3 between I1 and I3 There is a RAW dependency on R3 between I2 and I3 There is a WAW dependency on R3 between I3 and I4

Explanation

Answer: (A)

Take an earlier instruction and a later one. RAW (read after write) means the later one reads a register that the earlier one writes, WAR means the later one writes a register that the earlier one reads, and WAW means both write the same register. Here R3 is written by I1 and I3 and read by I2 and I4.

A: I1 writes R3 and I2 reads it. RAW, so true.
B: I1 and I3 both write R3, and I1 does not read it. That is WAW, not WAR.
C: I2 reads R3 and the later I3 writes it. That is WAR, not RAW (the RAW between them is on R5).
D: I3 writes R3 and I4 reads it. That is RAW, not WAW; I4 writes R7.

Answer: A

Question 32

MSQ · 1 mark

Which of the following fields of an IP header is/are always modified by any router before it forwards the IP packet?

Source IP Address Protocol Time to Live (TTL) Header Checksum

Explanation

Answer: (C), (D)

When a router forwards an IPv4 packet:

it decrements the TTL by 1 (and discards the packet if the TTL reaches 0), so the TTL always changes;
the header checksum covers the whole header, TTL included, so it must be recomputed and rewritten every time.

The source IP address identifies the original sender and stays the same end to end; only special devices such as NAT boxes rewrite it, not every router. The protocol field names the protocol of the payload (for example 6 for TCP), which a router has no reason to change.

Answer: C, D

Question 33

MSQ · 1 mark

Consider the following C function definition.

int fX(char *a){
    char *b = a;
    while(*b)
        b++;
    return b - a;}

Which of the following statements is/are TRUE?

The function call fX("abcd") will always return a value Assuming a character array c is declared as char c[] = "abcd" in main(), the function call fX(c) will always return a value The code of the function will not compile Assuming a character pointer c is declared as char *c = "abcd" in main(), the function call fX(c) will always return a value

Explanation

Answer: (A), (B), (D)

fX moves the pointer b forward until it reaches the terminating '\0' and returns b - a, the number of characters before it: the length of the string. The pointer difference is converted to int on return, so the function is valid C and (C) is false.

(A) A string literal is always stored with a terminating null character, so the call returns 4.
(B) char c[] = "abcd" creates a 5-element array whose last element is '\0', so the call returns 4.
(D) c points to the literal itself, which also ends in '\0', so the call returns 4.

The loop stops in every case, so all three calls return a value.

Answer: A, B, D

Question 34

NAT · 1 mark

Let $P$ be the partial order defined on the set $\{1,2,3,4\}$ as follows

\[P = \{(x, x) \mid x \in \{1,2,3,4\}\} \cup \{(1,2), (3,2), (3,4)\}\]

The number of total orders on $\{1,2,3,4\}$ that contain $P$ is __________

Your answer

Explanation

Answer: 5

A total order that contains $P$ is a linear extension of $P$: an arrangement of 1, 2, 3, 4 in which 1 comes before 2, 3 comes before 2, and 3 comes before 4. Only the minimal elements 1 and 3 can come first.

First 1: among 2, 3, 4 the element 3 must lead, and 2 and 4 follow in either order: 1, 3, 2, 4 and 1, 3, 4, 2.
First 3: the remaining 1, 2, 4 only need 1 before 2, which half of their $3! = 6$ orders satisfy: 3, 1, 2, 4; 3, 1, 4, 2; 3, 4, 1, 2.

So $2 + 3 = 5$ total orders contain $P$.

Answer: 5

Question 35

NAT · 1 mark

Let $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array $[2, 5, 3, 1, 4, 2, 6]$ is ___________

Your answer

Explanation

Answer: 3

The elements that are not replaced keep their values and positions, so they must already form a non-decreasing subsequence. Conversely, any kept non-decreasing subsequence works: every other element can be replaced by a value between its kept neighbours, since equal values are allowed. So the distance is the array length minus the length of the longest non-decreasing subsequence.

In $[2, 5, 3, 1, 4, 2, 6]$ the longest one is $2, 3, 4, 6$, of length 4; no subsequence of length 5 is non-decreasing. Replacing the other three elements (5, 1 and 2) by, say, 3, 4 and 5 gives $[2, 3, 3, 4, 4, 5, 6]$.

Distance $= 7 - 4 = 3$.

Answer: 3

Question 36

MCQ · 2 marks · −0.66

What is the output of the following C program?

#include <stdio.h>
int main() {
    double a[2]={20.0, 25.0}, *p, *q;
    p = a;
    q = p + 1;
    printf("%d,%d", (int)(q - p), (int)(*q - *p));
    return 0;}

4,8 1,5 8,5 1,8

Explanation

Answer: (B)

p points to a[0], and q = p + 1 points to the next element, a[1].

Subtracting two pointers into the same array counts elements, not bytes, so q - p is 1, even though a double usually takes 8 bytes.
*q - *p subtracts the stored values: $25.0 - 20.0 = 5.0$, which the cast turns into the int 5.

So the program prints 1,5. Option (C) reports the pointer gap in bytes instead of elements, and the 4 and 8 in (A) and (D) match neither expression.

Answer: B

Question 37

MCQ · 2 marks · −0.66

Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time.

A (0, 10), B (2, 6), C (4, 3), and D (6, 7).

Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?

SRTF = 6, NP-SJF = 7 SRTF = 6, NP-SJF = 7.5 SRTF = 7, NP-SJF = 7.5 SRTF = 7, NP-SJF = 8.5

Explanation

Answer: (B)

SRTF: A runs 0–2. B (6) preempts A (8 left) and runs 2–4. C (3) preempts B (4 left) and runs 4–7; D arrives at 6 but needs 7, more than C’s last unit. Then B runs 7–11, D 11–18 and A 18–26.

Waiting time = completion − arrival − burst: A $26 - 0 - 10 = 16$, B $11 - 2 - 6 = 3$, C $7 - 4 - 3 = 0$, D $18 - 6 - 7 = 5$. Average $= 24/4 = 6$.

NP-SJF: A, alone at time 0, runs 0–10 without interruption. Then the shortest waiting job goes first each time: C 10–13, B 13–19, D 19–26. Waiting times: A 0, C 6, B 11, D 13. Average $= 30/4 = 7.5$.

Answer: B

Question 38

MCQ · 2 marks · −0.66

Which one of the following CIDR prefixes exactly represents the range of IP addresses 10.12.2.0 to 10.12.3.255?

10.12.2.0/23 10.12.2.0/24 10.12.0.0/22 10.12.2.0/22

Explanation

Answer: (A)

The range holds $2 \times 256 = 512 = 2^{9}$ addresses, so the block needs 9 host bits: a /23 prefix. In the third octet, 2 is 00000010 and 3 is 00000011, so only its last bit varies, and 10.12.2.0 has all 9 host bits zero. So 10.12.2.0/23 covers exactly 10.12.2.0 to 10.12.3.255.

10.12.2.0/24 covers only 10.12.2.0 to 10.12.2.255, half the range.
10.12.0.0/22 covers 10.12.0.0 to 10.12.3.255, twice the range.
10.12.2.0 does not start a /22 block; with a /22 mask it falls in the block 10.12.0.0 to 10.12.3.255, again too large.

Answer: A

Question 39

MCQ · 2 marks · −0.66

You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty tree. The tree $T$ follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into $T$, and you do not have access to $T$.

Which one of the following statements is TRUE?

Inorder traversal of $T$ can be determined from $V$ Root node of $T$ can be determined from $V$ Preorder traversal of $T$ can be determined from $V$ Postorder traversal of $T$ can be determined from $V$

Explanation

Answer: (A)

An inorder traversal visits the left subtree, then the node, then the right subtree. In a binary search tree with smaller values on the left, this always lists the keys in increasing order, whatever the shape of the tree. So sorting $V$ gives the inorder traversal of $T$.

The other three depend on the insertion order. The root is simply the first value inserted: inserting 1, 2, 3 gives root 1 with a chain to the right, while 2, 1, 3 gives root 2 with two children. These two trees also differ in preorder (1, 2, 3 against 2, 1, 3) and postorder (3, 2, 1 against 1, 3, 2), so none of them can be found from $V$ alone.

Answer: A

Question 40

MCQ · 2 marks · −0.66

Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a,b,c,d\}$.

$S \to AaAb \mid BbBa$
$A \to cS \mid \epsilon$
$B \to dS \mid \epsilon$

The following is a partially-filled LL(1) parsing table.

	$a$	$b$	$c$	$d$
$S$	$S \to AaAb$	$S \to BbBa$	(1)	(2)
$A$	$A \to \epsilon$	(3)	$A \to cS$
$B$	(4)	$B \to \epsilon$		$B \to dS$

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, “blank” denotes that the corresponding cell is empty.

(1) $S \to AaAb$ (2) $S \to BbBa$ (3) $A \to \epsilon$ (4) $B \to \epsilon$ (1) $S \to BbBa$ (2) $S \to AaAb$ (3) $A \to \epsilon$ (4) $B \to \epsilon$ (1) $S \to AaAb$ (2) $S \to BbBa$ (3) blank (4) blank (1) $S \to BbBa$ (2) $S \to AaAb$ (3) blank (4) blank

Explanation

Answer: (A)

Fill each cell from FIRST and FOLLOW sets.

$\text{FIRST}(A) = \{c, \epsilon\}$, so $\text{FIRST}(AaAb) = \{c, a\}$: $S \to AaAb$ goes under $a$ and under $c$, which is cell (1).
$\text{FIRST}(B) = \{d, \epsilon\}$, so $\text{FIRST}(BbBa) = \{d, b\}$: $S \to BbBa$ goes under $b$ and under $d$, which is cell (2).
In $S \to AaAb$ the two $A$s are followed by $a$ and by $b$, so $\text{FOLLOW}(A) = \{a, b\}$ and $A \to \epsilon$ fills both the $a$ column and cell (3).
Likewise $\text{FOLLOW}(B) = \{a, b\}$ from $S \to BbBa$, so $B \to \epsilon$ fills cell (4).

No cell receives two entries, so the grammar is LL(1) and none of the numbered cells is blank; swapping (1) and (2) would mix up the FIRST sets.

Answer: A

	\(a\)	\(b\)	\(c\)	\(d\)
\(S\)	\(S \to AaAb\)	\(S \to BbBa\)	(1)	(2)
\(A\)	\(A \to \epsilon\)	(3)	\(A \to cS\)
\(B\)	(4)	\(B \to \epsilon\)		\(B \to dS\)

Computer Science and Information Technology