On This Page
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on Discrete Mathematics Set 16
Q1 | An undirected graph is tripartite if and only if it has no circuits of _______ lengths
- odd
- even
- distinct
- equal
Q2 | A graph is bipartite if and only if its chromatic number is ________.
- 1
- 2
- odd
- even
Q3 | G is strongly connected implies _________.
- G is unilaterally connected.
- G is bilaterally connected
- G is unilaterally connected
- G has more than one component
Q4 | The number of pendant vertices in a full binary tree with n vertices is ________.
- (n-a)/2
- (n-1)/2
- (n+a)/2
- n/2
Q5 | The number of vertices in a full binary tree is _______.
- odd
- even
- equal
Q6 | A binary tree with 2k vertices of level k has at least _______ vertices.
- 2 power k
- 2 power (k-1)
- 2 power (k-1)-1)
- 2 power (k+1)-1
Q7 | For a symmetric digraph, the adjacency matrix is _________.
- symmetric
- antisymmetric
- asymmetric
- symmetric and asymmetric
Q8 | The diagonal entries of A A^T where A is the adjacency matrix are the _______.
- outdegrees of the node
- indegrees of the nodes
- unit degree of the nodes
- in & out degrees of the nodes
Q9 | DFSA and NDFSA represent the ________ language.
- regular
- context free
- context sensitive
- phrase structure
Q10 | The chromatic number of the chess board is ______.
- 1
- 2
- 3
- 4
Q11 | The total number of degrees of an isolated node is _______.
- 0
- 1
- 2
- 3
Q12 | If G is a connected planar graph then it has a vertex of degree _______.
- 3 or less
- 4 or less
- 5 or less
- 6 or less
Q13 | A product of the variable and their negation in a formula is called ________.
- an elementary sum
- an elementary product
- a well-formed formula
- an equivalence of relation formula
Q14 | A formula consisting of disjunctions of min-terms is called _________.
- DNF
- CNF
- PDNF
- PCNF
Q15 | The less than relation < on real is __________.
- a partial ordering since it is asymmetric and reflexive
- a partial ordering since it is anti-symmetric and reflexive
- not a partial ordering since it is not asymmetric and not reflexive
- not a partial ordering since it is not anti-symmetric and not reflexive
Q16 | A relation R in X is said to be a ________, if it is reflexive and symmetric.
- void relation
- circular
- partial order relation
- compatibility relation
Q17 | The set X*X itself defines a relation in X is called a _____relation.
- void
- universal
- partial
- equivalence
Q18 | A self complemented distributive lattice is called _______.
- boolean algebra
- modular lattice
- complete lattice
- self dual lattice
Q19 | Every finite subset of a lattice has ____________.
- a Least Upper Bound and Greatest Lower Bound
- many Least Upper Bounds and a Greatest Lower Bound
- many Least Upper Bounds and many Greatest Lower Bounds
- either some Least Upper Bounds or some Greatest Lower Bounds
Q20 | A formula consisting of conjunctions of max-terms is called _________.
- DNF
- CNF
- PCNF
- PDNF
Q21 | The set of all divisors of 24 are ___________.
- {1, 2, 3, 4, 6, 8, 12, 24}
- {2, 3, 4, 6, 8, 12}
- {1, 3, 6, 12,}
- {2, 4, 6, 8}
Q22 | Which of the following is Absorption Law?
- a*a <=>a
- a+(a*b)<=> a
- a*b <=>a*a
- (a*b)*c <=>a*(b*c)
Q23 | In a bounded lattice, an element b belongs to L is called a complement of an element abelongs to L if ______.
- a*b=0
- a+b=1
- both a and b
- none
Q24 | If each non-empty subset of a lattice has a least upper bound and greatest lower bound thenthe lattice is called ________.
- complete
- associative
- absorption
- commutative
Q25 | A __________ is a complemented distributive lattice.
- boolean homomorphism
- boolean algebra
- boolean isomorphism
- boolean function