Graduate Aptitude Test in Engineering ( GATE )

Question Paper - 2003

COMPUTER SCIENCE & ENGINEERING

Answers were Sorted based on User's Feedback



Graduate Aptitude Test in Engineering ( GATE ) Question Paper - 2003 COMPUTER SCIENCE & EN..

Answer / anirudh

GATE ? 2003

COMPUTER SCIENCE & ENGINEERING


PAPER-I


Time Allowed: 3 Hours Maximum Marks: 150



Read the following instructions carefully



This question paper contains 90 objective questions. Q. 1-30
carry one mark each and Q.31-90 carry two marks each.
Answer all the questions.
Questions must be answered on special machine gradable
Objective Response Sheet (ORB) by darkening the appropriate
bubble (marked A, B, C, D) using HB pencil against the
question number on the left hand side of the ORS. Each
question has only one correct answer. In case you wish to
change an answer, erase the old answer completely using a
good soft eraser.
There will be NEGATIVE marking. For each wrong answer 0.25
mark from Q. 1-30 and 0.5 mark from Q. 31-90 will be
deducted. More than one answer marked against a question
will be deemed as an incorrect response and will be
negatively marked.
Write your registration number, name and name of the Centre
at the specified locations on the right half of the ORB.
Using HB pencil, darken the appropriate bubble under each
digit of your registration number.
Using HB pencil, darken the appropriate bubble under the
letters corresponding to your paper code.
No charts or tables are provided in the examination hall.
Use the blank pages given at the end of the question paper
for rough work.
Choose the closest numerical answer among the choices given.
This question paper contains 24 pages. Please report if
there is any discrepancy.


Q. 1 - 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

X Y
e x
ln (1 + x)
X X


2. Assume the following C variable declaration

int *A [10], B [10][10];

Of the following expressions

A[2]
A [2] [3]
B [1]
B [2] [3]
which will not give compile-time errors if used as left hand
sides of assignment statements in a C program ?

I, II, and IV only
II, III, and IV only
II and IV only
IV only


3. Let P(E) denote the probability of the event E. Given
P(A)= 1, P(B) = 1/2, the values of P(A \ B) and P(B / A)
respectively are

?, ?
?, ?
?, 1
1, ?


Let A be a sequence of 8 distinct integers sorted in
ascending order. How many distinct pairs of sequences, Band
C are there such that (i) each is sorted in ascending order,
(ii) B has 5 and C has 8 elements, and (iii) the result of
merging B and C gives A ? .
2
30
56
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)

3 n
(2n)!
2 n




6. Let T(n) be the number of different binary search trees
on n distinct elements.

Then T(n) = where x is



n - k + 1
n - k
n - k ? 1
n - k - 2


7. Consider the set ? * of all strings over the alphabet ? =
(0, 1). ? * with the concatenation operator for strings

does not form a group
forms a non-commutative group
does not have a right identity element
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

k and n
k - 1 and k + 1
k - 1 and n - 1
k + 1 and n-k


9. Assuming all numbers are in 2's complement
representation, which of the following numbers is divisible
by 11111011 ?

11100111
11100100
11010111
11011011


10. For a pipelined CPU with a single ALU, consider the
following situations

The j + 1-st instruction uses the result of the j-th
instruction as an operand
The execution of a conditional jump instruction
The j-th and j + 1-st instructions require the ALU at the
same time
Which of the above can cause a hazard?

I and II only
II and III only
III only
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

Q (1)
Q (log n)
Q (n)
Q (n 2)


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 ?, and Shyam shows a
polynomial time reduction from ? to 3-SAT. Which of the
following can be inferred from these reductions?

? is NP-hard but not NP-complete
? is in NP, but is not NP-complete
? is NP-complete
? is neither NP-hard, nor in NP


13. Nobody knows yet if P = NP. Consider the language L
defined as follows:





Which of the following statements is true?

L is recursive
L is recursively enumerable but not recursive
L is not recursively enumerable
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

(1*0)*1*
0 + (0 + 10)*
(0 + 1)* 10(0 + 1)*
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 n 1
states and the LALR parser for G has n 2 states. The
relationship between n l and n 2 is

(a) n 1 is necessarily less than n2

(b) n 1 is necessarily equal to n2

(c) n 1 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?

