GATE 2026 Question Paper Computer Science and Information Technology (CS-1)

FOR GATE EXAM PREPARATION

GATE 2026
Question Paper ·
Computer Science
Information
Technology (CS 1)
EXAM YEAR TYPE

GATE 2026 Question Paper
SUBJECT

Computer Science Information Technology (CS 1)

Notes · Sample Papers · Previous Year Papers · Mock Tests

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
General Aptitude (GA)
Q.1 – Q.5 Carry ONE mark Each

Q.1 The antonym of the word protagonist is ________.

m
c o m m .co
agnosticm
. s e
(A)
s e l a
l a ag
(B) agantagonist

(C) arsonist

(D) anarchist

m
m .co
s e
g la
a

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 1 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 1 of 46

Computer Science & Information Technology (CS1)

Q.2 The figure shows two 4-tile patterns.

Either one or both of the patterns can be used any number of times and in any
orientation to construct a new pattern. Which one of the options below cannot be
constructed by using only these two 4-tile patterns assuming there are no overlaps
among them?

(A)

(B)

(C)

(D)

Organizing Institute: IIT Guwahati Page 2 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 2 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.3 Consider a knock-out women’s badminton singles tournament where there are no
ties. The loser in each game is eliminated from the tournament. Every player
plays until she is defeated or remains the last undefeated player. The last
undefeated player is declared the winner of the tournament. If there are 64 players
in the beginning of the tournament, how many games should be played in total to

m
declare the winner of the tournament?

m .co
m .co s e m
s e l a
(A)
g l
127a ag
a
(B) 64

(C) 63

(D) 32
m
m .co
s e
g la
a

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 3 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 3 of 46

Computer Science & Information Technology (CS1)

Q.4 A student needs to enroll for a minimum of 60 credits. A student cannot enroll for
more than 70 credits. The credits are divided amongst project and three distinct
sets of courses namely, core courses, specialization courses, and elective courses.
It is compulsory for a student to enroll for exactly 15 credits of core courses and
exactly 20 credits of project. In addition, a student has to enroll for a minimum of
10 credits of specialization courses. The maximum credits of elective courses that
a student can enroll for is ______

(A) 10

(B) 15

(C) 20

(D) 25

Q.5 ‘When the teacher is in the room, all students stand silently.’

If the above statement is true, which one of the following statements is not
necessarily true?

(A) If any student is not standing silently, then the teacher is not in the room.

(B) When the teacher is in the room, all students are silent.

(C) If all students are standing, then the teacher is in the room.

(D) When the teacher is in the room, all students are standing.

Organizing Institute: IIT Guwahati Page 4 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 4 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.6 – Q.10 Carry TWO marks Each

Q.6 Combinatorics deals with problems involving counting. For example, “How many
distinct arrangements of N distinct objects in M spaces on a circle are possible?”
is a typical problem in combinatorics. This kind of counting is sometimes used in
the modeling of several physical phenomena. Often, in such models, the different
m
.co
combinatorial possibilities are assigned probability values. Assigning probabilities

o m
enables the computation of the average values of physical quantities.
m
. c s e
em a
Consider the following statements:
s
Combinatorics is always invoked in the modeling of physical phenomena. ag
P:la
l
agQ: Modeling some physical phenomena involves assigning probabilities to
combinatorial possibilities in order to compute average values of physical
quantities.

Based on the passage above, what can be inferred about statements P and Q?

m
m .co
e
(A) P is False and Q is False

las
(B) P is False and Q is True
ag
(C) P is True and Q is False

(D) P is True and Q is True

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 5 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 5 of 46

Computer Science & Information Technology (CS1)

Q.7 In Panel I of the figure below, the front view and top view of a structure are
shown. Which one of the 3D structures shown in Panel II possesses the views
shown in Panel I?

(A) (i)

(B) (ii)

(C) (iii)

(D) (iv)

Organizing Institute: IIT Guwahati Page 6 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 6 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.8 For positive real numbers 𝑆 and 𝐾, the function 𝐻𝐾 (𝑆) is defined as:
𝐻𝐾 (𝑆) = max(𝑆 − 𝐾, 0). The max function is defined as:

