GATE Sample Paper for Computer Science

Sample Paper aglase .co

CS: Computer Sc. and Information Technology

Q.No. 1 Which one of the following regular expressions represents the set of all binary strings with an odd
number of 1' s?

(A) ((0 + 1) 1(0 + 1) 1) 10
∗ ∗ ∗ ∗

(B) (0 10 10 ) 0 1
∗ ∗ ∗ ∗ ∗

(C) 10 (0 10 10 )
∗ ∗ ∗ ∗ ∗

(D) (0 10 10 ) 10
∗ ∗ ∗ ∗ ∗

Q.No. 2 Consider the following grammar and the semantic actions to support the inherited type declaration
attributes. Let 𝑋1, 𝑋2, 𝑋3, 𝑋4, 𝑋5, and 𝑋6 be the placeholders for 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 = 𝐿 , 𝑋2 = 𝑇, 𝑋3 = 𝐿1, 𝑋4 = 𝐿

(B) 𝑋1 = 𝑇 , 𝑋2 = 𝐿, 𝑋3 = 𝐿1, 𝑋4 = 𝑇

(C) 𝑋1 = 𝐿 , 𝑋2 = 𝐿, 𝑋3 = 𝐿1, 𝑋4 = 𝑇

(D) 𝑋1 = 𝑇 , 𝑋2 = 𝐿, 𝑋3 = 𝑇, 𝑋4 = 𝐿1

Q.No. 3 Which one of the following is used to represent the supporting many-one relationships of a weak entity
set in an entity-relationship diagram?

(A) Diamonds with double/bold border

(B) Rectangles with double/bold border

(C) Ovals with double/bold border

(D) Ovals that contain underlined identifiers

Q.No. 4 When two 8-bit numbers A7...A0 and B7....B0 in 2's complement representation (with A0 and B0 as
the least significant bits) are added using a ripple-carry adder. the sum bits obtained are S7....S0 and the bits are
C7………. C0 . An overflow is said to have occurred if:

(A) The carry C7 bit is 1.

(B) All the carry bits (C7………. C0) is 1.

(C) (A7.B7.S̅7 + A̅7.B̅7.S7) is 1.

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

Q.No. 5 A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the
alphabet {a,b,c}. 𝑇1: 𝑎? (𝑏|𝑐)∗𝑎 𝑇2: 𝑏? (𝑎|𝑐)∗𝑏 𝑇3: 𝑐? (𝑏|𝑎)∗𝑐 Note that ‘x?’ means 0 or 1 occurrence of the
symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string
𝑏𝑏𝑎𝑎𝑐𝑎𝑏𝑐 is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

(A) 𝑇1𝑇2𝑇3

(B) 𝑇1𝑇1𝑇3

(C) 𝑇2𝑇1𝑇3

(D) 𝑇3𝑇3

Q.No. 6 Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights Of T are:
Note: The height of a tree with a single node is 0.

(A) 4 and 15 respectively

(B) 3 and 14 respectively

(C) 4 and 14 respectively

(D) 3 and 15 respectively

Q.No. 7 Consider the following statements about the functionality of an IP based router. A router does not
modify the IP packets during forwarding. I. It is not necessary for a router to implement any routing protocol. II.
A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming
IP packet. Which of the above statements is/are TRUE?

(A) I and II only

(B) I only

(C) II and Ill only

(D) II only

Q.No. 8 Let c1,..........,cn be scalars, not all zero, such that ∑ where ai, are column vectors in Rn
n
ci a i = 0
t=1

Consider the set of linear equations Ax=b Where A= b = ∑ . The set of operations has:
n
ai
i=1

(A) a unique solution at x = Jn where J denotes a n -dimensional vector of all 1.

(B) no solution

(C) Infinitely many solutions.

(D) Finitely many solutions.

Q.No. 9 The statement (-p) => (-q) is logically equivalent to which of the statements below? I. p => q II. q => p
III. (-q) v p IV. (-p) v q

(A) I only

(B) I and IV only

(C) II only

(D) II and III only

Q.No. 10 Consider the following two statements about database transaction schedules: I. Strict two-phase
locking protocol generates conflict serializable schedules that are also recoverable. II. Timestamp-ordering
concurrency control protocol with Thomas’ Write Rule can generate view serializable schedules that are not
conflict serializable. Which of the above statements is/are TRUE?

