GATE Question Papers:
Computer Science and Engineering 2009
Q. No. 1 – 20 Carry One Mark Each
1.
Which one of the following in NOT necessarily a property of a Group?
(A) Commutativity
(B) Associativity
(C) Existence
of inverse for every element (D) Existence of identity
2. What
is the chromatic number of an n-vertex simple connected graph which does not contain
any odd length cycle? Assume n = 2.
(A) 2 (B)
3
(C) n-1
(D) n
3.
Which one of the following is TRUE for any simple connected undirected graph
with more than 2 vertices?
(A) No
two vertices have the same degree.
(B) At
least two vertices have the same degree.
(C) At
least three vertices have the same degree.
(D) All
vertices have the same degree.
4. Consider
the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.
Which
one of the following is TRUE?
(A) R
is symmetric but NOT antisymmetric
(B) R
is NOT symmetric but antisymmetric
(C) R
is both symmetric and antisymmetric
(D) R
is neither symmetric nor antisymmetric
5. (1217)8
is equivalent t o
(A) (1217)16
(B) (028F)16 (C) (2297)10 (D)
(0B17)16
6. What
is the minimum number of gates required to implement the Boolean function
(AB+C) if we have to use only 2-input NOR gates?
(A) 2 (B) 3
(C) 4 (D) 5
7. How
many 32K ´ 1 RAM chips are needed to provide a memory capacity
of 256K-bytes?
(A) 8 (B) 32 (C) 64
(D) 128
8. A
CPU generally handles an interrupt by executing an interrupt service routine
(A) As
soon as an interrupt is raised
(B) By
checking the interrupt register at the end of fetch cycle.
(C) By
checking the interrupt register after finishing the execution of the current
instruction.
(D) By
checking the interrupt register at fixed time intervals.
9. In
which one of t he following page replacement policies, Belady's anomaly may
occur?
(A) FIFO (B) Optimal
(C) LRU (D) MRU
10. The
essential content (s) in each entry of a page table is / are
(A) Virtual
page number
(B) Page
frame number
(C) Both
virtual page number and page frame number
(D) Access
right information
11. What is the
number of swaps required t o sort n elements using selection sort, in the worst
case?
(A) q(n) (B) q(n log n) (C) q(n2) (D) q(n2 log n)
12. S ® aSa|bSb|a|b; The language generated by the above grammar over the
alphabet {a,b} is the set of
(A) All
palindromes.
(B) All
odd length palindromes.
(C) Strings
that begin and end with the same symbol
(D) All
even length palindromes.
13. Which of the following
statement (s) is / are correct regarding Bellman-Ford shortest path algorithm?
P. Always
finds a negative weighted cycle, if one exist s.
Q. Finds
whether any negative weighted cycle is reachable from the source.
(A) P
only (B) Q only
(C) both
P and Q (D) Neither P nor Q
14. Let pA be a problem
that belongs to the class NP. Then which one of the following is TRUE?
(A) There
is no polynomial time algorithm for pA.
(B) If
pA can be
solved deterministically in polynomial time, then P = NP.
(C) If
pA is
NP-hard, then it is NP-complete.
(D) pA may be
undecidable.
15. Which one of
the following languages over the alphabet {0,1} is described by the regular
expression: (0+1)*0(0+1)*0(0+1)*?
(A) The
set of all strings containing the substring 00.
(B) The
set of all strings containing at most two 0's.
(C) The
set of all strings containing at least two 0's.
(D) The
set of all strings that begin and end with either 0 or 1.
16. Which one of
the following is FALSE?
(A) There
is unique minimal DFA for every regular language
(B) Every
NFA can be convert ed to an equivalent PDA.
(C) Complement
of every context-free language is recursive.
(D) Every
nondeterministic PDA can be converted to an equivalent deterministic PDA.
17. Match all
items in Group 1 with correct options from those given in Group 2.
|
Group 1
|
Group 2
|
|
P.
|
Regular expression
|
1.
|
Syntax analysis
|
|
Q.
|
Pushdown automata
|
2.
|
Code generation
|
|
R.
|
Dataflow analysis
|
3.
|
Lexical analysis
|
|
S.
|
Register allocation
|
4.
|
Code optimization
|
(A) P-4.
Q-1, R-2, S-3 (B) P-3, Q-1, R-4, S-2
(C)
P-3, Q-4, R-1, S-2 (D) P-2, Q-1, R-4,
S-3
18. Consider the
program below:
# include
< stdio.h >
int fun(int n, int * f_p) {
int
t, f;
if (n <= 1) {
* f_p =1;
return 1;
}
t = fun (n- 1, f_p);
f =
t+ * f_p;
* f_p = t;
return f;
}
int main() {
int x = 15;
printf
(" % d\ n", fun(5, & x));
return 0;
}
The value
printed is
(A) 6 (B) 8 (C)
14 (D) 15
19. The coupling
between different modules of a software is categorized as follows:
I. Content
coupling II. Common coupling
III. Control
coupling IV Stamp coupling
V. Data
coupling
Coupling between
modules can be ranked in the order of strongest (least desirable) to weakest
(most desirable) as follows:
(A) I-II-III-IV-V (B)
V-IV-III-II-I
(C) I-III-V
-II-IV (D) IV-II-V -III-I
20. Consider the HTML t able definition given
below:
< table
border=1>
<tr>
<td rowspan=2> ab </td>
<td
colspan=2> cd </td>
</tr>
<tr>
<td> ef </td>
<td
rowspan=2> gh </td>
</tr>
<tr>
<td colspan=2> ik </td>
</tr>
</table>
The number of
rows in each column and the number of columns in each row are:
(A) á2,2,3ñ
and á2,3,2ñ (B) á2,2,3ñ
and á2,2,3ñ
(C) á2,3,2ñ
and á2,3,2ñ (D)
á2,3,2ñ and á2,2,3ñ
Q. No. 21 – 56 Carry Two
Marks Each
21. An unbalanced dice
(with 6 faces, numbered from 1 to 6) is thrown. The probability that the face
value is odd is 90% of the probability that the face value is even. The
probability of getting any even numbered face is the same. If the probability that
the face is even given that it is greater than 3 is 0.75, which one of the
following options is closest to the probability that the face value exceeds 3?
(A) 0.453 (B)
0.468 (C) 0.485 (D) 0.492
22. For the
composition table of a cyclic group shown below
|
*
|
a
|
b
|
c
|
d
|
|
a
|
a
|
b
|
c
|
d
|
|
b
|
b
|
a
|
d
|
c
|
|
c
|
c
|
d
|
b
|
a
|
|
d
|
d
|
c
|
a
|
b
|
Which one of
the following choices is correct?
(A) a,
b are generators (B) b, c are generat ors
(C) c,
d are generators (D) d, a are generators
23.
Which one of the following is the most appropriate logical formula to represent
the statement? "Gold and silver ornaments are precious".
The
following notations are used:
G(x):
x is a gold ornament
S(x):
x is a silver ornament
P(x):
x is precious
(A) "x (P(x) ® (G(x) Ù
S (x))) (B) "x ((G(x) Ù
S (x)) ® P (x))
(C) $x
((G (x) Ù S (x)) ® P (x) (D) "x((G(x) Ú S(x)) ®
P (x))
24. The binary operation
c is
defined as follows
|
P
|
Q
|
PcQ
|
|
T
|
T
|
T
|
|
T
|
F
|
T
|
|
F
|
T
|
F
|
|
F
|
F
|
T
|
Which
one of the following is equivalent to P Ú Q?
(A)
ØQc ØP (B) PcØQ
(C)ØPcQ (D)
ØPcØQ
25. 
evaluates
to
(A) 0 (B)
1 (C) ln 2 (D) 1/2
ln 2
26. Consider
the following well-formed formulae:
I. Ø"x (P (x)) II. Ø$x(P
(x)) III. Ø$x(ØP(x)) IV. Ø$x (ØP(x))
(A)
I and III (B) I and IV (C) II and
III (D) II and IV
27. Given the
following state table of an FSM with two states A and B, one input and one
output:
|
Present State A
|
Present State B
|
Input
|
Next State A
|
Next State B
|
Output
|
|
0
|
0
|
0
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
0
|
0
|
|
1
|
0
|
0
|
0
|
1
|
0
|
|
1
|
1
|
0
|
1
|
0
|
0
|
|
0
|
0
|
1
|
0
|
1
|
0
|
|
0
|
1
|
1
|
0
|
0
|
1
|
|
1
|
0
|
1
|
0
|
1
|
1
|
|
1
|
1
|
1
|
0
|
0
|
1
|
If
the initial state is A = 0, B=0, what is the minimum length of an input string
which will take the machine to the state A=0, B=1 with Output=1?
(A)
3 (B) 4 (C) 5 (D)
6
28. Consider a 4
stage pipeline processor. The number of cycles needed by the four instructions
I1, I2, I3, I4 in stages S1, S2, S3, S4 is shown below:
|
|
S1
|
S2
|
S3
|
S4
|
|
I1
|
2
|
1
|
1
|
1
|
|
I2
|
1
|
3
|
2
|
2
|
|
I3
|
2
|
1
|
1
|
3
|
|
I4
|
1
|
2
|
2
|
2
|
What is the
number of cycles needed to execute the following loop?
For (i=1 to
2) {I1; I2; I3; I4;}
(A) 16
(B) 23 (C) 28 (D)
30
29. Consider
a 4-way set associative cache (initially empty) with total 16 cache blocks. The
main memory consists of 256 blocks and the request for memory blocks is in the
following order:
0,
255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155.
Which
one of the following memory block will NOT be in cache if LRU replacement
policy is used?
(A)
3 (B) 8 (C) 129 (D)
216
30. Consider a system
with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2
units). A non-preemptive resource allocation policy is used. At any given instance,
a request is not entertained if it cannot be completely satisfied. Three processes
P1, P2, P3 request the sources as follows if executed independently.
|
Process P1:
|
Process P2:
|
Process P3:
|
|
t=0: requests 2 units of R2
|
t=0: requests 2 units of R3
|
t=0: requests 1 unit of R4
|
|
t=1: requests 1 unit of R3
|
t=2: requests 1 unit of R4
|
t=2: requests 2 units of R1
|
|
t=3: requests 2 units of R1
|
t=4: requests 1 unit of R1
|
t=5: releases 2 units of R1
|
|
t=5: releases 1 unit of R2
|
t=6: releases 1 unit of R3
|
t=7: requests 1 unit of R2
|
|
and 1 unit of R1.
|
t=8: Finishes
|
t=8: requests 1 unit of R3
|
|
t=7: releases 1 unit of R3
|
|
t=9: Finishes
|
|
t=8:
requests 2 units of R4
|
|
|
|
t=10:
Finishes
|
|
|
Which
one of the following st atements is TRUE if all three processes run concurrently
starting at time t=0?
(A)
All processes will finish without any deadlock
(B)
Only P1 and P2 will be in deadlock.
(C)
Only P1 and P3 will be in a deadlock.
(D)
All three processes will be in deadlock.
31. Consider
a disk system with 100 cylinders. The requests to access the cylinders occur in
following sequence:
4,
34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming
that the head is currently at cylinder 50, what is the time taken to satisfy
all requests if it takes 1ms to move from one cylinder to adjacent one and
shortest seek time first policy is used?
(A)
95ms (B) 119ms (C) 233ms (D)
276ms
32. In the following
process state transition diagram for a uniprocessor system, assume that there
are always some processes in the ready state:
Now consider
the following statements:
I. If
a process makes a transition D, it would result in another process making
transition A immediately.
II.
A process P2 in blocked state can make transition E while
another process P1 is in running state.
III.
The OS uses preemptive scheduling.
IV.
The OS uses non-preemptive scheduling.
Which
of the above statements are TRUE?
(A)
I and II (B) I and III (C) II and
III (D) II and IV
33. The enter_CS()
and leave_CS() functions to implement critical section of a process are
realized using test-and-set instruction as follows:
void
enter_CS(X)
{
( )
while
test-and-set(X) ;
}
void
leave_CS(X)
{
X=0;
}
In
the above solution, X is a memory location associated with the CS and is
initialized to 0. Now consider the following statements:
I.
The above solution to CS problem is deadlock-free
II.
The solution is starvation free.
III.
The processes enter CS in FIFO order.
IV
More than one process can enter CS at the same time.
Which
of the above statements is TRUE?
(A) I
only (B) I and II (C) II and III (D)
IV only
34. A multilevel
page table is preferred in comparison t o a single level page table for
translating virtual address to physical address because
(A) It
reduces the memory access time to read or write a memory location.
(B) It helps to reduce the size of page
table needed to implement the virtual address space of a process.
(C) It
is required by the translation look aside buffer.
(D) It
helps to reduce the number of page faults in page replacement algorithms.
35. The running time
of an algorithm is represented by the following recurrence relation:
Which one of
the following represents the time complexity of the algorithm?
(A) q(n) (B) q(n log n) (C) q(n2) (D) q(n2 log n)
36. The keys 12,
18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of
length 10 using open addressing with hash function h(k) = k mod 10 and linear
probing. What is the resultant hash table?
37. What is the maximum
height of any AVL-tree with 7 nodes? Assume that the height of a tree with a
single node is 0.
(A) 2 (B)
3 (C) 4 (D) 5
38. Consider the
following graph:
Which
one of the following is NOT the sequence of edges added to the minimum spanning
tree using Kruskal's algorithm?
(A)
(b,e) (e,f) (a,c) (b,c) (f,g) (c,d) (B) (b,e) (e,f) (a,c)
(f,g) (b,c) (c,d)
(C)
(b,e) (a,c) (e,f) (b,c) (f,g) (c,d) (D) (b,e) (e,f) (b,c)
(a,c) (f,g) (c,d)
39. In
quick sort , for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n)
time algorithm. What is the worst case time complexity of the quick sort?
(A) q(n) (B)
q(n log n) (C) q(n2) (D)
(qn2
log n)
40. Let L
= L1 Ç L2,
where L1 and L2 are languages as defined
below:
L1
= {am bm c an bm | m, n ³
0}
L2 = {aibjck | i, j, k ³ 0}
Then L is
(A) Not
recursive
(B) Regular
(C) Context
free but not regular
(D) Recursively
enumerable but not context free.
41.
The above DFA
accepts the set of all strings over {0,1} that
(A)
begin either with 0 or 1 (B) end with 0
(C) end
with 00 (D) contain the
substring 00.
42. Which of the
following statements are TRUE?
I. There exist parsing algorithms
for some programming languages whose complexities are less than q(n3).
II. A programming language which allows
recursion can be implemented with static storage allocation.
III. No
L-attributed definition can be evaluated in t he framework of bottom-up
parsing.
IV. Code improving transformations can
be performed at both source language and intermediate code level.
(A) I
and II (B) I and IV
(C)
III and IV (D) I, III and
IV
43.
Consider two transactions T1 and T2, and four
schedules S1, S2, S3, S4 of T1
and T2 as given below:
T1 : R1 [x] W1
[x] W1 [y]
T2 : R2 [x] R2
[y] W2 [y]
S1 : R1 [x] R2
[x] R2 [y] W1 [x] W1 [y] W2 [y]
S2 : R1 [x] R2
[x] R2 [y] W1 [x] W2 [y] W1 [y]
S3 : R1 [x] W1
[x] R2 [x] W1 [y] R2 [y] W2 [y]
S4 : R2 [x] R2
[y] R1 [x] W1 [x] W1 [y] W2 [y]
Which of the above schedules are
conflict-serializable?
(A) S1
and S2 (B) S2 and S3 (C)
S3 only (D) S4 only
44. The
following key values are inserted into a B+ - tree in which order of the
internal nodes is 3, and that of the leaf nodes is 2, in the sequence given
below. The order of internal nodes is the maximum number of tree pointers in each
node, and the order of leaf nodes is the maximum number of data items that can
be stored in it. The B+ - tree is initially empty.
10,
3, 6, 8, 4, 2, 1
The
maximum number of times leaf nodes would get split up as a result of these
insertions is
(A)
2 (B) 3 (C) 4 (D)
5
45. Let R and S be
relational schemes such that R={a,b,c} and S={c}. Now consider the following
queries on the database:
I. pR-S (r) - pR-S (pR-S (r) ´
S - pR-S,S (r))
II. {t
| t Î pR-S (r) Ù
"u Î s ($v € r (u = v [s] Ù t = v [R -
S]))}
III. {t
| t Î pR-S (r) Ù
"v Î r ($u € s (u = v [s] Ù t = v [R -
S]))}
IV. Select
R.a, R.b
From
R, S
Where
R.c = S.c
Which of the
above queries are equivalent?
(A) I
and II (B) I and III (C) II and IV (D) III
and IV
46. In the RSA public
key cryptosystem, the private and public keys are (e,n) and (d,n) respectively,
where n=p*q and p and q are large primes. Besides, n is public and p and q are private.
Let M be an integer such that 0<M<n and f(n) = (p -
1) (q - 1). Now consider the following equations.
I. M¢ = Me mod n II. ed º 1 mod n
M
= (M¢)d
mod n
III. ed
º 1 mod f(n) IV. M¢ = Me mod f(n)
M
= (M¢)d mod f(n)
Which
of the above equations correctly represent RSA cryptosystem?
(A)
I and II (B) I and III (C) II and IV (D)
III and IV
47. While
opening a TCP connection, the initial sequence number is t o be derived using a
time-of-day (ToD) clock that keeps running even when the host is down. The low
order 32 bits of the counter of the ToD clock is to be used for the initial
sequence numbers. The clock counter increments once per millisecond. The
maximum packet lifetime is given to be 64s.
Which
one of the choices given below is closest to the minimum permissible rate at
which sequence numbers used for packets of a connection can increase?
(A) 0.015/s
(B) 0.064/s (C) 0.135/s (D)
0.327/s
48. Let
G(x) be the generator polynomial used for CRC checking. What is the condition
that should be satisfied by G(x) to detect odd number of bits in error?
(A) G(x)
contains more than two terms
(B) G(x)
does not divide 1+xk , for any not exceeding the frame length k
(C) 1+x
is a fact or of G(x)
(D) G(x)
has an odd number of terms.
49. Which
of the following statements are TRUE?
I.
The context diagram should depict t he system as a single bubble.
II. External
entities should be identified clearly at all levels of DFDs.
III. Control
information should not be represented in a DFD.
IV. A
data store can be connected either to another data store or to an external
entity.
(A) II
and III (B) II and III (C) I and III (D)
I, II and III
50. Consider the
following statements about the cyclomatic complexity of the control flow graph
of a program module. Which of these are TRUE?
I. The cyclomatic complexity of a
module is equal to the maximum number of linearly independent circuits in the
graph.
II. The cyclomatic complexity of a
module is the number of decisions in the module plus one, where a decision is
effectively any conditional statement in the module.
III. The
cyclomatic complexity can also be used as a number of linearly independent
paths that should be tested during path coverage testing.
(A) I
and II (B) II and III (C) I and III (D) I,
II and III
Common Data Questions: 51 & 52
A hard disk has 63 sectors per track, 10 platters each
with 2 recording surfaces and 1000 cylinders. The address of a sector is given
as a triple ác, h, sñ, where c is the
cylinder number, h is the surface number and s is the sector number. Thus, the
0th sector is addressed as á0, 0, 0ñ,
the 1st sector as á0, 0, 1ñ,
and so on
51. The
address <400, 16, 29> corre4sponds tp sector number:
(A) 505035
(B) 505036 (C) 505037 (D) 505038
52. The address of
the 1039th sector is
(A) á0,
15,31ñ (B) á0,16,30ñ
(C) á0,16, 31ñ (D) á0,
17,31ñ
Common Data Questions: 53 & 54
A sub-sequence of a given sequence is just the given sequence
with some elements (possibly none or all) left out. We are given two sequences
X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y
starting from 0.
53.
We wish to find the length of the longest common sub-sequence (LCS) of X[m]
and Y[n] as l(m,n), where an incomplete recursive definition for the function
l(i,j) to compute the length of t he LCS of X[m] and Y[n] is given below:
l (i, j) 0, if either i=0 or j=0
= expr1, if i,j>0
and X[i -1] = Y[j - 1]
= expr2, if i,j>0
and X[i - 1] = Y[j - 1]
Which
one of the following options is correct?
(A) expr1 º (i - 1, j) + 1 (B) expr1
º l(i, j - 1)
(C) expr2
º max (l(i - 1, j), l(i, j - 1) (D) expr2
º max (l(i - 1, j - 1), l(i, j))
54. The
values of l(i,j) could be obtained by dynamic programming based on the correct recursive
definition of l(i,j) of the form given above, using an array L[M,N], where M =
m+1 and N=n+1, such that L[i,j] = l(i,j).
Which
one of the following statements would be TRUE regarding the dynamic programming
solution for the recursive definition of l(i,j)?
(A) All
elements L should be initialized to 0 for the values of l(i,j) to be properly
computed.
(B) The
values of l(i,j) may be computed in a row major order or column major order of
L(M,N).
(C) The values of l(i,j) cannot be
computed in either row major order or column major order of L(M,N).
(D) L[p,q]
needs to be computed before L[r,s] if either p<r or q<s.
Common Data Questions: 55 & 56
Consider
the following relational schema:
Suppliers(sid:integer,
sname:string, city:string, street:string)
Parts(pid:integer,
pname:string, color:string)
Catalog(sid:integer,
pid:integer, cost:real)
55. Consider the
following relational query on the above database:
SELECT
S.sname
FROM
Suppliers S
WHERE
S.sid NOT IN (SELECT C.sid
FROM
Catalog C
WHERE
C.pid NOT (SELECT P.pid
FROM
Parts P
WHERE
P.color<> 'blue'))
Assume that
relations corresponding to the above schema are not empty. Which one of the
following is the correct interpretation of the above query?
(A) Find
the names of all suppliers who have supplied a non-blue part.
(B) Find
the names of all suppliers who have not supplied a non-blue part.
(C) Find
the names of all suppliers who have supplied only blue parts.
(D) Find
the names of all suppliers who have not supplied only blue parts.
56.
Assume that, in the suppliers relation above, each supplier and each
street within a city has a unique name, and (sname, city) forms a candidate key.
No other functional dependencies are implied other than those implied by primary
and candidate keys. Which one of the following is TRUE about the above schema?
(A) The
schema is in BCNF
(B) The
schema is in 3NF but not in BCNF
(C) The
schema is in 2NF but not in 3NF
(D) The
schema is not in 2NF
Linked Answer Questions: Q.57 to Q.60 Carry Two Marks
Each
Statement for Linked Answer Questions: 57 & 58
Frames of 1000 bits are sent over a 10 bps duplex link
between two hosts. The 6 propagation time is 25ms. Frames are to be transmitted
into this link to maximally pack them in transit (within the link).
57. What
is the minimum number of bits (l) that will be required to represent the
sequence numbers distinctly? Assume that no time gap needs to be given between transmissions
of two frames.
(A) l=2
(B) l=3 (C) l=4 (D)
l=5
58. Suppose that the sliding window protocol is
used with the sender window size of 2| , where l is the
number of bits identified in t he earlier part and l acknowledgements are
always piggy backed. After sending 2| frames, what is
the l minimum time the sender will have to wait before starting transmission of
the next frame? (Identify the closest choice ignoring the frame processing
time.)
(A) 16ms
(B) 18ms (C) 20ms (D) 22ms
Statement for Linked Answer Questions: 59 & 60
Consider
a binary max-heap implemented using an array.
59. Which
one of the following array represents a binary max-heap?
(A) {25,12,16,13,10,
8,14} (B) {25,14,13, 16,10, 8,12}
(C) {25,14,16,13,10,
8,12} (D) {25,14,12,13,10, 8,16}
60. What
is the content of the array after two delete operations on the correct answer
to the previous question?
(A) {14,
13,12,10, 8} (B) {14,12,13, 8,10}
(C) {14,13,
8, 12,10} (D) {14,13,12, 8,10}
End of Question Papers