𝑎, when 𝑎 > 𝑏
max(𝑎, 𝑏) = {
𝑏, when 𝑎 ≤ 𝑏

m
.co
The graph below shows the plot of a function 𝑁(𝑆) versus 𝑆.
m
.co
𝑁(𝑆) can be expressed as _____.
m s e m
s e l a
g l a ag
a

m
m .co
s e
g la
a
(A) 𝐻10 (𝑆) − 𝐻20 (𝑆)

(B) 𝐻10 (𝑆) − 2𝐻20 (𝑆)

(C) −𝐻10 (𝑆) + 𝐻20 (𝑆)
m
m
c. o(D) m.co
m 𝐻15 (𝑆) − 𝐻20 (𝑆)
s e
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 7 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 7 of 46

Computer Science & Information Technology (CS1)

Q.9 In the 2020 summer Olympics’ Javelin throw finals, Neeraj Chopra exhibited a
spectacular performance to win the gold medal. The silver medal was won by
Jakub Vadlejch and the bronze medal was won by Vitezlav Vesely. There were
six rounds of throws with each athlete having one throw per round. The best of
all the throws of each athlete is considered for the medal. Following were the
observations about the throws:

i. The first and second rounds were dominated by Neeraj Chopra with a gold
medal performance in his second throw, while the other two athletes did
not have any medal winning throws in these rounds.

ii. The throws in the last round by both Jakub Vadlejch and Vitezlav Vesely
were fouls and were not considered for scoring.

iii. After four rounds, Vitezlav Vesely was in the second position and could
not improve upon his best throw in the succeeding rounds.

iv. In the fourth round, the throw by Jakub Vadlejch was the best in that
round.

In which round did Vitezlav Vesely have his best throw?

(A) Third

(B) Fourth

(C) Fifth

(D) Sixth

Organizing Institute: IIT Guwahati Page 8 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 8 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.10 An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5,
and 6 is rolled twice in succession and the number on the top face is recorded
each time. The probability that the number appearing in the second roll is an
integer multiple of the number appearing in the first roll is __________

m
m .co
1
m .co s e m
(A)
s e l a
a ag
6
g l
(B)
a5
18

(C) 7
18

5
m
.co
(D)
6
e m
las
ag

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 9 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 9 of 46

Computer Science & Information Technology (CS1)

Q.11 – Q.35 Carry ONE mark Each

Q.11 An urn contains one red ball and one blue ball. At each step, a ball is picked
uniformly at random from the urn, and this ball together with another ball of the
same color is put back in the urn. The probability that there are equal number of red
and blue balls after two steps is

(A) 1/4

(B) 1/3

(C) 1/2

(D) 2/3

Q.12 Consider 4 × 4 matrices with their elements from {𝟎, 𝟏}. The number of such
matrices with even number of 𝟏s in every row and every column is

(A) 512

(B) 1025

(C) 1023

(D) 255

Organizing Institute: IIT Guwahati Page 10 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 10 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.13 For 𝑛 > 1, the maximum multiplicity of any eigenvalue of an 𝑛 × 𝑛 matrix with
elements from ℝ is

m
𝑛
m .co
.co
(A)

e m
e m l as
(B)
l as 𝑛−1
ag
g
(C) a 1

(D) 𝑛+1

m
.co
Q.14 Match each addressing mode in List I with a data element or an element of a data
structure (in a high-level language) in List II:
e m
las
g
List I List II
P. Immediate
Q. Indirect
a 1. Element of an array
2. Pointer
R. Base with index 3. Element of a record
S. Base with offset/displacement 4. Constant

m
.co
(A) P–4, Q–3, R–1, S–2
m
c. o(B) s e m
e m P–4, Q–2, R–1, S–3
l a
las ag
ag (C) P–1, Q–4, R–3, S–2

(D) P–2, Q–3, R–1, S–4

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 11 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 11 of 46

Computer Science & Information Technology (CS1)

Q.15 Consider a processor P whose instruction set architecture is the load-store
architecture. The instruction format is such that the first operand of any instruction
is the destination operand.

Which one of the following sequences of instructions corresponds to the high-level
language statement Z = X + Y ?

Note: X, Y, and Z are memory operands. R0, R1, and R2 are registers.

(A) ADD Z, X, Y

(B) LOAD R0, X
ADD Z, R0, Y

(C) ADD R0, X, Y
STORE Z, R0

(D) LOAD R0, X
LOAD R1, Y
ADD R2, R0, R1
STORE Z, R2

Organizing Institute: IIT Guwahati Page 12 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 12 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.16 Which one of the following dependencies among the register operands of different
instructions can cause a data hazard in a pipelined processor?

m
(A) Read-after-read
m .co
.co s e m
s em l a
ag
(B) Read-after-write

g la
(C) a Write-after-read

(D) Write-after-write

m
m .co
s e
g la
a

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 13 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 13 of 46

Computer Science & Information Technology (CS1)

Q.17 Consider the following recurrence relations:

For all 𝑛 > 1,
𝑛
𝑇1 (𝑛) = 4𝑇1 ( ) + 𝑇2 (𝑛)
2
𝑛
𝑇2 (𝑛) = 5𝑇2 ( ) + Θ(log2 𝑛)
4
Assume that for all 𝑛 ≤ 1, 𝑇1 (𝑛) = 1 and 𝑇2 (𝑛) = 1.

Which one of the following options is correct?

(A) 𝑇1 (𝑛) = Θ(𝑛2 )

(B) 𝑇1 (𝑛) = Θ(𝑛2 log2 𝑛)

(C) 𝑇1 (𝑛) = Θ(𝑛log4 5 )

(D) 𝑇1 (𝑛) = Θ(𝑛log4 5 log2 𝑛)

Organizing Institute: IIT Guwahati Page 14 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 14 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.18 With respect to a TCP connection between a client and a server, which one of the
following statements is true?

m
(A)
m
The client and server use a two-way handshake mechanism before the start of data
.co
transmission
m .co s e m
s e g l a
l a a
agclosing of the connection
(B) The server cannot initiate closing of the connection before the client initiates

(C) The TCP connection is half-duplex

(D) The client and server can initiate closing of the connection at the same time

m
m .co
Q.19
s e
Which of the following statements is/are true with respect to the interaction of a

g la
web browser with a web server using HTTP 1.1?
a

(A) HTTP 1.1 facilitates downloading multiple objects of the same webpage over the
same TCP connection, if the objects are stored in the same server

m
.co
(B) HTTP 1.1 facilitates downloading multiple objects of the same webpage over the
m
.co em
same TCP connection, even if they are stored in different servers

e m s
a without waiting
HTTP 1.1 facilitates sending a request for downloading one lobject
las (C)
a g
g
for a previously requested object to be downloaded completely
a
(D) HTTP 1.1 facilitates downloading multiple webpages on the same server to be
downloaded over a single TCP connection

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 15 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 15 of 46

Computer Science & Information Technology (CS1)

Q.20 Let 𝑛 > 1. Consider an 𝑛 × 𝑛 matrix 𝑀 with its elements from ℝ. Let the vector
(0, 1, 0, 0, … , 0) ∈ ℝ𝑛 be in the null space of 𝑀.

Which of the following options is/are always correct?

(A) Determinant of 𝑀 is 1

(B) Determinant of 𝑀 is 0

(C) Rank of 𝑀 is 1

(D) There are at least two non-zero vectors in the null space of 𝑀

Q.21 Consider the following Boolean expression of a function F :

𝐹(𝑃, 𝑄) = (𝑃̅ + 𝑄) ⊕ (𝑃̅𝑄)

Which of the following expressions is/are equivalent to F ?

(A) ̅̅̅̅̅̅̅̅
𝑃⊕𝑄

(B) 𝑃⊕𝑄

(C) 𝑃̅ ⊕ 𝑄

(D) 𝑃̅ ⊕ 𝑄̅

Organizing Institute: IIT Guwahati Page 16 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 16 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.22 Consider the 8-bit signed integers 𝑋, 𝑌 and 𝑍 represented using the sign-magnitude
form. The binary representations of 𝑋 and 𝑌 are as follows:

𝑋: 10110100 𝑌: 01001100

Which of the following operations to compute 𝑍 result(s) in an arithmetic
m
.co
overflow?
m
.co s e m
s em l a
g la= 𝑋 + 𝑌 ag
(A)
a 𝑍

(B) 𝑍 =𝑋−𝑌

(C) 𝑍 = −𝑋 + 𝑌

𝑍 = −𝑋 − 𝑌
m
.co
(D)

e m
las
ag

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 17 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 17 of 46

Computer Science & Information Technology (CS1)

Q.23 Let 𝑛 be an odd number greater than 100. Consider a binary minheap with
𝑛 elements stored in an array 𝑃 whose index starts from 1.

Which of the following indices of 𝑃 do/does NOT correspond to any leaf node of
the minheap?

(A) 𝑛+1
2

(B) 𝑛−1
2

(C) 𝑛−3
2

(D) 𝑛

Organizing Institute: IIT Guwahati Page 18 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 18 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.24 Consider a hash table 𝑃[0, 1, … , 10] that is initially empty. The hash table is
maintained using open addressing with linear probing. The hash function used is
ℎ(𝑥) = (𝑥 + 7) mod 11.

Consider the following sequence of insertions performed on 𝑃:

m
.co
1, 13, 22, 15, 11, 24
m
.co
Which of the following positions in the hash table is/are empty after these insertions
m s e m
e
are performed?
s l a
g l a ag
a
(A) 0

(B) 10

2 m
.co
(C)

e m
(D) 1
las
ag

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 19 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 19 of 46

Computer Science & Information Technology (CS1)

Q.25 Consider the following grammar where 𝑆 is the start symbol, and 𝑎 and 𝑏 are
terminal symbols.

𝑆 → 𝑎𝑆𝑏𝑆 ∣ 𝑏𝑆 ∣ ϵ

Which of the following statements is/are true?

(A) The grammar is ambiguous

(B) The string 𝑎𝑏𝑏 has two distinct derivations in this grammar

(C) The string 𝑎𝑏𝑎𝑏 has only one rightmost derivation

(D) The language generated by the grammar is undecidable

Q.26 Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite
alphabet.

Which of the following options CANNOT be the number of states in the minimal
deterministic finite automaton (DFA) that is equivalent to 𝑀 ?

(A) 32

(B) 65

(C) 1

(D) 128

Organizing Institute: IIT Guwahati Page 20 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 20 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.27 Consider the following C statements:

char *str1 = "Hello; /* Statement S1 */
char *str2 = "Hello;"; /* Statement S2 */
int *str3 = "Hello"; /* Statement S3 */

m
.co
Which of the following options is/are correct?
m
.co s e m
s em l a
g la ag
(A)
a S1 and S2 have syntactic errors

(B) S2 has a lexical error and S3 has a syntactic error

(C) S1 has a lexical error and S3 has a semantic error

m
.co
(D) S1 has a syntactic error and S3 has a semantic error

s em
g la
Q.28
a
Which of the following statements is/are true?

(A) LL(1) parser uses backtracking

m
m
(B) For a grammar to be LL(1), it must be left-recursive
.co
m .co s e m
s e (C) For a grammar to be LL(1), it must be left-factored
g l a
g la a
a (D) The LL(1) parsers are more powerful than the SLR parsers

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 21 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 21 of 46

Computer Science & Information Technology (CS1)

Q.29 With respect to deadlocks in an operating system, which of the following
statements is/are FALSE?

(A) Banker’s algorithm is used to prevent deadlocks

(B) Deadlock formation can be prevented by ensuring that the hold and wait
condition is not allowed

(C) An assignment edge in a resource allocation graph is marked from a process to a
resource

(D) A safe state guarantees that all processes can finish without formation of a
deadlock

Q.30 Let 𝑃, 𝑄, 𝑅 and 𝑆 be the attributes of a relation in a relational schema. Let 𝑋 ⟶ 𝑌
indicate functional dependency in the context of a relational database, where
𝑋, 𝑌 ⊆ {𝑃, 𝑄, 𝑅, 𝑆}.

Which of the following options is/are always true?

(A) If ( {𝑃, 𝑄} ⟶ {𝑅} and {𝑃} ⟶ {𝑅} ), then {𝑄} ⟶ {𝑅}

(B) If {𝑃, 𝑄} ⟶ {𝑅}, then ( {𝑃} ⟶ {𝑅} or {𝑄} ⟶ {𝑅} )

(C) If ( {𝑃} ⟶ {𝑅} and {𝑄} ⟶ {𝑆} ), then {𝑃, 𝑄} ⟶ {𝑅, 𝑆}

(D) If {𝑃} ⟶ {𝑅}, then {𝑃, 𝑄} ⟶ {𝑅}

Organizing Institute: IIT Guwahati Page 22 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 22 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
In the context of relational database normalization, which of the following
Q.31
statements is/are true?

m
It is always possible to obtain a dependency-preserving 3NF decomposition of a

.co
(A)
relation
m
.co s e
It is always possible to obtain a dependency-preserving 1NF decomposition of a m
em a
(B)
s
relation
g l
Itla a
agof a relation
is not always possible to obtain a dependency-preserving BCNF decomposition
(C)

It is not always possible to obtain a dependency-preserving 2NF decomposition of
(D)
a relation

m
m .co
s e
g la
a

Q.32 Consider the function 𝑓: ℝ → ℝ defined as follows:

1
m
.co
𝑥
𝑓(𝑥) = {𝑐 𝑒 − 𝑐 log ( ) , if 𝑥 > 0
m
1 2 e
𝑥

m .co 3
em
otherwise
s
s e where 𝑐 , 𝑐 ∈ ℝ.
g la
la
1 2

g a
a If 𝑓 is continuous at 𝑥 = 0, then 𝑐 + 𝑐 = _________. (answer in integer)
1 2

Q.33 The height of a binary tree is the number of edges in the longest path from the root
to a leaf in the tree. The maximum possible height of a full binary tree with
23 nodes is _________. (answer in integer)

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 23 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 23 of 46

Computer Science & Information Technology (CS1)

Q.34 Consider the following program in C:

#include <stdio.h>

void func(int i, int j) {
if(i < j) {
int i = 0;
while (i < 10) {
j += 2;
i++;
}
}
printf("%d", i);
}

int main() {
int i = 9, j = 10;
func(i, j);
return 0;
}

The output of the program is _________. (answer in integer)

Note: Assume that the program compiles and runs successfully.

Q.35 Consider a system consisting of 𝑘 instances of a resource 𝑅, being shared by
5 processes. Assume that each process requires a maximum of two instances of
resource 𝑅 and a process can request or release only one instance at a time. Further,
a process can request the second instance of the resource only after acquiring the
first instance.

The minimum value of 𝑘 for the system to be deadlock-free is ________. (answer
in integer)

Organizing Institute: IIT Guwahati Page 24 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 24 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l

Q.36 – Q.65 Carry TWO marks Each

m
Q.36 Consider the real valued variables X, Y and Z represented using the IEEE 754 single-

.co
precision floating-point format. The binary representations of X and Y in hexadecimal
m
.co m
notation are as follows:

s e
s em X: 35C00000 Y: 34A00000
l a
Letla
g 𝑍 = 𝑋 + 𝑌. ag
aWhich one of the following is the binary representation of 𝑍, in hexadecimal
notation?

m
(A) 35C80000

m .co
(B) 35CC0000
s e
g la
(C) 35E80000 a
(D) 35EC0000

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 25 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 25 of 46

Computer Science & Information Technology (CS1)

Q.37 Consider a 2-bit saturating up/down counter that performs the saturating up count
when the input P is 0, and the saturating down count when P is 1. The Next State
table of the counter is as shown. The counter is built as a synchronous sequential
circuit using D flip-flops.

Input Current Next
State State
𝑃 𝑄1 𝑄0 𝑄1+ 𝑄0+
0 0 0 0 1
0 0 1 1 0
0 1 0 1 1
0 1 1 1 1
1 0 0 0 0
1 0 1 0 0
1 1 0 0 1
1 1 1 1 0

Which one of the following options corresponds to the expressions for the inputs of
the D flip-flops, 𝐷1 and 𝐷0 ?

(A) 𝐷1 = 𝑃 𝑄1 + 𝑃̅𝑄0 + 𝑄1 𝑄0 𝐷0 = 𝑃 𝑄0 + 𝑃̅ 𝑄1 + 𝑄1 ̅̅̅
𝑄0

(B) 𝐷1 = 𝑃̅ 𝑄1 + 𝑃̅𝑄0 + 𝑄1 𝑄0 𝐷0 = 𝑃̅ ̅̅̅
𝑄0 + 𝑃̅ 𝑄1 + 𝑄1 ̅̅̅
𝑄0

(C) ̅̅̅1 + 𝑃̅ 𝑄0 + 𝑄1 𝑄0
𝐷1 = 𝑃̅ 𝑄 𝐷0 = 𝑃̅ 𝑄0 + 𝑃̅ 𝑄1 + 𝑄1 ̅̅̅
𝑄0

(D) ̅̅̅1 + 𝑃̅ 𝑄0 + 𝑄1 𝑄0
𝐷1 = 𝑃 𝑄 𝐷0 = 𝑃 ̅̅̅
𝑄0 + 𝑃̅ 𝑄1 + 𝑄1 ̅̅̅
𝑄0

Organizing Institute: IIT Guwahati Page 26 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 26 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.38 The size of the physical address space of a processor is 232 bytes. The capacity of a
cache memory unit is 223 bytes. The cache block size is 128 bytes. The cache
memory unit can be built as a direct mapped cache or as a 𝐾-way set-associative
cache, where 𝐾 = 2𝐿 and 𝐿 ∈ {1, 2, 3}. Let the length of the TAG field be 𝑀 bits
for the direct mapped cache, and 𝑁 bits for the set-associative cache.

m
.co
Which one of the following options is true?
m
.co s e m
s em l a
g l a
(A) a𝑁 = 𝑀 + 𝐿
ag

(B) 𝑁 =𝑀−𝐿

(C) 𝑁 =𝑀+𝐾

m
.co
(D) 𝑁 =𝑀−𝐾

e m
las
ag

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 27 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 27 of 46

Computer Science & Information Technology (CS1)

Q.39 Consider the following code snippet in C language that computes the number of
nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
int elt;
struct node *next;
};

int getListSize (struct node *head)
{
if( E1 ) return 1;
return E2;
}

Which one of the following options gives the correct replacements for the
expressions E1 and E2?

(A) E1: head == NULL
E2: 1 + getListSize(head)

(B) E1: head->next == NULL
E2: 1 + getListSize(head->next)

(C) E1: head == NULL
E2: 1 + getListSize(head->next)

(D) E1: head->next == NULL
E2: 1 + getListSize(head)

Organizing Institute: IIT Guwahati Page 28 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 28 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.40 Let 𝑃 be the set of all integers from 1 to 15. Consider any order of insertion of the
elements of 𝑃 into a binary search tree that creates a complete binary tree.

Which one of the following elements can NEVER be the third element that is
inserted?

m
m .co
m .co s e m
s e l a
a ag
(A) 4

g l
(B) a2

(C) 10

(D) 5

m
m .co
s e
g la
a

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 29 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 29 of 46

Computer Science & Information Technology (CS1)

Q.41 Let 𝐺(𝑉, 𝐸) be an undirected, edge-weighted graph with integer weights. The weight
of a path is the sum of the weights of the edges in that path. The length of a path is
the number of edges in that path.

Let 𝑠 ∈ 𝑉 be a vertex in 𝐺. For every 𝑢 ∈ 𝑉 and for every 𝑘 ≥ 0, let 𝑑𝑘 (𝑢) denote
the weight of a shortest path (in terms of weight) from 𝑠 to 𝑢 of length at most 𝑘. If
there is no path from 𝑠 to 𝑢 of length at most 𝑘, then 𝑑𝑘 (𝑢) = ∞.

Consider the statements:

S1: For every 𝑘 ≥ 0 and 𝑢 ∈ 𝑉, 𝑑𝑘+1 (𝑢) ≤ 𝑑𝑘 (𝑢).

S2: For every (𝑢, 𝑣) ∈ 𝐸, if (𝑢, 𝑣) is part of a shortest path (in terms of
weight) from 𝑠 to 𝑣, then for every 𝑘 ≥ 0, 𝑑𝑘 (𝑢) ≤ 𝑑𝑘 (𝑣).

Which one of the following options is correct?

(A) Only S1 is true

(B) Only S2 is true

(C) Both S1 and S2 are true

(D) Neither S1 nor S2 is true

Organizing Institute: IIT Guwahati Page 30 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 30 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.42 Consider the control flow graph shown in the figure.

m
m .co
m .co s e m
s e l a
g l a ag
a

o m
c
. lists the set of redundant expressions
m
Which one of the following options correctly
e
(common subexpressions) in the basic
la s blocks B4 and B5?

a g
Note: All the variables are integers.

(A) B4: { 𝑏 + 𝑖 }
B5: { 𝑐 + 𝑚 }

m
.co
B4: { 𝑔 ∗ 𝑘 }
m
(B)

.co m
B5: { 𝑐 + 𝑚 }

m s e
s e g l a
g la (C) B4: { 𝑔 ∗ 𝑘, 𝑏 + 𝑖 }
a
a B5: { }

(D) B4: { 𝑔 ∗ 𝑘 }
B5: { }

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 31 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 31 of 46

Computer Science & Information Technology (CS1)

Q.43 Consider a relational database schema with two relations 𝑅(𝑃, 𝑄) and 𝑆(𝑋, 𝑌).

Let 𝐸 = {⟨𝑢⟩ ∣ ∃𝑣 ∃𝑤 ⟨𝑢, 𝑣⟩ ∈ 𝑅 ∧ ⟨𝑣, 𝑤⟩ ∈ 𝑆} be a tuple relational calculus
expression.

Which one of the following relational algebraic expressions is equivalent to 𝐸 ?

(A) 𝛱𝑃 (𝑅 ⋈𝑅.𝑃=𝑆.𝑋 𝑆)

(B) 𝛱𝑃 (𝑆 ⋈𝑆.𝑋=𝑅.𝑄 𝑅)

(C) 𝛱𝑃 (𝑅 ⋈𝑅.𝑃=𝑆.𝑌 𝑆)

(D) 𝛱𝑃 (𝑆 ⋈𝑆.𝑌=𝑅.𝑄 𝑅)

Organizing Institute: IIT Guwahati Page 32 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 32 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.44 A TCP sender successfully establishes a connection with a TCP receiver and starts
the transmission of segments. The TCP congestion control mechanism’s slow-start
threshold is set to 10000 segments. Assume that the round-trip time is fixed at
1 millisecond. Assume that the sender always has data to send, the segments are
numbered from 1, and no segment is lost. Let 𝑡 denote the time (in milliseconds) at

m
which the transmission of segment number 2000 starts.

m .co
.co
Which one of the following options is correct?
e m
em l as
las ag
g
a 9 ≤ 𝑡 < 10
(A)

(B) 10 ≤ 𝑡 < 11

(C) 11 ≤ 𝑡 < 12

m
(D) 12 ≤ 𝑡 < 13
m .co
s e
g la
a

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 33 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 33 of 46

Computer Science & Information Technology (CS1)

Q.45 Consider the implementation of sliding window protocol over a lossless link, with a
window size of 𝑊 frames, where each frame is of size 1000 bits (including header).
The bandwidth of the link is 100 kbps (1k = 103) and the one-way propagation delay
is 100 milliseconds. Assume that processing times at the sender and receiver are zero
and the transmission time of acknowledgements is also zero. Which one of the
following options gives the minimum size of 𝑊 (in number of frames) required to
achieve 100% link utilization?

(A) 10

(B) 21

(C) 20

(D) 11

Organizing Institute: IIT Guwahati Page 34 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 34 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.46 Let 𝑓: ℝ → ℝ be defined as follows:

|𝑥| |𝑥|
𝑓(𝑥) = ( − 𝑥) (𝑥 − )
2 2

m
Which of the following statements is/are true?

m .co
.co s e m
s em l a
(A)
g la a local maximum
𝑓 has ag
a
(B) 𝑓 has a local minimum

(C) 𝑓 ′ is continuous over ℝ

(D) 𝑓 ′ is not differentiable over ℝ
m
.co
s em
Q.47 Let 𝐺(𝑉, 𝐸) be a simple, a gla graph. A vertex cover of 𝐺 is a subset
undirected
′ ′ ′
𝑉 ⊆ 𝑉 such that for every (𝑢, 𝑣) ∈ 𝐸, 𝑢 ∈ 𝑉 or 𝑣 ∈ 𝑉 . Let the size of the smallest
vertex cover in 𝐺 be 𝑘. Let 𝑆 be any vertex cover of size 𝑘.

For a vertex 𝑣 ∈ 𝑉, which of the following constraints will always ensure that
𝑣∈𝑆?

m
m
c. o(A) m.co
m
The degree of 𝑣 is at least 𝑘 + 1
s e
s e g l a
g la (B) The vertex 𝑣 is on a path of length 𝑘 + 1 a
a
(C) The vertex 𝑣 is on a cycle of length 𝑘 + 1

(D) The vertex 𝑣 is a part of a clique of size 𝑘

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 35 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 35 of 46

Computer Science & Information Technology (CS1)

Q.48 Consider a Boolean function F with the following minterm expression:

𝐹(𝑃, 𝑄, 𝑅, 𝑆) = ∑ 𝑚 (1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Which of the following options is/are the minimal sum-of-products expression(s)
of F ?

(A) 𝑃̅𝑆 + 𝑄𝑅̅ + 𝑃̅𝑄̅ 𝑅 + 𝑄̅ 𝑅𝑆̅

(B) 𝑃̅𝑆 + 𝑄𝑅̅ + 𝑃̅𝑄̅ 𝑅 + 𝑃𝑅𝑆̅

(C) 𝑃̅𝑆 + 𝑄𝑅̅ + 𝑃𝑄𝑆̅ + 𝑃𝑅𝑆̅

(D) 𝑃̅𝑆 + 𝑄𝑅̅ + 𝑃𝑄𝑆̅ + 𝑄̅ 𝑅𝑆̅

Organizing Institute: IIT Guwahati Page 36 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 36 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.49 Let 𝐺(𝑉, 𝐸) be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning trees (MST)
of 𝐺 is/are true?

m
c o m m .co
. s e
em
𝐶 of 𝐺, the edge with the largest weight in 𝐶 is not in any MST
(A) In every cycle
s g l a
l a a
(B)
aIng every cycle 𝐶 of 𝐺, the edge with the smallest weight in 𝐶 is in every MST
(C) For every vertex 𝑣 ∈ 𝑉, the edge with the largest weight incident on 𝑣 is not in any
MST

(D) For every vertex 𝑣 ∈ 𝑉, the edge with the smallest weight incident on 𝑣 is in every
MST
m
m .co
s e
g la
a

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 37 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 37 of 46

Computer Science & Information Technology (CS1)

Q.50 Consider the following pseudocode for depth-first search (DFS) algorithm which
takes a directed graph 𝐺(𝑉, 𝐸) as input, where 𝑑[𝑣] and 𝑓[𝑣] are the discovery time
and finishing time, respectively, of the vertex 𝑣 ∈ 𝑉.

𝐷𝐹𝑆(𝐺): 𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑣, 𝑡):
𝑢𝑛𝑚𝑎𝑟𝑘 𝑎𝑙𝑙 𝑣 ∈ 𝑉 𝑚𝑎𝑟𝑘 𝑣
𝑡 ←0 𝑡 ←𝑡+1
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑣 ∈ 𝑉 𝑑[𝑣] ← 𝑡
𝑖𝑓 𝑣 𝑖𝑠 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑 𝑓𝑜𝑟 𝑒𝑎𝑐ℎ (𝑣, 𝑤) ∈ 𝐸
𝑡 ← 𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑣, 𝑡) 𝑖𝑓 𝑤 𝑖𝑠 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑
𝑒𝑛𝑑 𝑖𝑓 𝑡 ← 𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑤, 𝑡)
𝑒𝑛𝑑 𝑓𝑜𝑟 𝑒𝑛𝑑 𝑖𝑓
𝑒𝑛𝑑 𝑓𝑜𝑟
𝑡 ←𝑡 + 1
𝑓[𝑣] ← 𝑡
𝑟𝑒𝑡𝑢𝑟𝑛 𝑡

