GATE CS 2024: Computer Science and Information Technology Session 2
Text of page 1
Computer Science and Information Technology Set 2 (CS2)
General Aptitude (GA)
Q.1 – Q.5 Carry ONE mark Each
Q.1 If ‘→’ denotes increasing order of intensity, then the meaning of the words
[walk → jog → sprint] is analogous to [bothered → ________ → daunted].
Which one of the given options is appropriate to fill the blank?
(A) phased
(B) phrased
(C) fazed
(D) fused
Q.2 Two wizards try to create a spell using all the four elements, water, air, fire, and
earth. For this, they decide to mix all these elements in all possible orders. They
also decide to work independently. After trying all possible combination of
elements, they conclude that the spell does not work.
How many attempts does each wizard make before coming to this conclusion,
independently?
(A) 24
(B) 48
(C) 16
(D) 12
Page 1 of 40
Organizing Institute: IISc, Bengaluru
Text of page 2
Computer Science and Information Technology Set 2 (CS2)
Q.3 In an engineering college of 10,000 students, 1,500 like neither their core branches
nor other branches. The number of students who like their core branches is 1/4th of
the number of students who like other branches. The number of students who like
both their core and other branches is 500.
The number of students who like their core branches is
(A) 1,800
(B) 3,500
(C) 1,600
(D) 1,500
Q.4 For positive non-zero real variables x and y, if
x+y 1
ln ( ) = [ln(x) + ln(y)]
2 2
x y
then, the value of + is
y x
(A) 1
(B) 1/2
(C) 2
(D) 4
Page 2 of 40
Organizing Institute: IISc, Bengaluru
Text of page 3
Computer Science and Information Technology Set 2 (CS2)
Q.5 In the sequence 6, 9, 14, x, 30, 41, a possible value of x is
(A) 25
(B) 21
(C) 18
(D) 20
Page 3 of 40
Organizing Institute: IISc, Bengaluru
Text of page 4
Computer Science and Information Technology Set 2 (CS2)
Q.6 – Q.10 Carry TWO marks Each
Q.6 Sequence the following sentences in a coherent passage.
P: This fortuitous geological event generated a colossal amount of energy and
heat that resulted in the rocks rising to an average height of 4 km across the
contact zone.
Q: Thus, the geophysicists tend to think of the Himalayas as an active geological
event rather than as a static geological feature.
R: The natural process of the cooling of this massive edifice absorbed large
quantities of atmospheric carbon dioxide, altering the earth’s atmosphere and
making it better suited for life.
S: Many millennia ago, a breakaway chunk of bedrock from the Antarctic Plate
collided with the massive Eurasian Plate.
(A) QPSR
(B) QSPR
(C) SPRQ
(D) SRPQ
Page 4 of 40
Organizing Institute: IISc, Bengaluru
Text of page 5
Computer Science and Information Technology Set 2 (CS2)
Q.7 A person sold two different items at the same price. He made 10% profit in one
item, and 10% loss in the other item. In selling these two items, the person made a
total of
(A) 1% profit
(B) 2% profit
(C) 1% loss
(D) 2% loss
Page 5 of 40
Organizing Institute: IISc, Bengaluru
Text of page 6
Computer Science and Information Technology Set 2 (CS2)
Q.8 The pie charts depict the shares of various power generation technologies in the
total electricity generation of a country for the years 2007 and 2023.
Year Solar Year
2007 5% 2023
Solar Coal
Coal 20% 20%
Hydro
35%
30% Gas
15%
Hydro
Gas 35%
25%
Wind
Wind
10%
5%
The renewable sources of electricity generation consist of Hydro, Solar and Wind.
Assuming that the total electricity generated remains the same from 2007 to 2023,
what is the percentage increase in the share of the renewable sources of electricity
generation over this period?
(A) 25%
(B) 50%
(C) 77.5%
(D) 62.5%
Page 6 of 40
Organizing Institute: IISc, Bengaluru
Text of page 7
Computer Science and Information Technology Set 2 (CS2)
Q.9 A cube is to be cut into 8 pieces of equal size and shape. Here, each cut should be
straight and it should not stop till it reaches the other end of the cube.
The minimum number of such cuts required is
(A) 3
(B) 4
(C) 7
(D) 8
Page 7 of 40
Organizing Institute: IISc, Bengaluru
Text of page 8
Computer Science and Information Technology Set 2 (CS2)
Q.10 In the 4 × 4 array shown below, each cell of the first three rows has either a
cross (X) or a number.
The number in a cell represents the count of the immediate neighboring cells
(left, right, top, bottom, diagonals) NOT having a cross (X). Given that the last row
has no crosses (X), the sum of the four numbers to be filled in the last row is
(A) 11
(B) 10
(C) 12
(D) 9
Page 8 of 40
Organizing Institute: IISc, Bengaluru
Text of page 9
Computer Science and Information Technology Set 2 (CS2)
Q.11 – Q.35 Carry ONE mark Each
Consider a computer with a 4 MHz processor. Its DMA controller can transfer
8 bytes in 1 cycle from a device to main memory through cycle stealing at regular
Q.11
intervals. Which one of the following is the data transfer rate (in bits per second) of
the DMA controller if 1% of the processor cycles are used for DMA?
(A) 2,56,000
(B) 3,200
(C) 25,60,000
(D) 32,000
Q.12 Let p and qbe the following propositions:
p: Fail grade can be given.
q: Student scores more than 50% marks.
Consider the statement: “Fail grade cannot be given when student scores more than
50% marks.”
Which one of the following is the CORRECT representation of the above statement
in propositional logic?
(A) q → ¬p
(B) q→p
(C) p→q
(D) ¬p → q
Page 9 of 40
Organizing Institute: IISc, Bengaluru
Text of page 10
Computer Science and Information Technology Set 2 (CS2)
Q.13 Consider the following C program. Assume parameters to a function are evaluated
from right to left.
#include <stdio.h>
int g(int p) { printf("%d", p); return p; }
int h(int q) { printf("%d", q); return q; }
void f(int x, int y) {
g(x);
h(y);
}
int main() {
f(g(10),h(20));
}
Which one of the following options is the CORRECT output of the above
C program?
(A) 20101020
(B) 10202010
(C) 20102010
(D) 10201020
Page 10 of 40
Organizing Institute: IISc, Bengaluru
Text of page 11
Computer Science and Information Technology Set 2 (CS2)
Q.14 The format of a single-precision floating-point number as per the
IEEE 754 standard is:
Sign Exponent Mantissa
(1bit) (8 bits) (23 bits)
Choose the largest floating-point number among the following options.
Sign Exponent Mantissa
0 0111 1111 1111 1111 1111 1111 1111 111
(A)
Sign Exponent Mantissa
0 1111 1110 1111 1111 1111 1111 1111 111
(B)
Sign Exponent Mantissa
0 1111 1111 1111 1111 1111 1111 1111 111
(C)
Sign Exponent Mantissa
(D)
0 0111 1111 0000 0000 0000 0000 0000 000
Page 11 of 40
Organizing Institute: IISc, Bengaluru
Text of page 12
Computer Science and Information Technology Set 2 (CS2)
Q.15 Let T(n) be the recurrence relation defined as follows:
T(0) = 1,
T(1) = 2, and
T(n) = 5T(n − 1) − 6T(n − 2) for n ≥ 2
Which one of the following statements is TRUE?
(A) T(n) = Θ(2n )
(B) T(n) = Θ(n2n )
(C) T(n) = Θ(3n )
(D) T(n) = Θ(n3n )
Q.16 Let f(x) be a continuous function from ℝ to ℝ such that
f(x) = 1 − f(2 − x)
2
Which one of the following options is the CORRECT value of ∫0 f(x)dx ?
(A) 0
(B) 1
(C) 2
(D) −1
Page 12 of 40
Organizing Institute: IISc, Bengaluru
Text of page 13
Computer Science and Information Technology Set 2 (CS2)
Q.17 Let A be the adjacency matrix of a simple undirected graph G. Suppose A is its own
inverse. Which one of the following statements is always TRUE?
(A) G is a cycle
(B) G is a perfect matching
(C) G is a complete graph
(D) There is no such graph G
Q.18 When six unbiased dice are rolled simultaneously, the probability of getting all
distinct numbers (i.e., 1, 2, 3, 4, 5, and 6) is
1
(A)
324
5
(B)
324
7
(C)
324
11
(D)
324
Page 13 of 40
Organizing Institute: IISc, Bengaluru
Text of page 14
Computer Science and Information Technology Set 2 (CS2)
Q.19 Once the DBMS informs the user that a transaction has been successfully
completed, its effect should persist even if the system crashes before all its changes
are reflected on disk. This property is called
(A) durability
(B) atomicity
(C) consistency
(D) isolation
Q.20 In the context of owner and weak entity sets in the ER (Entity-Relationship) data
model, which one of the following statements is TRUE?
(A) The weak entity set MUST have total participation in the identifying relationship
(B) The owner entity set MUST have total participation in the identifying relationship
Both weak and owner entity sets MUST have total participation in the identifying
(C)
relationship
Neither weak entity set nor owner entity set MUST have total participation in the
(D)
identifying relationship
Page 14 of 40
Organizing Institute: IISc, Bengaluru
Text of page 15
Computer Science and Information Technology Set 2 (CS2)
Q.21 Consider the following two sets:
Set X Set Y
P. Lexical Analyzer 1. Abstract Syntax Tree
Q. Syntax Analyzer 2. Token
R. Intermediate Code Generator 3. Parse Tree
S. Code Optimizer 4. Constant Folding
Which one of the following options is the CORRECT match from Set X to Set Y ?
(A) P – 4; Q – 1; R – 3; S – 2
(B) P – 2; Q – 3; R – 1; S – 4
(C) P – 2; Q – 1; R – 3; S – 4
(D) P – 4; Q – 3; R – 2; S – 1
Page 15 of 40
Organizing Institute: IISc, Bengaluru
Text of page 16
Computer Science and Information Technology Set 2 (CS2)
Q.22 Which one of the following regular expressions is equivalent to the language
accepted by the DFA given below?
0
1 0
1
(A) 0∗ 1(0 + 10∗ 1)∗
(B) 0∗ (10∗ 11)∗ 0∗
(C) 0∗ 1(010∗ 1)∗ 0∗
(D) 0(1 + 0∗ 10∗ 1)∗ 0∗
Page 16 of 40
Organizing Institute: IISc, Bengaluru
Text of page 17
Computer Science and Information Technology Set 2 (CS2)
Q.23 Node X has a TCP connection open to node Y. The packets from X to Y go through
an intermediate IP router R. Ethernet switch S is the first switch on the network path
between X and R. Consider a packet sent from X to Y over this connection.
Which of the following statements is/are TRUE about the destination IP and MAC
addresses on this packet at the time it leaves X?
(A) The destination IP address is the IP address of R
(B) The destination IP address is the IP address of Y
(C) The destination MAC address is the MAC address of S
(D) The destination MAC address is the MAC address of Y
Q.24 Which of the following tasks is/are the responsibility/responsibilities of the memory
management unit (MMU) in a system with paging-based memory management?
(A) Allocate a new page table for a newly created process
(B) Translate a virtual address to a physical address using the page table
(C) Raise a trap when a virtual address is not found in the page table
Raise a trap when a process tries to write to a page marked with read-only
(D)
permission in the page table
Page 17 of 40
Organizing Institute: IISc, Bengaluru
Text of page 18
Computer Science and Information Technology Set 2 (CS2)
Q.25 Consider a process P running on a CPU. Which one or more of the following events
will always trigger a context switch by the OS that results in process P moving to a
non-running state (e.g., ready, blocked)?
(A) P makes a blocking system call to read a block of data from the disk
(B) P tries to access a page that is in the swap space, triggering a page fault
(C) An interrupt is raised by the disk to deliver data requested by some other process
(D) A timer interrupt is raised by the hardware
Q.26 Which of the following file organizations is/are I/O efficient for the scan operation
in DBMS?
(A) Sorted
(B) Heap
(C) Unclustered tree index
(D) Unclustered hash index
Page 18 of 40
Organizing Institute: IISc, Bengaluru
Text of page 19
Computer Science and Information Technology Set 2 (CS2)
Q.27 Which of the following statements about the Two Phase Locking (2PL) protocol
is/are TRUE?
(A) 2PL permits only serializable schedules
With 2PL, a transaction always locks the data item being read or written just
(B)
before every operation and always releases the lock just after the operation
With 2PL, once a lock is released on any data item inside a transaction, no more
(C)
locks on any data item can be obtained inside that transaction
(D) A deadlock is possible with 2PL
Q.28 Which of the following statements about IPv4 fragmentation is/are TRUE?
The fragmentation of an IP datagram is performed only at the source of the
(A)
datagram
The fragmentation of an IP datagram is performed at any IP router which finds
(B)
that the size of the datagram to be transmitted exceeds the MTU
(C) The reassembly of fragments is performed only at the destination of the datagram
The reassembly of fragments is performed at all intermediate routers along the
(D)
path from the source to the destination
Page 19 of 40
Organizing Institute: IISc, Bengaluru
Text of page 20
Computer Science and Information Technology Set 2 (CS2)
Q.29 Which of the following statements is/are FALSE?
An attribute grammar is a syntax-directed definition (SDD) in which the functions
(A)
in the semantic rules have no side effects
The attributes in a L-attributed definition cannot always be evaluated in a depth-
(B)
first order
(C) Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed
All L-attributed definitions based on LR(1) grammar can be evaluated using a
(D)
bottom-up parsing strategy
Q.30 For a Boolean variable x, which of the following statements is/are FALSE?
(A) x. 1 = x
(B) x+1=x
(C) x. x = 0
(D) x + x̅ = 1
Page 20 of 40
Organizing Institute: IISc, Bengaluru
Text of page 21
Computer Science and Information Technology Set 2 (CS2)
Q.31 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?
(A) There is a RAW dependency on R3 between I1 and I2
(B) There is a WAR dependency on R3 between I1 and I3
(C) There is a RAW dependency on R3 between I2 and I3
(D) There is a WAW dependency on R3 between I3 and I4
Page 21 of 40
Organizing Institute: IISc, Bengaluru
Text of page 22
Computer Science and Information Technology Set 2 (CS2)
Q.32 Which of the following fields of an IP header is/are always modified by any router
before it forwards the IP packet?
(A) Source IP Address
(B) Protocol
(C) Time to Live (TTL)
(D) Header Checksum
Q.33 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?
(A) The function call fX(”abcd”) will always return a value
Assuming a character array c is declared as char c[] = ”abcd” in main(),
(B)
the function call fX(c)will always return a value
(C) The code of the function will not compile
(D) Assuming a character pointer c is declared as char *c = ”abcd” in main(),
the function call fX(c)will always return a value
Page 22 of 40
Organizing Institute: IISc, Bengaluru
Text of page 23
Computer Science and Information Technology Set 2 (CS2)
Q.34 Let P be the partial order defined on the set {1,2,3,4} as follows
P = {(x, x)|x ∈ {1,2,3,4}} ∪ {(1,2), (3,2), (3,4)}
The number of total orders on {1,2,3,4} that contain P is __________
Q.35 Let Abe 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 ___________
Page 23 of 40
Organizing Institute: IISc, Bengaluru
Text of page 24
Computer Science and Information Technology Set 2 (CS2)
Q.36 – Q.65 Carry TWO marks Each
Q.36 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;}
(A) 4,8
(B) 1,5
(C) 8,5
(D) 1,8
Page 24 of 40
Organizing Institute: IISc, Bengaluru
Text of page 25
Computer Science and Information Technology Set 2 (CS2)
Q.37 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?
(A) SRTF = 6, NP-SJF = 7
(B) SRTF = 6, NP-SJF = 7.5
(C) SRTF = 7, NP-SJF = 7.5
(D) SRTF = 7, NP-SJF = 8.5
Which one of the following CIDR prefixes exactly represents the range of
Q.38
IP addresses 10.12.2.0 to 10.12.3.255?
(A) 10.12.2.0/23
(B) 10.12.2.0/24
(C) 10.12.0.0/22
(D) 10.12.2.0/22
Page 25 of 40
Organizing Institute: IISc, Bengaluru
Text of page 26
Computer Science and Information Technology Set 2 (CS2)
Q.39 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?
(A) Inorder traversal of T can be determined from V
(B) Root node of T can be determined from V
(C) Preorder traversal of T can be determined from V
(D) Postorder traversal of T can be determined from V
Page 26 of 40
Organizing Institute: IISc, Bengaluru
Text of page 28
Computer Science and Information Technology Set 2 (CS2)
Q.41 Let M be the 5-state NFA with ε-transitions shown in the diagram below.
Which one of the following regular expressions represents the language accepted
by M ?
(A) (00)∗ + 1(11)∗
(B) 0∗ + (1 + 0(00)∗ )(11)∗
(C) (00)∗ + (1 + (00)∗ )(11)∗
(D) 0+ + 1(11)∗ + 0(11)∗
Page 28 of 40
Organizing Institute: IISc, Bengaluru
Text of page 29
Computer Science and Information Technology Set 2 (CS2)
Consider an array X that contains n positive integers. A subarray of X is defined to
Q.42 be a sequence of array locations with consecutive indices.
The C code snippet given below has been written to compute the length of the
longest subarray of X that contains at most two distinct integers. The code has two
missing expressions labelled (P)and (Q).
int first=0, second=0, len1=0, len2=0, maxlen=0;
for (int i=0; i < n; i++) {
if (X[i] == first) {
len2++; len1++;
} else if (X[i] == second) {
len2++;
len1 = (P);
second = first;
} else {
len2 = (Q);
len1 = 1; second = first;
}
if (len2 > maxlen) {
maxlen = len2;
}
first = X[i];
}
Which one of the following options gives the CORRECT missing expressions?
(Hint: At the end of the i-th iteration, the value of len1 is the length of the longest
subarray ending with X[i] that contains all equal values, and len2 is the length
of the longest subarray ending with X[i] that contains at most two distinct values.)
(A) (P) len1+1 (Q) len2+1
(B) (P) 1 (Q) len1+1
(C) (P) 1 (Q) len2+1
(D) (P) len2+1 (Q) len1+1
Page 29 of 40
Organizing Institute: IISc, Bengaluru
Text of page 30
Computer Science and Information Technology Set 2 (CS2)
Q.43 Consider the following expression: x[i] = (p + r) ∗ −s[i] + u/w. The following
sequence shows the list of triples representing the given expression, with entries
missing for triples (1), (3), and (6).
(0) + p r
(1)
(2) uminus (1)
(3)
(4) / u w
(5) + (3) (4)
(6)
(7) = (6) (5)
Which one of the following options fills in the missing entries CORRECTLY?
(A) (1) =[]si (3) * (0) (2) (6) []=xi
(B) (1) []=si (3) –(0)(2) (6) =[] x(5)
(C) (1) =[] si (3) * (0)(2) (6) []= x(5)
(D) (1) []= si (3) –(0)(2) (6) =[] xi
Page 30 of 40
Organizing Institute: IISc, Bengaluru
Text of page 31
Computer Science and Information Technology Set 2 (CS2)
Q.44 Let x and y be random variables, not necessarily independent, that take real values
in the interval [0,1]. Let z = xy and let the mean values of x, y, z be x̅ , y̅, z̅,
respectively. Which one of the following statements is TRUE?
(A) z̅ = x̅ y̅
(B) z̅ ≤ x̅ y̅
(C) z̅ ≥ x
̅ y̅
(D)
z̅ ≤ x̅
Q.45 The relation schema, Person(pid,city), describes the city of residence for
every person uniquely identified by pid. The following relational algebra operators
are available: selection, projection, cross product, and rename.
To find the list of cities where at least 3 persons reside, using the above operators,
the minimum number of cross product operations that must be used is
(A) 1
(B) 2
(C) 3
(D) 4
Page 31 of 40
Organizing Institute: IISc, Bengaluru
Text of page 32
Computer Science and Information Technology Set 2 (CS2)
Consider a multi-threaded program with two threads T1 and T2. The threads share
Q.46 two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also
share a global variable x (initialized to 0). The threads execute the code shown
below.
// code of T1 // code of T2
wait(s1); wait(s1);
x = x+1; x = x+1;
print(x); print(x);
wait(s2); signal(s2);
signal(s1); signal(s1);
Which of the following outcomes is/are possible when threads T1 and T2 execute
concurrently?
(A) T1 runs first and prints 1, T2 runs next and prints 2
(B) T2 runs first and prints 1, T1 runs next and prints 2
(C) T1 runs first and prints 1, T2 does not print anything (deadlock)
(D) T2 runs first and prints 1, T1 does not print anything (deadlock)
Let A be an n × n matrix over the set of all real numbers ℝ. Let B be a matrix
Q.47 obtained from A by swapping two rows. Which of the following statements is/are
TRUE?
(A) The determinant of B is the negative of the determinant of A
(B) If A is invertible, then B is also invertible
(C) If Ais symmetric, then B is also symmetric
(D) If the trace of A is zero, then the trace of Bis also zero
Page 32 of 40
Organizing Institute: IISc, Bengaluru
Text of page 33
Computer Science and Information Technology Set 2 (CS2)
Q.48 Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of
2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is
empty, as shown below.
400 (Top)
300
200 Stack S2
100
Stack S1
Only the following three operations are available:
PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the
user.
Note that the pop operation is not allowed on an empty stack and the push operation
is not allowed on a full stack.
Which of the following output sequences can be generated by using the above
operations?
(A) 100, 200, 400, 300
(B) 200, 300, 400, 100
(C) 400, 200, 100, 300
(D) 300, 200, 400, 100
Page 33 of 40
Organizing Institute: IISc, Bengaluru
Text of page 34
Computer Science and Information Technology Set 2 (CS2)
Q.49 Which of the following is/are EQUAL to 224 in radix-5 (i.e., base-5) notation?
(A) 64 in radix-10
(B) 100 in radix-8
(C) 50 in radix-16
(D) 121 in radix-7
Page 34 of 40
Organizing Institute: IISc, Bengaluru
Text of page 35
Computer Science and Information Technology Set 2 (CS2)
Q.50 Consider 4-variable functions f1, f2, f3, f4 expressed in sum-of-minterms form as
given below.
f1 = ∑(0,2,3,5,7,8,11,13)
f2 = ∑(1,3,5,7,11,13, 15)
f3 = ∑(0,1,4,11)
f4 = ∑(0,2,6,13)
With respect to the circuit given above, which of the following options is/are
CORRECT?
(A) Y = ∑(0,1,2,11,13)
(B) Y = Π(3,4, 5,6,7,8,9,10,12,14,15)
(C) Y = ∑(0,1,2,3,4,5,6,7)
(D) Y = Π(8,9,10,11,12,13,14,15)
Page 35 of 40
Organizing Institute: IISc, Bengaluru
Text of page 36
Computer Science and Information Technology Set 2 (CS2)
Q.51 Let G be an undirected connected graph in which every edge has a positive integer
weight. Suppose that every spanning tree in G has even weight. Which of the
following statements is/are TRUE for every such graph G ?
(A) All edges in G have even weight
(B) All edges in G have even weight OR all edges in G have odd weight
(C) In each cycle C in G, all edges in C have even weight
In each cycle C in G, either all edges in C have even weight OR all edges in C
(D)
have odd weight
Q.52 Consider a context-free grammar G with the following 3 rules.
S → aS, S → aSbS, S → c
Let w ∈ L(G). Let na (w), nb (w), nc (w)denote the number of times a, b, c
occur in w, respectively. Which of the following statements is/are TRUE?
(A) na (w) > nb (w)
(B) na (w) > nc (w) − 2
(C) nc (w) = nb (w) + 1
(D) nc (w) = nb (w) ∗ 2
Page 36 of 40
Organizing Institute: IISc, Bengaluru
Text of page 37
Computer Science and Information Technology Set 2 (CS2)
Q.53 Consider a disk with the following specifications: rotation speed of 6000 RPM,
average seek time of 5 milliseconds, 500 sectors/track, 512-byte sectors.
A file has content stored in 3000 sectors located randomly on the disk. Assuming
average rotational latency, the total time (in seconds, rounded off to 2 decimal
places) to read the entire file from the disk is _________
Q.54 Consider a TCP connection operating at a point of time with the congestion window
of size 12 MSS (Maximum Segment Size), when a timeout occurs due to packet
loss. Assuming that all the segments transmitted in the next two RTTs (Round Trip
Time) are acknowledged correctly, the congestion window size (in MSS) during the
third RTT will be _________
Q.55 Consider an Ethernet segment with a transmission speed of 108 bits/sec and a
maximum segment length of 500 meters. If the speed of propagation of the signal
in the medium is 2×108 meters/sec, then the minimum frame size (in bits) required
for collision detection is _________
Q.56 A functional dependency F:X → Y is termed as a useful functional dependency if
and only if it satisfies all the following three conditions:
• X is not the empty set.
• Y is not the empty set.
• Intersection of X and Y is the empty set.
For a relation R with 4 attributes, the total number of possible useful functional
dependencies is ________
Q.57 A processor with 16 general purpose registers uses a 32-bit instruction format. The
instruction format consists of an opcode field, an addressing mode field, two register
operand fields, and a 16-bit scalar field. If 8 addressing modes are to be supported,
the maximum number of unique opcodes possible for every addressing mode
is _________
Page 37 of 40
Organizing Institute: IISc, Bengaluru
Text of page 38
Computer Science and Information Technology Set 2 (CS2)
Q.58 A non-pipelined instruction execution unit operating at 2 GHz takes an average of
6 cycles to execute an instruction of a program P. The unit is then redesigned to
operate on a 5-stage pipeline at 2 GHz. Assume that the ideal throughput of the
pipelined unit is 1 instruction per cycle. In the execution of program P,
20% instructions incur an average of 2 cycles stall due to data hazards and
20% instructions incur an average of 3 cycles stall due to control hazards. The
speedup (rounded off to one decimal place) obtained by the pipelined design over
the non-pipelined design is _________
Q.59 The number of distinct minimum-weight spanning trees of the following graph
is _________
3
b c
1 2 2 1
2 2
a g d
2 2
1 1
f e
3
Q.60 The chromatic number of a graph is the minimum number of colours used in a
proper colouring of the graph. The chromatic number of the following graph
is _________
Page 38 of 40
Organizing Institute: IISc, Bengaluru
Text of page 39
Computer Science and Information Technology Set 2 (CS2)
Q.61 A processor uses a 32-bit instruction format and supports byte-addressable memory
access. The ISA of the processor has 150 distinct instructions. The instructions are
equally divided into two types, namely R-type and I-type, whose formats are shown
below.
R-type Instruction Format:
OPCODE UNUSED DST Register SRC Register1 SRC Register 2
I-type Instruction Format:
OPCODE DST Register SRC Register # Immediate value/address
In the OPCODE, 1 bit is used to distinguish between I-type and R-type instructions
and the remaining bits indicate the operation. The processor has 50 architectural
registers, and all register fields in the instructions are of equal size.
Let X be the number of bits used to encode the UNUSED field, Y be the number
of bits used to encode the OPCODE field, and Z be the number of bits used to
encode the immediate value/address field. The value of X + 2Y + Z is ________
Let L1 be the language represented by the regular expression b ∗ ab ∗ (ab ∗ ab ∗ )∗
Q.62
and L2 = {w ∈ (a + b)∗ ||w| ≤ 4}, where |w| denotes the length of string
w . The number of strings in L2 which are also in L1 is ___________
Q.63 Let Zn be the group of integers {0, 1, 2, … , n − 1} with addition modulo n as the
group operation. The number of elements in the group Z2 × Z3 × Z4 that are their
own inverses is ________
Page 39 of 40
Organizing Institute: IISc, Bengaluru
Text of page 40
Computer Science and Information Technology Set 2 (CS2)
Q.64 Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes
each. Assume 1 KB = 210 bytes. The OS uses a 2-level page table for memory
management, with the page table containing an outer page directory and an inner
page table. The OS allocates a page for the outer page directory upon process
creation. The OS uses demand paging when allocating memory for the inner page
table, i.e., a page of the inner page table is allocated only if it contains at least one
valid page table entry.
An active process in this system accesses 2000 unique pages during its execution,
and none of the pages are swapped out to disk. After it completes the page accesses,
let X denote the minimum and Y denote the maximum number of pages across the
two levels of the page table of the process.
The value of X+Y is ________
Q.65 Consider the following augmented grammar, which is to be parsed with a SLR
parser. The set of terminals is {a,b,c,d,#,@}
S′ → S
S → SS|Aa|bAc|Bc|bBa
A → d#
B→@
Let I0 = CLOSURE({S ′ →• S}). The number of items in the set GOTO(I0 , S)
is ___________
Page 40 of 40
Organizing Institute: IISc, Bengaluru
Text of page 1
Computer Science & Information Technology (CS2)
Final Answer Key
Question
Q. No. Session Section Key/Range Mark
Type
1 6 MCQ GA C 1
2 6 MCQ GA A 1
3 6 MCQ GA A 1
4 6 MCQ GA C 1
5 6 MCQ GA B 1
6 6 MCQ GA C 2
7 6 MCQ GA C 2
8 6 MCQ GA D 2
9 6 MCQ GA A 2
10 6 MCQ GA A 2
11 6 MCQ CS-2 C 1
12 6 MCQ CS-2 A 1
13 6 MCQ CS-2 A 1
14 6 MCQ CS-2 B 1
15 6 MCQ CS-2 A 1
16 6 MCQ CS-2 B 1
17 6 MCQ CS-2 B 1
18 6 MCQ CS-2 B 1
19 6 MCQ CS-2 A 1
20 6 MCQ CS-2 A 1
21 6 MCQ CS-2 B 1
22 6 MCQ CS-2 A 1
23 6 MSQ CS-2 B 1
24 6 MSQ CS-2 B;C;D 1
25 6 MSQ CS-2 A;B 1
26 6 MSQ CS-2 A;B 1
27 6 MSQ CS-2 A;C;D 1
28 6 MSQ CS-2 B;C 1
29 6 MSQ CS-2 B;D 1
Page 1 of 2
Text of page 2
30 6 MSQ CS-2 B;C 1
31 6 MSQ CS-2 A 1
32 6 MSQ CS-2 C;D 1
33 6 MSQ CS-2 A;B;D 1
34 6 NAT CS-2 5 to 5 1
35 6 NAT CS-2 3 to 3 1
36 6 MCQ CS-2 B 2
37 6 MCQ CS-2 B 2
38 6 MCQ CS-2 A 2
39 6 MCQ CS-2 A 2
40 6 MCQ CS-2 A 2
41 6 MCQ CS-2 B 2
42 6 MCQ CS-2 B 2
43 6 MCQ CS-2 A 2
44 6 MCQ CS-2 D 2
45 6 MCQ CS-2 B 2
46 6 MSQ CS-2 B;C 2
47 6 MSQ CS-2 A;B 2
48 6 MSQ CS-2 B;C;D 2
49 6 MSQ CS-2 A;B;D 2
50 6 MSQ CS-2 C;D 2
51 6 MSQ CS-2 D 2
52 6 MSQ CS-2 B;C 2
53 6 NAT CS-2 29.50 to 30.50 2
54 6 NAT CS-2 4 to 4 2
55 6 NAT CS-2 500 to 500 2
56 6 NAT CS-2 50 to 50 2
57 6 NAT CS-2 32 to 32 2
58 6 NAT CS-2 2.9 to 3.1 2
59 6 NAT CS-2 9 to 9 2
60 6 NAT CS-2 2 to 2 2
61 6 NAT CS-2 34 to 34 2
62 6 NAT CS-2 15 to 15 2
63 6 NAT CS-2 4 to 4 2
64 6 NAT CS-2 1028 to 1028 2
65 6 NAT CS-2 9 to 9 2
Page 2 of 2
Page 1 of 40
Source: GATE. Question paper published by GATE.