## Gate-1990

Question 2 |

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

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

Non-procedural query language → Domain calculus

Closure of set of attributes → Function dependency

Natural join → Relational algebraic operations

Question 3 |

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

Question 3 Explanation:

Pointer data type - Dynamic data structure

Activation record - Recursion

Repeat until - Non-deterministic loop

Coercion - Type conversion

Activation record - Recursion

Repeat until - Non-deterministic loop

Coercion - Type conversion

Question 4 |

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

Question 4 Explanation:

Note: Out of syllabus.

Question 5 |

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

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

Kruskal's minimum spanning tree algorithm - Greedy method

Biconnected components algorithm - Depth first search

Floyd's shortest path algorithm - Dynamic programming

Question 6 |

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

Question 6 Explanation:

Heap construction - O(n)

Constructing Hash table with linear probing - O(n

AVL tree construction - O(n log

Digital trie construction - Ω(n log

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 |

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

Question 7 Explanation:

Lexical analysis - Finite automaton

Code optimization - DAG

Code generation - Syntax tree

Abelian groups - Push down automaton

Code optimization - DAG

Code generation - Syntax tree

Abelian groups - Push down automaton

Question 8 |

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

Question 8 Explanation:

Group - Left inverse

Semigroup - Associative

Monoid - Identity

Abelian group - Commutative

Semigroup - Associative

Monoid - Identity

Abelian group - Commutative

Question 9 |

Y = ABC + DE | |

Y = ABC + DE | |

Y = ABC . DE | |

Y = ABC . DE | |

Both (C) and (D) |

Question 9 Explanation:

There should be bubbled connection between two gates

Y = ((ABC)' + (DE)')'

Y = ABC . DE

Y = ((ABC)' + (DE)')'

Y = ABC . DE

__Note__: Open gate works as NOR gate.Question 10 |

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

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.

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 |

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

Question 11 Explanation:

No. of rooted binary trees (unlabeled) with n nodes is given by n

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

≤ n ^{2} always. | |

≥ nlog _{2} n always. | |

Equal to n ^{2} always. | |

O(n) for some special 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 × logn

But for skewed tree it will be O(n) only.

So, answer will be (D).

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 × logn

But for skewed tree it will be O(n) only.

So, answer will be (D).

Question 13 |

Θ(nlogn) | |

Θ(n) | |

Θ(n ^{2}) | |

Θ(n√n) | |

Both (A) and (C) |

Question 13 Explanation:

Question 14 |

A proper superset of context free languages. | |

Always recognizable by pushdown automata. | |

Also called type ∅ languages. | |

Recognizable by Turing machines. | |

Both (A) and (D) |

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.

B) False.

C) False, because Type-0 language are actually recursively enumerable languages and not recursive languages.

D) True.

Question 15 |

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

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 behaviour of TM unknown hence, undecidable.

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 behaviour of TM unknown hence, undecidable.

Question 16 |

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

Question 16 Explanation:

Regular languages are closed under,

1) Intersection

2) Union

3) Complement

4) Kleen-closure

Σ* - R

Hence, (B) and (C) are true.

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 |

15!/(5!) ^{3} | |

15! | |

(15/5) | |

15!(5!3!) |

Question 17 Explanation:

The no. of ways,

Question 18 |

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

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

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

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

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.

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 |

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

Question 19 Explanation:

A graph is non-planar if and only if it contains a subgraph which is homomorphic to k

_{5}or k_{3,3}. This is kuratowshi theorem.Question 20 |

True | |

False |

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.

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 |

True | |

False |

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 |

True | |

False |

Question 22 Explanation:

Flags are tested during conditional call and jumps not affected or changed.

Question 23 |

True | |

False |

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 |

True | |

False |

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.

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.