Suppose that the input directed graph 𝐺(𝑉, 𝐸) is a directed acyclic graph (DAG).

For an edge (𝑢, 𝑣) ∈ 𝐸, which of the following options will NEVER be correct?

(A) 𝑑[𝑢] < 𝑑[𝑣] < 𝑓[𝑣] < 𝑓[𝑢]

(B) 𝑑[𝑣] < 𝑑[𝑢] < 𝑓[𝑢] < 𝑓[𝑣]

(C) 𝑑[𝑣] < 𝑓[𝑣] < 𝑑[𝑢] < 𝑓[𝑢]

(D) 𝑑[𝑢] < 𝑑[𝑣] < 𝑓[𝑢] < 𝑓[𝑣]

Organizing Institute: IIT Guwahati Page 38 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 38 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.51 Let 𝐿1 and 𝐿2 be two languages over a finite alphabet, such that 𝐿1 ∩ 𝐿2 and 𝐿2 are
regular languages.

Which of the following statements is/are always true?

m
c o m m .co
𝐿 is regular. s e
em a
(A)
l
1

la s ag
𝐿g ∪ 𝐿 is regular
(B)
a 1 2

(C) 𝐿2 is context-free

(D) 𝐿1 is context-free

m
m .co
s e
g la
a

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 39 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 39 of 46

