GATE 1990

Question 1

Match the pairs:

(a) Critical region     (p) Hoare's monitor
(b) Wait/Signal         (q) Mutual exclusion
(c) Working Set         (r) Principle of locality
(d) Deadlock            (s) Circular Wait
A
(a) - (q), (b) - (p), (c) - (r), (d) - (s)
       Operating-Systems       Match-the-Following
Question 2

Match the pairs in the following questions:

(a) Secondary index                  (p) Function dependency
(b) Non-procedural query language    (q) B-tree
(c) Closure of a set of attributes   (r) Domain calculus
(d) Natural join                     (s) Relational algebraic operations   </pre
A
(a) - (q), (b) - (r), (c) - (p), (d) - (s)
       Database-Management-System       Match-the-Following
Question 2 Explanation: 
Secondary index → B-Tree
Non-procedural query language → Domain calculus
Closure of set of attributes → Function dependency
Natural join → Relational algebraic operations
Question 3

Match the pairs in the following questions:

(a) Pointer data type       (p) Type conversion
(b) Activation record       (q) Dynamic data structure
(c) Repeat-until            (r) Recursion
(d) Coercion                (s) Non-deterministic loop
A
(a) - (q), (b) - (r), (c) - (s), (d) - (p)
       Compiler-Design       Match-the-Following
Question 3 Explanation: 
Pointer data type - Dynamic data structure
Activation record - Recursion
Repeat until - Non-deterministic loop
Coercion - Type conversion
Question 4

Match the pairs in the following questions:

(a) Small talk      (p) Logic programming
(b) LISP            (q) Data flow programming
(c) Prolog          (r) Functional programming
(d) VAL             (s) Object-oriented programming
A
(a) - (s), (b) - (r), (c) - (p), (d) - (q)
       Programming       Match-the-Following
Question 4 Explanation: 
Note: Out of syllabus.
Question 5

Match the pairs in the following questions:

(a) Strassen's matrix multiplication algorithm     (p) Greedy method
(b) Kruskal's minimum spanning tree algorithm      (q) Dynamic programming
(c) Biconnected components algorithm               (r) Divide and Conquer
(d) Floyd's shortest path algorithm                (s) Depth first search
A
(a) - (r), (b) - (p), (c) - (s), (d) - (q)
       Algorithms       Match-the-Following
Question 5 Explanation: 
Strassen's matrix multiplication algorithm - Divide and Conquer
Kruskal's minimum spanning tree algorithm - Greedy method
Biconnected components algorithm - Depth first search
Floyd's shortest path algorithm - Dynamic programming
Question 6

Match the pairs in the following questions:

(a) A heap construction                            (p) Ω(n log10 n)
(b) Constructing Hash table with linear probing    (q) O(n)
(c) AVL Tree construction                          (r) O(n2)
(d) Digital trie construction                      (s) O(n log10 n)
A
(a) - (q), (b) - (r), (c) - (s), (d) - (p)
       Data-Structures       Match-the-Following
Question 6 Explanation: 
Heap construction - O(n)
Constructing Hash table with linear probing - O(n2
AVL tree construction - O(n log10 n)
Digital trie construction - Ω(n log10 n)
Question 7

Match the pairs in the following questions:

(a) Lexical analysis         (p) DAG's
(b) Code optimization        (q) Syntax trees
(c) Code generation          (r) Push down automaton
(d) Abelian groups           (s) Finite automaton
A
(a) - (s), (b) - (p), (c) - (q), (d) - (r)
       Compiler-Design       Match-the-Following
Question 7 Explanation: 
Lexical analysis - Finite automaton
Code optimization - DAG
Code generation - Syntax tree
Abelian groups - Push down automaton
Question 8

Match the pairs in the following questions:

(a) Groups             (p) Associativity
(b) Semigroups         (q) Identity
(c) Monoids            (r) Commutativity
(d) Abelian groups     (s) Left inverse
A
(a) - (s), (b) - (p), (c) - (q), (d) - (r)
       Engineering-Mathematics       Match-the-Following
Question 8 Explanation: 
Group - Left inverse
Semigroup - Associative
Monoid - Identity
Abelian group - Commutative
Question 9

Choose the correct alternatives (More than one may be correct). Two NAND gates having open collector outputs are tied together as shown in below figure.

The logic function Y, implemented by the circuit is,

A
Y = ABC + DE
B
C
Y = ABC . DE
D
E
Both (C) and (D)
       Digital-Logic-Design       Circuits-Output
Question 9 Explanation: 
There should be bubbled connection between two gates
Y = ((ABC)' + (DE)')'
Y = ABC . DE
Note: Open gate works as NOR gate.
Question 10

Choose the correct alternatives (More than one may be correct).

Indicate which of the following statements are true: A relational database which is in 3NF may still have undesirable data redundancy because there may exist:

A
Transitive functional dependencies.
B
Non-trivial functional dependencies involving prime attributes on the right-side.
C
Non-trivial functional dependencies involving prime attributes only on the left-side.
D
Non-trivial functional dependencies involving only prime attributes.
E
Both (B) and (D).
       Database-Management-System       Normalization
Question 10 Explanation: 
A) Transitive functional dependency, so not in 3NF.
B) 3NF because right side is prime attribute.
C) Not in 3NF, because lets suppose ABC is a candidate key. Now consider
AB → Non-prime attribute
which show it is not in 3NF
D) Involves only prime attribute, so right side should definitely contain only prime attribute. So in 3NF.
Question 11

