## GATE 1993

Question 1 |

The eigen vector(s) of the matrix

is (are)

(0,0,α ) | |

(α,0,0) | |

(0,0,1) | |

(0,α,0) | |

Both B and D |

So the question as has

(A - λI)X = 0

AX = 0

What x

_{1}, x

_{2}, x

_{3}are suitable?

Which means:

x

_{1}times column 1 + x

_{2}times column 2 + x

_{3}times column 3 = zero vector

Since α is not equal to zero, so x

_{3}must be necessarily zero to get zero vector.

Hence, only (B) and (D) satisfies.

Question 2 |

The differential equation

d^{2}y/dx^{2} + dy/dx + siny = 0 is:

linear | |

non-linear | |

homogeneous | |

of degree two |

__Note: Out of syllabus.__

d

^{2}y/dx

^{2}+ dy/dx + siny = 0

In this DE, degree is 1 then this represent linear equation.

Question 3 |

Simpson’s rule for integration gives exact result when f(x) is a polynomial of degree

1 | |

2 | |

3 | |

4 |

Question 4 |

Which of the following is (are) valid FORTRAN 77 statement(s)?

DO 13 I = 1 | |

A = DIM ***7 | |

READ = 15.0 | |

GO TO 3 = 10 |

Question 5 |

Fourier series of the periodic function (period 2π) defined by

But putting x = π, we get the sum of the series.

π ^{2}/4 | |

π ^{2}/6 | |

π ^{2}/8 | |

π ^{2}/12 |

Question 6 |

Which of the following improper integrals is (are) convergent?

Question 7 |

The function f(x,y) = x^{2}y - 3xy + 2y + x has

no local extremum | |

one local minimum but no local maximum | |

one local maximum but no local minimum | |

one local minimum and one local maximum |

Question 8 |

1 |

Question 9 |

The radius of convergence of the power series

Out of syllabus. |

Question 10 |

If the linear velocity is given by

The angular velocity at the point (1, 1, -1) is ________

Out of syllabus. |

Question 11 |

Given the differential equation, y′ = x − y with the initial condition y(0) = 0. The value of y(0.1) calculated numerically upto the third place of decimal by the second order Runga-Kutta method with step size h = 0.1 is ________

Out of syllabus. |

Question 12 |

For X = 4.0, the value of I in the FORTRAN 77 statement

1 = -2**2 + 5.0*X/X*3 + 3/4 is _______

Out of syllabus. |

Question 13 |

The value of the double integral is

1/3 |

Question 14 |

If the matrix A^{4}, calculated by the use of Cayley-Hamilton theorem or otherwise, is _________

A ^{4} = I |

(1-λ) (-1-λ) (i-λ) (-i-λ)

= (λ

^{2}-1) (λ

^{2}+1)

= λ

^{4}-1

Characteristic equation is λ

^{4}-1 = 0.

According to Cayley-Hamilton theorem, every matrix satisfies its own characteristic equation, so

A

^{4}= I

Question 15 |

Given and S the surface of a unit cube with one corner at the origin and edges parallel to the coordinate axes, the value of integral

Out of syllabus. |

Question 16 |

The differential equation y^{n} + y = 0 is subjected to the boundary conditions.

y (0) = 0 y(λ) = 0

In order that the equation has non-trivial solution(s), the general value of λ is __________

Out of syllabus. |

Question 17 |

The Laplace transform of the periodic function f(t) described by the curve below, i.e.,

is _________

Out of syllabus. |

Question 18 |

Identify the logic function performed by the circuit shown in figure.

exclusive OR | |

exclusive NOR | |

NAND | |

NOR |

So finally, we can write

Question 19 |

If the state machine described in figure, should have a stable state, the restriction on the inputs is given by

Question 20 |

For the initial state of 000, the function performed by the arrangement of the J-K flip-flops in figure is:

Shift Register | |

Mod-3 Counter | |

Mod-6 Counter | |

Mod-2 Counter | |

Both A and C |

Circuit behaves as shift register and mod-6 counter. Note that this is the Johnson counter which is the application of shift register. And Johnson counter is mod-2N counter.

Question 21 |

Assume that each character code consists of 8 bits. The number of characters that can be transmitted per second through an asynchronous serial line at 2400 baud rate, and with two stop bits, is

