On This Page
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on Discrete Mathematics Set 14
Q1 | If a node v is reachable from node u then the path of minimum length u to v is called _____.
- reachability
- node base
- geodesic
- accessibility
Q2 | The eccentricity of a center in a tree is defined as ______ of the tree.
- radius
- diameter
- length
- path
Q3 | P -> Q , Q ->R then________.
- P -> R
- R -> P
- Q
- R
Q4 | If a normal form contains all minterms, then it is ________.
- a tautology
- a contradiction
- a contingency
- both a and b
Q5 | PCNF is also called _______.
- sum of product canonical form.
- product of sum canonical form
- sum canonical form
- product canonical form
Q6 | PDNF is also called _____________
- sum of product canonical form
- product of sum canonical form
- sum canonical form
- product canonical form
Q7 | Max-terms of two statements are formed by introducing the connective _________.
- disjunction
- conjunction
- negation
- conditional
Q8 | The Subset relation on a set of sets is ________.
- partial ordering
- equivalence relation
- reflexive and symmetric only
- symmetric and transitive only
Q9 | A relation R is defined on the set of integers as xRy if and only if (x+y) is even. Which ofthe following statement is TRUE?
- R is not an equivalence relation.
- R is an equivalence relation having one equivalence classes
- R is an equivalence relation having two equivalence classes
- R is an equivalence relation having three equivalence classes
Q10 | If R = {(1, y), (1, z), (3, y)} then R power (-1)= ___________.
- {(1, a), (y, z)}
- {(y, 1), (z, 1), (y, 3)}
- {(y, a), (1, z), (3, y)}
- {(y, a), (z, a), (3, y)}
Q11 | Let R ={ (a,b),(c,d),(b,b)}, S = {(d,b),(c,b),(a,d)} then R composite S = ___________
- {(a,e),(c,b),(b,e)}
- {(d,b),(c,b),(a,d)}
- {(a,b),(b,b)}
- {(c,b)}
Q12 | Let R and S be two relations on a set of positive integers I. If R = {(a, 3a+a)},S = {(a,a+a)}then R composition R composition R = __________.
- {(a,3a+a)}
- {(a,9a+a)}
- {(a,27a+a)}
- {(a,9a+c)}
Q13 | The number of relations from A = {a,b,c} to B = {1,2} are __________.
- 6
- 8
- 32
- 64
Q14 | The minimum number of edges in a connected graph with n vertices is ___________.
- n
- n-1
- n+1
- n+2
Q15 | The number of distinct simple graphs with up to three nodes is _________.
- 7
- 9
- 15
- 25
Q16 | A graph is planar if and only if it does not contain ________.
- subgraphs homeomorphic to k3 & k3,3
- subgraphs isomorphic to k5 or k3,3
- subgraphs isomorphic to k3 & k3,3
- sub graphs homeomorphic to k5 or k3,3
Q17 | Maximum number of edges in an n-node undirected graph without self loops is ____.
- [n(n-a)]/2
- n-1
- n
- [n(n+a)]/2
Q18 | Number of distinct nodes in any elementary path of length p is ________.
- p
- p-1
- p+1
- p*1
Q19 | The total number of edges in a complete graph of n vertices is _________.
- n
- n/2
- [n(n-a)]/3
- [n(n-a)]/2
Q20 | A directed complete graph of n vertices contains __________.
- one arrow between each pair of distinct vertices
- two arrows between each pair of distinct vertices
- n-1 arrows between each pair of distinct vertices
- path between every two distinct vertices
Q21 | A directed graph G = (V, E) is said to be finite if its ________.
- set V of vertices is finite
- set V of vertices & set E of edges are finite
- set E of edges are finite
- no vertices & edges are repeated
Q22 | A state from which a deterministic finite state automata can never come out is called a____________.
- trape state
- starting symbol
- transition table
- transition diagram
Q23 | If a compound statement is made up of three simple statements then the number of rows inthe truth table is _______.
- 2
- 4
- 6
- 8
Q24 | Let R = {(3, 3), (6, 6), (9, 9), (12,12), (3,6), (6,3), (3, 9), (9, 3), (9, 12),(12,9)} be a relationon the set A = {3, 6, 9, 12}. The relation is _________
- reflexive and transitive
- reflexive and symmetric
- symmetric and transitive
- equivalence relation
Q25 | Let R={(1,b),(3,d),(2,b)} and S={(b,4),(2,5),(d,a)} be a relation then R compositionS=____.
- {(1,b),(3,d),(2,b)}
- {(1,4),(3,a),(2,4)}
- {(4,b),(2,5),(3,a)}
- {(1,d),(3,b),(2,c)}