# GATE CSE 1992

 Question 1
Which of the following predicate calculus statements is/are valid?
 A $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$ B $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$ C $(\forall (x)) (P(x) \vee Q(x)) \implies (\forall (x)) P(x) \vee (\forall (x)) Q(x)$ D $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$
Discrete Mathematics   Propositional Logic
Question 1 Explanation:
 Question 2
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
The operation which is commutative but not associative is:
 A AND B OR C EX-OR D NAND
Digital Logic   Boolean Algebra
Question 2 Explanation:
 Question 3
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
All digital circuits can be realized using only
 A Ex-OR gates B Multiplexers C Half adders D OR gates
Digital Logic   Boolean Algebra
Question 3 Explanation:
 Question 4
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
Bit-slice processors
 A can be cascaded to get any desired word length processor B speed of operation is independent of the word length configured C do not contain anything equivalent of program counter in a 'normal' microprocessor D Contain only the data path of a 'normal' CPU
Computer Organization
Question 4 Explanation:
 Question 5
PCHL is an instruction in 8085 which transfers the contents of the register pair HL to PC. This is not a very commonly used instruction as it changes the flow of control in rather 'unstructured' fashion. This instruction can be useful in implementing.
 A if ... then ... else ... construct B while .. construct C case .. construct D call ... construct
Computer Organization
Question 5 Explanation:
 Question 6
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
Following algorithm(s) can be used to sort n in the range $[1\ldots n^3]$ in O(n) time
 A Heap sort B Quick sort C Merge sort D Radix sort
Algorithm   Sorting
Question 6 Explanation:
 Question 7
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
Start and stop bits do not contain any 'information' but are used in serial communication
 A Error detection B Error correction C Synchronization D Slowing down the communications
Question 7 Explanation:
 Question 8
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
Which of the following problems is not NP-hard?
 A Hamiltonian circuit problem B The 0/1 Knapsack problem C Finding bi-connected components of a graph D The graph coloring problem
Algorithm
Question 8 Explanation:
 Question 9
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

A 2-3 tree is such that
a. All internal nodes have either 2 or 3 children
b. All paths from root to the leaves have the same length.

The number of internal nodes of a 2-3 tree having 9 leaves could be
 A 4 B 5 C 6 D 7
Data Structure   B Tree
Question 9 Explanation:
 Question 10
Choose the correct alternatives ( more than one may be correct) and write the corresponding letters only:
A non-planar graph with minimum number of vertices has
 A 9 edges, 6 vertices B 6 edges, 4 vertices C 10 edges, 5 vertices D 9 edges, 5 vertices
Discrete Mathematics   Planar Graph
Question 10 Explanation:
There are 10 questions to complete.