GATE 2027 Sample Paper (Computer Science - CS)

SAMPLE PAPER

S A M P L E Q U E S T I O N P A P E R

GATE 2027 (Computer Science - CS)
Modelled on the actual exam pattern
.

QUESTIONS MAX MARKS TIME

65 100 180 Min

GENERAL INSTRUCTIONS

1. This paper contains 65 multiple-choice questions. All questions are compulsory.

2. Each question has four options — (A), (B), (C) and (D) — of which only one is correct.

3. Each correct answer carries 1 or 2 marks (varies by question); for a multiple-choice question, one-third (1-mark
question) or two-thirds (2-mark question) of the allotted marks is deducted for a wrong answer; numerical-answer-type
questions carry no negative marking.

4. Total time allowed is 180 minutes. Manage your time across all sections.

5. Use of calculators, mobile phones or any electronic device is not permitted.

6. Attempt the paper first, then check your answers against the Answer Key at the end.

Candidate Name: Roll No.: Date:

SAMPLE PAPER

GATE 2027 (Computer Science - CS)
SAMPLE QUESTION PAPER

Questions 65 Max Marks 100 Time 180 Min

Attempt all questions. Choose the one correct option for each.

GENERAL APTITUDE

1. P, Q, R, S and T are related and belong to the same 2. Five numbers 10, 7, 5, 4 and 2 are to be arranged in a
family. P is the brother Of S. Q is the wife Of P. R and T sequence from left to right following the directions given
are the children Of the siblings P and S respectively. below: 1. NO two Odd or even numbers are next to each
Which one of the following statements is necessarily other. 2. The second number from the left is exactly half
FALSE? Of the left-most number. 3. The middle number is exactly
twice the right-most number. Which is the second
(A) S is the aunt Of R
number from the right?
(B) S is the aunt Of T
(A) 2
(C) S is the sister-in-law Of Q
(B) 4
(D) S is the brother of P
(C) 7

(D) 10

3. M and N had four children P, Q, R and S. Of them, only 4. The boat arrived ______ dawn.
P and R were married. They had children X and Y
(A) in
respectively. If Y is a legitimate child Of W, which one Of
(B) at
the following statements is necessarily FALSE?
(C) on
(A) M is the grandmother Of Y
(D) under
(B) R is the father of Y

(C) W is the wife of R

(D) W is the wife of P

5. It takes two hours for a person X to mow the lawn. Y 6. A final examination is the __________ of a series of
can mow the same lawn in four hours. How long (in evaluations that a student has to go through.
minutes) will it take X and Y, if they work together to
(A) culmination
mow the lawn?
(B) consultation
(A) 60
(C) desperation
(B) 80
(D) insinuation
(C) 90

(D) 120

7. Given two sets X = {1, 2, 3} and Y = {2, 3, 4}, we 8. Three of the five students allocated to a hostel put in
construct a set Z Of all possible fractions where the special requests to the warden. Given the floor plan of
numerators belong to set X and the denominators belong the vacant rooms, select the allocation plan that will
to set Y. The product Of elements having minimum and accommodate all their requests. Request by X: Due to
maximum values in the set Z is pollen allergy, I want to avoid a wing next to the garden.
Request by Y: I want to live as far from the washrooms as
(A) 1/12
possible, since I am very sensitive to smell. Request by Z:
(B) 1/8
I believe in Vaastu and so want to stay in the South-west
(C) 1/6 wing. The shaded rooms are already occupied. WR is
(D) 3/8 washroom.

(A)

(B)

(C)

(D)

9. On a horizontal ground, the base Of a straight ladder 10. The strategies that the company ______ to sell its
is 6 m away from the base Of a vertical pole. The ladder products ___ house-to-house marketing.
makes an angle Of 450 to the horizontal. If the ladder is
(A) use, includes
resting at a point located at one-fifth Of the height Of the
(B) uses, include
pole from the bottom, the height Of the pole is __________
meters. (C) used, includes