Computer Science & Information Technology (CS1)

Q.52 Consider the following context-free grammar 𝐺.

𝑆 → 𝑎𝑏𝑎𝐴𝐵𝐴𝑏𝑏𝑎

𝐴 → 𝑎𝑎𝐵𝐵𝐴𝑏 | 𝑏𝐵𝑎𝑏𝑎𝑎

𝐵 → 𝑎𝐵𝑏 | 𝑎𝑏

In the above grammar, 𝑆 is the start symbol, 𝑎 and 𝑏 are terminal symbols, and 𝐴 and
𝐵 are non-terminal symbols.

Let 𝐿(𝐺) be the language generated by the grammar 𝐺. For a string 𝑠 ∈ 𝐿(𝐺), let
𝑛1 (𝑠) be the number of 𝑎’s in 𝑠 and 𝑛2 (𝑠) be the number of 𝑏’s in 𝑠.

Which of the following statements is/are true?

(A) There is a string 𝑠 ∈ 𝐿(𝐺) such that 𝑛1 (𝑠) < 𝑛2 (𝑠)

(B) For every string 𝑠 ∈ 𝐿(𝐺), 𝑛1 (𝑠) ≥ 𝑛2 (𝑠)

(C) There is a string 𝑠 ∈ 𝐿(𝐺) such that 𝑛1 (𝑠) > 2𝑛2 (𝑠)

