## 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) - (q), (b) - (p), (c) - (r), (d) - (s) |

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) - (q), (b) - (r), (c) - (p), (d) - (s) |

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) - (q), (b) - (r), (c) - (s), (d) - (p) |

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) - (s), (b) - (r), (c) - (p), (d) - (q) |

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) - (r), (b) - (p), (c) - (s), (d) - (q) |

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 log_{10}n) (b) Constructing Hash table with linear probing (q) O(n) (c) AVL Tree construction (r) O(n^{2}) (d) Digital trie construction (s) O(n log_{10}n)

(a) - (q), (b) - (r), (c) - (s), (d) - (p) |

Constructing Hash table with linear probing - O(n

^{2}

AVL tree construction - O(n log

_{10}n)

Digital trie construction - Ω(n log

_{10}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) - (s), (b) - (p), (c) - (q), (d) - (r) |

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) - (s), (b) - (p), (c) - (q), (d) - (r) |

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,

Y = ABC + DE | |

Y = ABC . DE | |

Both (C) and (D) |

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:

Transitive functional dependencies. | |

Non-trivial functional dependencies involving prime attributes on the right-side.
| |

Non-trivial functional dependencies involving prime attributes only on the left-side.
| |

Non-trivial functional dependencies involving only prime attributes. | |

Both (B) and (D). |

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,

Equal to the number of ways of multiplying (n+1) matrices. | |

Equal to the number of ways of arranging n out of 2n distinct elements. | |

Equal to n! | |

Both (A) and (C). |

^{th}catalan number which equals (

^{2n}C

_{n})/(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 n

^{th}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 = ∑_{w}Iw, where I

_{w}is the path length of external node w),

≤ n ^{2} always. | |

≥ n log _{2} n always. | |

Equal to n ^{2} always. | |

O(n) for some special trees. |

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:

Θ(n logn) | |

Θ(n) | |

Θ(n ^{2}) | |

Θ(n√n) | |

Both (A) and (C) |

Question 14 |

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

A proper superset of context free languages. | |

Always recognizable by pushdown automata. | |

Also called type ∅ languages. | |

Recognizable by Turing machines. | |

Both (A) and (D) |

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:An arbitrary Turing machine halts after 100 steps. | |

A Turing machine prints a specific letter. | |

A Turing machine computes the products of two numbers. | |

None of the above. | |

Both (B) and (C). |

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 R_{1} and R_{2} be regular sets defined over the alphabet Σ Then:

R _{1} ∩ R_{2} is not regular. | |

R _{1} ∪ R_{2} is regular. | |

Σ* − R _{1} is regular. | |

R _{1}* is not regular. | |

Both (B) and (C). |

1) Intersection

2) Union

3) Complement

4) Kleen-closure

Σ* - R

_{1}is the complement of R

_{1}.

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:15!/(5!) ^{3} | |

15! | |

(15/5) | |

15!(5!3!) |

Question 18 |

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

(P⇒Q) ∧ (Q⇒R) ⇒ (P⇒R) | |

(P⇒Q) ⇒ (¬P⇒¬Q) | |

(P∧(¬P∨¬Q)) ⇒ Q
| |

(P⇒R) ∨ (Q⇒R) ⇒ ((P∨Q)⇒R) |

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,It does not contain subgraphs homeomorphic to k _{5} and k_{3,3}. | |

It does not contain subgraphs isomorphic to k _{5} or k_{3,3}. | |

It does not contain a subgraph isomorphic to k _{5} or k_{3,3}. | |

It does not contain a subgraph homeomorphic to k _{5} or k_{3,3}. |

_{5}or k

_{3,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.True | |

False |

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

False |

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

False |

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

False |

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

False |

Whereas in link, load and go scheme the linkage editor does not co-exists with program in main memory while performing linking task.