Graduate Aptitude Test in Engineering ( GATE ) Question Paper

Graduate Aptitude Test in Engineering ( GATE )

Question Paper - 2000

COMPUTER SCIENCE & ENGINEERING

Question Posted / anirudh

2 Answers
9764 Views
I also Faced
E-Mail Answers

Answers were Sorted based on User's Feedback

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

Answer / anirudh

GATE - 2000

COMPUTER SCIENCE & ENGINEERING

SECTION -A (75 marks)

1. This question consists of 23 (TWENTY THREE)
multiple-choice questions, each carrying one mark. For each
question (1. 1-1. 23), four alternatives (a, b, c and d) are
given, out of which only one is correct. Write the correct
answers in the boxes corresponding to the questions only on
the FIRST sheet of the answer book. ( 23 X l = 23)

1.1 The minimum number of cards to be dealt from an
arbitrarily shuffled deck of 52 cards to guarantee that
three cards are from some same suit is

3
8
9
12

1.2 An n x n array v is defined as follows:

v [i, j] = i-j for all i, j, 1 ? i ? n, 1 ? j ? n

The sum of the elements of the array v is

0
n-1
n 2 - 3n + 2
n 2 (n + 1) /2

1.3 The determinant of the matrix is

4
0
5
20

1.4 Let S and T be languages over S = {a, b} represented by
the regular expressions (a + b *) * and (a + b) *,
respectively. Which of the following is true?

S ? T
T ? S
S = T
S ? T = f

1.5 Let L denotes the language generated by the grammar S ?
0S0/00.

Which of the following is true?

L = 0 +
L is regular but not 0 +
L is context free but not regular
L is not context free

1.6 The number 43 in 2's complement representation is

01010101
11010101
00101011
10101011

1.7 To put the 8085 microprocessor in the wait state

lower the-HOLD input
lower the READY input
raise the HOLD input
raise the READY input

1.8 Comparing the time T1 taken for a single instruction on
a pipelined CPU with time T2 taken on a non? pipelined but
identical CPU, we can say that

T1 ? T2
T1 ? T2
T1< T2
T1 is T2 plus the time taken for one instruction fetch cycle

1.9 The 8085 microprocessor responds to the presence of an
interrupt

as soon as the TRAP pin becomes 'high'
by checking the TRAP pin for 'high' status at the end of
each instruction fetch
by checking the TRAP pin for 'high' status at the end of the
execution of each instruction
by Checking the TRAP pin for 'high' status at regular intervals

1.10 The most appropriate matching for the following pairs

X: Indirect addressing 1 : Loops

Y: Immediate addressing 2 : Pointers

Z: Auto decrement addressing 3: Constants

is

X-3, Y-2, Z-1
X-I, Y-3, Z-2
X-2, Y-3, Z-1
X-3, Y-l, Z-2

1.11 The following C declarations

struct node {

int i;

float j ;

};

struct node *s[10] ;

define s to be

(a) An array, each element of which is a pointer to a
structure of type node

(b) A structure of 2 fields, each field being a pointer to
an array of 10 elements

(c) A structure of 3 fields: an integer, a float, and an
array of 10 elements

(d) An array, each element of which is a structure of type node

1.12 The most appropriate matching for the following pairs

X: m = malloc (5); m=NULL; 1 : using dangling pointers

Y: free (n) ; n-> value=5; 2 : using uninitialized pointers

Z: char *p; *p = 'a' ; 3 : lost memory

is

X-I, Y-3, Z-2
X-2, Y-l, Z-3
X-3, Y-2, Z-l
X-3, Y-l, Z-2

1.13 The most appropriate matching for the following pairs

X: depth first search 1: heap

Y: breadth-first search 2: queue

Z: sorting 3: stack

is

,X-l,Y-2; Z-3
X-3, Y-l, Z-2
X-3, Y-2, Z-l
X-2, Y-3, Z-l

1.14 Consider the following nested representation of binary
trees: (X Y Z) indicates Y and Z are the left and right sub
trees, respectively, of node X Note that Y and Z may be
NULL, or further nested. Which of the following represents a
valid binary tree?

(1 2 (4 5 6 7))
(1( (2 3 4) 5 6)7)
(1 (2 3 4)(5 67))
(1 (23 NULL) ( 4 5))

1.15 Let s be a sorted array of n integers. Let t (n) denote
the time taken for the most efficient algorithm to determine
if there are two elements with sum less than 1000 in s.
Which of the following statements is true?

t (n) is 0 (1)
n ? t (n) ? n log 2 n
n log 2 n ? t (n) <
t (n) =

1.16 Aliasing in the context of programming languages refers to

multiple variables having the same memory location
multiple variables having the same value
multiple variables having the same identifier
multiple uses of the same variable

1.17 Consider the following C declaration

struct {

short s [5]

union {

float y;

long z;

}u;

} t;

Assume that objects of the type short, float and long occupy
2 bytes, 4 bytes and 8 bytes, respectively. The memory
requirement for variable t, ignoring alignment
considerations, is