(D) For every string 𝑠 ∈ 𝐿(𝐺), 𝑛1 (𝑠) ≤ 2𝑛2 (𝑠)

Organizing Institute: IIT Guwahati Page 40 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 40 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.53 Consider the following two syntax-directed definitions SDD1 and SDD2 for type
declarations.

SDD1 SDD2
Grammar Semantic Rules Grammar Semantic Rules
(G1) (G2)
m
𝐷 →𝑇𝑉

c o m 𝐷. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑉. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝐷 → 𝐷1 𝑖𝑑 𝐷. 𝑡𝑦𝑝𝑒 = 𝐷1 . 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝐷1 . 𝑡𝑦𝑝𝑒)
m .co
𝑇 → 𝑖𝑛𝑡 . e
m
𝑇 → e𝑓𝑙𝑜𝑎𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑖𝑛𝑡 𝐷 → 𝑇 𝑖𝑑 𝐷. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
l as
s
𝑉a→ 𝑉 𝑖𝑑
l
𝑇. 𝑡𝑦𝑝𝑒 = 𝑓𝑙𝑜𝑎𝑡
𝑉1 . 𝑡𝑦𝑝𝑒 = 𝑉. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑇. 𝑡𝑦𝑝𝑒)
ag
g
1
𝑇 → 𝑖𝑛𝑡 𝑇. 𝑡𝑦𝑝𝑒 = 𝑖𝑛𝑡
a 𝑉 → 𝑖𝑑 𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑉. 𝑡𝑦𝑝𝑒)
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑉. 𝑡𝑦𝑝𝑒)
𝑇 → 𝑓𝑙𝑜𝑎𝑡 𝑇. 𝑡𝑦𝑝𝑒 = 𝑓𝑙𝑜𝑎𝑡

