## Gate-1990

 Question 1
 A (a) - (q), (b) - (p), (c) - (r), (d) - (s)
Operating-Systems       Match-the-Following
 Question 2
 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
 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
 A (a) - (s), (b) - (r), (c) - (p), (d) - (q)
Programming       Match-the-Following
Question 4 Explanation:
Note: Out of syllabus.
 Question 5
 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
 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
 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
 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
 A Y = ABC + DE B Y = ABC + DE C Y = ABC . DE D Y = ABC . DE 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
 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
 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
 A ≤ n2 always. B ≥ nlog2 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 × logn
But for skewed tree it will be O(n) only.
So, answer will be (D).
 Question 13
 A Θ(nlogn) B Θ(n) C Θ(n2) D Θ(n√n) E Both (A) and (C)
Algorithms        Time-Complexity
Question 13 Explanation: Question 14
 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
 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 behaviour of TM unknown hence, undecidable.
 Question 16
 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
 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
 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
 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
 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
 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
 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
 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
 A True B False