109 | |

216 | |

218 | |

219 |

= 8 bit data + 2 stop bit + 1 start bit

= 11 bits

No. of characters = 2400/11 = 218.18

Since, it is asked for transmitted characters we take floor and answer is 218.

Question 22 |

Convert the following numbers in the given bases into their equivalents in the desired bases.

(a) 110.101)_{2} = x)_{10}

(b) 1118)_{10} = y)_{H}

(a) 6.625, (b) (45E) _{H} |

^{2}+ 1*2

^{1}+ 0*2

^{0}+ 1*2

^{-1}+ 0*2

^{-2}+ 1*2

^{-3}

= 4 + 2 + 0 + 0.5 + 0 + 0.125

= 6.625

(b) 1118 mod 16 = E, quotient = 69

69 mod 16 = 5, quotient = 4

4 mod 16 = 4

Writing the mods result in reverse order gives (45E)

_{H}.

Question 23 |

A ROM is used to store the Truth table for a binary multiple unit that will multiply two 4-bit numbers. The size of the ROM (number of words × number of bits) that is required to accommodate the Truth table is M words × N bits. Write the values of M and N.

M = 256, N = 8 |

^{8}address.

Output will be of 8 bits.

So memory will be of 2

^{8}× 8.

So, M = 256, N = 8.

Question 24 |

A certain moving arm disk storage, with one head, has the following specifications.

Number of tracks/recording surface = 200 Disk rotation speed = 2400 rpm Track storage capacity = 62,500 bits

The average latency of this device is P msec and the data transfer rate is Q bits/sec.

Write the value of P and Q.

P = 12.5, Q = 2.5×10 ^{6} |

So, in DOS, the disk rotates 2400 times.

Average latency is the time for half a rotation

= 0.5×60/2400 s

= 12.5 ms

In one full rotation, entire data in a track can be transferred. Track storage capacity = 62500 bits

So, disk transfer rate

= 62500 × 2400/60

= 2.5 × 10

^{6}bps

So,

P = 12.5, Q = 2.5×10

^{6}

Question 25 |

The details of an interrupt cycle are shown in figure.

Given that an interrupt input arrives every 1 msec, what is the percentage of the total time that the CPU devotes for the main program execution.

90% |

= saving state of CPU + ISR execution + restoring of CPU state

= (80 + 10 + 10) × 10

^{-6}

= 100 μs

For every 1ms an interrupt occurs which is served for 100 μs.

1ms = 1000μs

Thus, for every 1000μs, (1000 - 100) = 900 μs of main program and 100μs of interrupt overhead exists.

Thus, 900/1000 is usage of CPU to execute main program .

∴ % of CPU to execute main program is (900/1000) × 100 = 90%

Question 26 |

Program PARAM (input, output); var m, n : integer; procedure P (var, x, y : integer); var m : integer; begin m : = 1; x : = y + 1 end; procedure Q (x:integer; vary : integer); begin x:=y+1; end; begin m:=0; P(m,m); write (m); n:=0; Q(n*1,n); write (n) end

The value of m, output by the program PARAM is:

1, because m is a local variable in P | |

0, because m is the actual parameter that corresponds to the formal parameter in p
| |

0, because both x and y are just reference to m, and y has the value 0 | |

1, because both x and y are just references to m which gets modified in procedure P | |

none of the above |

Question 27 |

Program PARAM (input, output); var m, n : integer; procedure P (var, x, y : integer); var m : integer; begin m : = 1; x : = y + 1 end; procedure Q (x:integer; vary : integer); begin x:=y+1; end; begin m:=0; P(m,m); write (m); n:=0; Q(n*1,n); write (n) end

The value of n, output by the program PARAM is:

0, because n is the actual parameter corresponding to x in procedure Q. | |

0, because n is the actual parameter to y in procedure Q. | |

1, because n is the actual parameter corresponding to x in procedure Q. | |

1, because n is the actual parameter corresponding to y in procedure Q. | |

none of the above |

Question 28 |

Program PARAM (input, output); var m, n : integer; procedure P (var, x, y : integer); var m : integer; begin m : = 1; x : = y + 1 end; procedure Q (x:integer; vary : integer); begin x:=y+1; end; begin m:=0; P(m,m); write (m); n:=0; Q(n*1,n); write (n) end