𝐷 is the start symbol, and 𝑖𝑛𝑡, 𝑓𝑙𝑜𝑎𝑡 and 𝑖𝑑 are the three terminals. The non-terminal
𝑉1 is the same as 𝑉 and the non-terminal 𝐷1 is the same as 𝐷. Here, the subscript is
used to differentiate the grammar symbols on the two sides of a production. The
function 𝑝𝑢𝑡 updates the symbol table with the type information for an identifier.

m
Let P and Q be the languages specified by grammars G1 and G2, respectively.

Which of the following statements is/are true?
m .co
s e
g la
a
(A) The languages P and Q are the same

(B) SDD2 is S-attributed and contains only synthesized attributes

(C) SDD1 is L-attributed and contains only inherited attributes
o m
m . c
c. o(D) The specifications of SDD1 and SDD2 are such that the same entriesmget added to
s e
e m the symbol table
l a
l as ag
ag

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 41 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 41 of 46

Computer Science & Information Technology (CS1)

Q.54 Consider a system that has a cache memory unit and a memory management unit
(MMU). The address input to the cache memory is a physical address. The MMU
has a translation lookaside buffer (TLB). Assume that when a page is evicted from
the main memory, the corresponding blocks in the cache are marked as invalid.

For a given memory reference, which of the following sequences of events can
NEVER happen?