7 5 1 0 3 2 4 6 8 9
0 2 4 3 1 6 5 9 8 7
0 1 2 3 4 5 6 7 8 9
9 8 6 4 2 3 0 1 5 7


20. Consider the following three claims

(n + k) m = Q (n m), where k and m are constants
2 n + 1 = 0(2 n)
2 2n + 1 = 0(2 n)
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

a b e g h f
a b f e h g
a b f h g e
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

(e) 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 (n 2) (b) become Q (n (log n) 2)

(e) become Q (n log n) (d) become Q (n)



23. In a heap with n elements with the smallest element at
the root, the 7 th smallest element can be found in time

Q (n log n)
Q (n)
Q (log n)
Q (1)


24. Which of the following statements is FALSE?

(a) In statically typed language, 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

better disk throughput but poorer disk space utilization
better disk throughput and better disk space utilization
poorer disk throughput but better disk space utilization
poorer disk throughput and poorer disk space utilization


26. In a system with 32 bit virtual addresses and 1 KB 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 transaction writes a data item after it is read by an
uncommitted transaction
A transaction reads a data item after it is read by an
uncommitted transaction
A transaction reads a data item after it is written by a
committed transaction
A transaction reads a data item after it is written by an
uncommitted transaction


30. Consider the following SQL query

select distinct a 1. a 2, ...... , a n

from r 1, r 2???.., r m

where P



For an arbitrary predicate P, this query is equivalent to
which of the following relational algebra expressions?

(a)

(b)

(c)

(d)


Q. 31-90 CARRY TWO MARKS EACH