(D) uses, including
(A) 15

(B) 25

(C) 30

(D) 35

COMPUTER SCIENCE & INFORMATION TECHNOLOGY

11. Consider the following statements. I. Daisy chaining 12. Let L be a language and L be its complement. Which
is used to assign priorities in attending interrupts. II. one of the following is NOT a viable possibility ?
When a device raises a vectored interrupt, the CPU does
(A) Neither L nor L is recursively enumerable (r.e.).
polling to identify the source of the interrupt. III. In
(B) One of L and L is r.e. but not recursive; the other is not
polling, the CPU periodically checks the status bits to
r.e.
know if any device needs its attention. IV. During DMA,
both the CPU and DMA controller can be bus masters at (C) Both L and L are r.e. but not recursive.

the same time. Which of the above statements is/are (D) Both L and L are recursive.
TRUE?

(A) I and II only

(B) I and IV Only

(C) I and Ill only

(D) III only

13. Consider the following system of equations 3x + 2y = 14. Let G = (V, E) be a weighted undirected graph and let
1 4x + 7z = 1 x + y + z = 3 x – 2y + 7z = 0 The number of T be a Minimum Spanning Tree (MST) of G maintained
solutions for this system is __________________ using adjacency lists. Suppose a new weighted edge (u,
v) ∈ V x V is added to G. The worst case time complexity
(A) 1
of determining if T is still an MST of the resultant graph
(B) 2
is
(C) 3
(A) θ(|E| + |V|)
(D) 4
(B) θ(|E| |V|)

(C) θ(|E| log|V|)

(D) θ(|V|)

15. The function f(x) = x sinx satisfies the following 16. Consider the following sets: S1. Set of all recursively
equation: f"(x) + f(x) + t cosx = 0. The value of is ____ . enumerable languages over the alphabet {0,1} S2. Set of
all syntactically valid C programs S3. Set of all languages
(A) -4
over the alphabet {0,1} S4. Set of all non-regular
(B) -3
languages over the alphabet {0,1} Which of the above
(C) -2 sets are uncountable?
(D) -1
(A) S1 and S2

(B) S3 and S4

(C) S2 and S3

(D) S1 and S4

17. Consider a TCP client and a TCP server nmmng on 18. Consider a 6-stage instruction pipeline, where all
two different machines. After completing data transfer. stages are perfectly balanced.Assume that there is no
the TCP client calls close to terminate the connection and cycle-time overhead of pipelining. When an application is
a FIN segment is sent to the TCP server. Server-side TCP executing on this 6-stage pipeline, the speedup achieved
responds by sending an ACK. which is received by the with respect to non-pipelined execution if 25% of the
client-side TCP. As per the TCP connection state diagram instructions incur 2 pipeline stall cycles is
(RFC 793). in which state does the client-side TCP ______________________.
connection wait for the FIN from the server-side TCP?
(A) 4
(A) LAST-ACK (B) 5
(B) TIME-WAIT (C) 6
(C) FIN-WAIT-I (D) 7
(D) FN-WAIT-2

19. Consider the first-order logic sentence 20. Assume that there are 3 page frames which are
F:∀x(∃yR(x,y)). Assuming non-empty logical domains. initially empty. If the page reference string is 1, 2, 3, 4,
which of the sentences below are implied by F? I. 2, 1, 5, 3, 2, 4, 6, the number of page faults using the
∃y(∃xR(x,y)) II. ∃y(∀xR(x,y)) III. ∀y(∃xR(x,y)) IV. optimal replacement policy is__________.
∃x(∀yR(x,y))
(A) 7
(A) IV only (B) 8
(B) I and IV only (C) 3
(C) II only (D) 4
(D) II and III only