(A) TLB miss, Page table hit, Cache hit

(B) TLB hit, Page table miss, Cache hit

(C) TLB miss, Page table miss, Cache hit

(D) TLB miss, Page table miss, Cache miss

Organizing Institute: IIT Guwahati Page 42 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 42 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.55 An undirected, unweighted, simple graph 𝐺(𝑉, 𝐸) is said to be 2-colorable if there
exists a function 𝑐: 𝑉 → {0, 1} such that for every (𝑢, 𝑣) ∈ 𝐸, 𝑐(𝑢) ≠ 𝑐(𝑣).

Which of the following statements about 2-colorable graphs is/are true?

m
c o m m .co
m . then 𝐺 may contain cycles of odd length
If 𝐺 is 2-colorable, s e
(A)
s e l a
l a
Ifg𝐺 is 2-colorable, then 𝐺 may contain cycles of even length
ag
(B)
a
(C) An optimal algorithm for testing whether 𝐺 is 2-colorable runs in time Θ(|𝑉| + |𝐸|),
if 𝐺 is represented as an adjacency list

(D) An optimal algorithm for testing whether 𝐺 is 2-colorable runs in time Θ(|𝐸| log|𝑉|),
if 𝐺 is represented as an adjacency list
m
.co
s em
g a
l202.16.0.0/15
a
Q.56 An ISP having an address block assigns a block of 6000 IP addresses
to a client, using the classless internet domain routing (CIDR) super-netting
approach. Which of the following address blocks can be assigned by the ISP?