(a) 22 bytes (b) 14 bytes

(e) 18 bytes (d) 10 bytes

1.18 The number of tokens in the following C statement

printf("i=%d, &i= %x", i, &i);

is

3
26
10
21

1.19 Which of the following derivations does a top-down
parser use while parsing an input string? The input is
assumed to be scanned in left to right order.

(a) Leftmost derivation

(b) Leftmost derivation traced out in reverse

(c) Rightmost derivation

(d) Rightmost derivation traced out in reverse

1.20 Which of the following need not necessarily be saved on
a context switch between processes?

General purpose registers
Translation look aside buffer
Program counter
All of the above

1.21 Let m [0]?.m [4] be mutexes (binary semaphores) and P
[0] ... P [4] be processes. Suppose each process P[i]
executes the following :

wait (m [i]); wait (m [(i + 1) mode 4]);

??..

release (m [i]) ; release (m[(i + 1) mod 4 ] );

This could cause

Thrashing
Deadlock
Starvation, but not deadlock
None of the above

1.22 B + -trees are preferred to binary trees in databases
because

Disk capacities are greater than memory capacities
Disk access is much slower than memory access
Disk data transfer rates are much less than memory data
transfer rates
Disks are more reliable than memory

1.23 Given the relations

employee (name, salary, deptno), and

department (deptno, deptname, address) .

which of the following queries cannot be expressed using the
basic relational algebra operations ( s , p , ? , |X|, ? , ?
, - )?

(a) Department address of every employee

(b) Employees whose name is the same as their department name

(c) The sum of all employee salaries

(d) All employees of a given department

2. This question consists of 26 (TWENTY SIX) multiple-choice
questions, each carrying two marks. For each question (2.1-
2. 26), four alternatives (a, b, c and d) are given, out of
which only one is correct. Write the correct answers in the
boxes corresponding to the questions only on the SECOND
sheet of the answer book. (26 x 2 = 52)

2.1 X, Y and Z are closed intervals of unit length on the
real line. The overlap of X and Y is half a unit. The
overlap of Y and Z is also half a, unit. Let the overlap of
X and Z be k units. Which of the following is true?

k must be 1
k must be 0?
k can take any value between 0 and 1
None of the above

E 1 and E 2 are events in a probability space satisfying the
following constraints:
Pr (E I) = Pr (E 2)
Pr (E I U E 2) = 1
E 1 and E 2 are independent
The value of Pr (E 1), the probability of the event E p is

0

1

2.3 Let

and

Which of the following statements is true?

S > T
S = T
S < T and 2S > T
2S ? T

2.4 A polynomial p(x) satisfies the following:

p (1) = p(3) = p(5) = 1

p(2) = p(4) = -1

The minimum degree of such a polynomial is

1
2
3
4

2.5 A relation R is defined on the set of integers as x Ry
if f(x + y) is even. Which of the following state?ments is
true?

R is not an equivalence relation
R is an equivalence relation having 1 equivalence class
R is an equivalence relation having 2 equivalence classes
R is an equivalence relation having 3 equivalence classes

2.6 Let P(S) denotes the power set of set S. Which of the
following is always true?

P(P (S)) = P(S)
P(S) ? P(P(S)) = { f }
P(S) ? S = P(S)
S ? P(S)

2.7 Let a, b, c, d be propositions. Assume that the
equivalences a ? (b V-b) and b ? c hold. Then the truth
value of the formula (a ? b) -J. (a ? c) ? d) is always

True
False
Same as the truth value of b
Same as the truth value of d

2.8 What can be said about a regular language L over {a}
whose minimal finite state automaton has two states?

L must be {a n| n is odd}
L must be {a n| n is even}
L must be {a n| ? O}
Either L must be {a n | n is odd}, or L must be {a n | n is
even}

2.9 Consider the following decision problems :

(PI) Does a given finite state machine accept a given string

(P2) Does a given context free grammar generate an infinite
number of stings

Which of the following statements is true?

(a) Both (PI) and (P2) are decidable (b) Neither (PI) nor
(P2) are decidable

(c) Only (PI) is decidable (d) Only (P2) is decidable

2.10 The simultaneous equations on the Boolean variables x,
y, z and w,

x+y+z=l

xy =0

xz+w = l

x+ =0

have the following solution for x, y, z and w, respectively.

(a) 0 1 0 0 (b) 1 1 0 1

(c) 1 0 1 1 (d) 1 0 0 0

2.11 Which function does NOT implement the Karnaugh map
given below?

WZ ?
00
01
11
10

Xy ?

00
0
x
0
0

01
0
x
1
1

11
1
1
1
1

10
0
x
0
0

(a) (w + x) y (b) xy + yw

(c) (w + x) (w + y) (x + y) (d) None of the above

The following arrangement of master-slave flip flops has the
initial state of P, Q as 0, 1 (respectively). After three
clock cycles the output state P, Q is (re?spectively),
1,0
1,1
0,0
0,1
?