(A) I only

(B) II only

(C) Both I and II

(D) Neither I nor II

Q.No. 11 For Σ = {𝑎, 𝑏}, let us consider the regular language 𝐿 = { 𝑥 |𝑥 = 𝑎2+3𝑘 or 𝑥 = 𝑏10+12𝑘,𝑘 ≥ 0}. Which one
of the following can be a pumping length (the constant guaranteed by the pumping lemma) for 𝐿 ?

(A) 3

(B) 5

(C) 9

(D) 24

Q.No. 12 Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to
N. Which one of the following is necessarily true?

(A) 𝑘 ≥ 2𝑛

(B) 𝑘 ≥ 𝑛

(C) 𝑘 ≤ 𝑛2

(D) 𝑘 ≤ 2𝑛

Q.No. 13 A computer system with a word length of 32 bits has a 16 MB byte-addressable main memory and a
64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider the following four
physical addresses represented in hexadecimal notation. A1 = 0x42C8A4, A2=0x546888, A3 = 0x6A289C, A4=
0x5E4880 Which one of the following is TRUE?

(A) A1 and A4 are mapped to different cache sets.

(B) A2 and A3 are mapped to the same cache set.

(C) A3 and A4 are mapped to the same cache set.

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

1
Q.No. 14 Consider a matrix P whose only eigenvectors are the multiples of [ ] Consider the following
4

statements. (I) P does not have an inverse (II) P has a repeated eigenvalue (III) P cannot be diagonalized Which
one of the following options is correct?

(A) Only I and III are necessarily true

(B) Only II is necessarily true

(C) Only I and II are necessarily true

(D) Only II and III are necessarily true

Q.No. 15 Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-
flop is connected to the input Of the T flip-flop and the output Of the T flip-flop is connected to the input of the

D flip-flop. Initially, both Qo and QI
are set to I (before the 1 clock cycle). The outputs

(A) Q1 Q0 after the 3rd are 11 and after the 4th cycle are 00 respectively.

(B) Q1 Q0 after the 3rd cycle are 11 and after the cycle are 01 respectively.

(C) Q1 Q0 after the 3rd cycle are 00 and after the 4th cycle are 11 respectively.

(D) Q1 Q0 after the 3rd cycle are 01 and after the cycle are 01 respectively.

Q.No. 16 A sender S sends a message m to receiver R. which is digitally signed by S with its private key. In this
scenario. one or more of the following security violations can take place. (I) S can launch a birthday attack to
replace m with a fraudulent message. (II) A third party attacker can launch a birthday attack to replace m with a
fraudulent message. (Ill) R can launch a birthday attack to replace m with a fraudulent message. Which of the
following are possible security violations?

(A) (I) and (II) only

(B) (I) only

(C) (II) only

(D) (II) and (III) only

