# GATE CSE 1990

 Question 1
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 $Y=\overline{ABC + DE}$ C Y=ABC.DE D $Y=\overline{ABC.DE}$
Digital Logic   Boolean Algebra
Question 1 Explanation:
 Question 2
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.
Database Management System   Normal Form
Question 2 Explanation:

 Question 3
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 2 n distinct elements. C Equal to $\frac{1}{(n+1)}\binom{2n}{n}$. D Equal to n!.
Data Structure   Binary Tree
Question 3 Explanation:
 Question 4
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, $\Sigma _w=Iw$, where $I_{w}$ is the path length of external node w),
 A $\leq n^{2}$ always. B $\geq n \log_{2}$ n always. C Equal to $n^{2}$ always. D O(n) for some special trees.
Data Structure   Binary Tree
Question 4 Explanation:
 Question 5
Choose the correct alternatives (More than one may be correct).
The complexity of comparision based sorting algorithms is:
 A $\Theta (n \log n)$ B $\Theta (n)$ C $\Theta \left(n^2\right)$ D $\Theta (n\sqrt n)$
Algorithm   Sorting
Question 5 Explanation:

There are 5 questions to complete.