Graduate Aptitude Test in Engineering ( GATE ) Question Paper

Graduate Aptitude Test in Engineering ( GATE )

Question Paper - 1999

COMPUTER SCIENCE & ENGINEERING

Question Posted / anirudh

1 Answers
12771 Views
NIC, I also Faced
E-Mail Answers

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

Answer / anirudh

GATE - 1999

COMPUTER SCIENCE & ENGINEERING

SECTION - A (75 Marks)

1. This question consists of (Twenty-five) multiple-choice
questions each carrying one mark. For each ques?tion, four
options are provided out of which exactly one is correct.
Write the correct option for each question ONLY in the box
provided for the question in the first sheet of the answer
book. (25 x 1 = 25)

1.1 Suppose that the expectation of a random variable X is
5. Which of the following statements is true?

There is a sample point at which X has the value 5.
There is a sample point at which X has value greater than 5.
There is a sample point at which X has a value greater than
or equal to 5.
None of the above.

1.2 The number of binary relations on a set with n elements is:

n 2
2 n

None of the above

1.3 The number of binary strings of n zeros and k ones that
no two ones are adjacent is

n-1 C k
n C k
n C k+l
None of the above

1.4 Consider the regular expression (0 + 1) (0 + 1)??..n
times. The minimum state finite automation that recognizes
the language represented by this regular expression contains

n states
n + I states
n + 2 states
(d) None of the above

1.5 Context-free languages are closed under:

Union , intersection
Union , Kleene closure
Intersection, complement
Complement, Kleene Closure

1.6 Let L p be the set of all languages accepted by a PDA by
final state and L E the set of all languages accepted by
empty stack. Which of the following is true?

(a) L D = L E (b) L D ? L E

(c) L D = L E (d) None of the above

1.7 Which of the following expressions is not equivalent to ?

x NAND x
x NOR x
x NAND 1
x NOR 1

1.8 Which of the following functions implements the Karnaugh
map shown below?

AB/CD
00
00
11
10

00
0
0
1
0

01
X
X
1
X

11
0
1
1
0

10
0
1
1
0

(a)

(b) D (C + A)

(c)

(d)

1.9 Listed below are some operating system abstractions (in
the left column) and the hardware components (in the right
column)?

Thread 1. Interrupt
Virtual address space 2. Memory
File system 3. CPU
Signal 4. Disk

(A)-2, (B)-4, (C)-3, (D)-1
(A)-I, (B)-2, (C)-3, (D)-4
(A)-3, (B)-2, (C)-4, (D)-1
(A)-4, (B)-1, (C)-2, (D)-3

1.10 Which of the following disk scheduling strategies is
likely to give the best through put?

Farthest cylinder next
Nearest cylinder next
First come first served
Elevator algorithm

1.11 System calls are usually invoked by using

a software interrupt
polling
an indirect jump
a privileged instruction

1.12 A sorting technique is called stable if

it takes 0 (n log n) time
it maintains the relative order of occurrence of
non-distinct elements
it uses divide and conquer paradigm
(d) it takes 0 (n) space.

1.13 Suppose we want to arrange the n numbers stored in any
array such that all negative values occur before all
positive ones. Minimum number of exchanges required in the
worst case is

n-I
n
n + 1
None of the above

1.14 If one uses straight two-way, merge sort algorithm to
sort the following elements in ascending order:

20, 47, 15, 8, 9, 4, 40, 30, 12, 17

then the order of these elements after second pass of the
algorithm is :

8,9, 15,20,47,4, 12, 17,30,40
8, 15,20,47,4,9,30,40, 12, 17
15,20,47, 4, 8, 9,12,30,40,17
4,8,9,15, 20,47, 12, 17,30,40

The number of articulation points of the following graph is

0
1
2
3

1.16 If n is a power of 2, then the minimum number of
multiplications needed to compute a* is

log 2n

n-I
n

1.17 Which of the following is the most powerful parsing
method?

LL (I)
Canonical LR
SLR
LALR

1.18 Consider the join of a relation R with a relation S. If
R has m tuples and S has n tuples then the maximum and
minimum sizes of the join respectively are

m+n and O
mn and O
m+ n and |m-n |
mn and m+ n

1.19 The relational algebra expression equivalent to the
following tuple calculus expression:

{t | t ? r ? (t [A] = 10 ? t[B] = 20)} is :