Choose the correct alternatives (More than one may be correct). The number of rooted binary trees with n nodes is,

A
Equal to the number of ways of multiplying (n+1) matrices.
B
Equal to the number of ways of arranging n out of 2n distinct elements.
C
D
Equal to n!
E
Both (A) and (C).
       Data-Structures       Binary-Trees
Question 11 Explanation: 
No. of rooted binary trees (unlabeled) with n nodes is given by nth catalan number which equals (2nCn)/(n+1)
Here, both options A and C are true as option A corresponds to n multiply operations of (n+1) matrices, the no. of ways for this is again given by the nth catalan number.
Question 12

Choose the correct alternatives (More than one may be correct).

The total external path length, EPL, of a binary tree with n external nodes is, EPL = ∑wIw, where Iw is the path length of external node w),
A
≤ n2 always.
B
≥ n log2 n always.
C
Equal to n2 always.
D
O(n) for some special trees.
       Data-Structures       Binary-Trees
Question 12 Explanation: 
Here the question asked for binary tree.
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
Question 13

Choose the correct alternatives (More than one may be correct). The complexity of comparison based sorting algorithms is:

A
Θ(n logn)
B
Θ(n)
C
Θ(n2)
D
Θ(n√n)
E
Both (A) and (C)
       Algorithms        Time-Complexity
Question 13 Explanation: 
Question 14

Choose the correct alternatives (More than one may be correct). Recursive languages are:

A
A proper superset of context free languages.
B
Always recognizable by pushdown automata.
C
Also called type ∅ languages.
D
Recognizable by Turing machines.
E
Both (A) and (D)
       Theory-of-Computation       Recursive-Languages
Question 14 Explanation: 
A) True, since there are languages which are not CFL still recursive.
B) False.
C) False, because Type-0 language are actually recursively enumerable languages and not recursive languages.
D) True.
Question 15

Choose the correct alternatives (More than one may be correct).

It is undecidable whether:
A
An arbitrary Turing machine halts after 100 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the products of two numbers.
D
None of the above.
E
Both (B) and (C).
       Theory-of-Computation       Decidability-and-Undecidability
Question 15 Explanation: 
A) An arbitrary TM halts after 100 steps is decidable. We can run TM for 100 steps and conclude that.
B) A TM prints a specific letter is undecidable.
C) A TM computes the products of two numbers is undecidable. Eventhough we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behavior of TM unknown hence, undecidable.
Question 16

Choose the correct alternatives (More than one may be correct). Let R1 and R2 be regular sets defined over the alphabet Σ Then:

A
R1 ∩ R2 is not regular.
B
R1 ∪ R2 is regular.
C
Σ* − R1 is regular.
D
R1* is not regular.
E
Both (B) and (C).
       Theory-of-Computation       Regular-Language
Question 16 Explanation: 
Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleen-closure
Σ* - R1 is the complement of R1.
Hence, (B) and (C) are true.
Question 17

Choose the correct alternatives (More than one may be correct).

The number of ways in which 5 A's, 5 B's and 5 C's can be arranged in a row is:
A
15!/(5!)3
B
15!
C
(15/5)
D
15!(5!3!)
       Engineering-Mathematics       Combinatorics