21. Consider a matrix P whose only eigenvectors are the 22. Which one of the following statements is FALSE?
multiples of [arrayl 1 \\ 4 array] Consider the following
(A) Context-free grammar can be used to specify both
statements. (I) P does not have an inverse (II) P has a
lexical and syntax rules.
repeated eigenvalue (III) P cannot be diagonalized Which
(B) Type checking is done before parsing.
one of the following options is correct?
(C) High-level language programs can be translated to
(A) Only I and III are necessarily true
different Intermediate Representations.
(B) Only II is necessarily true
(D) Arguments to a function can be passed using the
(C) Only I and II are necessarily true program stack.
(D) Only II and III are necessarily true

23. Suppose a polynomial time algorithm is discovered 24. Consider a token ring network with a length of 2 km
that correctly computes the largest clique in a given having 10 stations including a monitoring station. The
graph. In this scenario, which one of the following propagation speed of the signal is 2 × 108 m/s and the
represents the correct Venn diagram of the complexity token transmission time is ignored. If each station is
classes P, NP and NP Complete (NPC)? allowed to hold the token for 2 μsec, the minimum time
for which the monitoring station should wait (in
μsec)before assuming that the token is lost is _______.

(A) 30

(B) 29

(C) 31
(A)
(D) 28

(B)

(C)

(D)

25. In a balanced binary search tree with n elements, 26. Consider the following five disk access requests of
what is the worst case time complexity of reporting all the form (request id, cylinder number) that are present in
elements in range [a, b]? Assume that the number of the disk scheduler queue at a given time. (P, 155), (Q,
reported elements is k. 85), (R, 110), (S, 30), (T, 115) Assume the head is
positioned at cylinder 100. The scheduler follows
(A) θ(log n)
Shortest Seek Time First scheduling to service the
(B) θ(log n + k)
requests. Which one of the following statements is
(C) θ(k log n) FALSE?
(D) θ(n log k)
(A) T is serviced before P.

(B) Q is serviced after S, but before T.

(C) The head reverses its direction of movement between
servicing of Q and P

(D) R is serviced before P

27. Let G be a graph with n vertices and m edges. What is 28. Which one of the following is TRUE?
the tightest upper bound on the running time of Depth
(A) The language L = { anbn | n ≥ 0 } is regular.
First Search on G, when G is represented as an adjacency
(B) The language L = { an | n is prime} is regular.
matrix ?
(C) The language L = { w | w has 3k + 1 b's for some k ∈ N
(A) Θ(n)
with Σ = {a, b}} is regular.
(B) Θ(n + m)
(D) The language L = { ww| ∈ Σ* with Σ = {0, 1}} is
(C) Θ(n2) regular.
(D) Θ(m2)

29. A computer system with a word length of 32 bits has 30. Consider three machines M, N, and P with IP
a 16 MB byte-addressable main memory and a 64 KB, 4- addresses 100.10.5.2, 100.10.5.5, and 100.10.5.6
way set associative cache memory with a block size of respectively. The subnet mask is set to 255.255.255.252
256 bytes. Consider the following four physical addresses for all the three machines. Which one of the following is
represented in hexadecimal notation. A1 = 0x42C8A4, true?
A2=0x546888, A3 = 0x6A289C, A4= 0x5E4880 Which one
(A) M, N, and P all belong to the same subnet
of the following is TRUE?
(B) Only M and N belong to the same subnet
(A) A1 and A4 are mapped to different cache sets.
(C) Only N and P belong to the same subnet
(B) A2 and A3 are mapped to the same cache set.
(D) M, N, and P belong to three different subnets
(C) A3 and A4 are mapped to the same cache set.

(D) A1 and A3 are mapped to the same cache set.