(A) 202.16.0.0/19
m
m
c. o(B) m.co
e
202.17.64.0/19

e m l as
las (C) 202.16.32.0/19
ag
ag
(D) 202.17.24.0/19

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 43 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 43 of 46

Computer Science & Information Technology (CS1)

Q.57 Let 𝐺 be an undirected graph, which is a path on 8 vertices. The number of matchings
in 𝐺 is ______. (answer in integer)

Q.58 Let 𝑋 be a random variable which takes values in the set {1, 2, 3, 4, 5, 6, 7, 8}.
1
Further, Pr(𝑋 = 1) = Pr(𝑋 = 2) = Pr(𝑋 = 5) = Pr(𝑋 = 7) = and
6
1
Pr(𝑋 = 3) = Pr(𝑋 = 4) = Pr(𝑋 = 6) = Pr(𝑋 = 8) = .
12

The expected value of 𝑋, denoted by 𝐸[𝑋], is equal to ___________. (rounded off
to two decimal places)

Q.59 Consider a hard disk with a rotational speed of 15000 rpm. The time to move the
read/write head from a track to its adjacent track is 1 millisecond. Initially, the head
is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes.
It is necessary to transfer data from 10 randomly located sectors in each of the
following tracks in the order: 5, 12 and 7.

The total time for the data transfer (in milliseconds) from the hard disk is _________.
(rounded off to one decimal place)

Q.60 The EX stage of a pipelined processor performs the memory read operations for
LOAD instructions, and the operations for the arithmetic and logic instructions. Let
𝑡𝐸𝑋 denote the time taken by the EX stage to perform the operation for an instruction.
For each instruction type, the values of 𝑡𝐸𝑋 and M (the number of instructions of that
type in a sequence of 100 instructions for a program P), are given in the table below.

The duration of the pipeline clock cycle is 1 nanosecond. Assume that the latch time
for the interstage buffers in the pipeline is negligible.

Instruction 𝑡𝐸𝑋 in 𝑀
nanoseconds
LOAD 1.8 15
IMUL 1.5 10
IDIV 2.5 5
FADD 1.7 10
FSUB 1.7 5
FMUL 2.8 15
FDIV 3.2 5
All other Less than 35
instructions 1.0

When program P is executed, the number of clock cycles for which the pipeline is
stalled due to structural hazards in the EX stage is ______. (answer in integer)

Organizing Institute: IIT Guwahati Page 44 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 44 of 46

o m
m c
. Technology (CS1)

.co e m
Computer Science & Information

m a s
se ag l
Q.61 Consider the recursive functions represented by the following code segment:

int bar(int n){
if (n == 1) return 0;
else return 1 + bar(n/2);
m
.co
}
m int foo(int n){
m .co s e m
s e
if (n == 1) return 1;
l a
a ag
else return 1 + foo(bar(n));

g l }
a
The smallest positive integer n for which foo(n) returns 5 is ______. (answer in
integer)

Note: Ignore syntax errors (if any) in the function.

m
Q.62
.co
The following sequence corresponds to the preorder traversal of a binary search

em
tree 𝑇:

50, 25, 13,las
g
40, 30, 47, 75, 60, 70, 80, 77
a
The position of the element 60 in the postorder traversal of 𝑇 is ______. (answer in
integer)

Note: The position begins with 1.

m
m .co
m .co s e m
s e g l a
g la a
a

m .
.co s e m
s em l a
la
Organizing Institute: IIT Guwahati

g
Page 45 of 46
ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 45 of 46

Computer Science & Information Technology (CS1)

Q.63 Consider the following program snippet. Assume that the program compiles and runs
successfully. Further, assume that the fork() system call is always successful in
creating a process.

int main () {
int i;
for (i = 0; i < 3; i++){
if (fork() == 0){
continue;
}
break;
}
printf("Hello!");
return 0;
}

The total number of times that the printf statement gets executed is ________.
(answer in integer)

Q.64 Consider a CPU that has to execute two types of processes. The first type,
Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C),
requires a CPU burst of 8 seconds. A new process of type A arrives at time 𝑡 = 10,
20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time 𝑡 =
11, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First
Serve (FCFS). The first process of type A starts running at 𝑡 = 10 seconds. The
average waiting time (in seconds) for the 10 processes is ___________. (rounded off
to one decimal place)

Q.65 Consider a relational database schema with a relation 𝑅(𝐴, 𝐵, 𝐶, 𝐷). If {𝐴, 𝐵} and
{𝐴, 𝐶} are the only two candidate keys of the relation 𝑅, then the number of superkeys
of relation 𝑅 is ______. (answer in integer)

Organizing Institute: IIT Guwahati Page 46 of 46

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 46 of 46