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 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 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 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 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 6
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 0 languages.
D
Recognizable by Turing machines.
Theory of Computation   Recursive Language
Question 7
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.
Theory of Computation   Undecidability
Question 8
Choose the correct alternatives (More than one may be correct).
Let R_{1} and R_{1} be regular sets defined over the alphabet \Sigma Then:
A
R_{1} \cap R_{2} is not regular.
B
R_{1} \cup R_{2} is regular.
C
\Sigma^{*}-R_{1} is regular.
D
R_{1}^{*} is not regular.
Theory of Computation   Regular Grammar
Question 9
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
\left(\frac{15}{5}\right)
D
15!(5!3!).
Discrete Mathematics   Combination
Question 10
Choose the correct alternatives (More than one may be correct).
Indicate which of the following well-formed formulae are valid:
A
\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)
B
\left(P\Rightarrow Q\right) \Rightarrow \left( \neg P \Rightarrow \neg Q\right)
C
\left(P{\wedge} \left(\neg P \vee \neg Q\right)\right) \Rightarrow Q
D
\left(P \Rightarrow R\right) \vee \left(Q \Rightarrow R\right) \Rightarrow \left(\left(P \vee Q \right) \Rightarrow R\right)
Discrete Mathematics   Propositional Logic
There are 10 questions to complete.

Leave a Comment