Q.No. 17 Let G — (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are
positive and distinct. Consider the following statements: (l) Minimum Spanning Tree Of G is always unique.
(II) Shortest path between any two vertices Of G is always unique. Which of the above statements is/are
necessarily true?

(A) (I) only

(B) (II) only

(C) both (I) and (II)

(D) neither (I) nor (II)

Q.No. 18 Consider the following C program. The
output of this program is:

(A) 0, c

(B) 0, a+2

(C) '0', 'a+2'

(D) '0', 'c'

Q.No. 19 Consider the language {a |n ≥ 0} ∪ {a b |n ≥ 0} and the following statements. I. L is
n n n

deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?

(A) I only

(B) II only

(C) I and III only

(D) III only

Q.No. 20 Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate
formula without any free occurrence of x.

(A) ∀x (p(x ) ∨ W) ≡ ∀x p(x ) ∨ W

(B) ∃x (p(x ) ∧ W) ≡ ∃x p(x ) ∧ W

(C) ∀x (p(x ) → W) ≡ ∀x p(x ) → W

(D) ∃x (p(x ) → W) ≡ ∀x p(x ) → W

Q.No. 21 What is the worst case time complexity of inserting n elements into an empty linked list, if the linked
list needs to be maintained in sorted order?

(A) θ(n)

(B) θ(n log n)

(C) θ(n2

(D) θ(1)

Q.No. 22 Let A and B be finite alphabets and let # be a symbol outside both .4 and B. Let f be a total function
from A toB . We say fis computable if there exists a Turing machine M which given an input x in A , always
halts with fix) on its tape. Let L denote the language {x# f(x) | x ∈ A*} which of the following statements is
true:

(A) fis computable if and only if Lf is recursive.

(B) fis computable if and only if Lf is recursively enumerable.

(C) If fis computable then Lf is recursive. but not conversely.

(D) If fis computable then Lf is recursively enumerable. but not conversely.

Q.No. 23 A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail
pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by
inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the
most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

(A) θ(1), θ(1)

(B) θ(1), θ(n)

(C) θ(n), θ(1)

(D) θ(n), θ(n)

Q.No. 24 Let 𝐺 be an arbitrary group. Consider the following relations on 𝐺: 𝑅1: ∀𝑎, 𝑏 ∈ 𝐺, 𝑎 𝑅1𝑏 if and only
if ∃𝑔 ∈ 𝐺 such that 𝑎 = 𝑔-1𝑏𝑔 𝑅2: ∀𝑎, 𝑏 ∈ 𝐺, 𝑎 𝑅2𝑏 if and only if 𝑎 = 𝑏-1 Which of the above is/are equivalence
relation/relations?

(A) 𝑅1 and 𝑅2

(B) 𝑅1 only

(C) 𝑅2 only

(D) Neither 𝑅1 nor 𝑅2

Q.No. 25 Assume that multiplying a matrix G1 of dimension 𝑝 × 𝑞 with another matrix G2 of dimension 𝑞 × 𝑟
requires 𝑝𝑞𝑟 scalar multiplications. Computing the product of n matrices G1G2G3…Gn can be done by
parenthesizing in different ways. Define Gi, Gi+1 as an explicitly computed pair for a given parenthesization if
they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6 using
parenthesization (G1(G2G3))(G4(G5G6)), G2G3 and G5G6 are the only explicitly computed pairs. Consider a
matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2×25, 25×3,
3×16, 16×1 and 1×1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of
scalar multiplications, the explicitly computed pairs is/are

(A) F1F2 and F3F4 only

(B) F2 F3 only

(C) F3F4only

(D) F1F2 and F4 F5 only

Q.No. 26 In a database system. unique timestamps are assigned to each transaction using Lamport's logical
clock. Let TS(T1) and TS(T2) be the timestamps of transactions T1 and T2 respectively. Besides.T1 holds a
lock on the resource R, and T2 has requested a conflicting lock on the same resource R. The following
algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with
the same timestamp. if TS(T2) < TS(T1) then Tl is killed else T2 waits. Assume any transaction that is not killed
terminates eventually, which of the following is TRUE about the database system that uses the above algorithm
to prevent deadlocks?

(A) The database system is both deadlock-free and starvation-free.

(B) The database system is deadlock-free, but not starvation-free.

(C) The database system is starvation-free. but not deadlock-free.

(D) The database system is neither deadlock-free nor starvation-free.

Q.No. 27 Consider the C functions foo and bar given below: int foo (int val) { int x = 0; while (val > O) { x= x
+ foo (val - -); } return val; } int bar (int val) { int x = 0; while (val > O) x = x + bar (val-1) ; } return val; }
Invocations of foo (3) and bar (3) will result in:

(A) Return of 6 and 6 respectively.

(B) Infinite loop and abnormal termination respectively.

(C) Abnormal tennination and infinite loop respectively.

(D) Both terminating abnormally.

Q.No. 28 The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let
i = n - f. The range of decimal values for X in this representation is

(A) 2-f to 2i

(B) 2-f to (2i - 2-f)

(C) 0 to 2i

(D) 0 to (2i - 2-f)

Q.No. 29 In a balanced binary search tree with n elements, what is the worst case time complexity of reporting
all elements in range [a, b]? Assume that the number of reported elements is k.

(A) θ(log n)

(B) θ(log n + k)

(C) θ(k log n)

(D) θ(n log k)

Q.No. 30 Consider three 4-variable functions f1, f2, and f3, which are expressed in sum-of-minterms as f1 = Σ
(0, 2, 5, 8, 14), f2 =Σ(2, 3, 6, 8, 14, 15), f3= Σ(2, 7, 11, 14) For the following circuit with one AND gate and one

XOR gate, the output function f can be expressed as:

(A) Σ (7, 8, 11)

(B) Σ (2, 7, 8, 11, 14)

(C) Σ (2, 14)

(D) Σ (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)

Q.No. 31 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}

