GATE 1993

Question 1

The eigen vector(s) of the matrix

is (are)

A
(0,0,α )
B
(α,0,0)
C
(0,0,1)
D
(0,α,0)
E
Both B and D
       Engineering-Mathematics       Linear-Algebra
Question 1 Explanation: 
Since, the given matrix is an upper triangular one, all eigen values are A. And hence A - λI = A.
So the question as has
(A - λI)X = 0
AX = 0

What x1, x2, x3 are suitable?
Which means:
x1 times column 1 + x2 times column 2 + x3 times column 3 = zero vector
Since α is not equal to zero, so x3 must be necessarily zero to get zero vector.
Hence, only (B) and (D) satisfies.
Question 2

The differential equation
d2y/dx2 + dy/dx + siny = 0 is:

A
linear
B
non-linear
C
homogeneous
D
of degree two
       Engineering-Mathematics       Calculus
Question 2 Explanation: 
Note: Out of syllabus.
d2y/dx2 + 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

A
1
B
2
C
3
D
4
       Engineering-Mathematics       Simphson\'s-Rule
Question 3 Explanation: 
Note: Out of syllabus.
Question 4

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

A
DO 13 I = 1
B
A = DIM ***7
C
READ = 15.0
D
GO TO 3 = 10
       Computer-Organization       FORTRAN
Question 4 Explanation: 
Note: Out of syllabus.
Question 5

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

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

A
π2/4
B
π2/6
C
π2/8
D
π2/12
       Engineering-Mathematics       Calculus
Question 5 Explanation: 
Note: Out of syllabus.
Question 6

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

A
B
C
D
       Engineering-Mathematics       Calculus
Question 7

The function f(x,y) = x2y - 3xy + 2y + x has

A
no local extremum
B
one local minimum but no local maximum
C
one local maximum but no local minimum
D
one local minimum and one local maximum
       Engineering-Mathematics       Functions
Question 7 Explanation: 
Note: Out of syllabus.
Question 8
A
1
       Engineering-Mathematics       Calculus
Question 8 Explanation: 
Since the given expression is in 0/0 form, so we can apply L-Hospital rule.
Question 9

The radius of convergence of the power series

A
Out of syllabus.
       Engineering-Mathematics       Calculus
Question 10

If the linear velocity is given by

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

A
Out of syllabus.
       Engineering-Mathematics       Vectors
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 ________

A
Out of syllabus.
       Engineering-Mathematics       R-K-Method
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 _______

A
Out of syllabus.
       Engineering-Mathematics       FORTRAN
Question 13

The value of the double integral is

A
1/3
       Engineering-Mathematics       Calculus
Question 13 Explanation: 
Question 14

If the matrix A4, calculated by the use of Cayley-Hamilton theorem or otherwise, is _________

A
A4 = I
       Engineering-Mathematics       Linear-Algebra