31. Let (S, ? ) be a partial order with two minimal 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, 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 ? 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 v b ] ? ( $ x)[ a ]) ? ( " x) [ a ]

(d) ( " x) [ a ? b ] ? (( " x)[ a ] ? ( " x) [ b ])



33. Consider the following formula a and its two
interpretations I 1 and I 2

a: ( " x) [P x ? ( " y) [Q xy ? ? Q yy]] ==> ( " x) [ ? P x]

I 1: Domain: the set of natural numbers

P x == 'x is a prime number

Q xy == 'y divides x'

I 2: same as I 2 except that Px = 'x is a composite number'.

Which of the following statements is true?

(a) I 1 satisfies a , I 2 does not

(b) I 2 satisfies a , I 1 does not

(c) Neither I 1 nor I? 2 satisfies a

(d) Both I 1 and I 2 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(m 2) for m ? 1 is

(a)

(b)

(c)

(d)



36. How many perfect matchings are there in a complete graph
of 6 vertices?

15
24
30
60


37. Let f: A ? B be an injective (one-to-one) function.
Define g: 2 A ? 2 B as:

g(C) = (f(x) \x ? C}, for all subsets C of A.

Define h: 2 B ? 2 A as: h(D) = { x\x ? A, f(x) ? D}, for all
subsets D of B.

Which of the following statements is always true?

g(h(D)) ? D
g(h(D)) ? D
g(h(D)) ? D = f
g(h(D)) ? (B-D) ? f


38. Consider the set {a, b, c} with binary operators + and x
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 x b = c and b x c = a.
Given the following set of equations:



(a x x)+(a x y)=c

(b x x)+(c x 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 P i denote the i-th prime number (p 1 = 2)

For a non-empty string s = a 1...a n where each a i ? ? ,
define f(s) = ? n i= 1p i g(ai). For

a non-empty sequence (< Sl?Sn>) of strings from ? + , define



h(<s l?s n>) = ? n i = 1 p i f(si)

Which of the following numbers is the encoding, h of a
non-empty sequence of strigs ?

2 73 75 7
2 83 85 8
2 93 95 9
2 105 107 10


40. A graph G = (V,E) satisfies | E | ? 3 | V | - 6. The
min-degree of G is defined as

min {degree (v)}. Therefore, min-degree of G cannot be

v ? V

3
4
5
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?

0
1
2
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).





I f we use the Newton-Raphson method to find the roots of
f(x) = 0 using x 0, x 1 and x 2 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.3respectively

(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:







What is the maximum difference between two successive real
numbers representable in this system?

2 ?40
2-9
2 22
2 31


44. A 1-input, 2-output synchronous sequential circuit
behaves as follows:

Let Z k n k denote the number of O's and 1's respectively in
initial k bits of the input

(Z k + n k = k). The circuit outputs 00 until one of the
following conditions holds.

Z k ? n k = 2. In this case, the output at the k-th and all
subsequent clock ticks Is 10
N k ? Z k = 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? ?

5
6
7
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-or-sum
and sum-of ?product representations respectively of the
function given by the following Karnaugh map? Here, X
denotes "don't care"



xy ?
00
01
11
10

Zw ?





00
X
1
0
1

01
0
1
X
0

11
1
X
X
0

10
X
0
0
X














(11, 9)
(9, 13)
(9, 10)
(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 C o only (+ and -denote
addition and subtraction respectively)?

A+ B, and A-B, but not A+ 1
A+B, and A+ 1, but not A-B
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 d 1 = 2 ns and d 2 = 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 ?



1
2
3
4


THE FOLLOWING INFORMATION PERTAINS TO Q. 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.



MOVB, #0 ; B O

MOVC, #8 ; C 8

Z: CMP C, # 0 ; compare C with 0

JZX ; jump to X if zero flag is set

SUB C, # 1 ; C C-l

RRCA, # 1 ; right rotate A through carry by one bit. Thus:

; if the initial values of A and the carry

flag are a 7...a O and

; Co respectively, their values after the execution

of this

; instruction will be C 0a 7...a 1 and a 0 respectively.

JCY ; jump to Y if carry flag is set

JMPZ ; jump to Z

Y: ADD B, # 1 ; B B+l

JMPZ ; jump to Z

X:



48. If the initial value of register A is A 0, the value of
register B after the program execution will be

the number of 0 bits in A 0
the number of 1 bits in A 0
A 0
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?

RRCA, #
NOP ; no operation
LRC A, # 1 ; left rotate A through carry flag by one bit
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 l e

Which of the following statements is true?

(a) G is not ambiguous

(b) There exist x, y, ? L (G) such that xy ? 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 L 1 and L 2 each on the alphabet
? . Let f: ? ? ? be a

polynomial time computable bijection such that ( " x) [x ? L
1 iff f(x) ? L 2].Further,

let f -l be also polynomial time computable..

Which of the following CANNOT be true ?

(a) L 1 ? P and L 2 is finite

(b) L 1 ? NP and L 2 ? P

(c) L 1 is undecidable and L 2 is decidable

(d) L 1 is recursively enumerable and L 2 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
q0, 1, 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 string ending in a 0

(d) M halts on all string ending in a 1





54. Define languages L 0 and L 1 as follows:

L 0 = {<M, w,O> I M halts on w}

L 1 = {<M, w, 1> I M does not halts 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 = L 0 ? L 1.
Which of the following is true?

(a) L is recursively enumerable, but is not

(b) is recursively enumerable, but L is not

(c) Both Land L 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 L 1 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 state of M to accepting states. Which of the
following statements is true?



L 1 = {O, 1}* - L
L 1 = {O, 1}*
L 1 ? L
L 1 = L


56. Consider the grammar shown below

S ? i E t S S ' l a

S' ? e S | e

E ? b

In the predictive parse table. M, of this grammar, the
entries M[S', eJ 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 ? CC

C ? cC | d

The grammar is

LL (1)
SLR (1) but not LL (1)
LALR (1) but not SLR (1)
LR (1) but not LALR (1)




58. Consider the translation scheme shown below

S ? TR

R ? + T {print ('+');} R | e

T ? num {print (num.val);}

Here num 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

9 + 5 + 2
9 5 + 2 +
9 5 2 + +
+ + 9 5 2


59. Consider the syntax directed definition shown below.

S ? id : = E {gen (id.place = E.place;);}

E ?E 1 + E 2 {t = newtemp ( );

gen (t = E 1. place + E 2.place;);

E.place = t}

E ? id {E.place = id.place;}

Here, gen 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 t i'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) t 1 = Y + Z; X t 1

(c) t 1 = Y; t 2 = t 1 + Z; X = t2

(d) t 1 = Y; t 2 = Z; t 3 = t 1 + t 2; X = t 3



60. A program consists of two modules executed sequentially.
Let f 1(t) and f 2(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



f 1 (t) + f 2(t)


max {f 1(t), f 2(t)}
THE FOLLOWING INFORMATION PERTAINS TO Q. 61-62

In a permutation a 1?a n of n distinct integers, an
inversion is a pair (a i, a j) such that i <j and a i >a j



61. If all permutations are equally likely, what is the
expected number of inversions in a randomly chosen
permutation of 1...n ?

(a) n(n -1)/2 (b) n(n -1)/4

(c) n(n + 1)/4 (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 (n 2) (b) Q (n log n)

(c) Q (n 1.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 (log n) time, where n is the number of elements in
the set.

Delection of the smallest element
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 operation take X seconds each, and Y seconds
elapse between the end of one such stack operation and the
Blurt 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

n (X+ Y)
3Y + 2X
n (X+ Y)-X
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 m 3 ? n. The complexity
of computing the cube root of n (n is represented in binary
notation) is

O(n) but not O(n 0.5)
O(n 0.5) but not O ((log n) k) for any constant k > 0
O ((log n) k) for some constant k > 0, but not O ((log log
n) m) for any constant m > 0
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 sub graph G
1 = (V 1, E 1). 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 v 1 of V 1
as the source. Which of the following can always be inferred
from the path costs computed?

The number of edges in the shortest paths from V 1 to all
vertices of G
G 1 is connected
V 1 forms a clique in G
G 1 is a tree


68. What is the weight of a minimum spanning tree of the
following graph?



29
31
38
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: "a s b s a s a e d s a e e s f s b e d
e g s e e f e h s g e h e". Here, x s denotes the starting
time and X e denotes the ending time of activity X. W 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 V i to V j in G is sequence of vertices (V i, v
i+1, ..., V j) such that (V k, V k+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 follow



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 terminal of the above algorithm?

A[j,k] ? n
If A [j, j] ? n - 1, then G has a Hamiltonian cycle
If there exists a path from j to k, A[j, k] contains the
longest path lens from j to k
If there exists a path from j to k, every simple path from j
to k contain 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(xx)]

(b) ( " x) [( " y) [B (x, y) ? C (y)] ? A (x) ] ? ? ( $ x)
[B(xx)]

(c) ( " x) [( $ y) [B (x, y) ? C (y)] ? A (x) ] ? ? ( $ x)
[B(xx)]

(d) ( " x) [( " y) [B (x, y) ? C (y) ? A (x) ? ( $ x) [B(xx)]



72. The following resolution rule is used in logic programming:

Derive clause (P ? Q) from clauses (P ? B), (Q ? ? R)

Which of the following statements related to this rule is
FALSE?

((P v R) ? (Q ? ? R)) ? (P v Q) is logically valid
(P v Q) ? ((P v R) ? (Q ? ? R)) is logically valid
(P v Q) is satisfiable if and only if (P v R) ? (Q ? ? R) is
satisfiable
(P v) ? FALSE if and only if both P and Q are unsatisfiable
THE Q FOLLOWING INFORMATION PERTAINS TO Q. 73-741

The following program fragment is written in a programming
language that allows 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:

P x = new Q ( );

Q y = new Q ( );

P z = 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

1 2 1
2 1 1
2 1 2
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 10ms CPU bursts with 90ms 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?

First come first served scheduling
Shortest remaining time first scheduling
Static priority scheduling with different priorities for the
two processes
Round robin scheduling with a time quantum of 5 ms.


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)

1.5 ns
2 ns
3 ns
4 ns




79. Suppose a process has only the following pages in its
virtual address space: two contiguous code pages starting at
virtual address 0x00000000, two contiguous data pages
starting at virtual address OxO0400000, and a stack page
starting at virtual address 0xFFFFF000. The amount of memory
required for storing the page tables of this process is

8 KB
12 KB
16 KB
20 KB
THE FOLLOWING INFORMATION 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' ?

P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially I,
and T initially 0
p(S) at W, V(T) at X, p(T) at Y, V(S) at Z, S and T initially 1
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 0.1"0 or 10"1
where n is odd?

p(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S and T initially 1
P(S) at W, V(T) at X, p(T) at Y, V(S) at Z, Sand T initially 1
P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1
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 10 7 bps bandwidth and uses
CSMA/CD. The signal travels along the wire at 2 x 10 8 m/s.
What is the minimum packet size that can be used on this
network?

50 bytes
100 bytes
200 bytes
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
m s. Acknowledgement packets (sent only from B to A) are
very small and require negligible transmission time. The
propagation delay over the link is 200 m S. What is the
maximum achievable throughput in this communication?

(a) 7.69 x 10 6 bps (b) 11.11 x 10 6 bps

(c) 12.33 x 10 6 bps (d) 15.00 x 10 6 bps

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)

select distinct Name

from Students, Courses, Grades

where Students. Roll _number = Grades. Roll _number

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) Name 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.



















T1 T2 T3





R (D3);

R (D2);

W (D2);

R (D2);

R (D3);

Time R(D1);

W(Dl);

W(D2);

W(D3);



R(Dl);

R(D2);

W(D2);



W(Dl);



The schedule is serializable as T2; T3; T1
The schedule is serializable as T2; T1; T3
The schedule is serializable as T3; T2; T1
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 intialized to an integer ? 3, and TwoLog _n is
initialized to the value of2* ? iog 2(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]) print f ("%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 =
i 2]}

(c) {m I m ? n, m is prime} (d) {}

89. Consider the C program shown below.

# include <stdio.h>

#define print (x) print f ("%d", x)

intx;

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

1276
22 12 11
14 6 6
766


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

the list is empty or has exactly one element
the elements in the list are sorted in non-decreasing order
of data value
the elements in the list are sorted in non-increasing order
of data value
not all elements in the list have the same data value.

Is This Answer Correct ?    10 Yes 2 No

Graduate Aptitude Test in Engineering ( GATE ) Question Paper - 2003 COMPUTER SCIENCE & EN..

Answer / rrt

option c

Is This Answer Correct ?    3 Yes 1 No

Graduate Aptitude Test in Engineering ( GATE ) Question Paper - 2003 COMPUTER SCIENCE & EN..

Answer / kumarvimlendra

answer to q80 - option b

Is This Answer Correct ?    2 Yes 1 No

Graduate Aptitude Test in Engineering ( GATE ) Question Paper - 2003 COMPUTER SCIENCE & EN..

Answer / guest

1 b

Is This Answer Correct ?    2 Yes 1 No

Graduate Aptitude Test in Engineering ( GATE ) Question Paper - 2003 COMPUTER SCIENCE & EN..

Answer / guest

Answer 73:c
74:b

Is This Answer Correct ?    0 Yes 0 No

Graduate Aptitude Test in Engineering ( GATE ) Question Paper - 2003 COMPUTER SCIENCE & EN..

Answer / anu

Answer 73-c

Is This Answer Correct ?    0 Yes 0 No

Graduate Aptitude Test in Engineering ( GATE ) Question Paper - 2003 COMPUTER SCIENCE & EN..

Answer / anil

58-b

Is This Answer Correct ?    0 Yes 2 No

Post New Answer

More GATE Interview Questions

what is abstract class?

11 Answers  


The horse has played a little known but very important role in the field of medicine. Horses were injected with toxins of diseases until their blood built up immunities. Then a serum was made from their blood.Serums to fight with diphtheria and tetanus were developed this way. It can be inferred from the passage, that horses were (A) given immunity to diseases (B) generally quite immune to diseases (C) given medicines to fight toxins (D) given diphtheria and tetanus serums

0 Answers   GATE,


weather any body knows how th partiton of sections in rrb is aote 1,genera nowlge 2,intellgince 3,maths 4,english 5,science

0 Answers  


how to prepare for bcil bitp

0 Answers  


Tripura Board of Secondary Education Agartala, Tripura Examination Results 2009 Tripura Board of Secondary Education Higher Secondary (+2 Stage) Examination - Year 2009

0 Answers  






hai i need to no hpcl portion i am going to write on march2 so please send to my id satish_don334@yahoo.co.in

0 Answers  


hi all,my name is RANJAN...may i know how gate 2010 paper is going to be and culd u suggest me some imp tiptricks to prepare and also plz give me information about assistant engineer exam and how to prepare for it. waiting for reply in kind......... thnq..

0 Answers  


explain cyber security?

0 Answers   Infosys,


What is Curency of Somalia

0 Answers  


difference between connection less and wireless network ?

1 Answers   GATE, KLN College of Engineering,


What qualification is required for appearing for mpsc exam?

3 Answers   ABC,


what is inflationWhat is Inflation? How can we calucalate inflation? and what is the present rate of Inflation?

1 Answers  


Categories