Question 17 Explanation: 
The no. of ways,
Question 18

Choose the correct alternatives (More than one may be correct). Indicate which of the following well-formed formulae are valid:

A
(P⇒Q) ∧ (Q⇒R) ⇒ (P⇒R)
B
(P⇒Q) ⇒ (¬P⇒¬Q)
C
(P∧(¬P∨¬Q)) ⇒ Q
D
(P⇒R) ∨ (Q⇒R) ⇒ ((P∨Q)⇒R)
       Engineering-Mathematics       Propositional-Logic
Question 18 Explanation: 
To prove any well formed formula valid or tautology try to use this analogy.
Since implication A → B is False only when A = T and B = F. So to prove any implication is valid or not try to get
TRUE → FALSE, if we succeed then it is not valid, if we not then well formed formula is valid.
So, for option (A),
Substitute P=T and R=F
RHS:
P→R becomes False.
LHS:
(P→Q) ∧ (P→R)
To get true here we need T∧T. So substitute Q=T which makes P→Q TRUE and P→R FALSE.
So, T∧F = F which makes LHS = False.
Hence, we are unable to get T→F which proves well formed formula given in option (A) is valid.
Similarly, try for (B), (C), (D). We get T → F in these options which says these well formed formula is invalid.
Question 19

Choose the correct alternatives (More than one may be correct).

A graph is planar if and only if,
A
It does not contain subgraphs homeomorphic to k5 and k3,3.
B
It does not contain subgraphs isomorphic to k5 or k3,3.
C
It does not contain a subgraph isomorphic to k5 or k3,3.
D
It does not contain a subgraph homeomorphic to k5 or k3,3.
       Engineering-Mathematics       Graph-Theory
Question 19 Explanation: 
A graph is non-planar if and only if it contains a subgraph which is homomorphic to k5or k3,3. This is kuratowshi theorem.
Question 20

State whether the following statements are TRUE or FALSE with reason:

RAM is a combinational circuit and PLA is a sequential circuit.
A
True
B
False
       Digital-Logic-Design       Combinational-and-Sequential-Circuits
Question 20 Explanation: 
1) RAM is not a combinational circuit. For RAM, the input is the memory location selector and operation (read or write) and another byte (which can be input for write operation or output for read operation), and the output is either a success indicator (for write operation) or the byte at the selected location (for read operation). It does depend on past inputs, or rather, on the past write operations at the selected byte. This is a sequential logic circuit.
2) PLA is a combination circuit as ROM. PLA is a programmable AND array and a programmable OR array. A PLA with n inputs has fewer than 2n AND gates (otherwise there would be no advantage over a ROM implementation of the same size). A PLA only needs to have enough AND gates to decode as many unique terms as there are in the functions it will implement it.
Question 21

State whether the following statements are TRUE or FALSE with reason:

The data transfer between memory and I/O devices using programmed I/O is faster than interrupt-driven I/O.
A
True
B
False
       Computer-Organization       Modes-of-Transfer
Question 21 Explanation: 
In programmed I/0, no interface register is there but in interrupt driven I/0 interface register is used. So interrupt driven is faster than programmed I/0.
Question 22

State whether the following statements are TRUE or FALSE with reason:

The flags are affected when conditional CALL or JUMP instructions are executed.
A
True
B
False
       Computer-Organization       Instruction-Execution
Question 22 Explanation: 
Flags are tested during conditional call and jumps not affected or changed.
Question 23

State whether the following statements are TRUE or FALSE with reason:

Transferring data in blocks from the main memory to the cache memory enables an interleaved main memory unit to operate at its maximum speed.
A
True
B
False
       Computer-Organization       Cache
Question 23 Explanation: 
Main memory transfer the data in the form of block to cache and cache transfer the data in the form of words, so it enables the interleaved main memory unit to operate unit at maximum speed.
Question 24

State whether the following statements are TRUE or FALSE with reason:

The Link-load-and-go loading scheme required less storage space than the link-and-go loading scheme.
A
True
B
False
       Operating-Systems       Linker
Question 24 Explanation: 
In link and go scheme the linkage editor co-exists with program in main memory while performing the linking task.
Whereas in link, load and go scheme the linkage editor does not co-exists with program in main memory while performing linking task.
There are 24 questions to complete.