Q.No. 32 Consider the functions I. e-x II. x2 - sin x III. √x 3
+ 1 Which of the above functions is/are increasing
everywhere in [0, 1]?

(A) III only

(B) II only

(C) II and III only

(D) I and III only

Q.No. 33 Consider a database that has the relation schemas EMP(EmpId, EmpName, Deptld), and
DEPT(DeptName, Deptld). Note that the Deptld can be permitted to be NULL in the relation EMP. Consider the
following queries on the database expressed in tuple relational calculus. (I)
{t|∃u ∈ EMP(t[ EmpName ] = u[ EmpName ] ∧ \f orallv ∈ DEPT(t[ DeptId ] ≠ v[ DeptId ]))} (II)

{t|∃u ∈ EMP(t[ EmpName ] = u[ EmpName ] ∧ ∃v ∈ DEPT(t[ DeptId ] ≠ v[ DeptId ]))} (III)

{t|∃u ∈ E M P (t[ EmpName ] = u[ EmpName ] ∧ ∃v ∈ D E P T(t[ DeptId ] = v[ DeptId ]))}

(A) (I) and (II) only

(B) (I) and (III) only

(C) (II) and (III) only

(D) (I), (II) and (III)

Q.No. 34 Consider a process executing on an operating system that uses demand paging. The average time for a
memory access in the system is M units if the corresponding memory page is available in memory, and D units
if the memory access causes a page fault. It has been experimentally measured that the average time taken for a
memory access in the process is X units. Which one of the following is the correct expression for the page fault
rate experienced by the process?

(A) (D – M) / (X – M)

(B) (X – M) / (D – M)

(C) (D – X) / (D – M)

(D) (X – M) / (D – X)

Q.No. 35 Consider the following two tables and four queries in SQL.

Which one of the queries above is certain to have an output
that is a superset of the outputs of the other three queries?

(A) Query 1

(B) Query 2

(C) Query 3

(D) Query 4

Q.No. 36 Consider the following intermediate program in three address code: p=a-b q=p*c p=u*v q=p+q Which
one of the following corresponds to a static single assignment form of the above code?

p1 = a − b

q1 = p1 ∗ c
(A)
p1 = u ∗ v

q1 = p1 + q1

P3 = a − b

q4 = p3 ∗ c
(B)
P4 = u ∗ v

q5 = p4 + q4

p1 = a − b

q1 = p2 ∗ c
(C)
p3 = u ∗ v

q2 = p4 + q3

p1 = a − b

q1 = p ∗ c
(D)
P2 = u ∗ v

q2 = p + q

Q.No. 37 Threads of a process share

(A) global variables but not heap.

(B) heap but not global variables.

(C) neither global variables nor heap.

(D) both heap and global variables,

Q.No. 38 Consider the first-order logic sentence 𝜑 ≡ ∃𝑠∃𝑡∃𝑢∀𝑣∀𝑤∀𝑥∀𝑦 𝜓(𝑠, 𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦) where 𝜓(𝑠, 𝑡, 𝑢, 𝑣,
𝑤, 𝑥, 𝑦) is a quantifier-free first-order logic 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.

Q.No. 39 Let u and v be two vectors in R2 whose Euclidean norms satisfy ∥u∥=2∥v∥. What is the value of ∝
such that w=u+∝v bisects the angle between u and v?

(A) 2

(B) ½

(C) 1

(D) -½

7 5

Q.No. 40 The value of lim x →1
x

x
3
−2x

−3x
2
+1

+2

(A) is 0

(B) is -1

(C) is 1

(D) does not exist.

Q.No. 41 Let 𝑈 = {1,2, … , 𝑛}. Let 𝐴 = {(𝑥, 𝑋)|𝑥 ∈ 𝑋, 𝑋 ⊆ 𝑈}. Consider the following two statements on |𝐴|. I. |
𝐴| = 𝑛2𝑛−1 II. |𝐴| = ∑ 𝑘(𝑛) 𝑛𝑘=1 Which of the above statements is/are TRUE?

(A) Only I

(B) Only II

(C) Both I and II

(D) Neither I nor II

Q.No. 42 Consider the Boolean function z(a, b, c).

Which one of the following
minterm lists represents the circuit given above?

(A) z = ∑(0, 1, 3, 7)

(B) z = ∑(1, 4, 5, 6, 7)