31. When two 8-bit numbers A7...A0 and B7....B0 in 2's 32. The minimum number of comparisons required to find
complement representation (with A0 and B0 as the least the minimum and the maximum of 100 numbers is
significant bits) are added using a ripple-carry adder. the _________________.
sum bits obtained are S7....S0 and the bits are C7……….
(A) 146.1 to 147.1
C0 . An overflow is said to have occurred if:
(B) 147.1 to 148.1
(A) The carry C7 bit is 1.
(C) 143.1 to 144.1
(B) All the carry bits (C7………. C0) is 1.
(D) 140.1 to 141.2
(C) (A7.B7.S̅7 + A̅7.B̅7.S7) is 1.

(D) (A0.B0.S̅0 + A̅0.B̅0.S0) is 1.

33. Consider the following context-free grammar over
the alphabet Σ= {a, b, c} with S as the start symbol: S
—> abScT I abcT Which one of the following represents
the language generated by the above grammar?

(A) {(ab)n (cb)n|n>=1}

(B) \(a b)n c bm1 c bm2 … c bmn | n, m , m , …, m ≥ 1\
1 2 n
(C) \(a b)n(c bm)n | m, n ≥ 1\

(D) \(a b)n(c bn)m | m, n ≥ 1\

34. Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?

(A) R has a nontrivial functional dependency X → A, where X is not a superkey and A is a prime attribute.

(B) R has a nontrivial functional dependency X → A, where X is not a superkey and A is a non-prime attribute and X is not a
proper subset of any key.

(C) R has a nontrivial functional dependency X → A, where X is not a superkey and A is a non-prime attribute and X is a proper
subset of some key.

(D) A cell in R holds a set instead of an atomic value.

35. Which of the following are used to generate a 36. Given the following two statements: S1: Every table
message digest by the network security protocols ? (P) with two single-valued attributes is in 1NF, 2NF, 3NF and
RSA (Q) SHA-1 (R) DES (S) MD5 BCNF. S2: AB → C, D → E, E → C is a minimal cover for the
set of functional dependencies AB → C, D → E, AB → E, E →
(A) P and R only
C. Which one of the following is CORRECT?
(B) Q and R only
(A) S1 is TRUE and S2 is FALSE.
(C) Q and S only
(B) Both S1 and S2 are TRUE.
(D) R and S only
(C) S1 is FALSE and S2 is TRUE.

(D) Both S1 and S2 are FALSE.

37. Consider the following pseudo code. What is the total 38. Consider the language \an | n ≥ 0\ \an bn | n ≥ 0\ and
number of multiplications to be performed? D = 2 for i = the following statements. I. L is deterministic context-
1 to n do for j = i to n do for k = j + 1 to n do D = D * 3 free. II. L is context-free but not deterministic context-
free. III. L is not LL(k) for any k. Which of the above
(A) Half of the product of the 3 consecutive integers.
statements is/are TRUE?
(B) One-third of the product of the 3 consecutive integers.
(A) I only
(C) One-sixth of the product of the 3 consecutive integers.
(B) II only
(D) None of the above.
(C) I and III only

(D) III only

39. Consider the following set of processes that need to 40. Consider the following intermediate program in three
be scheduled on a single CPU. All the times are given in address code: p=a-b q=p*c p=u*v q=p+q Which one of
milliseconds. the following corresponds to a static single assignment

Process Name Arrival Time Execution Time form of the above code?

A 0 6 (A) arrayl p =a-b \\ q =p * c \\ p =u * v \\ q =p +q array
1 1 1 1 1 1 1
B 3 2 (B) aligned &P =a-b\\ &q =p * c\\ &P =u * v\\ &q =p +q
3 4 3 4 5 4 4
C 5 4 aligned
D 7 6 (C) aligned &p =a-b\\ &q =p * c\\ &p =u * v\\ &q2=p4+q
1 1 2 3 3
E 10 3 aligned
Using the shortest remaining time first scheduling
(D) aligned &p =a-b\\ &q =p * c\\ &P =u * v\\ &q =p+q
1 1 2 2
algorithm, the average process turnaround time (in
aligned
msec) is ____________________.

(A) 7.2

(B) 7.4