Question 14 Explanation: 
Let λ be eigen value, then characteristic equation will be
(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
A4 = 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

A
Out of syllabus.
       Engineering-Mathematics       Vector Algebra
Question 16

The differential equation yn + 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 __________

A
Out of syllabus.
       Engineering-Mathematics       Calculus
Question 17

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

is _________

A
Out of syllabus.
       Engineering-Mathematics       Functions
Question 18

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

A
exclusive OR
B
exclusive NOR
C
NAND
D
NOR
       Digital-Logic-Design       Logic-Gates
Question 18 Explanation: 

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

A
B
C
D
       Theory-of-Computation       Finite-Automata
Question 20

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

A
Shift Register
B
Mod-3 Counter
C
Mod-6 Counter
D
Mod-2 Counter
E
Both A and C
       Digital-Logic-Design       J-K-Flip-Flop
Question 20 Explanation: 

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

A
109
B
216
C
218
D
219
       Computer-Organization       Serial-Communication
Question 21 Explanation: 
Total bit per character
= 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
(a) 6.625, (b) (45E)H
       Digital-Logic-Design       Number-Systems
Question 22 Explanation: 
(a) 1*22 + 1*21 + 0*20 + 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.

A
M = 256, N = 8
       Digital-Logic-Design       Truth Table
Question 23 Explanation: 
Input will consist of 8 bit (two 4-bit numbers) = 28 address.
Output will be of 8 bits.
So memory will be of 28 × 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.

A
P = 12.5, Q = 2.5×106
       Operating-Systems       Memory-Management
Question 24 Explanation: 
RPM = 2400
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 × 106 bps
So,
P = 12.5, Q = 2.5×106
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.

A
90%
       Computer-Organization       Interrupt
Question 25 Explanation: 
Time to service an interrupt
= 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:

A
1, because m is a local variable in P
B
0, because m is the actual parameter that corresponds to the formal parameter in p
C
0, because both x and y are just reference to m, and y has the value 0
D
1, because both x and y are just references to m which gets modified in procedure P
E
none of the above
       Programming       Programming
Question 26 Explanation: 
0, because global m is not modified, m is just passed to formal argument of P.
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:

A
0, because n is the actual parameter corresponding to x in procedure Q.
B
0, because n is the actual parameter to y in procedure Q.
C
1, because n is the actual parameter corresponding to x in procedure Q.
D
1, because n is the actual parameter corresponding to y in procedure Q.
E
none of the above
       Programming       Programming
Question 27 Explanation: 
0, because n is just passed to formal parameters of Q and no modification in global n.
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?

A
PARAM, P, Q
B
PARAM, P
C
PARAM, Q
D
P, Q
E
none of the above
       Programming       Programming
Question 28 Explanation: 
Since m is defined global it is visible inside all the procedures.
Question 29

What does the following code do?

 var a, b : integer;
 begin
    a:=a+b;
    b:=a-b;
    a:=a-b
 end; 
A
exchanges a and b
B
doubles a and stores in b
C
doubles b and stores in a
D
leaves a and b unchanged
E
none of the above
       Programming       Programming
Question 29 Explanation: 
Exchanges a and b.
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. 
A
The program leads to compile time error
B
The program leads to run time error
C
The program outputs 5.2
D
The program produces error relating to nil pointer dereferencing
E
None of the above
       Compiler-Design       Compilers
Question 30 Explanation: 
Note: Out of syllabus.
Question 31

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

A
It allocates space for the literals.
B
It computes the total length of the program
C
It builds the symbol table for the symbols and their values.
D
It generates code for all the load and store register instructions.
E
A, B and C
       Computer-Organization       Assembler
Question 31 Explanation: 
Pass 1:
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:

A
text editor
B
assembler
C
linker
D
loader
E
none of the above
       Compiler-Design       General
Question 32 Explanation: 
In a program the loader that can loads the object of the program from secondary memory into the main memory to execute the corresponding program. Then the loader is to be resides in the main memory.
Question 33

The root directory of a disk should be placed

A
at a fixed address in main memory
B
at a fixed location on the disk
C
anywhere on the disk
D
at a fixed location on the system disk
E
anywhere on the system disk
       Algorithms
Question 33 Explanation: 
Root directory can points to the various user directories. Then they will be stored in a way that user can't be easily modify them. Then they should be at fixed location on the 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?

A
7
B
9
C
13, 15
D
13
E
15
       Operating-Systems       Deadlock
Question 34 Explanation: 
A requires 3, B-4, C-6;
→ 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.

A
4
B
10
C
11
D
12
E
None of the above
       Operating-Systems       Deadlock
Question 35 Explanation: 
Algorithm: Round robin; TQ: 1

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?

A
G has no cycles.
B
The graph obtained by removing any edge from G is not connected.
C
G has at least one cycle.
D
The graph obtained by removing any two edges from G is not connected.
E
Both C and D.
       Algorithms       Graphs
Question 36 Explanation: 
If a graph have n vertices and n edges (n>2) then it is to be cyclic graph. Then it have atleast one cycle and if we remove two edges then it is not connected.
For example let us consider, n=3.
Question 37

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

A
a tautology
B
logically equivalent to p ∧ q
C
logically equivalent to p ∨ q
D
a contradiction
E
none of the above
       Engineering-Mathematics       Prepositional-Logic
Question 37 Explanation: 
p ∧(~p ∨ q)
(p ∧ ~p) ∨ (p ∧ q)
F ∨ (p ∧ q)
(p ∧ q)
Question 38

Let S be an infinite set and S1 ..., Sn be sets such that S1 ∪ S2 ∪ ... ∪ Sn = S. Then,

A
at least one of the set Si is a finite set
B
not more than one of the set Si can be finite
C
at least one of the sets Si is an infinite set
D
not more than one of the sets Si can be infinite
E
None of the above
       Engineering-Mathematics       Set-Theory
Question 38 Explanation: 
Given sets are finite union of sets. One set must be infinite to make whole thing to be infinite.
Question 39

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

A
22n
B
2n2
C
(2n)2
D
(22)n
E
None of the above
       Engineering-Mathematics       Set-Theory
Question 39 Explanation: 
Cardinality of A = n × n = n2
A = {1,2}
|A| = {∅, {1}, {2}, {1,2}}
Cardinality of power set of A = 2n2
A × A = {1,2} × {1,2}
= {(1,1), (1,2), (2,1), (2,2)}
Cardinality of A × A = n2
Cardinality of power set of A × A = 2n2
Question 40

The less-than relation, <, on reals is

A
a partial ordering since it is asymmetric and reflexive
B
a partial ordering since it is antisymmetric and reflexive
C
not a partial ordering because it is not asymmetric and not reflexive
D
not a partial ordering because it is not antisymmetric and reflexive
E
none of the above
       Engineering-Mathematics       Relations
Question 40 Explanation: 
Relation < is:
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:

A
mn
B
nPm
C
mCn
D
nCm
E
mPn
       Engineering-Mathematics       Functions
Question 41 Explanation: 
Let,
A = {a1, a2, ... am} and
B = {b1, b2, ... bn}
A one-one function 'f' assigns each element ai of A a distinct element, bj=f(ai) of Bi for a, there are n choices, for a2 there are n-1 choices, for am there are (n-(m-1)) choices.
i.e.,
Question 42

where O(n) stands for order n is:

A
O(n)
B
O(n2)
C
O(n3)
D
O(3n2)
E
O(1.5n2)
F
B, C, D and E
       Algorithms       Time-Complexity
Question 42 Explanation: 

⇒ In this 'n' is constant. So, n is added to n times itself which is O(n2).
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.

A
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?

A
Theory Explanation.
Question 45

In the three-level memory hierarchy shown in the following table, pi denotes the probability that an access request will refer to Mi.

If a miss occurs at level Mi, a page transfer occurs from Mi+1 to Mi and the average time required for such a page swap is Ti. Calculate the average time tA required for a processor to read one word from this memory system.

A
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.
A
Theory Explanation.
Question 47

Consider a singly linked list having n nodes. The data items d1, d2, ...dn are stored in these n nodes. Let X be a pointer to the j-th node (1≤j≤n) in which dj 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 d1, d2, ..., dj-1, dj, ..., dn in the order without using the header.

A
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?

A
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 an 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 an in terms of an-1. Solve for an.

A
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.

A
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?

A
Theory Explanation.
Question 52

Show that proposition C is a logical consequence of the formula

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

Using truth tables.

A
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.

A
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  
A
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.

A
Theory Explanation.
Question 56

Write a concurrent program using parbegin-parend and semaphores to represent the precedence constraints of the statements S1 to S6, as shown in figure below.

A
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.

A
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 3rd 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).

A
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  
A
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?

A
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.

A
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 
A
Theory Explanation.
There are 62 questions to complete.