What is the scope of m declared in the main program?

PARAM, P, Q | |

PARAM, P | |

PARAM, Q | |

P, Q | |

none of the above |

Question 29 |

What does the following code do?

var a, b : integer; begin a:=a+b; b:=a-b; a:=a-b end;

exchanges a and b | |

doubles a and stores in b | |

doubles b and stores in a | |

leaves a and b unchanged | |

none of the above |

Let us consider a=5; b=2

a := a+b = 5+2 = 7

b := a-b = 7-2 = 5

a := a-b = 7-5 = 2

O/P: a=2; b=5

Question 30 |

For the program segment given below, which of the following are true?

program main (output); type link = ^data; data = record d : real; n : link end; var ptr : link; begin new (ptr); ptr:=nil; .ptr^.d:=5.2; write ln(ptr) end.

The program leads to compile time error | |

The program leads to run time error | |

The program outputs 5.2 | |

The program produces error relating to nil pointer dereferencing | |

None of the above |

Question 31 |

A simple two-pass assembler does the following in the first pass:

It allocates space for the literals. | |

It computes the total length of the program | |

It builds the symbol table for the symbols and their values. | |

It generates code for all the load and store register instructions. | |

A, B and C |

1) Assign address to all statements in the program.

2) Save the values assigned to all tables for use in pass 2.

3) Perform some processing of assembler directives.

Question 32 |

A part of the system software, which under all circumstances must reside in the main memory, is:

text editor | |

assembler | |

linker | |

loader | |

none of the above |

Question 33 |

The root directory of a disk should be placed

at a fixed address in main memory | |

at a fixed location on the disk | |

anywhere on the disk | |

at a fixed location on the system disk | |

anywhere on the system disk |

Question 34 |

Consider a system having m resources of the same type. These resources are shared by 3 processes A, B and C, which have peak demands of 3, 4 and 6 respectively. For what value of m deadlock will not occur?

7 | |

9 | |

13, 15 | |

13 | |

15 |

→ If A have 2, B have 3, C have 5 then deadlock will occur i.e., 2+3+5=10.

→ If we have one extra resource then deadlock will not occur i.e., 10+1=11.

→ If we have equal (or) more than 11 resources then deadlock will never occur.

Question 35 |

Assume that the following jobs are to be executed on a single processor system

The jobs are assumed to have arrived at time 0^{+} and in the order p, q, r, s, t. Calculate the departure time (completion time) for job p if scheduling is round robin with time slice 1.

4 | |

10 | |

11 | |

12 | |

None of the above |

p is departure at 11.

Question 36 |

Consider a simple connected graph G with n vertices and n-edges (n>2). Then, which of the following statements are true?

G has no cycles. | |

The graph obtained by removing any edge from G is not connected. | |

G has at least one cycle. | |

The graph obtained by removing any two edges from G is not connected. | |

Both C and D. |

For example let us consider, n=3.

Question 37 |

The proposition p ∧(~p ∨ q) is:

a tautology | |

logically equivalent to p ∧ q | |

logically equivalent to p ∨ q | |

a contradiction | |

none of the above |

(p ∧ ~p) ∨ (p ∧ q)

F ∨ (p ∧ q)

(p ∧ q)

Question 38 |

Let S be an infinite set and S_{1} ..., S_{n} be sets such that S_{1} ∪ S_{2} ∪ ... ∪ S_{n} = S. Then,

at least one of the set S _{i} is a finite set | |

not more than one of the set S _{i} can be finite | |

at least one of the sets S _{i} is an infinite set | |

not more than one of the sets S _{i} can be infinite | |

None of the above |

Question 39 |

Let A be a finite set of size n. The number of elements in the power set of A × A is:

2 ^{2n} | |

2 ^{n2} | |

(2 ^{n})^{2} | |

(2 ^{2})^{n} | |

None of the above |

^{2}

A = {1,2}

|A| = {∅, {1}, {2}, {1,2}}

Cardinality of power set of A = 2

^{n2}

A × A = {1,2} × {1,2}

= {(1,1), (1,2), (2,1), (2,2)}

