GATE question papers: Computer Science and Engineering 2003 (CS)
Q.1 – Q.30 carry
one mark each.
1. Consider
the following C function.
float
f,(float x, int y) {
float
p, s; int i;
for
(s=1,p=1,i=1; i<y; i++) {
p
*= x/i;
s+=p;
}
return
s;
}
For
large values of y, the return value of the function f best approximates
(A) Xy (B) ex (C) ln(1+x) (D) Xx
2. Assume
the following C variable declaration
int *
A[10], B[10][10];
Of the
following expressions
I.
A[2] II. A[2][3] III. B[1]
IV. B[2][3]
which will
not give compile-time errors if used as left hand sides of assignment statements
in a C program?
(A)
I,II, and IV only (B) II, III, and
IV only
(C)
II and IV only (D) IV only
3. Let P(E) denote
the probability of the event E. Given P(A) = 1, P(B) =
,
the values of P(A|B) and P(B|A) respectively are
(A) 
,
(B) ,
(C) ,
1 (D) 1,
4. Let A be a
sequence of 8 distinct integers sorted in ascending order. How many distinct pairs
of sequences, B and C are there such that (i) each is sorted in ascending
order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and
C gives A?
(A)
2 (B) 30 (C) 56 (D)
256
5. n couples
are invited to a party with the condition that every husband should be accompanied
by his wife. However, a wife need not be accompanied by her husband. The number
of different gatherings possible at the party is
(A) 
(B) 3n (C) 
(D) 
6. Let T(n) be
the number of different binary search trees on n distinct elements. Then T(n)=
(K-1)
T (x), where x is
(A)
n - k + 1 (B) n - k (C) n - k - 1 (D)
n - k - 2
7. Consider the
set å* of all strings over the alphabet å = {0, 1}. å* with the
concatenation operator for strings
(A)
does not form a group
(B)
forms a non-commutative group
(C)
does not have a right identity element
(D)
forms a group if the empty string is removed from å*
8. Let G be an
arbitrary graph with n nodes and k components. If a vertex is removed from G, the
number of components in the resultant graph must necessarily lie between
(A) k
and n (B) k - 1 and k + 1
(C) k
- 1 and n - 1 (D)
k + 1 and n - k
9. Assuming all
numbers are in 2's complement representation, which of the following numbers is
divisible by 11111011?
(A)
11100111 (B) 11100100 (C) 11010111 (D)
11011011
10. For a
pipelined CPU with a single ALU, consider the following situations
I. The
j + 1-st instruction uses the result of the j-th instruction as an operand
II. The
execution of a conditional jump instruction
III. The
j-th and j + 1-st instructions require the ALU at the same time
Which of
the above can cause a hazard?
(A)
I and II only (B) II and III only (C) III only (D)
All the three
11. Consider
an array multiplier for multiplying two n bit numbers. If each gate in the circuit
has a unit delay, the total delay of the multiplier is
(A)
Q (1) (B) Q (log n) (C) Q (n) (D) Q (n2)
12. Ram and Shyam
have been asked to show that a certain problem is NP-complete. Ram shows a
polynomial time reduction from the 3-SAT problem to P, and Shyam shows a polynomial time reduction from
to 3-SAT. Which of the following can be inferred from these reductions?
(A)
is NP-hard but not NP-complete (B) is in NP, but is not
NP-complete
(C)
is NP-complete (D) is neither NP-hard,
nor in NP
13. Nobody
knows yet if P = NP. Consider the language L defined as follows.
L = 
Which of
the following statements is true?
(A)
L is recursive
(B)
L is recursively enumerable but not recursive
(C)
L is not recursively enumerable
(D)
Whether L is recursive or not will be known after we find out if P = NP
14. The
regular expression 0*(10*)* denotes the same set as
(A)
(1*0)*1* (B) 0+(0+10)*
(C)
(0+1)*10(0+1)* (D) None of the above
15. If the
strings of a language L can be effectively enumerated in lexicographic (i.e.,
alphabetic) order, which of the following statements is true?
(A)
L is necessarily finite
(B)
L is regular but not necessarily finite
(C)
L is context free but not necessarily regular
(D)
L is recursive but not necessarily context free
16. Which of
the following suffices to convert an arbitrary CFG to an LL(1) grammar?
(A)
Removing left recursion alone
(B)
Factoring the grammar alone
(C)
Removing left recursion and factoring the grammar
(D)
None of the above
17. Assume
that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is
(A)
n1 is necessarily less
than n2 (B)
n1 is necessarily equal
to n2
(C)
n1 is necessarily greater
than n2 (D)
None of the above
18. In a
bottom-up evaluation of a syntax directed definition, inherited attributes can
(A)
always be evaluated
(B)
be evaluated only if the definition is L-attributed
(C)
be evaluated only if the definition has synthesized attributes
(D)
never be evaluated
19. Suppose
the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an
initially empty binary search tree. The binary search tree uses the usual
ordering on natural numbers. What is the in-order traversal sequence of the resultant
tree?
(A)
7 5 1 0 3 2 4 6 8 9 (B) 0 2 4 3 1 6 5 9
8 7
(C)
0 1 2 3 4 5 6 7 8 9 (D) 9 8 6 4 2 3 0 1
5 7
20. Consider
the following three claims
I. (n + k)m = Q(nm)
where k and m are constants
II. 2n+1
= O(2n) III. 22n+1
= O(2n)
Which of
these claims are correct?
(A)
I and II (B) I and III (C) II and III (D)
I, II, and III
21. Consider the following graph
Among
the following sequences
I. a b e g h f II. a b f e h g III. a b f h g e IV. a
f g h b e
Which
are depth first traversals of the above graph?
(A)
I, II and IV only (B) I and IV only
(C)
II, III and IV only (D) I, III and IV
only
22. The usual
Q(n2) implementation of Insertion Sort to sort an array
uses linear search to identify the position where an element is to be inserted
into the already sorted part of the array. If, instead, we use binary search to
identify the position, the worst case running time will
(A)
remain Q(n2) (B)
become Q(n (log n)2)
(C)
become Q n log n) (D) become Q(n)
23. In a heap
with n elements with the smallest element at the root, the 7th smallest element
can be found in time
(A) T (n log n) (B)
T (n) (C) T (log n) (D) T (1)
24. Which of
the following statements is FALSE?
(A) In
statically typed languages, each variable in a program has a fixed type
(B) In
un-typed languages, values do not have any types
(C) In
dynamically typed languages, variables have no types
(D) In all statically typed
languages, each variable in a program is associated with values of only a
single type during the execution of the program
25. Using a
larger block size in a fixed block size file system leads to
(A)
better disk throughput but poorer disk space utilization
(B)
better disk throughput and better disk space utilization
(C)
poorer disk throughput but better disk space utilization
(D)
poorer disk throughput and poorer disk space utilization
26. In a system
with 32 bit virtual addresses and 1KB page size, use of one-level page tables
for virtual to physical address translation is not practical because of
(A)
the large amount of internal fragmentation
(B)
the large amount of external fragmentation
(C)
the large memory overhead in maintaining page tables
(D)
the large computation overhead in the translation process
27. Which of
the following assertions is FALSE about the Internet Protocol (IP)?
(A) It
is possible for a computer to have multiple IP addresses
(B) IP packets from the same
source to the same destination can take different routes in the network
(C) IP ensures that a packet is
discarded if it is unable to reach its destination within a given number of
hops
(D) The packet source cannot
set the route of an outgoing packets; the route is determined only by the
routing tables in the routers on the way
28. Which of the
following functionalities must be implemented by a transport protocol over and
above the network protocol?
(A)
Recovery from packet losses (B) Detection of duplicate
packets
(C)
Packet delivery in the correct order (D) End to end
connectivity
29. Which of
the following scenarios may lead to an irrecoverable error in a database system?
(A)
A transaction writes a data item after it is read by an uncommitted transaction
(B)
A transaction reads a data item after it is read by an uncommitted transaction
(C)
A transaction reads a data item after it is written by a committed transaction
(D)
A transaction reads a data item after it is written by an uncommitted
transaction
30. Consider
the following SQL query
select
distinct a1, a2, ..., an
from r1, r2, ..., rm
where P
For an arbitrary
predicate P, this query is equivalent to which of the following relational
algebra expressions?
(A) 
sp
(r1 ´ r2 ´ ... ´
rm)
(B)
sp
(r1
r2 ... rm)
(C)
sp
(r1 È r2 È ... È
rm)
(D)
sp
(r1 Ç r2 Ç ... Ç
rm)
Q. 31-90 carry two marks each.
31. Let (S,£ ) be a partial order with two minima elements
a and b , and a maximum element c.
Let P: S® {True, False} be a predicate defined on
S. Suppose that p(a) = True , and P(b) = False and P(x)
Þ P(y) for all x, yÎ S
satisfying x£ y, where Þ stands for logical
implication. Which of the following statements CANNOT be true?
(A)
P(x) = True for all x Î S such
that x ¹ b
(B)
P(x) = False for all x Î S such
that x¹ a and x¹ c
(C)
P(x) = False for all x Î S such
that b £x and x¹c
(D)
P(x) = False for all x Î S such
that a £x and b£ x
32. Which of
the following is a valid first order formula? (Here a and b are first
order formulae with x as their only free variable)
(A)
(( "x) [ a] Þ ("x ) [b]) Þ ("x ) [ a Þ b ]
(B)
("x) [ a ] Þ ($ x)[a Ù b ]
(C)
(("x)[ aÚ b ] Þ ($ x)[a] Þ ("x )[ a]
(D)
("x)[ a Þ b Þ ((" x) [a] Þ ("x )[ b])
33. Consider
the following formula and its two interpretations I1 and I2
a: ("x)
[Px Û ("y)[Qxy Û ¬Qyy]] Þ ("x)[¬ P ]
I1 : Domain: the set of natural numbers
Px º 'x is a
prime number'
Qxy
º 'y divides x'
I2 : same as I1 except that Px = 'x is a composite
number'.
Which of
the following statements is true?
(A) I1 satisfies a, I2 does not (B) I2 satisfies a , I1 does not
(C) Neither
I2 nor I1 satisfies a (D) Both
I1 and 12 satisfy a
34. m identical
balls are to be placed in n distinct bags. You are given that , m ³ kn, where k is a natural number ³ 1. In how many ways can the balls be placed in
the bags if each bag must contain at least k balls?
(A) 
(B) 
(C) 
(D) 
35. Consider
the following recurrence relation
T(1) = 1
T(n + 1)
= T(n)+ ë
û for all n³1
The
value of T(m2) for m
³ 1 is
(A) 
(B) 
(C) 
(D) 
36. How many
perfect matching are there in a complete graph of 6 vertices?
(A)
15 (B) 24 (C) 30 (D) 60
37. Let f : A
® B be an injective (one-to-one) function. Define
g : 2A ® 2B as: g(C) = {f(x) | xÎ C}, for all subsets C of A.
Define h
: 2B ® 2A as
: h(D) = {x | xÎ A, f(x) Î D}, for all
subsets D of B.
Which of
the following statements is always true?
(A) g(h(D))
Í D (B) g(h(D
) Ê D
(C) g(h(D)) Ç D = f (D) g(h(D))
D Ç (B-D) ¹ f
38. Consider the set {a, b, c} with binary
operators + and × defined as follows.
|
+
|
a
|
b
|
c
|
|
x
|
a
|
b
|
c
|
|
a
|
b
|
a
|
c
|
|
a
|
a
|
b
|
c
|
|
b
|
a
|
b
|
c
|
|
b
|
b
|
c
|
a
|
|
c
|
a
|
c
|
b
|
|
c
|
c
|
c
|
b
|
For
example, a + c = c, c + a = a, c × b = c and b × c = a. Given the following
set of
equations: (a ´ x) + (a ´ y) = c
(b
´ x) + (c ´ y) = c
The
number of solution(s) (i.e., pair(s) (x, y) that satisfy the equations) is
(A)
0 (B) 1 (C) 2 (D) 3
39. Let å = {a, b, c, d, e} be an alphabet. We define an
encoding scheme as follows:
g(a) =
3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11.
Let pi denote the i-th prime number (p1 = 2).
For a
non-empty string s = a1 ... an, where each ai
Î å,
define f (s) = 
.
For a
non-empty sequence < si ,..., sn > of strings from å+,
define h (si....sn)
= 
.
which of the following numbers is the encoding,
h, of a non-empty sequence of strings?
(A)
27 37 57 (B) 28
38 58 (C) 29
39 59 (D) 210
510 710
40. A graph G
= (V, E) satisfies |E| 3 £ |V| -6. The min-degree of G is defined as 
{degree
(v)}. Therefore, min-degree of G cannot be
(A)
3 (B) 4 (C) 5 (D)
6
41. Consider the following system of linear
equations
Notice
that the second and the third columns of the coefficient matrix are linearly
dependent. For how many values of a, does this system
of equations have infinitely many solutions?
(A)
0 (B) 1 (C) 2 (D)
infinitely many
42. A piecewise
linear function f(x) is plotted using thick solid lines in the figure below
(the plot is drawn to scale).
If we
use the Newton-Raphson method to find the roots of f(x) =0 using x0, x1, and x2
respectively as initial guesses, the roots obtained would be
(A)
1.3, 0.6, and 0.6 respectively (B) 0.6, 0.6, and 1.3
respectively
(C)
1.3, 1.3, and 0.6 respectively (D) 1.3, 0.6, and 1.3
respectively
43. The following
is a scheme for floating point number representation using 16 bits.
|
Bit position
|
15
|
14.....9
|
8.....0
|
|
|
s
|
e
|
m
|
|
|
sign
|
exponent
|
Mantissa
|
Let s,
e, and m be the numbers represented in binary in the sign, exponent,
and
mantissa
fields respectively. Then the floating point number represented is:
(-1)s (1+m ´
2-9 )2e-31, if
the exponent ¹ 111111
0, otherwise
What is the
maximum difference between two successive real numbers representable in this
system?
(A)
2-40 (B) 2-9
(C) 222 (D) 231
44. A
1-input, 2-output synchronous sequential circuit behaves as follows:
Let zk, nk denote the number of 0's and 1's respectively in initial k bits of the
input
(zk + nk = k). The circuit outputs 00 until one of the following conditions
holds.
• zk
- nk =2. In this case, the output at the k-th and all subsequent clock
ticks is 10.
• nk - zk = 2. In this case, the output at the k-th and
all subsequent clock ticks is 01.
What is
the minimum number of states required in the state transition graph of the
above circuit?
(A)
5 (B) 6 (C) 7 (D)
8
45. The literal count of a Boolean expression
is the sum of the number of times each literal appears in the expression. For
example, the literal count of (xy + xz¢) is 4. What
are the minimum possible literal counts of the product-of-sum and
sum-of-product representations respectively of the function given by the following
Karnaugh map? Here, X denotes "don't care"
(A)
(11, 9) (B) (9, 13) (C) (9, 10) (D)
(11, 11)
46. Consider the ALU shown below.
If the operands
are in 2's complement representation, which of the following operations can be
performed by suitably setting the control lines K and C0 only (+ and - denote addition and subtraction
respectively)?
(A)
A + B, and A - B, but not A + 1 (B) A + B, and A + 1, but
not A - B
(C)
A + B, but not A - B or A + 1 (D) A + B, and A - B,
and A + 1
47. Consider the following circuit composed
of XOR gates and non-inverting buffers.
The non-inverting
buffers have delays d1= 2 ns and d2=
4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume
that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If
the following waveform is applied at input A, how many transition(s) (change of
logic levels) occur(s) at B during the interval from 0 to 10 ns?
(A)
1 (B) 2 (C) 3 (D)
4
The following
information pertains to 48-49:
Consider the
following assembly language program for a hypothetical processor
A, B, and C are 8 bit
registers. The meanings of various instructions are shown as comments.
MOV B, #0 ; B
¬ 0
MOV C, #8 ; C
¬ 8
Z: CMP C, #0 ; compare
C with 0
JZ X ; jump
to X if zero flag is set
SUB C, #1 ; C¬ C - 1
RRC A, #1 ;
right rotate A through carry by one bit. Thus:
; if
the initial values of A and the carry flag are
a7 ..a0 and
;
c0 respectively,
their values after the execution
of this
; instruction
will be c0 a7 ..a1 and a0 respectively.
JC Y ;
jump to Y if carry flag is set
JMP Z ;
jump to Z
Y: ADD B, #1 ; B
¬ B + 1
JMP Z ;
jump to Z
X:
48. If the initial
value of register A is A0 the value of register B after the program execution
will be
(A)
the number of 0 bits in A0
(B) the number of 1 bits in A0
(C)
A0 (D)
8
49. Which of the
following instructions when inserted at location X will ensure that the value
of register A after program execution is the same as its initial value?
(A)
RRC A, #1
(B)
NOP ; no operation
(C)
LRC A, #1 ; left rotate A through carry flag by one bit
(D)
ADD A, #1
50. Consider
the following deterministic finite state automaton M.
Let S
denote the set of seven bit binary strings in which the first, the fourth, and
the last bits are 1. The number of strings in S that are accepted by M is
(A)
1 (B) 5 (C) 7 (D) 8
51. Let G =
({S}, {a, b}, R, S) be a context free grammar where the rule set R is S ® a S b | S S |e
Which of
the following statements is true?
(A)
G is not ambiguous
(B)
There exist x, y Î L(G) such that x y Ï L(G)
(C)
There is a deterministic pushdown automaton that accepts L(G)
(D)
We can find a deterministic finite state automaton that accepts L(G)
52. Consider two
languages L1 and L2 , each on the alphabet å. Let f: å be a polynomial
time computable bijection such that (" x)[xÎ L1 iff f(x) Î L2 ]. Further, let f-1 be also polynomial time computable.
Which of
the following CANNOT be true?
(A) L1 Î P and L2 is finite
(B) L1 Î NP and L2 Î P
(C) L1 is undecidable and L2 is decidable
(D) L1 is recursively enumerable and L2 is recursive
53. A single tape Turing Machine M has two states
q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1,
B} and its input alphabet is {0,1}. The symbol B is the blank symbol used to
indicate end of an input string. The transition function of M is described in
the following table.
|
|
0
|
1
|
B
|
|
q0
|
q1, 1, R
|
q1, 1, R
|
Halt
|
|
q1
|
q1, 1, R
|
q01, L
|
q0, B, L
|
The
table is interpreted as illustrated below.
The
entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and
reads 1 on the current tape square, then it writes 1 on the same tape square,
moves its tape head one position to the right and transitions to state q1.
Which of
the following statements is true about M?
(A)
M does not halt on any string in (0+1)+
(B)
M does not halt on any string in (00+1)*
(C)
M halts on all strings ending in a 0
(D)
M halts on all strings ending in a 1
54. Define
languages L0 and L1 as follows:
L = {<M, w, 0> | M halts on w}
L1 = {<M, w, 1> | M does not halt on
w}
Here <M, w, i> is a triplet, whose first component, M, is an encoding of a
Turing
Machine,
second component, w, is a string, and third component, i, is a
bit.
Let L =
L0 È L1 . Which of the following is true?
(A) L
is recursively enumerable, but 
is
not
(B)
is recursively enumerable, but is
not
(C) Both
L and are
recursive
(D) Neither
L nor is
recursively enumerable
55. Consider the NFA M shown below.
Let the
language accepted by M be L. Let L1 be the language accepted by the NFA M1 obtained by changing the accepting state of M to
a non-accepting state and by changing the non-accepting states of M to accepting
states. Which of the following statements is true?
(A)
L1 = {0, 1}* - L (B) L1 = {0, 1}*
(C)
L1 Í L (D) L1 = L
56. Consider
the grammar shown below
S ® i E t S S¢ | a
S¢ ® e S |e
E ® b
In the predictive
parse table, M, of this grammar, the entries M[S¢, e] and
M[S¢, $] respectively are
(A) {S¢
® e S} and {S¢ ® e} (B) {S¢ ®
e S} and { }
(C) {S¢
® e}
and {S¢ ®
e } (D) {S¢ ® e
S, S¢ ®
e} and { S¢ ® e}
57. Consider
the grammar shown below.
S ® C C
C ® c C | d
This
grammar is
(A) LL(1)
(B) SLR(1) but not
LL(1)
(C) LALR(1)
but not SLR(1) (D) LR(l) but not LALR(1)
58. Consider
the translation scheme shown below.
S ® T R
R ® + T {print ('+');} R| e
T® num {print
(num.val);}
Here is a token that represents an integer and num.val
represents the corresponding integer value. For an input string '9 + 5 + 2', this
translation scheme will print
(A)
9 + 5 + 2 (B) 9 5 + 2 +
(C)
9 5 2 + + (D) + + 9 5 2
59. Consider
the syntax directed definition shown below.
S ® id
: = E { (gen(id.place = E.place;);}
E ® E1
+ E2 {t
= newtemp ( );
gen (t = E1.place + E2.place;);
E.place
= t;}
E®
id {E.place
= id.place;}
Here, is a function that generates the output code,
and newtemp is a function that returns the name of a new temporary variable
on every call. Assume that ti's are the temporary variable names generated by newtemp.
For the statement 'X : = Y + Z', the 3-address code sequence generated by this definition
is
(A) X = Y + Z (B) t1 = Y + Z; X =
t1
(C) t1 = Y; t2= t2 + Z; X = t2 (D) t1 = Y; t2 = Z; t3 = t1 + t2 ; X = t3
60. A program
consists of two modules executed sequentially. Let f1(t) and f2(t) respectively
denote the probability density functions of time taken to execute the two
modules. The probability density function of the overall time taken to execute
the program is given by
(A) f1 (t) + f2 (t) (B) 
(C) 
(D) max {f1(t), f2(t)}
The following
information pertains to 61-62:
In a permutation, a1
... an, of distinct
integers, an inversion is a pair (ai, aj) such that i < j and ai
> aj.
61. If all
permutations are equally likely, what is the expected number of inversions in a
randomly chosen permutation of 1 . . . n?
(A) 
(B) 
(C) 
(D) 2n[log2n]
62. What
would be the worst case time complexity of the Insertion Sort algorithm, if the
inputs are restricted to permutations of 1. . . n with at most n inversions?
(A)
Q(n2) (B) Q(n log n) (C) Q(n1.5) (D) Q(n)
63. A data structure
is required for storing a set of integers such that each of the following operations
can be done in O(log n) time, where n is the number of elements in the set.
I. Deletion
of the smallest element
II. Insertion
of an element if it is not already present in the set
Which of
the following data structures can be used for this purpose?
(A)
A heap can be used but not a balanced binary search tree
(B)
A balanced binary search tree can be used but not a heap
(C)
Both balanced binary search tree and heap can be used
(D)
Neither balanced binary search tree nor heap can be used
64. Let S be
a stack of size n ³ 1. Starting with the empty stack, suppose we
push the first n natural numbers in sequence, and then perform n pop
operations. Assume that Push and Pop operations take X seconds each, and Y seconds
elapse between the end of one such stack operation and the start of the next
operation. For m = 1, define the stack-life of m as the time elapsed from the
end of Push(m) to the start of the pop operation that removes m from S. The average
stack-life of an element of this stack is
(A) n(X + Y) (B)
3Y + 2X (C) n(X + Y) - X (D)
Y + 2X
65. Consider
the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which
each data item is a letter. The usual alphabetical ordering of letters is used
in constructing the tree.
What is the result
of inserting G in the above tree?
(A) 
(B)
(C)
(D)
None of the above
66. The cube root
of a natural number n is defined as the largest natural number m such that m3 £ n. The complexity of computing the cube root of
n (n is representedin binary notation) is
(A) O(n)
but not O(n0.5)
(B) O(n0.5)
but not O((log n)k) for any constant k > 0
(C) O((log
n)k) for some constant k > 0, but not O((log log
n)m) for any constant m > 0
(D) O((log
log n)k) for some constant k > 0.5, but not O((log
log n)0.5)
67. Let G =
(V, E) be an undirected graph with a subgraph G1 = (V1, E1). Weights
are assigned to edges of G as follows.
A single-source
shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary
vertex v1 of V1 as the source. Which of the following can always
be inferred from the path costs computed?
(A)
The number of edges in the shortest paths from v1 to all vertices of G
(B)
G1 is connected (C)
V1 forms a clique in G (D)
G1 is a tree
68. What is
the weight of a minimum spanning tree of the following graph?
(A)
29 (B) 31 (C) 38 (D)
41
69. The following
are the starting and ending times of activities A, B, C, D, E, F, G and H
respectively in chronological order: 'as bs cs ae ds ce es fs be de gs ee fe hs ge he'. Here, xs denotes the starting time and xe denotes the ending time of activity X. We need
to schedule the activities in a set of rooms available to us. An activity can be
scheduled in a room only if the room is reserved for the activity for its
entire duration. What is the minimum number of rooms required?
(A)
3 (B) 4 (C) 5 (D)
6
70. Let G = (V,
E) be a directed graph with n vertices. A path from vi to vj in G is a sequence of vertices (vi, vi+1, ... , vj) such
that (vk, vk+1) Î E for all k
in i through j - 1. A simple path is a path in which no vertex
appears more than once.
Let A be
an n x n array initialized as follows.
A[j, k]
= 
Consider
the following algorithm.
for
i = 1 to n
for
j = 1 to n
for
k = 1 to n
A[j,k]
= max(A[j,k], A[j,i] + A[i,k]);
Which
of the following statements is necessarily true for all j and k after
termination of the above algorithm?
(A) A[j,
k] £ n
(B) If
A[j, j] ³ n - 1, then G
has a Hamiltonian cycle
(C) If
there exists a path from j to k, A[j, k] contains the longest path length from
j to k
(D) If
there exists a path from j to k, every simple path from j to k contains at most
A[j, k] edges
71. Consider
the following logic program P
A(x) ¬ B(x, y), C(y)
¬ B(x, x)
Which of the following first order sentences is
equivalent to P?
(A) ("x) [($y)
[B(x, y) Ù C(y)] Þ A(x)]
Ù Ø($x)[B(x,x)]
(B) ("x) [("y)
[B(x, y) Ù C(y)] Þ A(x)] Ù Ø($x)[B(x,x)]
(C) ("x) [($y) [B(x,
y) Ù C(y)] Þ A(x)] Ú Ø($x)[B(x,x)]
(D) ("x) [("y)
[B(x, y) Ù C(y)] Þ A(x)] Ù ($x)[B(x,x)]
72. The
following resolution rule is used in logic programming.
Derive
clause (P Ú Q) from clauses (P Ú R), (Q ØR)
Which of
the following statements related to this rule is FALSE?
(A)
((P Ú R) Ù (Q Ú ØR)) (P Ú Q) is logically valid
(B)
(P Ú Q) Þ ((P Ú R) Ù (Q Ú ØR)) is
logically valid
(C)
(P Ú Q) is satisfiable if and only if (P Ú R) Ù (Q Ú ØR) is
satisfiable
(D)
(P Ú Q) FALSE if and only if both P and Q are
unsatisfiable
The following
information pertains to 73-74:
The following program fragment is written in a
programming language that allows global variables and does not allow nested
declarations of functions.
global int i = 100, j = 5;
void
P(x) {
int
i = 10;
print(x
+ 10);
i
= 200;
j
= 20;
print
(x);
}
main() {P(i + j);}
73. If the programming
language uses static scoping and call by need parameter passing mechanism, the
values printed by the above program are
(A)
115, 220 (B) 25, 220 (C) 25, 15 (D)
115, 105
74. If the
programming language uses dynamic scoping and call by name parameter passing
mechanism, the values printed by the above program are
(A)
115, 220 (B) 25, 220 (C) 25, 15 (D)
115, 105
75. Consider the
following class definitions in a hypothetical Object Oriented language that supports
inheritance and uses dynamic binding. The language should not be assumed to be
either Java or C++, though the syntax is similar.
Class
P { Class Q subclass of P {
void
f(int i) { void f(int i) {
print(i);
print(2*i);
}
}
}
}
Now
consider the following program fragment:
Px = new
Q()
Qy = new
Q();
Pz = new
Q();
x.f(1);
((P)y).f(1); z.f(1);
Here ((P)y)
denotes a typecast of y to P. The output produced by executing the above
program fragment will be
(A)
1 2 1 (B) 2 1 1 (C) 2 1 2 (D)
2 2 2
76. Which of
the following is NOT an advantage of using shared, dynamically linked libraries
as opposed to using statically linked libraries?
(A)
Smaller sizes of executable files
(B)
Lesser overall page fault rate in the system
(C)
Faster program startup
(D)
Existing programs need not be re-linked to take advantage of newer versions of
libraries
77. A uni-processor
computer system only has two processes, both of which alternate 10 ms CPU bursts
with 90 ms I/O bursts. Both the processes were created at nearly the same time.
The I/O of both processes can proceed in parallel. Which of the following
scheduling strategies will result in the least CPU utilization (over a long
period of time) for this system?
(A)
First come first served scheduling
(B)
Shortest remaining time first scheduling
(C)
Static priority scheduling with different priorities for the two processes
(D)
Round robin scheduling with a time quantum of 5 ms
The following
information pertains to Q.78-79:
A processor uses 2-level page tables for virtual to
physical address translation. Page tables for both levels are stored in the
main memory. Virtual and physical addresses are both 32 bits wide. The memory is
byte addressable. For virtual to physical address translation, the 10 most
significant bits of the virtual address are used as index into the first level
page table while the next 10 bits are used as index into the second level page
table. The 12 least significant bits of the virtual address are used as offset within
the page. Assume that the page table entries in both levels of page tables are
4 bytes wide.
Further, the processor has a translation
look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used
virtual page numbers and the corresponding physical page numbers. The processor
also has a physically addressed cache with a hit rate of 90%. Main memory access
time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns.
78. Assuming that
no page faults occur, the average time taken to access a virtual address is
approximately (to the nearest 0.5 ns)
(A)
1.5 ns (B) 2 ns (C) 3 ns (D)
4 ns
79. Suppose a
process has only the following pages in its virtual address space: two
contiguous code pages starting at virtual address 0×00000000, two contiguous
data pages starting at virtual address 0×00400000, and a stack page starting at
virtual address 0×FFFFF000. The amount of memory required for storing the page
tables of this process is
(A)
8 KB (B) 12 KB (C) 16 KB (D)
20 KB
The following
information pertains to Q.80-81:
Suppose we want to synchronize two concurrent processes
P and Q using binary semaphores S and T. The code for the processes P and Q is
shown below.
Process
P: Process Q:
while
(1) { while (1) {
W: Y:
print '0'; print
'1';
print
'0'; print '1';
X: Z:
} }
Synchronization statements can be inserted only at points W, X, Y, and
Z
80. Which of
the following will always lead to an output staring with '001100110011'?
(A)
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
(B)
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
(C)
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
(D)
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0
81. Which of the
following will ensure that the output string never contains a substring of the
form 01n0 or 10n1 where n is odd?
(A)
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
(B)
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
(C)
P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1
(D)
V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1
82. The
subnet mask for a particular network is 255.255.31.0. Which of the following
pairs of IP addresses could belong to this network?
(A)
172.57.88.62 and 172.56.87.233 (B) 10.35.28.2 and 10.35.29.4
(C)
191.203.31.87 and 191.234.31.88 (D) 128.8.129.43 and
128.8.161.55
83. A 2km
long broadcast LAN has 107 bps bandwidth and uses CSMA/CD. The signal travels
along the wire at 2 ´ 108 m/s. What is the minimum packet size that can be
used on this network?
(A)
50 bytes (B) 100 bytes
(C)
200 bytes (D) None of the
above
84. Host A is
sending data to host B over a full duplex link. A and B are using the sliding
window protocol for flow control. The send and receive window sizes are 5
packets each. Data packets (sent only from A to B) are all 1000 bytes long and
the transmission time for such a packet is 50 ms
Acknowledgement packets (sent only from B to A) are very small and require negligible
transmission time. The propagation delay over the link is 200 ms. What is the maximum achievable throughput in
this communication?
(A)
7.69 × 10 bps (B) 11.11 × 10 bps 6
6
(C)
12.33 × 10 bps (D) 15.00 × 10 bps 6
6
85. Consider
the following functional dependencies in a database.
Date_of_Birth
® Age Age
®Eligibility
Name ® Roll_number Roll_number
®Name
Course_number
® Course_name Course_number
® Instructor
(Roll_number,
Course_number) ® Grade
The
relation (Roll_number, Name, Date_of_birth, Age) is
(A)
in second normal form but not in third normal form
(B)
in third normal form but not in BCNF
(C)
in BCNF (D) in none of the above
86. Consider the set of relations shown below and the SQL query
that follows.
Students: (Roll_number, Name, Date_of_birth)
Courses: (Course number, Course_name, Instructor)
Grades: (Roll_number, Course_number, Grade)
Name select distinct
Students, Courses, Grades from
Students. Roll_number = Grades.Roll_number where
and Courses.Instructor = Korth
and Courses.Course_number =
Grades.Course_number
and Grades.grade = A
Which
of the following sets is computed by the above query?
(A)
Names of students who have got an A grade in all courses taught by Korth
(B)
Names of students who have got an A grade in all courses
(C)
Names of students who have got an A grade in at least one of the courses taught
by Korth
(D)
None of the above
87. Consider three data items D1, D2, and
D3, and the following execution schedule of transactions T1, T2, and T3. In the
diagram, R(D) and W(D) denote the actions reading and writing the data item D
respectively.
Which of
the following statements is correct?
(A)
The schedule is serializable as T2; T3; T1
(B)
The schedule is serializable as T2; T1; T3
(C)
The schedule is serializable as T3; T2; T1
(D)
The schedule is not serializable
88. In the
following C program fragment, j, k, n and TwoLog_n are integer variables, and A
is an array of integers.
The
variable n is initialized to an integer ³ 3, and
TwoLog_n is initialized to the value of n 2 * élog2(n)ù
for
(k=3; k <= n; k++)
A[k]
= 0;
for
(k=2; k <= TwoLog_n; k++)
for
(j=k+1; j <= n; j++)
A[j]
= A[j] || (j%k);
for
(j=3; j <= n; j++)
if
(!A[j]) printf("% d", j);
The set
of numbers printed by this program fragment is
(A) {m | m £ n, ($i) [m = i!]} (B) {m
| m £ n, ($i) [m = i2]}
(C) {m | m £ n, m is prime} (D) {}
89. Consider
the C program shown below.
#include
<stdio.h>
#define
print(x) printf("% d —, x)
int
x;
void Q(int z) {
z
+= x; print(z);
}
void P(int *y) {
int
x = *y+2;
Q(x);
*y = x-1;
print(x);
}
main(void)
{
x
= 5;
P(&x)
print(x);
}
The output of this program is
(A)
12 7 6 (B) 22 12 11 (C) 14 6 6 (D)
7 6 6
90. Consider
the function f defined below.
struct
item {
int
data;
struct
item * next;
};
int
f(struct item *p) {
return
((p == NULL) || (p ->next == NULL) ||
((p->data
<= p -> next -> data) &&
f(p->
next)));
}
For a
given linked list p, the function f returns 1 if and only if
(A)
the list is empty or has exactly one element
(B)
the elements in the list are sorted in non-decreasing order of data value
(C)
the elements in the list are sorted in non-increasing order of data value
(D)
not all elements in the list have the same data value
End of
question paper
