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 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 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 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 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 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
Computer Network   Data Link Layer
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 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 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
There are 10 questions to complete.

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.