Cardinality of A × A = n

^{2}

Cardinality of power set of A × A = 2

^{n2}

Question 40 |

The less-than relation, <, on reals is

a partial ordering since it is asymmetric and reflexive | |

a partial ordering since it is antisymmetric and reflexive | |

not a partial ordering because it is not asymmetric and not reflexive | |

not a partial ordering because it is not antisymmetric and reflexive
| |

none of the above |

1) not reflexive

2) irreflexive

3) not symmetric

4) Asymmetric

5) Antisymmetric

Question 41 |

Let A and B be sets with cardinalities m and n respectively. The number of one-one mappings (injections) from A to B, when m < n, is:

m ^{n} | |

^{n}P_{m} | |

^{m}C_{n} | |

^{n}C_{m} | |

^{m}P_{n} |

A = {a

_{1}, a

_{2}, ... a

_{m}} and

B = {b

_{1}, b

_{2}, ... b

_{n}}

A one-one function 'f' assigns each element a

_{i}of A a distinct element, b

_{j}=f(a

_{i}) of B

_{i}for a, there are n choices, for a

_{2}there are n-1 choices, for a

_{m}there are (n-(m-1)) choices.

i.e.,

Question 42 |

where O(n) stands for order n is:

O(n) | |

O(n ^{2}) | |

O(n ^{3}) | |

O(3n ^{2}) | |

O(1.5n ^{2}) | |

B, C, D and E |

⇒ In this 'n' is constant. So, n is added to n times itself which is O(n

^{2}).

Hence, (a) is wrong. And rest (B), (C), (D), (E) are correct.

Question 43 |

Assume that only half adders are available in your laboratory. Show that any binary Boolean function can be implemented using half adders only.

Theory Explanation. |

Question 44 |

The instruction format of a CPU is:

Mode and RegR together specify the operand. RegR specifies a CPU register and Mode specifies an addressing mode. In particular, Mode = 2 specifies that ‘the register RegR contains the address of the operand, after fetching the operand, the contents of RegR are incremented by 1’.

An instruction at memory location 2000 specifies Mode = 2 and the RegR refers to program counter (PC).

(a) What is the address of the operand?

(b) Assuming that this is a non-jump instruction, what are the contents of PC after the execution of this instruction?

Theory Explanation. |

Question 45 |

In the three-level memory hierarchy shown in the following table, p_{i} denotes the probability that an access request will refer to M_{i}.

If a miss occurs at level M_{i}, a page transfer occurs from M_{i+1} to M_{i} and the average time required for such a page swap is T_{i}. Calculate the average time t_{A} required for a processor to read one word from this memory system.

Theory Explanation. |

Question 46 |

The following Pascal program segments finds the largest number in a two-dimensional integer array A[0...n-1,0...n-1] using a single loop. Fill up the boxes to complete the program and write against in your answer book. Assume that max is a variable to store the largest value and i,j are the indices to the array.

begin max:= , i:=0,j:=0; while do begin if A[i,j]>max then max:=A[i,j] if then j:=j+1 else begin j:=0; i:= end end end.

Theory Explanation. |

Question 47 |

Consider a singly linked list having n nodes. The data items d_{1}, d_{2}, ...d_{n} are stored in these n nodes. Let X be a pointer to the j-th node (1≤j≤n) in which d_{j} is stored. A new data item d stored in node with address Y is t be inserted. Give an algorithm to insert d into the list to obtain a list having items d_{1}, d_{2}, ..., d_{j-1}, d_{j}, ..., d_{n} in the order without using the header.

Theory Explanation. |

Question 48 |

An ISAM (indexed sequential) file consists of records of size 64 bytes each, including key field of size 14 bytes. An address of a disk block takes 2 bytes. If the disk block size is 512 bytes and there are 16 K records, compute the size of the data and index areas in terms of number of blocks. How many levels of tree do you have for the index?

Theory Explanation. |

Question 49 |

Consider the recursive algorithm given below:

procedure bubblersort (n); var i,j: index; temp : item; begin for i:=1 to n-1 do if A[i] > A [i+1] then begin temp : A[i]; A[i]:=A[i+1]; A[i+1]:=temp end; bubblesort (n-1) end

