Discrete Mathematics MCQS:
Following are some mcqs that will be very useful to test yourself that how strong is your grip in discrete mathematics:
 A sequence in which every term after the first is obtained from the preceding term by adding a constant number is called _________.
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 A sequence in which every term after the first is obtained from preceding term by multiplying it with a constant number is called __________.
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 In general, if a is the first term and d the common difference of an _____________then the series is given as: a+(a+d)+(a+2d)+….
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 In general, if a is the first term and r the common ratio of a ________, then the series is given as: a+ar+a+a+….
(a) Sequence (b) Geometric sequence (c) Arithmetic sequence
 Recursive definitions can be used in a “_________” manner.
(a) Generative (b) Nongenerative (c)both a & b.
 An integer n is _______ if, and only if n=2k for some integer k.
(a) Even (b) odd (c) prime
 An integer n is ______ if, and only if n=2k+1 for some integer k.
(a) Even (b) odd (c) prime
 An integer n is _______ if and only if n>1 and for all positive integers r and s, if n=r.s, then r = 1 or s = 1.
(a) Rational (b) composite (c) prime
 An integer n>1 is ________ if and only if n=r.s for some positive integer rand s with r ≠ 1 and s ≠ 1
(a) Rational (b) composite (c) prime
 A real number r is ________ if and only if for some integers a and b with b ≠ 0.
(a) Rational (b) composite (c) prime
 If n and d are integers and d ≠ 0, then d _______ n if and only if n=d.k for some integers k.
(a) Multiplies (b) divides (c) subtracts
 An integer n is called a perfect _______ if and only if n= for some integer k.
(a) cube (b) square (c) multiple
 Square of an even integer is _____ .
(a) Even (b) odd (c) both

 If a graph is a tree, then its only ________ is itself.
(a) Rooted tree (c) Binary tree (c) Trivial tree

A _______ spanning tree for a weighted graph is a spanning tree that has the least possible total weight compared to all other spanning trees of the graph.

(a) Minimal rooted (b) Minimal spanning (c) minimal trivial
 How many bit strings of length 8 begin and end with 1.
(a) 87 (b) 64 (c) 72
 How many three digit integers are divisible by 5.
(a) 140 (b) 160 (c) 180
 A ksample of a set of n elements is a choice of k elements taken from the set of n elements such that the order of elements matters and elements _________ .
(a) Can be repeated (b) cannot be repeated (c)none
 A ________ of a set of n elements is a selection of k elements taken from the set of n elements such that the order of elements matter but repetition of elements is not allowed.
(a) kpermutation (b) kselections (c) kcombinations
 With a kcombination the order in which the elements are selected ________ and the elements cannot repeat.
(a) Does matter (b) does not matter (c) none
 C (n, 0) = __.
(a) 0 (b) 1 (c) 2
 C (n, n) = __.
(a) 0 (b) 1 (c) 2
 C (n, 1) = __.
(a) n (b) n1 (c) n2
 C (n, 2) =______.
(a) n (n1) (b) n (n2) (c) n (n1)/2
 C (n, k) = ______ .
(a) n, nk (b) n, n1 (c) n, n2
 C (n, k) + C (n, k+1) = ___________ .
(a)n+1, k+1 (b) n+2, k+2 (c)C(n+1, k+1)
 How many 16bit strings contain at least one 1’s.
(a)45573 (b) 84522 (c) 65535
 __________ are similar to kcombinations in that the order in which the elements are selected does not matter, but in this case repetitions can occur.
(a) kpermutation (b) kselections (c) kcombinations
 A ________ is a useful tool to list all the logical possibilities of a sequence of events where each event can occur in a finite number of ways.
(a) logical diagram (b) mathematical diagram (c) tree diagram
 n (AB)= _____________.
(a) n(A) + n(B) (b) n(A) – n(B) + n(AB) (c) n(A) + n(B) – n(AB)
 A function from a set of k+1 or more elements to a set of k elements must have at least two elements in domain that have the same image in the codomain is called _____________ .
(a) sparrowhole principle (b) pigeonhole principle (c) logical principle
 The theory of probability was first developed in the ______ century when certain gambling games were analyzed by the French mathematician Blaise Pascal.
(a) 16^{th} (b) 17^{th} (c) 18^{th}
 In the 18^{th} century, the French mathematician Laplace, who also studied gambling, gave definition of the _________ as the number of successful outcomes divided by the number of total outcomes.
(a) Sample space (b) Event (c) probability
 An _________ is a procedure that yields a given set of possible outcomes.
(a) Sample space (b) Event (c) Experiment
 The __________ of the experiment is the set of possible outcomes.
(a) Sample space (b) Event (c) Experiment
 An _____ is a subset of the sample space.
(a) Sample space (b) Event (c) Experiment
 If A and B are two disjoint events of a sample space S, then P (AB) = _________ .
(a) P(A) (b) P(A) + P(B) (c) P(A) – P(B)
 If A and B are any two events of a sample space S, then P (AB) = __________ .
