GATE CS 2025: Computer Science and Information Technology Session 2
Text of page 1
Computer Science and Information Technology (CS2)
General Aptitude
Q.1 – Q.5 Carry ONE mark Each
Q.1 Despite his initial hesitation, Rehman’s _________ to contribute to the success of
the project never wavered.
Select the most appropriate option to complete the above sentence.
(A) ambivalence
(B) satisfaction
(C) resolve
(D) revolve
Organising Institute: IIT Roorkee Page 1 of 48
Text of page 2
Computer Science and Information Technology (CS2)
Q.2 Bird : Nest :: Bee : _______
Select the correct option to complete the analogy.
(A) Kennel
(B) Hammock
(C) Hive
(D) Lair
Organising Institute: IIT Roorkee Page 2 of 48
Text of page 3
Computer Science and Information Technology (CS2)
Q.3 If Pe x = Qe −x for all real values of x, which one of the following statements is
true?
(A) P=Q=0
(B) P=Q=1
(C) P = 1; Q = −1
(D) P
=0
Q
Organising Institute: IIT Roorkee Page 3 of 48
Text of page 4
Computer Science and Information Technology (CS2)
Q.4 The paper as shown in the figure is folded to make a cube where each square
corresponds to a particular face of the cube. Which one of the following options
correctly represents the cube?
Note: The figures shown are representative.
(A)
(B)
(C)
(D)
Organising Institute: IIT Roorkee Page 4 of 48
Text of page 5
Computer Science and Information Technology (CS2)
Q.5 Let p1 and p2 denote two arbitrary prime numbers. Which one of the following
statements is correct for all values of p1 and p2 ?
(A) p1 + p2 is not a prime number.
(B) p1 p2 is not a prime number.
(C) p1 + p2 + 1 is a prime number.
(D) p1 p2 + 1 is a prime number.
Organising Institute: IIT Roorkee Page 5 of 48
Text of page 6
Computer Science and Information Technology (CS2)
Q.6 – Q.10 Carry TWO marks Each
Q.6 Based only on the conversation below, identify the logically correct inference:
“Even if I had known that you were in the hospital, I would not have gone there to
see you”, Ramya told Josephine.
(A) Ramya knew that Josephine was in the hospital.
(B) Ramya did not know that Josephine was in the hospital.
(C) Ramya and Josephine were once close friends; but now, they are not.
(D) Josephine was in the hospital due to an injury to her leg.
Organising Institute: IIT Roorkee Page 6 of 48
Text of page 7
Computer Science and Information Technology (CS2)
Q.7 If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which
one among the given options is the most appropriate code for BEACH ?
(A) CEADP
(B) IDBFC
(C) JGIBC
(D) IBCEC
Organising Institute: IIT Roorkee Page 7 of 48
Text of page 8
Computer Science and Information Technology (CS2)
Q.8 Which one of the following options is correct for the given data in the table?
Iteration (i) 0 1 2 3
Input (I) 20 −4 10 15
Output (X) 20 16 26 41
Output (Y) 20 −80 −800 −12000
(A) X(i) = X(i − 1) + I(i); Y(i) = Y(i − 1)I(i); i>0
(B) X(i) = X(i − 1)I(i); Y(i) = Y(i − 1) + I(i); i>0
(C) X(i) = X(i − 1)I(i); Y(i) = Y(i − 1)I(i); i>0
(D) X(i) = X(i − 1) + I(i); Y(i) = Y(i − 1)I(i − 1); i>0
Organising Institute: IIT Roorkee Page 8 of 48
Text of page 9
Computer Science and Information Technology (CS2)
Q.9 In the given figure, PQRS is a square of side 2 cm and PLMN is a rectangle. The
corner L of the rectangle is on the side QR. Side MN of the rectangle passes through
the corner S of the square.
What is the area (in cm2) of the rectangle PLMN?
Note: The figure shown is representative.
N
P S
M
Q L R
(A) 2√2
(B) 2
(C) 8
(D) 4
Organising Institute: IIT Roorkee Page 9 of 48
Text of page 10
Computer Science and Information Technology (CS2)
Q.10 The diagram below shows a river system consisting of 7 segments, marked P, Q, R,
S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We
need to connect these zones using the least number of bridges. Out of the following
options, which one is correct?
Note: The figure shown is representative.
Z2 Z3
R
V
P T
Q Z4
Z1 U
S Z5
(A) Bridges on P, Q, and T
(B) Bridges on P, Q, S, and T
(C) Bridges on Q, R, T, and V
(D) Bridges on P, Q, S, U, and V
Organising Institute: IIT Roorkee Page 10 of 48
Text of page 11
Computer Science and Information Technology (CS2)
Q.11 – Q.35 Carry ONE mark Each
Q.11 1 2
If A = ( ), then which ONE of the following is A8 ?
2 −1
(A) 25 0
( )
0 25
(B) 125 0
( )
0 125
(C) 625 0
( )
0 625
(D) 3125 0
( )
0 3125
x 1
Q.12 The value of x such that x > 1, satisfying the equation ∫1 t ln t dt = 4 is
(A) √e
(B) e
(C) e2
(D) e−1
Organising Institute: IIT Roorkee Page 11 of 48
Text of page 12
Computer Science and Information Technology (CS2)
Q.13 Consider a binary tree T in which every node has either zero or two children.
Let n > 0 be the number of nodes in T.
Which ONE of the following is the number of nodes in T that have exactly two
children?
(A) n−2
2
(B) n−1
2
(C) n
2
(D) n+1
2
Organising Institute: IIT Roorkee Page 12 of 48
Text of page 13
Computer Science and Information Technology (CS2)
Q.14 Let L, M, and N be non-singular matrices of order 3 satisfying the equations
L2 = L−1 , M = L8 and N = L2 .
Which ONE of the following is the value of the determinant of (M − N)?
(A) 0
(B) 1
(C) 2
(D) 3
Q.15 Let P(x) be an arbitrary predicate over the domain of natural numbers.
Which ONE of the following statements is TRUE?
(A) (P(0) ∧ (∀x [P(x) ⇒ P(x + 1)])) ⇒ (∀x P(x))
(B) (P(0) ∧ (∀x [P(x) ⇒ P(x − 1)])) ⇒ (∀x P(x))
(C) (P(1000) ∧ (∀x [P(x) ⇒ P(x − 1)])) ⇒ (∀x P(x))
(D) (P(1000) ∧ (∀x [P(x) ⇒ P(x + 1)])) ⇒ (∀x P(x))
Organising Institute: IIT Roorkee Page 13 of 48
Text of page 14
Computer Science and Information Technology (CS2)
Q.16 Consider the following statements:
(i) Address Resolution Protocol (ARP) provides a mapping from an IP
address to the corresponding hardware (link-layer) address.
(ii) A single TCP segment from a sender S to a receiver R cannot carry both
data from S to R and acknowledgement for a segment from R to S.
Which ONE of the following is CORRECT?
(A) Both (i) and (ii) are TRUE
(B) (i) is TRUE and (ii) is FALSE
(C) (i) is FALSE and (ii) is TRUE
(D) Both (i) and (ii) are FALSE
Organising Institute: IIT Roorkee Page 14 of 48
Text of page 15
Computer Science and Information Technology (CS2)
Q.17 Consider the routing protocols given in List I and the names given in List II:
List I List II
(i) Distance vector routing (a) Bellman-Ford
(ii) Link state routing (b) Dijkstra
For matching of items in List I with those in List II, which ONE of the following
options is CORRECT?
(A) (i) – (a) and (ii) – (b)
(B) (i) – (a) and (ii) – (a)
(C) (i) – (b) and (ii) – (a)
(D) (i) – (b) and (ii) – (b)
Organising Institute: IIT Roorkee Page 15 of 48
Text of page 16
Computer Science and Information Technology (CS2)
Q.18 A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the
protocol number of a protocol X.
Which ONE of the following is NOT a possible candidate for X?
(A) Internet Control Message Protocol (ICMP)
(B) Internet Group Management Protocol (IGMP)
(C) Open Shortest Path First (OSPF)
(D) Routing Information Protocol (RIP)
Organising Institute: IIT Roorkee Page 16 of 48
Text of page 17
Computer Science and Information Technology (CS2)
Q.19 Consider the following C program:
#include <stdio.h>
void stringcopy(char *, char *);
int main(){
char a[30] = "@#Hello World!";
stringcopy(a, a + 2);
printf("%s\n", a);
return 0;
}
void stringcopy(char *s, char *t) {
while(*t)
*s++ = *t++;
}
Which ONE of the following will be the output of the program?
(A) @#Hello World!
(B) Hello World!
(C) ello World!
(D) Hello World!d!
Organising Institute: IIT Roorkee Page 17 of 48
Text of page 18
Computer Science and Information Technology (CS2)
Q.20 Consider an unordered list of N distinct integers.
What is the minimum number of element comparisons required to find an integer
in the list that is NOT the largest in the list?
(A) 1
(B) N−1
(C) N
(D) 2N − 1
Q.21 Consider the following statements about the use of backpatching in a compiler for
intermediate code generation:
(I) Backpatching can be used to generate code for Boolean expression in
one pass.
(II) Backpatching can be used to generate code for flow-of-control
statements in one pass.
Which ONE of the following options is CORRECT?
(A) Only (I) is correct.
(B) Only (II) is correct.
(C) Both (I) and (II) are correct.
(D) Neither (I) nor (II) is correct.
Organising Institute: IIT Roorkee Page 18 of 48
Text of page 19
Computer Science and Information Technology (CS2)
Q.22 Given the following syntax directed translation rules:
Rule 1: R → AB {B. i = R. i − 1; A. i = B. i; R. i = A. i + 1; }
Rule 2: P → CD {P. i = C. i + D. i; D. i = C. i + 2; }
Rule 3: Q → EF {Q. i = E. i + F. i; }
Which ONE is the CORRECT option among the following?
(A) Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed;
Rule 3 is neither S-attributed nor L-attributed
(B) Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-
attributed; Rule 3 is S-attributed and L-attributed
(C) Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and
is L-attributed; Rule 3 is S-attributed and L-attributed
(D) Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and
is L-attributed; Rule 3 is S-attributed and L-attributed
Organising Institute: IIT Roorkee Page 19 of 48
Text of page 20
Computer Science and Information Technology (CS2)
Q.23 Consider a network that uses Ethernet and IPv4. Assume that IPv4 headers do not
use any options field. Each Ethernet frame can carry a maximum of 1500 bytes in
its data field. A UDP segment is transmitted. The payload (data) in the UDP
segment is 7488 bytes.
Which ONE of the following choices has the CORRECT total number of fragments
transmitted and the size of the last fragment including IPv4 header?
(A) 5 fragments, 1488 bytes
(B) 6 fragments, 88 bytes
(C) 6 fragments, 108 bytes
(D) 6 fragments, 116 bytes
Q.24 Which ONE of the following languages is accepted by a deterministic pushdown
automaton?
(A) Any regular language.
(B) Any context-free language.
(C) Any language accepted by a non-deterministic pushdown automaton.
(D) Any decidable language.
Organising Institute: IIT Roorkee Page 20 of 48
Text of page 21
Computer Science and Information Technology (CS2)
Q.25 Let G1 , G2 be Context Free Grammars (CFGs) and R be a regular expression. For a
grammar G, let L(G) denote the language generated by G.
Which ONE among the following questions is decidable?
(A) Is L(G1 ) = L(G2 )?
(B) Is L(G1 ) ∩ L(G2 ) = ∅?
(C) Is L(G1 ) = L(R)?
(D) Is L(G1 ) = ∅?
Q.26 Processes P1, P2, P3, P4 arrive in that order at times 0, 1, 2, and 8 milliseconds
respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively.
Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling
policy. Ignore context switching times.
Which ONE of the following correctly gives the average turnaround time of the four
processes in milliseconds?
(A) 22
(B) 15
(C) 37
(D) 19
Organising Institute: IIT Roorkee Page 21 of 48
Text of page 22
Computer Science and Information Technology (CS2)
Q.27 An audit of a banking transactions system has found that on an earlier occasion, two
joint holders of account A attempted simultaneous transfers of Rs. 10000 each from
account A to account B. Both transactions read the same value, Rs. 11000, as the
initial balance in A and were allowed to go through. B was credited Rs. 10000 twice.
A was debited only once and ended up with a balance of Rs. 1000.
Which of the following properties is/are certain to have been violated by the
system?
(A) Atomicity
(B) Consistency
(C) Isolation
(D) Durability
Q.28 Which of the following is/are part of an Instruction Set Architecture of a processor?
(A) The size of the cache memory
(B) The clock frequency of the processor
(C) The number of cache memory levels
(D) The total number of registers
Organising Institute: IIT Roorkee Page 22 of 48
Text of page 23
Computer Science and Information Technology (CS2)
Q.29 Which of the following statements regarding Breadth First Search (BFS) and
Depth First Search (DFS) on an undirected simple graph G is/are TRUE?
(A) A DFS tree of G is a Shortest Path tree of G.
(B) Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
(C) If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from
the source vertex s to u and v in the BFS tree are within ±1 of each other.
(D) Both BFS and DFS can be used to find the connected components of G.
Organising Institute: IIT Roorkee Page 23 of 48
Text of page 24
Computer Science and Information Technology (CS2)
Q.30 Consider the two lists List I and List II given below:
List I List II
(i) Context free languages (a) Closed under union
(ii) Recursive languages (b) Not closed under complementation
(iii) Regular languages (c) Closed under intersection
For matching of items in List I with those in List II, which of the following
option(s) is/are CORRECT?
(A) (i) – (a), (ii) – (b), and (iii) – (c)
(B) (i) – (b), (ii) – (a), and (iii) – (c)
(C) (i) – (b), (ii) – (c), and (iii) – (a)
(D) (i) – (a), (ii) – (c), and (iii) – (b)
Organising Institute: IIT Roorkee Page 24 of 48
Text of page 25
Computer Science and Information Technology (CS2)
Q.31 Consider the following logic circuit diagram.
Which is/are the CORRECT option(s) for the output function F?
(A) ̅̅̅̅̅
XY
(B) X̅ + Y̅ + XY̅
(C) ̅̅̅̅̅
X Y + X̅ + XY̅
(D) X + Y̅
Q.32 The following two signed 2’s complement numbers (multiplicand M and
multiplier Q) are being multiplied using Booth’s algorithm:
M: 1100 1101 1110 1101 and Q: 1010 0100 1010 1010
The total number of addition and subtraction operations to be performed is
___________. (Answer in integer)
Organising Institute: IIT Roorkee Page 25 of 48
Text of page 26
Computer Science and Information Technology (CS2)
Q.33 int x=126,y=105;
do {
if(x>y) x=x-y;
else y=y-x;
} while(x!=y);
printf("%d",x);
The output of the given C code segment is ________. (Answer in integer)
Q.34 In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64
microseconds, then the frequency of the ripple counter in kHz is ________. (Answer
in integer)
Q.35 Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an
initially empty binary search tree. Let T be the resulting binary search tree.
The number of edges in the path from the node containing 19 to the root node of T
is ___________. (Answer in integer)
Organising Institute: IIT Roorkee Page 26 of 48
Text of page 27
Computer Science and Information Technology (CS2)
Q.36 – Q.65 Carry TWO marks Each
Q.36 Suppose we are transmitting frames between two nodes using Stop-and-Wait
protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000
bps (bits/second) and the propagation delay between the two nodes is 100
milliseconds. Assume that the processing times at the source and destination are
negligible. Also, assume that the size of the acknowledgement packet is negligible.
Which ONE of the following most accurately gives the channel utilization for the
above scenario in percentage?
(A) 88.23
(B) 93.75
(C) 85.44
(D) 66.67
Organising Institute: IIT Roorkee Page 27 of 48
Text of page 28
Computer Science and Information Technology (CS2)
Q.37 Let G be an edge-weighted undirected graph with positive edge weights. Suppose a
positive constant α is added to the weight of every edge.
Which ONE of the following statements is TRUE about the minimum spanning
trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
(A) Every MST remains an MST, and every SP remains an SP.
(B) MSTs need not remain MSTs, and every SP remains an SP.
(C) Every MST remains an MST, and SPs need not remain SPs.
(D) MSTs need not remain MSTs, and SPs need not remain SPs.
Organising Institute: IIT Roorkee Page 28 of 48
Text of page 29
Computer Science and Information Technology (CS2)
Q.38 A meld operation on two instances of a data structure combines them into one single
instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node
of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for
meld operation on instances of size n of these data structures?
(A) P: Θ(1), Q: Θ(n), R: Θ(n)
(B) P: Θ(1), Q: Θ(n log n), R: Θ(n)
(C) P: Θ(n), Q: Θ(n log n), R: Θ(n2 )
(D) P: Θ(1), Q: Θ(n), R: Θ(n log n)
Organising Institute: IIT Roorkee Page 29 of 48
Text of page 30
Computer Science and Information Technology (CS2)
Q.39 For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to
index into a cache block. The size of each cache block is one byte. Assume that
there is no other information stored for each cache block.
Which ONE of the following is the CORRECT option for the sizes of the main
memory and the cache memory in this system (byte addressable), respectively?
(A) 64 KB and 4 KB
(B) 128 KB and 16 KB
(C) 64 KB and 8 KB
(D) 128 KB and 6 KB
Q.40 Given a Context-Free Grammar G as follows:
S → Aa | bAc | dc | bda
A→d
Which ONE of the following statements is TRUE?
(A) G is neither LALR(1) nor SLR(1)
(B) G is CLR(1), not LALR(1)
(C) G is LALR(1), not SLR(1)
(D) G is LALR(1), also SLR(1)
Organising Institute: IIT Roorkee Page 30 of 48
Text of page 31
Computer Science and Information Technology (CS2)
Q.41 An array A of length n with distinct elements is said to be bitonic if there is an index
1 ≤ i ≤ n such that A[1. . i] is sorted in the non-decreasing order and A[i + 1 . . n]
is sorted in the non-increasing order.
Which ONE of the following represents the best possible asymptotic bound for the
worst-case number of comparisons by an algorithm that searches for an element in
a bitonic array A?
(A) Θ(n)
(B) Θ(1)
(C) Θ(log 2 n)
(D) Θ(log n)
Q.42 Let ℱ be the set of all functions from {1, … , n} to {0,1}. Define
the binary relation ≼ on ℱ as follows:
∀f, g ∈ ℱ, f ≼ g if and only if ∀x ∈ {1, … , n}, f(x) ≤ g(x), where 0 ≤ 1.
Which of the following statement(s) is/are TRUE?
(A) ≼ is a symmetric relation
(B) (ℱ, ≼ ) is a partial order
(C) (ℱ, ≼ ) is a lattice
(D) ≼ is an equivalence relation
Organising Institute: IIT Roorkee Page 31 of 48
Text of page 32
Computer Science and Information Technology (CS2)
Q.43 Given the following Karnaugh Map for a Boolean function F(w, x, y, z):
Which one or more of the following Boolean expression(s) represent(s) F?
(A) w
̅x̅ y̅z̅ + wx̅ y̅z̅ + w
̅x̅ yz̅ + wx̅ yz̅ + xz
(B) w
̅x̅ y̅z̅ + w
̅x̅ yz̅ + wx̅ yz + xz
(C) w
̅x̅ y̅z̅ + wx̅ y̅z̅ + wx̅ y̅z + xz
(D) x̅ z̅ + xz
Organising Institute: IIT Roorkee Page 32 of 48
Text of page 33
Computer Science and Information Technology (CS2)
Q.44 Consider a system of linear equations PX = Q where P ∈ ℝ3×3 and Q ∈ ℝ3×1 .
Suppose P has an LU decomposition, P = LU, where
1 0 0 u11 u12 u13
l
L = [ 21 1 0] and U = [ 0 u22 u23 ].
l31 l32 1 0 0 u33
Which of the following statement(s) is/are TRUE?
(A) The system PX = Q can be solved by first solving LY = Q and then UX = Y.
(B) If P is invertible, then both L and U are invertible.
(C) If P is singular, then at least one of the diagonal elements of U is zero.
(D) If P is symmetric, then both L and U are symmetric.
Organising Institute: IIT Roorkee Page 33 of 48
Text of page 34
Computer Science and Information Technology (CS2)
Q.45 Consider a stack data structure into which we can PUSH and POP records. Assume
that each record pushed in the stack has a positive integer key and that all keys are
distinct.
We wish to augment the stack data structure with an O(1) time MIN operation that
returns a pointer to the record with smallest key present in the stack
1) without deleting the corresponding record, and
2) without increasing the complexities of the standard stack operations.
Which one or more of the following approach(es) can achieve it?
(A) Keep with every record in the stack, a pointer to the record with the smallest key
below it.
(B) Keep a pointer to the record with the smallest key in the stack.
(C) Keep an auxiliary array in which the key values of the records in the stack are
maintained in sorted order.
(D) Keep a Min-Heap in which the key values of the records in the stack are maintained.
Organising Institute: IIT Roorkee Page 34 of 48
Text of page 35
Computer Science and Information Technology (CS2)
Q.46 Consider the following relational schema along with all the functional dependencies
that hold on them.
R1(A, B, C, D, E): { D → E, EA → B, EB → C}
R2(A, B, C, D): { A → D, A → B, C → A}
Which of the following statement(s) is/are TRUE?
(A) R1 is in 3NF
(B) R2 is in 3NF
(C) R1 is NOT in 3NF
(D) R2 is NOT in 3NF
Organising Institute: IIT Roorkee Page 35 of 48
Text of page 36
Computer Science and Information Technology (CS2)
Q.47 Consider a demand paging system with three frames, and the following page
reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows
initially and after each reference (from left to right):
initially after
- 1* 2* 3* 4* 5* 4 1 6* 4 5 1* 3* 2*
- 1 1 1 1 1 1 1 6 6 6 6 6 2
- - 2 2 4 4 4 4 4 4 4 1 1 1
- - - 3 3 5 5 5 5 5 5 5 3 3
The *-marked references cause page replacements.
Which one or more of the following could be the page replacement policy/policies
in use?
(A) Least Recently Used page replacement policy
(B) Least Frequently Used page replacement policy
(C) Most Frequently Used page replacement policy
(D) Optimal page replacement policy
Organising Institute: IIT Roorkee Page 36 of 48
Text of page 37
Computer Science and Information Technology (CS2)
Q.48 P = {P1 , P2 , P3 , P4 } consists of all active processes in an operating system.
R = {R1 , R2 , R3 , R4 } consists of single instances of distinct types of resources in the
system.
The resource allocation graph has the following assignment and claim edges.
Assignment edges: R1 → P1 , R2 → P2 , R3 → P3 , R4 → P4 (the assignment edge
R1 → P1 means resource R1 is assigned to process P1 , and so on for others)
Claim edges: P1 → R2 , P2 → R3 , P3 → R1 , P2 → R4 , P4 → R2 (the claim edge
P1 → R2 means process P1 is waiting for resource R2 , and so on for others)
Which of the following statement(s) is/are CORRECT?
(A) Aborting P1 makes the system deadlock free.
(B) Aborting P3 makes the system deadlock free.
(C) Aborting P2 makes the system deadlock free.
(D) Aborting P1 and P4 makes the system deadlock free.
Organising Institute: IIT Roorkee Page 37 of 48
Text of page 38
Computer Science and Information Technology (CS2)
Q.49 Three floating point numbers X, Y, and Z are stored in three registers RX, RY, and
RZ, respectively in IEEE 754 single precision format as given below in
hexadecimal:
RX = 0xC1100000, RY = 0x40C00000, and RZ = 0x41400000
Which of the following option(s) is/are CORRECT?
(A) 4(X + Y) + Z = 0
(B) 2Y – Z = 0
(C) 4X + 3Z = 0
(D) X+Y+Z = 0
Q.50 Which of the following Boolean algebraic equation(s) is/are CORRECT?
(A) A̅ B C + A B̅ C̅ + A̅ B̅ C̅ + A B̅ C + A B C = B C + B̅ C̅ + A̅ B̅
(B) A B + A̅ C + B C = A B + A̅ C
(C) (A + C) (A̅ + B) = A B + A̅ C
(D) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(A + B̅ + D ̅ ) (C + D) (A̅ + C + D ) (A + B + D ̅ ) = A̅ D + C̅ D
̅
Organising Institute: IIT Roorkee Page 38 of 48
Text of page 39
Computer Science and Information Technology (CS2)
Q.51 Consider two grammars G1 and G2 with the production rules given below:
G1 : S → if E tℎen S | if E tℎen S else S | a
E→b
G2 : S → if E tℎen S | M
M → if E tℎen M else S | c
E→b
where if, tℎen, else, a, b, c are the terminals.
Which of the following option(s) is/are CORRECT?
(A) G1 is not LL(1) and G2 is LL(1).
(B) G1 is LL(1) and G2 is not LL(1).
(C) G1 and G2 are not LL(1).
(D) G1 and G2 are ambiguous.
Organising Institute: IIT Roorkee Page 39 of 48
Text of page 40
Computer Science and Information Technology (CS2)
Q.52 Let Σ = {a, b, c}. For x ∈ Σ ∗ , and α ∈ Σ, let #α (x) denote the number of
occurrences of α in x.
Which one or more of the following option(s) define(s) regular language(s)?
(A) {am b n | m, n ≥ 0}
(B) {a, b}∗ ∩ {am b n c m−n | m ≥ n ≥ 0}
(C) {w | w ∈ {a, b}∗ , #a (w) ≡ 2 (mod 7), and #b (w) ≡ 3 (mod 9)}
(D) {w | w ∈ {a, b}∗ , #a (w) ≡ 2 (mod 7), and #a (w) = #b (w)}
Organising Institute: IIT Roorkee Page 40 of 48
Text of page 41
Computer Science and Information Technology (CS2)
Q.53 Consider the database transactions T1 and T2, and data items X and Y. Which of
the schedule(s) is/are conflict serializable?
Transaction T1
Transaction T2
R1(X)
W2(X)
W1(Y)
W2(Y)
R1(X)
COMMIT(T2)
W1(X)
COMMIT(T1)
(A) R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1)
(B) W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)
(C) R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2)
(D) W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)
Organising Institute: IIT Roorkee Page 41 of 48
Text of page 42
Computer Science and Information Technology (CS2)
Q.54 Consider the following relational schema:
Students (rollno: integer, name: string, age: integer, cgpa: real)
Courses (courseno: integer, cname: string, credits: integer)
Enrolled (rollno: integer, courseno: integer, grade: string)
Which of the following options is/are correct SQL query/queries to retrieve the
names of the students enrolled in course number (i.e., courseno) 1470?
(A) SELECT S.name
FROM Students S
WHERE EXISTS (SELECT * FROM Enrolled E
WHERE E.courseno = 1470
AND E.rollno = S.rollno);
(B) SELECT S.name
FROM Students S
WHERE SIZEOF (SELECT * FROM Enrolled E
WHERE E.courseno = 1470
AND E.rollno = S.rollno) > 0;
(C) SELECT S.name
FROM Students S
WHERE 0 < (SELECT COUNT(*)
FROM Enrolled E
WHERE E.courseno = 1470
AND E.rollno = S.rollno);
(D) SELECT S.name
FROM Students S NATURAL JOIN Enrolled E
WHERE E.courseno = 1470;
Organising Institute: IIT Roorkee Page 42 of 48
Text of page 43
Computer Science and Information Technology (CS2)
Q.55 Given a computing system with two levels of cache (L1 and L2) and a main
memory. The first level (L1) cache access time is 1 nanosecond (ns) and the “hit
rate” for L1 cache is 90% while the processor is accessing the data from L1 cache.
Whereas, for the second level (L2) cache, the “hit rate” is 80% and the “miss
penalty” for transferring data from L2 cache to L1 cache is 10 ns. The “miss
penalty” for the data to be transferred from main memory to L2 cache is 100 ns.
Then the average memory access time in this system in nanoseconds is
___________ . (rounded off to one decimal place)
A 5-stage instruction pipeline has stage delays of 180, 250, 150, 170, and 250,
respectively, in nanoseconds. The delay of an inter-stage latch is 10 nanoseconds.
Q.56 Assume that there are no pipeline stalls due to branches and other hazards. The time
taken to process 1000 instructions in microseconds is __________ . (rounded off to
two decimal places)
Q.57 In a B+- tree where each node can hold at most four key values, a root to leaf path
consists of the following nodes:
A = (49, 77, 83, -), B = (7, 19, 33, 44), C = (20*, 22*, 25*, 26*)
The *-marked keys signify that these are data entries in a leaf.
Assume that a pointer between keys k1 and k2 points to a subtree containing keys
in [k1 , k2 ), and that when a leaf is created, the smallest key in it is copied up into
its parent.
A record with key value 23 is inserted into the B+- tree.
The smallest key value in the parent of the leaf that contains 25* is __________.
(Answer in integer)
Organising Institute: IIT Roorkee Page 43 of 48
Text of page 44
Computer Science and Information Technology (CS2)
Q.58 A computer system supports a logical address space of 232 bytes. It uses two-level
hierarchical paging with a page size of 4096 bytes. A logical address is divided into
a b-bit index to the outer page table, an offset within the page of the inner page
table, and an offset within the desired page. Each entry of the inner page table uses
eight bytes. All the pages in the system have the same size.
The value of b is ___________ . (Answer in integer)
Q.59 Consider the following algorithm someAlgo that takes an undirected graph G as
input.
someAlgo(G)
1. Let v be any vertex in G. Run BFS on G starting at
v. Let u be a vertex in G at maximum distance from
v as given by the BFS.
2. Run BFS on G again with u as the starting vertex.
Let z be the vertex at maximum distance from u as
given by the BFS.
3. Output the distance between u and z in G.
The output of someAlgo(T) for the tree shown in the given figure is
___________. (Answer in integer)
Organising Institute: IIT Roorkee Page 44 of 48
Text of page 45
Computer Science and Information Technology (CS2)
Q.60 Let Σ = {1,2,3,4}. For x ∈ Σ ∗ , let prod(x) be the product of symbols in
x modulo 7. We take prod(ε) = 1, where ε is the null string.
For example, prod(124) = (1 × 2 × 4) mod 7 = 1.
Define L = {x ∈ Σ ∗ | prod(x) = 2}.
The number of states in a minimum state DFA for L is ___________. (Answer in
integer)
Q.61 An application executes 6.4 × 108 number of instructions in 6.3 seconds. There are
four types of instructions, the details of which are given in the table. The duration
of a clock cycle in nanoseconds is _________. (rounded off to one decimal place)
Instruction type Clock cycles required per Number of instructions
instruction (CPI) executed
Branch 2 2.25 × 108
Load 5 1.20 × 108
Store 4 1.65 × 108
Arithmetic 3 1.30 × 108
Organising Institute: IIT Roorkee Page 45 of 48
Text of page 46
Computer Science and Information Technology (CS2)
Q.62 Consider the following C program:
#include <stdio.h>
int main(){
int a;
int arr[5] = {30,50,10};
int *ptr;
ptr = &arr[0] + 1;
a = *ptr;
(*ptr)++;
ptr++;
printf("%d", a + (*ptr) + arr[1]);
return 0;
}
The output of the above program is ___________. (Answer in integer)
Organising Institute: IIT Roorkee Page 46 of 48
Text of page 47
Computer Science and Information Technology (CS2)
Q.63 Consider the following C program:
#include <stdio.h>
int g(int n) {
return (n+10);
}
int f(int n) {
return g(n*2);
}
int main() {
int sum, n;
sum=0;
for (n=1; n<3; n++)
sum += g(f(n));
printf ("%d", sum);
return 0;
}
The output of the given C program is ________. (Answer in integer)
Q.64 A quadratic polynomial (x − α)(x − β) over complex numbers is said to be square
invariant if (x − α)(x − β) = (x − α 2 )(x − β 2 ). Suppose from the set of all
square invariant quadratic polynomials we choose one at random.
The probability that the roots of the chosen polynomial are equal is __________.
(rounded off to one decimal place)
Organising Institute: IIT Roorkee Page 47 of 48
Text of page 48
Computer Science and Information Technology (CS2)
Q.65 The unit interval (0,1) is divided at a point chosen uniformly distributed over (0,1)
in ℝ into two disjoint subintervals.
The expected length of the subinterval that contains 0.4 is ___________. (rounded
off to two decimal places)
Organising Institute: IIT Roorkee Page 48 of 48
Text of page 1
Answer Key for Computer Science and Information Technology 2 (CS2)
Q. No. Session Q. Type Section Key/Range Marks
1 2 MCQ GA C 1
2 2 MCQ GA C 1
3 2 MCQ GA A 1
4 2 MCQ GA A 1
5 2 MCQ GA B 1
6 2 MCQ GA B 2
7 2 MCQ GA B 2
8 2 MCQ GA A 2
9 2 MCQ GA D 2
10 2 MCQ GA C 2
11 2 MCQ CS-2 C 1
12 2 MCQ CS-2 A 1
13 2 MCQ CS-2 B 1
14 2 MCQ CS-2 A 1
15 2 MCQ CS-2 A 1
16 2 MCQ CS-2 B 1
17 2 MCQ CS-2 A 1
18 2 MCQ CS-2 D 1
19 2 MCQ CS-2 D 1
20 2 MCQ CS-2 A 1
21 2 MCQ CS-2 C 1
22 2 MCQ CS-2 C 1
23 2 MCQ CS-2 D 1
24 2 MCQ CS-2 A 1
25 2 MCQ CS-2 D 1
26 2 MCQ CS-2 D 1
27 2 MSQ CS-2 B;C 1
28 2 MSQ CS-2 D 1
29 2 MSQ CS-2 B;C;D 1
30 2 MSQ CS-2 B;C 1
Page 1 of 2
Text of page 2
31 2 MSQ CS-2 A;B;C 1
32 2 NAT CS-2 13 to 13 1
33 2 NAT CS-2 21 to 21 1
34 2 NAT CS-2 250 to 250 1
35 2 NAT CS-2 4 to 4 1
36 2 MCQ CS-2 A 2
37 2 MCQ CS-2 C 2
38 2 MCQ CS-2 A 2
39 2 MCQ CS-2 A 2
40 2 MCQ CS-2 C 2
41 2 MCQ CS-2 D 2
42 2 MSQ CS-2 B;C 2
43 2 MSQ CS-2 A;D 2
44 2 MSQ CS-2 A;B;C 2
45 2 MSQ CS-2 A 2
46 2 MSQ CS-2 C;D 2
47 2 MSQ CS-2 D 2
48 2 MSQ CS-2 C;D 2
49 2 MSQ CS-2 A;B;C 2
50 2 MSQ CS-2 B;C;D 2
51 2 MSQ CS-2 C;D 2
52 2 MSQ CS-2 A;C 2
53 2 MSQ CS-2 B 2
54 2 MSQ CS-2 A;C;D 2
55 2 NAT CS-2 4.0 to 4.0 2
56 2 NAT CS-2 260.20 to 261.20 2
57 2 NAT CS-2 33 to 33 2
58 2 NAT CS-2 11 to 11 2
59 2 NAT CS-2 6 to 6 2
60 2 NAT CS-2 6 to 6 2
61 2 NAT CS-2 3.0 to 3.0 2
62 2 NAT CS-2 111 to 111 2
63 2 NAT CS-2 46 to 46 2
64 2 NAT CS-2 0.5 to 0.5 2
65 2 NAT CS-2 0.70 to 0.80 2
Page 2 of 2
Page 1 of 48
Source: GATE. Question paper published by GATE.