s (A=10vB=20) (r)
s (A=l0) (r) ? s (B=20) (r)
s (A= 10) (r) ? s (B=20) (r)
s (A=IO) (r) - s (B=20) (r)

1.20 Booth's coding in 8 bits for the decimal number - 57 is

0 - 100 + 1000
0 - 100 + 100 ? I
0 - 1 + 100 -10 + I
00- 10 + 100-1

1.21 The maximum gate delay for any output to appear in an
array multiplier for multiplying two n bit number is

O(n 2)
O(n)
O (log n)
O (I)

1.22 The main memory of a computer has 2 cm blocks while the
cache has 2 c blocks. If the cache uses the set associative
mapping scheme with 2 blocks per set, then block k of the
main memory maps to the set

(k mod m) of the cache
(k mod c) of the cache
(k mod 2c) of the cache
(k mod 2 cm) of the cache

1.23 The Newton-Raphson method is to be used to find the
root of the equation f (x) = 0 where Xo is the initial
approximation and f 1 is the derivative of f. The method
converges

always
only if f is a polynomial
only if f (x o) < 0
none of the above

1.24 Let R = (a, b, c, d, e, f) be a relation scheme with
the following dependencies c ? f, e ? a, ec ? d, a ? b.
Which of the following is a key for R ?

CD
EC
AE
AC

1.25 Which of the following is correct?

B-trees are for storing data on disk and B* trees are for
main memory.
Range queries are faster on B* trees.
B-trees are for primary indexes and B* trees are for
secondary indexes.
The height of a B* tree is independent of the number of
records.

2. This question consists of 25 (Twenty-five)
multiple-choice questions each carrying 2 marks. For each
question , 4 options are provided out of which one or more
are correct. Write ALL the correct options for each
question, only in the box provided for the question in the
second sheet of the answer book. Credit will be given only
if all and only the correct options are written. (25 x 2 = 50)

Consider two events E 1 and E 2 such that probability of E
1, Pr [E 1] = ? probability of E 2, Pr [E 21 ] = 1/3, and
probability of E 1 and E 2, Pr [E 1 and E 2] = 1/5. Which of
the following statements is/are true?
Pr [E 1 or E 2] is 2/3
Events E 1 and E 2 are independent
Events E 1 and E 2 are not independent

Two girls have picked 10 roses, 15 sunflowers and 15
daffodils. What is the number of ways they can divide the
flowers amongst themselves?
1638
2100
2640
None of the above

2.3 Let L be a set with a relation R which is transitive,
anti-symmetric and reflexive and for any two elements a, b ?
L let the least upper bound lub (a, b) and the greatest
lower bound glb (a, b) exist. Which of the following is/are
true?

L is a poset
L is a boolean algebra
L is a lattice
None of the above

2.4 If L1 is context free language and L2 is a regular
language which of the following is/are false?

L1 - L2 is not context free
L1 ? L2 is context free
~ L1 is context free
~ L2 is regular

2.5 Given the programming constructs (i) assignment (ii) for
loops where the loop parameter cannot be changed within the
loop (iii) If-then-else (iv) forward go to (v) arbitrary go
to (vi) non-recursive proce dure call (vii) recursive
procedure/function call (viii) repeat loop, which constructs
will you not include in a programming language such that it
should be possible to program the terminates (i.e. halting)
function in the same programming language.

(ii), (iii), (iv)
(v), (vii), (viii)
(vi), (vii), (viii)
(iii), (vii), (viii)

For the schedule given below, which of the following is
correct:
1 Read A

2 Read B

3 Write A

4 Read A

5 Write A

6 Write B

7 Read B

8 Write B

(a) This schedule is serialisable and can occur in a scheme
using 2PL protocol.

(b) This schedule is serialisable but cannot occur in a
scheme using 2PL protocol.

(c) This schedule is not serialisable but can occur in a
scheme using 2PL protocol.

(d) This schedule is not serialisable and cannot occur in a
scheme using 2PL protocol.

2.7 Consider the schema R = (S T U V) and the dependencies S
? T, T ? U. U ? V and V ? S. Let R = (R1 and R2) be a
decomposition such that R1 ? R2 = ? . The decomposition is

not in 2NF
in 2NF but not 3NF
in 3NF but not in 2NF
in both 2NF and 3NF

Consider the circuit shown below. In a certain steady
state, the line Y is at '1 '. What are the possible values
of A, B, and C in this state?