Let a_{n} be the number of times the ‘if…then….’ Statement gets executed when the algorithm is run with value n. Set up the recurrence relation by defining a_{n} in terms of a_{n-1}. Solve for a_{n}.

Theory Explanation. |

Question 50 |

Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has 2 descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

Theory Explanation. |

Question 51 |

Out of a group of 21 persons, 9 eat vegetables, 10 eat fish and 7 eat eggs : 5 persons eat all three. How many persons eat at least two out the three dishes?

Theory Explanation. |

Question 52 |

Show that proposition C is a logical consequence of the formula

A ∧ (A →(B ∨ C)) ∧ (B → ~A)

Using truth tables.

Theory Explanation. |

Question 53 |

A control algorithm is implemented by the NAND – gate circuitry given in figure below, which A and B are state variable implemented by D flip-flops, and P is control input. Develop the state transition table for this controller.

Theory Explanation. |

Question 54 |

Given that the following is an 8085 program segment:

(a) Identify the function performed by it, and

(b) List the roles of the registers used and the address referred to by it.

LHLD 5000 MVI B, 5 GET: IN 20 MOV M, A INX H DCR B JNZ GET

Theory Explanation. |

Question 55 |

The following page addresses, in the given sequence, were generated by a program:

1 2 3 4 1 3 5 2 1 5 4 3 2 3

This program is run on a demand paged virtual memory system, with main memory size equal to 4 pages. Indicate the page references for which page faults occurs for the following page replacement algorithms.

(a) LRU (b) FIFO

Assume that the main memory is empty initially.

Theory Explanation. |

Question 56 |

Write a concurrent program using parbegin-parend and semaphores to represent the precedence constraints of the statements S_{1} to S_{6}, as shown in figure below.

Theory Explanation. |

Question 57 |

The following relations are used to store data about students, courses, enrollment of students in courses and teachers of courses. Attributes for primary key in each relation are marked by ‘*’.

Students (rollno*, sname, saddr) courses (cno*, cname) enroll(rollno*, cno*,grade) teach(tno*,tname,cao*)

(cno is course number, cname is course name, tno is teacher number, tname is teacher name, sname is student name, etc.)

Write a SQL query for retrieving roll number and name of students who got A grade in at least one course taught by teacher named Ramesh for the above relational database.

Theory Explanation. |

Question 58 |

The following relations are used to store data about students, courses, enrollment of students in courses and teachers of courses. Attributes for primary key in each relation are marked by ‘*’.

Students (rollno*, sname, saddr) courses (cno*, cname) enroll(rollno*, cno*,grade) teach(tno*,tname,cao*)

(cno is course number, cname is course name, tno is teacher number, tname is teacher name, sname is student name, etc.)

For the relational database given above, the following functional dependencies hold:

rollno → sname,sdaddr cno → cname tno → tname rollno, cno → grade

(a) Is the database in 3^{rd} normal form (3NF)?

(b) If yes, prove that it is in 3 NF. If not, normalize, the relations so that they
are in 3 NF (without proving).

Theory Explanation. |

Question 59 |

A simple Pascal like language has only three statements.

(i) assignment statement e.g. x:=expression

(ii) loop construct e.g. for i:=expression to expression do statement.

(iii) sequencing e.g. begin statement ;…; statement end

(a) Write a context-free grammar (CFG) for statements in the above language. Assume that expression has already been defined. Do not use optional
parentheses and * operator in CFG.

(b) Show the parse tree for the following statement:

for j:=2 to 10 do begin x:=expr1; y:=expr2 end

Theory Explanation. |

Question 60 |

A stack is used to pass parameters to procedures in a procedure call.

(a) If a procedure P has two parameters as described in procedure definition:

procedure P (var x :integer; y: integer); and if P is called by ; P(a,b)

State precisely in a sentence what is pushed on stack for parameters a and b.

(b) In the generated code for the body of procedure P, how will the addressing of formal parameters x and y differ?

Theory Explanation. |

Question 61 |

Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet {a,b}, such that no string has 3 consecutive occurrences of the letter b.

Theory Explanation. |

Question 62 |

Let ({p,q{,*) be a semigroup where p * q = q. Show that:

(a) p * q = q * p and (b) q * q = q

Theory Explanation. |