(C) z = ∑(2, 4, 5, 6, 7)

(D) z = ∑(2, 3, 5)

Q.No. 43 Consider the unsigned 8-bit fixed point binary number representation below,
b b_ bs b b , b , b b where the position of the binary point is between b3 and b2. Assume b7 is the most
7 4 3 2 1 0

significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above
representation: (i) 31.500 (ii) 0.875 (iii) 12.100 (iv) 3.001 Which one of the following statements is true?

(A) None of (i), (ii), (iii), (iv) can be exactly represented

(B) Only (ii) cannot be exactly represented

(C) Only (iii) and (iv) cannot be exactly represented

(D) Only (i) and (ii) cannot be exactly represented

Q.No. 44 Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?

(A) IMAP, POP3

(B) SMTP, POP3

(C) SMTP, MIME

(D) IMAP, SMTP

Q.No. 45 Let A and B be two n x n matrices over real numbers. Let rank(M) and det(M) denote the rank and
determinant of a matrix M, respectively. Consider the following statements. I. rank( AB) = rank( A) rank( B) II.
det( AB) = det( A) det( B) III. rank( A + B) ≤ rank( A) + rank( B) IV. det( A + B) ≤ det(A) + det( B) Which of
the above statements are TRUE?

(A) I and II only

(B) I and IV only

(C) II and Ill only

(D) Ill and IV only

Q.No. 46 Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all non-
regular languages over the alphabet {0,1} Which of the above sets are uncountable?

(A) S1 and S2

(B) S3 and S4

(C) S2 and S3

(D) S1 and S4

Q.No. 47 Let G be a simple undirected graph. Let TDbe a depth first search tree of G. Let TB be a breadth first
search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A
cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge
(u,v) of G, if u is at depth i and v is at depth j in TB, then |𝑖 − 𝑗| = 1. Which of the statements above must
necessarily be true?

(A) I only

(B) II only

(C) Both I and II

(D) Neither I nor II

Q.No. 48 What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements
initially ?

(A) θ(n4)

(B) θ(n2)

(C) θ(n2log n)

(D) θ(n3)

Q.No. 49 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.

Q.No. 50 Consider the following C function. void convert(int n){ if(n<0) printf(“%d”,n); else { convert(n/2);
printf(“%d”,n%2); } } Which one of the following will happen when the function convert is called with any
positive integer n as argument?

(A) It will print the binary representation of n and terminate

(B) It will print the binary representation of n in the reverse order and terminate

(C) It will print the binary representation of n but will not terminate

(D) It will not print anything and will not terminate

Q.No. 51 Consider the following languages: I. {𝑎𝑚𝑏𝑛𝑐𝑝𝑑𝑞| 𝑚 + 𝑝 = 𝑛 + 𝑞, where 𝑚, 𝑛, 𝑝, 𝑞 ≥ 0} II. {𝑎𝑚𝑏𝑛𝑐𝑝𝑑𝑞| 𝑚
= 𝑛 and 𝑝 = 𝑞, where 𝑚, 𝑛, 𝑝, 𝑞 ≥ 0} III. {𝑎𝑚𝑏𝑛𝑐𝑝𝑑𝑞| 𝑚 = 𝑛 = 𝑝 and 𝑝 ≠ 𝑞, where 𝑚, 𝑛, 𝑝, 𝑞 ≥ 0} IV. {𝑎𝑚𝑏𝑛𝑐𝑝𝑑𝑞|
𝑚𝑛 = 𝑝 + 𝑞, where 𝑚, 𝑛, 𝑝, 𝑞 ≥ 0} Which of the languages above are context-free?

(A) I and IV only

(B) I and II only

(C) II and III only

(D) II and IV only

Q.No. 52 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

Q.No. 53 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) {{(ab) cb
n m1 m2
cb … cb
mn
|n, m 1 , m 2 , … , m n ≥ 1} }

(C) {{(ab) (cb ) |m , n ≥ 1}}
n m n

(D) {{(ab) (cb ) |m , n ≥ 1}}
n n m

Q.No. 54 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

Q.No. 55 Which one of the following statements is FALSE?

(A) Context-free grammar can be used to specify both lexical and syntax rules.

(B) Type checking is done before parsing.

(C) High-level language programs can be translated to different Intermediate Representations.

(D) Arguments to a function can be passed using the program stack.