(C) 7.5

(D) 7.9

41. Consider the C code fragment given below. typedef 42. Consider a selective repeat sliding window protocol
struct node { int data; node* next; node; void join (node* that uses a frame size of 1 KB to send data on a 1.5 Mbps
m, node* ){ Node * p = n; while (p—>next != NULL) P = link with a one-way latency of 50 msec. To achieve a link
p—>next ; } p—>next= m; } Assuming that m and n point utilization of 60%, the minimum number of bits required
to valid NULL-terminated linked lists. invocation of joint to represent the sequence number field is ________.
will
(A) 5
(A) append list m to the end of list n for all inputs. (B) 4
(B) either cause a null pointer dereference or append list m (C) 3
to the end of list n.
(D) 2
(C) cause a null pointer dereference for all inputs.

(D) append list n to the end of list m for all inputs.

43. Consider the following snapshot of a system running �� concurrent processes. Process �� is holding ���� instances of a
resource R, 1 ≤ �� ≤ ��. Assume that all instances of R are currently in use. Further, for all ��, process �� can place a request
for at most ���� additional instances of R while holding the ���� instances it already has. Of the �� processes, there are exactly
two processes �� and �� such that ���� = ���� = 0. Which one of the following conditions guarantees that no other process apart
from �� and �� can complete execution?

(A) ���� + ���� Min {���� | 1 ≤ �� ≤ �� , k ≠p, k ≠q}

(B) ���� + ���� Max {���� | 1 ≤ �� ≤ �� , k ≠p, k≠q}

(C) Min (���� , ����) ≥ Min {���� | 1 ≤ �� ≤ �� , k ≠p, k≠q}

(D) Min (����, ����) ≤ Max {���� | 1 ≤ �� ≤ �� , k ≠p, k≠q}

44. Suppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in
its subnet. Which one of the following techniques can be used for this?

(A) X sends an ARP request packet to the local gateway’s IP address which then finds the MAC address of Y and sends to X

(B) X sends an ARP request packet to the local gateway’s MAC address which then finds the MAC address of Y and sends to X

(C) X sends an ARP request packet with broadcast MAC address in its local subnet

(D) X sends an ARP request packet with broadcast IP address in its local subnet

45. Consider the relations r(A, B) and s(B, C), where s.B
is a primary key and r.B is a foreign key referencing s.B.
Consider the query Q: �� ⋈ (��
(��)) Let LOJ denote the natural
��5
left outer-join operation. Assume that r and s contain no
null values. Which one of the following queries is NOT
equivalent to Q?

