Answer / anirudh

GATE ? 2001

COMPUTER SCIENCE & ENGINEERING




SECTION - A

(75 Marks)



1. This Question consists of (TWENTY FIVE) sub-questions
(1.1-1.25) of ONE mark each. For each of the sub questions,
four possible answers (a, b, c and d) are given, out of
which only one is correct. Answer each sub question by
darkening the appropriate bubble on the OBJECTIVE RESPONSE
SHEET (ORS) using a soft HB pencil. Do not use the ORS for
any rough work. You may like to use the Answer Book for any
rough work, if needed.



1.1 Consider the following statements:

S1 : The sum of two singular n x n matrices may be non-singular

S2 : The sum of two n x n non-singular matrices may be singular

Which of the following statements is correct?

Both S1 and S2 are true
S1 is true, S2 is false
S1 is false, S2 is true
S1 and S2 are both false


1.2 Consider the following relations:

R1 (a, b) if f(a + b) is even over the set of integers

R2 (a, b) if f(a + b) is odd over the set of integers

R3 (a, b) if f a.b > 0 over the set of non-zero rational
numbers

R4 (a, b) iff |a - b | ? 2 over the set of natural numbers

Which of the following statements is correct?

R1 and R2 are equivalence relations, R3 and R4 are not
R1 and R3 are equivalence relations, R2 and R4 are not
R1 and R4 are equivalence relations, R2 and R3 are not
R1, R2, R3 and R4 are all equivalence relations


1.3 Consider two well-formed formulas in prepositional logic

Fl : P ? ? P F2 : (P ? ? P) v ( ? P ? P)

Which of the following statements is correct?

F1 is satisfiable, F2 is valid
F1 unsatisfiable, F2 is satisfiable
F1 is unsatisfiable, F2 is valid
F1 and F2 are both satisfiable.


Consider the following two statements:
S1: {O 2n |n ? l} is a regu1ar language

S2: { O m 1 n O m+n lm ? l and n ? l} is a regu1ar language

Which of the following statements is correct?

Only S1 is correct
Only S2 is correct
Both S1 and S2 are correct
None of S1 andS2 is correct


1.5 Which of the following statements in true?

(a) If a language is context free it can always be accepted
by a deterministic push-down automaton

(b) The union of two context free languages is context free

(c) The intersection of two context free languages is
context free

(d) The complement of a context free language is context free



1.6 Given an arbitrary non-deterministic finite automaton
(NFA) with N states, the maximum number of states in an
equivalent minimized DFA is at least

(a) N 2 (b) 2 N

(c) 2N (d) N!



1.7 More than one word are put in one cache block to

(a) exploit the temporal locality of reference in a program

(b) exploit the spatial locality of reference in a program

(c) reduce the miss penalty

(d) none of the above



1.8 Which of the following statements is false? .

Virtual memory implements the translation of a program's
address space into physical memory address space
Virtual memory allows each program to exceed the size of the
primary memory
Virtual memory increases the degree of multiprogramming
Virtual memory reduces the context switching overhead


A low memory can be connected to 8085 by using
INTER

HOLD
READY


Suppose a processor does not have any stack pointer
register. Which of the following statements is true?
It cannot have subroutine call Instruction,
In can have subroutine call instruction, but no nested
subroutine calls
(c) Nested subroutine calls are possible, but interrupts are
not

(d) All sequences of subroutine calls and also interrupts
are possible



1.11 Given the following Karnaugh map, which one of the
following represents the minimal Sum-Of-Products of the map?



wx ?
00
01
11
10

Yz ?





00
0
X
0
X

01
X
1
X
1

11
0
X
1
0

10
0
1
X
0




xy+y'z (b) wx'y'+xy+xz
(c)w'x+y'z+xy (d) xz+y



1.12 A processor needs software interrupt to

test the interrupt system of the processor
implement co-routines
(c) obtain system services which need execution of
privileged instructions

(d) return from subroutine



1.13 A CPU has two modes - privileged and non-privileged. In
order to change the mode from privileged to non-privileged

a hardware interrupt is needed
a software interrupt is needed
a privileged instruction (which does not generate an
interrupt) is needed
a non-privileged instruction (which does not generate an
interrupt) is needed