(a) P(A) + P(B) (b) P(A) – P(B) + P(A∩B) (c) P(A) + P(B) –P(A∩B)
 A ________ X is a rule that assigns a numerical value to each outcome in a sample space S.
(a) Random variable (b) Unique variable (c) None
 A ________ is a nonempty set of points called vertices and a set of lines segments joining pairs of vertices called edges.
(a) Chart (b) Graph (c) Diagram
 An edge connects either one or two vertices are called its ________.
(a) Incident (b) Adjacent (c) Endpoints
 An edge with just one end point is called a _______.
(a) Incident (b) Loop (c) isolated
 Two vertices that are connected by an edge are called ________.
(a) Incident (b) Adjacent (c) Endpoints
 An edge is said to be _________ to each of its endpoint.
(a) Incident (b) Adjacent (c) Endpoints
 A vertex on which no edges are incident is called _______.
(a) Incident (b) Loop (c) isolated
 Two distinct edges with the same set of end point are said to be ________.
(a) Incident (b) parallel (c) isolated
 A graph G is regular of degree or kregular if every _______ of G has degree k.
(a) Vertex (b) Edge (c) Loop
 The complete graph is ______ regular.
(a) n (b) (n1) (c) (n+1)
 The __________ G is a simple graph whose vertex set can be partitioned into two ,mutually disjoint non empty subsets A and B such that the vertices in A may be connected to vertices in B, but no vertices in A are connected to vertices in A and no vertices in B are connected to B.
(a) Regular graph (b) Bipartite graph (c) Complete bipartite graph
 A ________________ on (m+n) vertices denoted is a simple graph whose vertex set can be partitioned into two mutually disjoint non empty subsets A and B containing m and n vertices respectively, such that each vertex in set A is connected to every vertex in set B, but the vertices within a set are not connected.
(a) Regular graph (b) Bipartite graph (c) Complete bipartite graph
 A square matrix A=[] of size n×n is called _______ if and only if .
(a) Transpose (b) symmetric (c) Graph
 If the number of columns of A is not equal to the number of rows of B, then the product AB is ________.
(a) Defined (b) not defined (c) none
 A directed graph or digraph, consists of two finite sets: a set V (G) of vertices and a set D (G) of directed edges, where each edge is associated with an ordered pair of vertices called its_________ .
(a) End points (b) vertices (c) loop
 A _____ is a connected graph that does not contain any nontrivial circuit.
(a) Tree (b) trivial tree (c) empty tree
 A graph that consists of single vertex is a called a _______ .
(a) Tree (b) trivial tree (c) empty tree
 A tree that does not have any vertices or edges is called an _________.
(a) rooted Tree (b) trivial tree (c) empty tree
 A graph is called a _______ if and only if it is circuitfree.
(a) rooted Tree (b) Binary tree (c) forest
 A tree with n vertices has _______ edges.
(a) n (b) n + 1 (c) n – 1
 A tree has no nontrivial circuit; but if one new edge (but no new vertex) is added to it, then the resulting graph has exactly one _____________.
(a) trivial circuit (b) Non trivial circuit (c) binary circuit
 A tree is connected but if any edge is _________ from it, then the resulting graph is not connected.
(a) Deleted (b) subtracted (c) None
 Any tree that has more than one vertex has at least _____ vertices of degree 1.
(a) Two (b) three (c) four
 A graph is a _____ if there is a unique path between any two of its vertices.
(a) Binary tree (b rooted tree (c) tree
 A ________ is a tree in which one vertex is distinguished from the others is called the root.
(a) Binary tree (b) rooted tree (c) tree
 The ______ of a vertex is the number of edges along the unique path between it and the root.
(a) Level (b) Height (c) Children
 The _________ of a rooted tree is the maximum level to any vertex of the tree.
(a) Level (b) Height (c) Children
 The ________ of any internal vertex v are all those vertices that are adjacent to v and are one level further away from the root then v.
(a) Level (b) Height (c) Children
 If w is a child of v, then v is called the _______ of w.
(a) Children (b) parent (c) siblings
 Two vertices that are both children of same parent are called ______.
(a) Children (b) parent (c) siblings
 Given vertices v and w, if v lies on the unique path between w and the root, then v is an ancestor of w and w is the _________of v.
(a) Descendant (b) parent (c) siblings
 A _________ is a rooted tree in which every internal vertex has at most two children.
(a) Rooted tree (c) Binary tree (c) Trivial tree
 Every child in a binary tree is designated either a left or right child but ________.
(a) Both (b) not both (c) none
 A full binary tree is a binary tree in which each internal vertex has exactly ______ children.
(a) Two (b) Three (c) Four
 A ________ for a graph G is a sub graph of G that contains every vertex of G and is a tree.
(a) Rooted tree (c) Binary tree (c) Spanning tree
 Every connected graph has a __________.
(a) Rooted tree (c) Binary tree (c) Trivial tree
 A graph may have more than ______ spanning trees.
(a) Two (b) Three (c) Four
 Any two spanning trees for a graph have the ______ number of edges.
(a) Same (b) Different (c) Both a & b