(A) ��(�� ⋈ ��)
��5
(B) ��(�� ������ ��)
��5
(C) �� ������
(��)) (��
��5
(D) ��(��) ������ ��
��5

46. Let G = (V, E) be a directed, weighted graph with weight function w: E → R. For some function f : V → R, for each
edge (u, v) ∈ E, define w'(u,v) as Which one of the options completes the following sentence so that it is TRUE? "The
shortest paths in G under w are shortest paths under w' too,_________”

(A) for every f : V → R

(B) if and only if u V , f (u) is positive

(C) if and only if u V , f (u) is negative

(D) if and only if f (u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight
from s to every vertex of G

47. Consider the following grammar and the semantic
actions to support the inherited type declaration
attributes. Let ��, ��, ��, ��, ��, and ��be the placeholders for
1 2 3 4 5 6
the non-terminals D, T, L or L1 in the following table:
Which one of the following are the appropriate choices
for ��1, ��2, ��3 and ��4?

(A) ��= �� , =
�� ��, =
�� ��1, =
�� ��
1 2 3 4
(B) ��= �� , =
�� ��, =
�� ��1, =
�� ��
1 2 3 4
(C) ��= �� , =
�� ��, =
�� ��1, =
�� ��
1 2 3 4
(D) ��= �� , =
�� ��, =
�� ��, =
�� ��
1 2 3 4 1

48. Consider the first-order logic sentence �� ≡ ∃��∃��∃��∀��∀��∀��∀�� ��(��, ��, ��, ��, ��, ��, ��) where ��(��, ��, ��, ��, ��, ��, ��) is
formula using only predicate symbols, and possibly equality, but no function symbols. Suppose �� has a model with a
universe containing 7 elements. Which one of the following statements is necessarily true?

(A) There exists at least one model of �� with universe of size less than or equal to 3.

(B) There exists no model of �� with universe of size less than or equal to 3.

(C) There exists no model of �� with universe of size greater than 7.

(D) Every model of �� has a universe of size equal to 7.

49.  Which one of the following is a closed form
expression for the generating function of the sequence
{a }, where a = 2n + 3 for all n = 0, 1, 2,… ?
n n

(A) 3/(1-x)2
50.
(B) 3x/(1-x)2

(C) (2-x)/(1-x)2
(A) I only
(D) (3-x)/(1-x)2
(B) II only

(C) Both I and II

(D) Neither I nor II

51. Which one of the following propositional logic
formulas is TRUE when exactly two of p, q, and r are
TRUE?

(A) ((p ↔ q) ∧ r ∨ (p ∧ q ∧ ∼ r)

(B) (∼ (p ↔ q) ∧ r ∨ (p ∧ q ∧ ∼ r)

(C) ((p → q) ∧ r ∨ (p ∧ q ∧ ∼ r)

(D) (∼ (p ↔ q) ∧ r ∧ (p ∧ q ∧ ∼ r)

52. In an Entity-Relationship (ER) model, suppose �� is a many-to-one relationship from entity set E1 to entity set E2.
Assume that E1 and E2 participate totally in �� and that the cardinality of E1 is greater than the cardinality of E2. Which
one of the following is true about ��?

(A) Every entity in E1 is associated with exactly one entity in E2.

(B) Some entity in E1 is associated with more than one entity in E2.

(C) Every entity in E2 is associated with exactly one entity in E1.

(D) Every entity in E2 is associated with at most one entity in E1.

53. In a system, there are three types of resources: E, F and G. Four processes P , P , P and P execute concurrently.
0 1 2 3
At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given
below. For example, Max[P ,F] is the maximum number of instances of F that P would require. The number of
2 2
instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation.
Consider a state of the system with the Allocation matrix as shown below, and in which 3instances of E and 3
instances of F are the only resources available. From the perspective of deadlock avoidance, which one of the
following is true?

(A) The system is in safe state.

(B) The system is not in safe state, but would be safe if one more instance of E were available

(C) The system is not in safe state, but would be safe if one more instance of F were available

(D) The system is not in safe state, but would be safe if one more instance of G were available

54. Which one of the following is FALSE ? 55. Consider the following statements about process
state transitions for a system using preemptive
(A) User level threads are not scheduled by the kernel.
scheduling. I. A running process can move to ready state.
(B) When a user level thread is blocked, all other threads of
II. A ready process can move to running state. III. A
its process are blocked.
blocked process can move to running state. IV. A blocked
(C) Context switching between user level threads is faster process can move to ready state. Which of the above
than context switching between kernel level threads statements are TRUE?
(D) Kernel level threads cannot share the code segment.
(A) I, II, and Ill only

(B) II and Ill only

(C) I, II, and IV only

(D) I, II, III, and IV

56. Consider the following C program: The output of the 57. What is the worst case time complexity of inserting n
program above is elements into an empty linked list, if the linked list needs
to be maintained in sorted order?
(A) Hi Bye Bye Hi

(B) Hi Bye Hi Bye (A) θ(n)

(C) Bye Hi Hi Bye (B) θ(n log n)

(D) Bye Hi Bye Hi (C) θ(n2

(D) θ(1)

58. Which of the following protocol pairs can be used to 59. Consider the first order predicate formula ��: ∀�� [(∀�� ��|�� ⇒
send and retrieve e-mails (in that order)? ((�� = ��) ∨ (�� = 1))) ⇒ ∃�� (�� > ��) ∧ (∀�� ��|�� ⇒ ((�� = ��) ∨ (�� = 1
denotes that ‘�� divides ��’, where �� and �� are integers.
(A) IMAP, POP3
Consider the following sets: S1. {1,2,3, … , 100} S2. Set
(B) SMTP, POP3
of all positive integers S3. Set of all integers Which of the
(C) SMTP, MIME above sets satisfy ��?
(D) IMAP, SMTP
(A) S1 and S2

(B) S1 and S3

(C) S2 and S3

(D) S1, S2 and S3

60. Threads of a process share 61. Let denote the set of all functions f : 0,14 → 0,1.
Denote by N the number of functions from S to the set
(A) global variables but not heap.
0,1. The value of log log N is ________ .
2 2
(B) heap but not global variables.
(A) 17
(C) neither global variables nor heap.
(B) 16
(D) both heap and global variables,
(C) 19

(D) 20

62. Consider the following three statements about link state and distance vector routing protocols, for a large network
with 500 network nodes and 4000 links. [S1] The computational overhead in link state protocols is higher than in
distance vector protocols. [S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not
a link state protocol. [S3] After a topology change, a link state protocol will converge faster than a distance vector
protocol. Which one of the following is correct about S1, S2, and S3 ?

(A) S1, S2, and S3 are all true.

(B) S1, S2, and S3 are all false.

(C) S1 and S2 are true, but S3 is false.

(D) S1 and S3 are true, but S2 is false.

63. Let N be the set of natural numbers. Consider the 64. There are n unsorted arrays: A , A , …, A . Assume
1 2 n
following sets. P: Set of Rational numbers (positive and that n is odd. Each of A , A , …, A contains n distinct
1 2 n
negative) Q: Set of functions from {0, 1} to N R: Set of elements. There are no common elements between any
functions from N to {0, 1} S: Set of finite subsets of N. two arrays. The worst-case time complexity of computing
Which of the sets above are countable? the median of the medians of A , A , …, A is
1 2 n

(A) Q and S only (A) O(n)

(B) P and S only (B) O(n log n)

(C) P and R only (C) O(n2)

(D) P, Q and S only (D) Ω(n2log n)

65. Recall that Belady's anomaly is that the page-fault
rate may increase as the number of allocated frames
increase. Now. consider the following statements: S1:
Random page replacement algorithm (where a page
chosen at random is replaced) suffers from Belady's
anomaly S2: LRU page replacement algorithm suffers
from Belady's anomaly Which of the following is
CORRECT?

(A) S1 is true, S2 is true

(B) S1 is true, S2 is false

(C) S1 is false, S2 is true

(D) S1 is false, S2 is false

ANSWER KEY

1. (B) 2. (C) 3. (D) 4. (B) 5. (B) 6. (A) 7. (D)

8. (D) 9. (C) 10. (B) 11. (C) 12. (C) 13. (A) 14. (D)

15. (C) 16. (B) 17. (D) 18. (A) 19. (B) 20. (A) 21. (D)

22. (B) 23. (D) 24. (D) 25. (B) 26. (B) 27. (C) 28. (C)

29. (B) 30. (C) 31. (C) 32. (B) 33. (B) 34. (A) 35. (C)

36. (A) 37. (C) 38. (C) 39. (A) 40. (B) 41. (B) 42. (A)

43. (A) 44. (C) 45. (C) 46. (A) 47. (A) 48. (A) 49. (D)

50. (C) 51. (B) 52. (A) 53. (A) 54. (D) 55. (C) 56. (A)

57. (C) 58. (B) 59. (C) 60. (D) 61. (B) 62. (D) 63. (D)

64. (C) 65. (B)