2.13 A graphics card has on board memory of 1 MB. Which of
the following modes can the card not support?

(a) 1600 x 400 resolution with 256 colours on a 17-inch monitor

(b) 1600 x 400 resolution with 16 million colours on a
14-inch monitor

(c) 800 x 400 resolution with 16 million colours on a
17-inch monitor

(d) 800 x 800 resolution with 256 colours on a 14-inch monitor

2.14 Consider the values A = 2.0 x 10 30, B =-2.0 x 10 30 ,
C= 1.0, and the sequence

X: =A+B Y: =A+C

X: = X + C Y: =Y+B

executed on a computer where floating-point numbers are
represented with 32 bits. The values for X and Y will be

X = 1.0, Y = 1.0
X = 1.0, Y = 0.0
X = 0.0, Y = 1.0
X = 0.0, Y = 0.0

2.15 Suppose you are given an array s[1..n] and a procedure
reverse (s, i, j) which reverses the order of elements in a
between positions i and j (both inclusive). What does the
following sequence do, where 1 ? k ? n:

reverse (s, 1, k) ;

reverse (s, k + 1, n);

reverse (s, l, n) ;

(a) Rotates s left by k positions (b) Leaves s unchanged

(c) Reverses all elements of s (d) None of the above

2.16 Let LASTPOST, LASTIN and LASTPRE denote the last vertex
visited in a postorder, inorder and preorder traversal,
respectively, of a complete binary tree. Which of the
following is always true?

(a) LASTIN = LASTPOST (b) LASTIN = LASTPRE

(c) LASTPRE = LASTPOST (d) None of the above

2.17 Consider the following functions

Which of the following is true?

(a) h (n) is O (f (n) ) (b) h (n) is O (g (n))

(c) g (n) is not O (f (n) ) (d) f(n) is O(g (n))

2.18 Let G be an undirected connected graph with distinct
edge weight. Let e max be the edge with maximum weight and e
min the edge with minimum weight. Which of the following
statements is false?

Every minimum spanning tree of G must contain e min
If e max is in a minimum spanning tree, then its removal
must disconnect G
No minimum spanning tree contains e max
G has a unique minimum spanning tree

2.19 Let G be an undirected graph. Consider a depth-first
traversal of G, and let T be the resulting depth-first
search tree. Let u be a vertex in G and let v be the first
new (unvisited) vertex visited after visiting u in the
traversal. Which of the following statements is always true?

(a) {u,v} must be an edge in G, and u is a descendant of v in T

(b) {u,v} must be an edge in G, and v is a descendant of u in T

(c) If {u,v} is not an edge in G then u is a leaf in T

(d) If {u,v} is not an edge in G then u and v must have the
same parent in T

The value of j at the end of the execution of the following
C program
int incr (int i)

{

static int count = 0 ;

count = count + i ;

return ( count) ;

}

main ( ) {

int i, j ;

for (i = 0; i < = 4 ; i++)

j = incr (i) ;

}

is

10
4
6
7

Given the following expression grammar:
E ? E * F | F+E | F

F ? F-F | id

Which of the following is true?

(a) * has higher precedence than + (b) - has higher
precedence than *

(c) + and - have same precedence (d) + has higher precedence
than *

2.22 Suppose the time to service a page fault is on the
average 10 milliseconds, while a memory access takes 1
microsecond. Then a 99.99% hit ratio results in average
memory access time of

(a) 1.9999 milliseconds (b) 1 millisecond

(c) 9.999 microseconds (d) 1.9999 microseconds

2.23 Which of the following is NOT a valid deadlock
prevention scheme?

(a) Release all resources before requesting a new resource

(b) Number the resources uniquely and never request a lower
numbered resource than the last one requested

(c) Never request a resource after releasing any resource

(d) Request and all required resources be allocated before
execution

2.24 Given the following relation instance

X Y Z
1 4 2

1 5 3

1 6 3

3 2 2

Which of the following functional dependencies are satisfied
by the instance?

(a) XY ? Z and Z ? Y (b)YZ ? X and Y ? Z

(c)YZ ? X and X ? Z (d) XZ ? Y and Y ? X

2.25 Given relations r (w, x) and s (V, 1,), the result of

select distinct w, x

from r, s

is guaranteed to be same as r, provided

r has no duplicates and s is non-empty
r and shave no duplicates
s has no duplicates and r is non-empty
r and s have the same number of tuples

2.26 In SQL, relations can contain null values, and
comparisons with null values are treated as unknown. Suppose
all comparisons with a null value are treated as false.
Which of the following pairs is not equivalent?

(a) x = 5 not (not (x = 5 ) )

(b) x= 5 x> 4 and x < 6, where x is an integer

(c) x ? 5 not (x = 5)

(d) None of the above

Is This Answer Correct ?

18 Yes

5 No

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

Answer / ajay ghule

Is This Answer Correct ?

7 Yes

2 No

Post New Answer