A = 0, B = 0, C = I
A = 0, B = 1, C = 1
A = 1, B = 0, C = 1
A = 1, B = 1, C = 1

2.9 Which of the following sets of component (s) is/are
sufficient to implement any arbitrary boolean func? tion?

XOR gates, NOT gates
2 to I multiplexors
AND gates, XOR gates
Three-input gates that output (A. B) + C for the inputs A B.
and C.

2.10 A multi-user, multi-processing operating system cannot
be implemented on hardware that does not support

Address translation
DMA for disk transfer
At least two modes of CPU execution (privileged and
non-privileged)
Demand paging.

2.11 Which of the following is/are advantages of virtual
memory?

(a) Faster access to memory on an average.

(b) Processes can be given protected address spaces.

(c) Linker can assign addresses independent of where the
program will be loaded in physical memory.

(d) Programs larger than the physical memory size can be run.

2.12 Which of the following actions is/are typically not
performed by the operating system when switching context
from process A to process B?

(a) Saving current register values and restoring saved
register values for process B.

(b) Changing address translation tables.

(c) Swapping out the memory image of process A to the disk

(d) Invalidating the translation look-aside buffer.

Consider the following program in a language that has
dynamic scoping
var x: real;

procedure show:

begin print (x) ; end;

procedure small :

var x: real;

begin x : = 0.125; show; end:

begin x : = 0.25;

show; small

end.

Then the output of the program is :

0.125 0.125
0.25 0.25
0.25 0.125
0.125 0.25

The number of tokens in the Fortran statement DO 10I= 1.25 is
3
4
5
None of the above

2.15 A grammar that is both left and right recursive for a
non-terminal, is

Ambiguous
Unambiguous
Information is not sufficient to decide whether it is
ambiguous or unambiguous
None of the above

2.16 The number of full and half-adders required to add
16-bit numbers is

8 half-adders, 8 full-adders
1 half-adder, 15 full-adders
16 half-adders, 0 full-adders
4 half-adders, 12 full-adders

2.17 Zero has two representations in

Sign magnitude
1's complement
2's complement
none of the above

Raid configurations of disks are used to provide
Fault-tolerance
High speed
High data density
None of the above

2.19 Arrange the following configurations for. CPU in
decreasing order of operating speeds: Hard wired control,
vertical microprogramming, horizontal microprogramming.

Hard wired control, vertical micro-programming, horizontal
micro-programming
Hard wired control, horizontal micro-programming, vertical
micro-programming
Horizontal micro-programming, vertical micro-programming,
hard wired control.
Vertical micro-programming, horizontal micro-programming,
hard wired control.

2.20 The minimum number of record movements required to
merge five files A (with 10 records), B (with 20 records), C
(with 15 records), D (with 15 records), D (with 5 records)
and E (with 25 records) is:

165
90
75
65

2.21 If T 1 = 0 (1), give the correct matching for the
following pairs:

(M) T n = T n-1 + n (U) T n = 0 (n)

(N) T n = T n/2 + n (V) T n = 0 (nlog n)

(0) T n =T n/2+n1ogn (W) T n=0(n 2)

(P) T n = T n-1 + log n (X) T n = 0 (log 2 n)

M-W, N-V, O-U, P-X
M-W, N-U, O-X, P-V
M-V, N-W, O-X, P-U
M-W, N-U, O-V, P-X

2.22 The main difference(s) between a ClSC and a RISC
processor is/are that a RISC processor typically

has fewer instructions
has fewer addressing ,modes
has more registers
is easier to implement using hard-wired control logic

2.23 A certain processor supports only the immediate and the
direct addressing modes. Which of the follow?ing programming
language features cannot be implemented on this processor?

Pointers
Arrays
Records
Recursive procedures with local variable

Consider the following C function definition
int Trial (int a, int b, int c)

{

if ((a> = b)&& (c < b) return b;

else if (a> = b) return Trial (a, c, b);

else return Trial (b, a, c) ;

}

The function Trial :

finds the maximum of a, b and c
finds the minimum of a, b and c
finds the middle number of a, b, c
none of the above

2.25 Which of the following is/are correct ?

An SQL query automatically eliminates duplicates
An SQL query will not work if there are no indexes on the
relations
SQL permits attribute names to be repeated in the same relation
None of the above

Is This Answer Correct ?

46 Yes

6 No

Post New Answer