1.14 Randomized quick sort is an extension of quick sort
where the pivot is chosen randomly. What is the worst-case
complexity of sorting n numbers using randomized quick sort?

O(n)
O(n log n)
O (n 2)
O(n!)
1.15 Consider an array representation of an n element binary
heap where the elements are stored from index 1 to index n
of the array. For the element stored at index i of the array
(i ? n), the index of the parent is

i-I
? i/2 ?
? i/21 ?
(i+1)/2


1.16 Let f(n) = n 2 1 g n and g(n) = n (1 g n) 10 be two
positive functions of n. Which of the following statements
is correct ?

f(n) = O(g(n) and g(n) ? O(f(n))
g(n) = O(f(n) and f(n) ? O(g(n))
f(n) ? O(g(n)) and g(n) ? O(f(n))
(d) f(n) = O(g(n)) and g(n) = O(f(n))



1.17 The process of assigning load addresses to the various
parts of the program and adjusting the code and date in the
program to reflect the assigned addresses is called

(a) Assembly (b) Parsing

(c) Relocation (d) Symbol resolution



1.18 Which of the following statements is false? ?

An unambiguous grammar has same leftmost and rightmost
derivation
An LL(1) parser is a top-down parser
LALR is more powerful than SLR
(d) An ambiguous grammar can never be LR(k) for any k



1.19 Consider a set of n tasks with known runtimes r 1, r 2,
... r n to be run on a uniprocessor machine. Which of the
following processor scheduling algorithms will result in the
maximum throughput?

(a) Round-Robin (b) Shortest-Job-First

(c) Highest-Response-Ratio-Next (d) First-Come-First-Served



1.20 Where does the swap space reside ?

(a) RAM (b) Disk

(c) ROM (d) On-chip cache

1.21 Consider a virtual memory system with FIFO page
replacement policy. For an arbitrary page access pattern,
increasing the number of page frames in main memory will

always decrease the number of page faults
always increase the number of page faults
some times increase the number of page faults
never affect the number of page faults


1.22 Which of the following requires a device driver?

Register
Cache
Main memory
Disk


1.23 Consider a schema R(A, B, C, D) and functional
dependencies A ? B and C ? D. Then the decomposition of R
into R 1 (AB) and R 2(CD) is

dependency preserving and loss less join
loss less join but not dependency preserving
dependency preserving but not loss less join
not dependency preserving and not loss less join


1.24 Suppose the adjacency relation of vertices in a graph
is represented in a table Adj(X, Y). Which of the following
queries cannot be expressed by a relational algebra
expression of constant length?

(a) List all vertices adjacent to a given vertex

List all vertices which have self loops
List all vertices which belong to cycles of less than three
vertices
List all vertices reachable from a given vertex


1.25 Let r and s be two relations over the relation schemes
R and S respectively, and let A be an attribute in R. Then
the relational algebra expression s A=a (r |X| s) is always
equal to

(a) s A=a (r) (b) r

(e) s A=a (r) |X| s (d) none of the above



2. This question consists of (TWENTY FIVE) sub-questions
(2.1- 2.25) of TWO marks each. For each of the
sub-questions, four possible answers (A, B, C and D) are
given, out of which only one is correct. Answer each
sub-question by darkening the appropriate bubble on the
OBJECTIVE RESPONSE SHEET (ORS) using a soft HB pencil. Do
not use the ORS for any rough work. You may like to use the
Answer Book for any rough work, if needed.



2.1 How many 4-digit even numbers have all 4 digits distinct?

(a) 2240 (b) 2296

(c) 2620 (d) 4536



2.2 Consider the following statements:

S1 : There exist infinite sets A, B, C such that A ? (B ? C)
is finite.

S2: There exist two irrational numbers x and y such that (x
+y) is rational. Which of the following is true about S1 and
S2 ?

Only S1 is correct
Only S2 is correct
Both S1 and S2 are correct
None of S1 and S2 is correct
2.3 Let f : A ? B be a function, and let E and F be subsets
of A. Consider the following statements about images.

S1 :f (E ? F)=f (E) ? f (F)

S2 :f (E ? F)=f(E) ? f (F)

Which of the following is true about S1 and S2 ?

Only S1 is correct
Only S2 is correct
Both S1 and S2 are correct
None of S1 and S2 is correct


2.4 Seven (distinct) car accidents occurred in a week. What
is the probability that they all occurred on the same day?

1/7 7
1/7 6
1/2 7
7/2 7


2.5 Consider a DFA over S = {a, b} accepting all strings
which have number of a's divisible by 6 and number of b's
divisible by 8. What is the minimum number of states that
the DFA will have?

8
14
15
48


Consider the following languages:
L1={w w l w ? {a,b}*}

L2={ww R | w ? {a, b}*, w R is the reverse of w}

L3 = { 0 2i | i is an integer}

L4 = {O i2| i is an integer}

Which of the languages are regular?



Only L1 and L2
Only L2, L3, and L4
Only L3 and L4
Only L3


2.7 Consider the following problem X .

Given a Turing machine M over the input alphabet ? , any
state q of M

and a word W ? S *, does the computation of M on w visit the
state q ?

Which of the following statements about X is correct?

X is decidable
X is undecidable but partially decidable
X is undecidable and not even partially decidable.
X is not a decision problem


2.8 Consider the following circuit with initial state Q o =
Q 1 = 0. The D Flip-Flops are positive edge triggered and
have set up times 20 nanosecond and hold times 0.











Consider the following timing diagrams of X and C; the clock
period of C ? 40 nanosecond. Which one is the correct plot
of Y?







2.9 Which is the most appropriate match for the items in the
first column with the items in the second column ?

X Indirect Addressing I. Array implementation

Y Indexed Addressing II. Writing relocatable code

Z. Base Register Addressing III. Passing array as parameter



(X. III), (Y, I), (Z, II)
(X, II), (Y, III), (Z, I)
(X, III), (Y, II), (Z, I)
(x, I), (Y, III), (Z, II)


2.10 The 2's complement representation of (-539) 10 in
hexadecimal is

ABE
DBC
DE5
9E7


Consider the circuit shown below. The output of a 2:1 Mux is
given by the function (ac' + bc).












Which of the following is true?

f=x1'+x2
f=x1 ? x 2+xlx2'
f=x1x2+x1 ?x2'
f=x1 +x2'


2.12 Consider the circuit given below with initial state Q 0
= 1, Q 1 = Q 2 = O. The state of the circuit is given by the
value 4Q 2 + 2Q 1 +Q 0























Which one of the following is the correct state sequence of
the circuit?

(a) 1,3,4,6,7,5,2 (b) 1,2,5,3,7,6,4

(c) 1,2,7,3,5,6,4 (d) 1,6,5,7,2,3,4.



2.13 Consider the following data path of a simple
non-pipelined CPU. The registers A, B, A 1, A 2, MDR, the
bus and the ALU are 8-bit wide. SP and MAR are 16-bit
registers. The MUX is of size 8 x (2:1) and the DEMUX is of
size 8 x (1: 2). Each memory operation takes 2 CPU clock
cycles and uses MAR (Memory Address Register) and MDR(Memory
Date Register). SP can be decremented locally.

























The CPU instruction "push r". where = A or B, has the
specification

M[SP] r

SP SP-l

How many CPU clock cycles are needed to execute the "push r"
instruction?

2
3
4
5


2.14 Consider an undirected unweighted graph G. Let a
breadth-first traversal of G be done starting from a node r.
Let d(r, u) and d(r, v) be the lengths of the shortest paths
from r to u and v respectively, in G. lf u is visited before
v during the breadth-first traversal, which of the following
statements is correct?

d(r, u) < d (r, v)
d(r, u) > d(r, v)
d(r, u) ? d (r, v)
None of the above


2.15 How many undirected graphs (not necessarily connected)
can be constructed out of a given set V= {V 1, V 2,?V n} of
n vertices?

n(n-l)/2
2 n
n!
2 n(n-1)/2
2.16 What is the minimum number of stacks of size n required
to implement a queue of size n ?

(0) One (b) Two

(c) Three (d) Four



What is printed by the print statements in the program P1
assuming call by reference parameter passing?
Program Pl ( )

{

x=10;

y=3;

func1(y, x, x);

print x;

print y;

,

func1 (x, y, z)

{

y=y+4;

z=x+y+z;

}

10,3
31,3
27,7
None of the above


2.18 Consider the following three C functions :

[PI] int * g (void)

{

int x= 10;

return (& x);

}

[P2] int * g (void)

{

int * px;

*px= 10;

return px;

}

[P3] int * g (void)

{

int * px;

px = (int *) malloc (sizeof(int));

*px= 10;.

return px;

}

Which of the above three functions are likely to cause
problems with pointers?

(a) OnlyP3 (b) Only P1 and P3

(c) Only P1 and P2 (d) P1,P2,andP3



2.19 Consider the following program

Program P2

Var n: int:

procedure W (var x: int)

begin

x=x+1;

print x;



end

procedure D

begin



var n: int;

n=3;

W(n); .



end

begin \\beginP2

n=10;

D;

end

If the language has dynamic scoping and parameters are
passed by reference, what will be printed by the program?

10
11
3
None of the above


2.20 Which of the following does not interrupt a running
process? .

(a) A device (b) Timer

(c) Scheduler process (d) Power failure



2.21 Consider a machine with 64 M B physical memory and a
32-bit virtual address space. If the page size is 4KB, what
is the approximate size of the page table?

(a) 16 MB (b) 8 MB

(c) 2 MB (d) 24 MB



2.22 Consider Peterson's algorithm for mutual exclusion
between two concurrent processes i and j. The program
executed by process is shown below.

repeat



flag [i] = true;

turn = j;

while ( P ) do no-op;

Enter critical section, perform actions, then exit critical
section

flag [ i ] = false;

Perform other non-critical section actions.

until false;



For the program to guarantee mutual exclusion, the predicate
P in the while loop should be

flag [j] = true and turn = i
flag [j] = true and turn = j
flag [i] = true and turn = j
flag [i] = true and turn = i


2.23 R (A, B, C, D) is a relation. Which of the following
does not have a loss less join, dependency preserving BCNF
decomposition?

A ? B,B ? CD
A ? B,B ? C, C ? D
AB ? C,C ? AD
A ? BCD
2.24 Which of the following relational calculus expressions
is not safe?

{t | $ u ? R 1 (t [A] = u [A] ) ? ? $ s ? R 2 (t [A] = s [A]) }
{t | " u ? R 1(u [A] = "x" ? $ s ? R 2 (t [A] = s [A] ? s
[A] = u [A] )) }
{t | ? (t ? R 1)}
{t | $ u ? R 1 (t [A] = u [A] ) ? $ s ? R 2 (t [A] = s [A]) }


2.25 Consider a relation geq which represents "greater than
or equal to", that is, (x, y) ? geq only if y ? x.

create table geq

(Ib integer not null

ub integer not null

primary key Ib

foreign key (ub) references geq on delete cascade)

Which of the following is possible if a tuple (x, y) is
deleted?

A tuple (z, w) with z > y is deleted
A tuple (z, w) with z > x is deleted
A tuple (z, w) with w < x is deleted
The deletion of (x, y) is prohibited

Answer / arabinda pattanayak

ALL QUESTION GATE 2001

types of highways

0 Answers  

---

c program to compare the initial portions of the two strings and return the matched portion if matches, otherwise return the empty string.

0 Answers  

---

Hi, I am also looking for pattern & questions of NIC exam. If anyone knows it pls send it to gaurav.yagik@gmail.com. thanks in advance. regards Gaurav

0 Answers  

---

why networking is nessasary

1 Answers  

---

A rectangular wave guide a=5,b=3.75cm and freq 10 GHZ ,the wavelength is 7 cm. find mode of operation of wave guide

0 Answers   BSNL,

---

---

a resistor with the colour bands sequnce yellow, violet, orange, golden idecates a resistance value

3 Answers  

---

can u explain me the way to know the relation between the active as well as the reactive power acting on an electical machine under the under excitation as well as over excitation mode

0 Answers   Siemens,

---

why is trnsformer rating in kva

2 Answers  

---

I want to know the exact syllabus for gate in electrical engineering and minimum marks to be secured

0 Answers  

---

sir can you send me previous question paper of jsplGET entrance test

0 Answers  

---

The famous financial advisor to akbar was

1 Answers   CHS,

---

please send me NTPC previous papers on my email ID 18amarjeet.civil@gmail.com or mr.yadav143@gmail.com

0 Answers  

---