Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Subsets”.

1. If a set contains 3 elements then the number of subsets is?
a) 6
b) 3
c) 12
d) 8

Answer: d
Clarification: For elements with n elements the number of subsets are 2ⁿ.

2. The set containing all the collection of subsets is known as _________
a) Subset
b) Power set
c) Union set
d) None of the mentioned

Answer: b
Clarification: Power set contains all the subsets as its elements.

3. If a set is empty then number of subsets will be _________
a) 1
b) 2
c) 0
d) 4

Answer: a
Clarification: The set has zero elements so 2^o = 1.

4. If the number of subsets of a set are 4 then the number of elements in that sets are _________
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The number of elements be x then x² = 4 thus x=2.

5. The number of subsets of a set is 5.
a) True
b) False

Answer: b
Clarification: The number of subsets will always be a power of 2.

6. The number of subsets of a set can be odd or even.
a) True
b) False

Answer: a
Clarification: The number of subsets will be odd in case of empty set otherwise even.

7. Let a set be A={1, 2, 3} then the number of subsets containing two elements will be _________
a) 4
b) 3
c) 5
d) 8

Answer: b
Clarification: The subsets will be {1, 2}, {2, 3}, {1, 3}.

8. Let the set be A= {a, b, c, {a,b}} then which of the following is false?
a) {a, b} Є A
b) a Є A
c) {a} Є A
d) b, c ЄA

Answer: c
Clarification: Only elements belongs to a set, {a} is a subset of this set.

9. If A={1, 2, 3, 4}, then the number of the subsets of A that contain the element 2 but not 3, is?
a) 16
b) 4
c) 8
d) 24

Answer: b
Clarification: The subsets would be {1, 2, 4},{1, 2}, {2, 3}, {2}.

10. Let A(1), A(2), A(3),…….., A(100) be 100 sets such that number of elements in A(i)=i+1 and A(1) is subset of A(2), A(2)is subset of A(3),….., A(99) is subset of A(100). The number of elements in union of the all the sets are: n(A(1) U A(2) U A(3) …..U A(100)).
a) 99
b) 100
c) 101
d) 102

Answer: c
Clarification: Since all sets are subsets of A(100) therefore in union only elements of A(100)will come.A(100) contains 101 elements.

Discrete Mathematics Problems on “Transpose of Matrices”.

1. For a matrix A, if a matrix B is obtained by changing its rows into columns and column into rows, then relation between A and B is?
a) A² = B
b) A^T = B
c) Depends on the matrix
d) None of the mentioned

Answer: b
Clarification: A = [a_ij] and B = [a_ji], B = A^T.

2. For matrix A, (A^T)^T is equals to ___________
a) A
b) A^T
c) Can’t say
d) None of the mentioned

Answer: a
Clarification: Transpose of a transposed matrix results in same matrix.

3. For matrix Aand a scalar k, (kA)^T is equal to _________
a) k(A)
b) k(A)^T
c) k²(A)
d) k²(A)^T

Answer: b
Clarification: Scalar has no effect on transpose.

4. If A is a lower triangular matrix then A^T is a _________
a) Lower triangular matrix
b) Upper triangular matrix
c) Null matrix
d) None of the mentioned

Answer: b
Clarification: By transpose a lower triangular matrix will turn to upper triangular matrix and vice – versa.

5. If matrix A and B are symmetric and AB = BA iff _________
a) AB is symmetric matrix
b) AB is an anti-symmetric matrix
c) AB is a null matrix
d) None of the mentioned

Answer: a
Clarification: For two symmetric matrices A and B, AB is a symmetric matrix if and only if AB = BA.

6. A matrix can be expressed as sum of symmetric and anti-symmetric matrices.
a) True
b) False

Answer: a
Clarification: Since A = (¹⁄₂)(A + A^T) + ((¹⁄₂)(A – A^T)

7. The determinant of a diagonal matrix is the product of leading diagonal’s element.
a) True
b) False

Answer: a
Clarification: Since in diagonal matrix all element other than diagonal are zero.

8. If for a square matrix A and B,null matrix O, (AB)^T = O implies A^T = O and B^T = O.
a) True
b) False

Answer: b
Clarification: Let A=[0 1 0 0 ], B=[1 0 0 0 ] AB=O and B, A^T, B^T is not equal to O.

9. Let A = [a_ij] given by ab_ij = (i-j)³ is a _________
a) Symmetric matrix
b) Anti-Symmetric matrix
c) Identity matrix
d) None of the mentioned

Answer: b
Clarification: aji =(j-i³) = -a_ij, A is Anti-symmetric matrix.

10. Trace of the matrix of odd ordered anti-symmetric matrix is _________
a) 0
b) 1
c) 2
d) All of the mentioned

Answer: a
Clarification: Since in odd ordered anti-symmetric matrix all diagonal matrix are zero.

Discrete Mathematics Multiple Choice Questions on “Applications of Number Theory”.

1. The linear combination of gcd(252, 198) = 18 is?
a) 252*4 – 198*5
b) 252*5 – 198*4
c) 252*5 – 198*2
d) 252*4 – 198*4

Answer: a
Clarification: By using the Euclidean algorithm.

2. The inverse of 3 modulo 7 is?
a) -1
b) -2
c) -3
d) -4

Answer: b
Clarification: By using the Euclidean algorithm, 7 = 2*3 + 1. From this we see that -2*3 + 1*7 = 1. This show that -2 is an inverse.

3. The integer 561 is a Carmichael number.
a) True
b) False

Answer: a
Clarification: By using the Fermat’s theorem, it follows that b⁵⁶⁰ is congruent to 1 (mod 561).

4. The linear combination of gcd(117, 213) = 3 can be written as _________
a) 11*213 + (-20)*117
b) 10*213 + (-20)*117
c) 11*117 + (-20)*213
d) 20*213 + (-25)*117

Answer: a
Clarification: By using the Euclidean algorithm.

5. The inverse of 7 modulo 26 is?
a) 12
b) 14
c) 15
d) 20

Answer: c
Clarification: By using the Euclidean algorithm.

6. The inverse of 19 modulo 141 is?
a) 50
b) 51
c) 54
d) 52

Answer: d
Clarification: By using the Euclidean algorithm.

7. The integer 2821 is a Carmichael number.
a) True
b) False

Answer: a
Clarification: By using the Fermat’s theorem, it follows that b²⁸²⁰ is congruent to 1 (mod 2821).

8. The solution of the linear congruence 4x = 5(mod 9) is?
a) 6(mod 9)
b) 8(mod 9)
c) 9(mod 9)
d) 10(mod 9)

Answer: b
Clarification: The inverse of 5 modulo 9 is -2. Multiply by (-2) on both sides in equation 4x = 5(mod 9), it follows that x is congruent to 8(mod 9).

9. The linear combination of gcd(10, 11) = 1 can be written as _________
a) (-1)*10 + 1*11
b) (-2)*10 + 2*11
c) 1*10 + (-1)*11
d) (-1)*10 + 2*11

Answer: a
Clarification: By using the Euclidean theorem, it follows that 1 = (-1)*10 + 1*11.

10. The value of 5²⁰⁰³ mod 7 is?
a) 3
b) 4
c) 8
d) 9

Answer: a
Clarification: By using the Fermat’s theorem.

Discrete Mathematics Questions & Answers for Exams on “Counting – Number of Equations Solution”.

1. The linear system Cx = d is known as _________ if d! = 0.
a) homogeneous
b) heterogeneous
c) nonhomogeneous
d) augmented system

Answer: c
Clarification: A linear system Cx = d is known as a homogeneous system if d! = 0. The homogeneous linear system Ax = 0 is called its corresponding homogeneous linear system.

2. Every linear equation determines a _______ in n-dimensional space for n variables.
a) shipshape
b) hyperplane
c) cone
d) pyramid

Answer: b
Clarification: In an m-dimensional space, every linear equation produces a hyperplane for n variables. The solution set is the intersection of these hyperplanes and is planar which may have any dimension smaller than m.

3. Determine all possibilities for the number of solutions of the system of 7 equations in 5 unknowns and it has x₁ = 0, x₂ = −6, and x₃ = 4 as a solution.
a) unique or infinitely many
b) unique
c) finitely many
d) zero

Answer: a
Clarification: Let i be the number of equations and j be the number of unknowns in the given system. Since i> j, the system has at least one solution x₁ = 0, x₂ = −6, and x₃ = 4 and so it is consistent. Thus, it results in either a unique solution or infinitely many solutions.

4. Determine all possibilities for the solution set of the homogeneous system that has y₁ = 6, y₂ = −4, y₃ = 0 as a solution.
a) zero
b) infinitely many
c) finitely many
d) only one

Answer: b
Clarification: Since m<n, the system is either inconsistent or has infinitely many solutions. Since y₁ = 6, y₂ = −4, y₃ = 0 is a solution of the system, the system is not inconsistent. Thus the only possibility is infinitely many solutions.

5. Determine all possibilities for the solution set of the homogeneous system of 5 equations in 3 unknowns and the rank of the system is 3.
a) more than two
b) only one
c) zero
d) infinite

Answer: c
Clarification: Since the rank of this homogeneous system(which is always consistent) and the number of unknowns are equal, the only possible solution is zero and it is a unique solution.

6. Determine all possibilities for the solution set of a homogeneous system that has y₁ = 5, y₂ = −3, y₃ = 2 as a solution.
a) one
b) finitely many
c) infinitely many
d) either one or infinitely many

Answer: c
Clarification: The possibilities for the solution set for any homogeneous system is either a unique solution or infinitely many solutions. Since the homogeneous system has the zero solution and y₁ = 5, y₂ = −3, y₃ = 2 is another solution, it has at least two distinct solution. Thus the only possibility is infinitely many solutions.

7. Determine all possibilities for the solution set of the system of 2 equations in 3 unknowns that has x₁ = 4, x₂ = −7, x₃ = 0 as a solution.
a) one or finitely many
b) infinite
c) finite
d) zero

Answer: b
Clarification: Since m1 = 4, x₂ = −7, x₃ = 0 is a solution of the system, the system is not inconsistent. Thus the only possibility is infinitely many solutions.

8. Determine all possibilities for the solution set of a homogeneous system of 4 equations in 4 unknowns.
a) only one
b) finitely many or zero
c) zero
d) one or infinitely many

Answer: b
Clarification: Here the number of equations and the number of unknowns are equal and the system is homogeneous, so it may have the zero solution or infinitely many solutions.

9. Determine all possibilities for the solution set of a homogeneous system of 6 equations in 5 unknowns.
a) only one
b) zero
c) one or infinitely many
d) finitely many

Answer: c
Clarification: Since the system is homogeneous and there are more equations than the number of unknowns, so the possibilities are either a unique solution or infinitely many solutions. However, if the rank r of the system is 5, then it can be a unique solution as well as if r<5, then there are infinitely many solutions.

10. Determine all possibilities for the solution set of a homogeneous system of 5 equations in 4 unknowns and the rank of the system is 3.
a) finite
b) zero or finitely many
c) only one
d) infinite

Answer: d
Clarification: A homogeneous system is consistent. The rank is r = 3 and the number of variables is n = 4. Hence there is n – r = 1 free variable. Thus there are infinitely many solutions.

Discrete Mathematics Multiple Choice Questions on “Closure on Relations”.

1. R is a binary relation on a set S and R is reflexive if and only if _______
a) r(R) = R
b) s(R) = R
c) t(R) = R
d) f(R) = R

Answer: a
Clarification: Let reflexive closure of R:r(R) = R. If R is reflexive, it satisfies all the condition in the definition of reflexive closure. So, a reflexive closure of a relation is the smallest number of reflexive relation contain in R. Hence, R = r(R).

2. If R₁ and R₂ are binary relations from set A to set B, then the equality ______ holds.
a) (R^c)^c = R^c
b) (A x B)^c = Φ
c) (R₁ U R₂)^c = R₁^c ∪ R₂^c
d) (R₁ U R₂)^c = R₁^c ∩ R₂^c

Answer: c
Clarification: To proof (R₁ U R₂)^c = R₁^c ∪ R₂^c,
if <x,y> belongs to (R₁ U R₂)^c
⇔ <y,x> ∈ (R₁ U R₂)
⇔ <y,x> ∈ R₁ or <y,x> ∈ R₂
⇔ <x,y> ∈ R₁^c or <x,y> ∈ R₂^c
⇔ <x,y> ∈ R₁^c ∪ R₂^c.

3. The condition for a binary relation to be symmetric is _______
a) s(R) = R
b) R ∪ R = R
c) R = R^c
d) f(R) = R

Answer: c
Clarification: If <a,b> ∈ R then <b,a> ∈ R, where a and b belong to two different sets and so its symmetric.
R^c also contains <b,a>
R^c = R.

4. ______ number of reflexive closure exists in a relation R = {(0,1), (1,1), (1,3), (2,1), (2,2), (3,0)} where {0, 1, 2, 3} ∈ A.
a) 2⁶
b) 6
c) 8
d) 36

Answer: b
Clarification: The reflexive closure of R is the relation, R ∪ Δ = { (a,b) | (a,b) R (a,a) | a A }. Hence, R ∪ Δ = {(0,1), (1,1), (1,3), (2,1), (2,2), (3,0)} and the answer is 6.

5. The transitive closure of the relation {(0,1), (1,2), (2,2), (3,4), (5,3), (5,4)} on the set {1, 2, 3, 4, 5} is _______
a) {(0,1), (1,2), (2,2), (3,4)}
b) {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}
c) {(0,1), (1,1), (2,2), (5,3), (5,4)}
d) {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}

Answer: d
Clarification: Let R be a relation on a set A. The connectivity relation on R* consists of pairs (a,b) such that there is a path of length at least one from a to b in R. Mathematically, R* = R¹ ∪ R² ∪ R³ ∪ … ∪ Rⁿ. Hence the answer is {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}.

6. Amongst the properties {reflexivity, symmetry, antisymmetry, transitivity} the relation R={(a,b) ∈ N² | a!= b} satisfies _______ property.
a) symmetry
b) transitivity
c) antisymmetry
d) reflexivity

Answer: a
Clarification: It is not reflexive as aRa is not possible. It is symmetric as if aRb then bRa. It is not antisymmetric as aRb and bRa are possible and we can have a!=b. It is not transitive as if aRb and bRc then aRc need not be true. This is violated when c=a. So the answer is symmetry property.

7. The number of equivalence relations of the set {3, 6, 9, 12, 18} is ______
a) 4
b) 2⁵
c) 22
d) 90

Answer: a
Clarification: Number of equivalence Relations are given by BELL number. The nth of these numbers i.e, B_n counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it. Let’s say, 1 -> Equivalence relation with 1 element; 1 2 -> Equivalence relation with 2 element; 2 3 5 -> Equivalence relation with 3 element; 5 7 10 15 -> Equivalence relation with 4 element. Hence, the answer is 4.

8. Let R₁ and R₂ be two equivalence relations on a set. Is R₁ ∪ R₂ an equivalence relation?
a) an equivalence relation
b) reflexive closure of relation
c) not an equivalence relation
d) partial equivalence relation

Answer: a
Clarification: R₁ union R₂ is not equivalence relation because transitivity property of closure need not hold. For instance, (x, y) can be in R₁ and (y, z) be in R₂ and (x, z) not in either R₁ or R₂. However, R₁ intersection R₂ is an equivalence relation.

9. A relation R is defined on the set of integers as aRb if and only if a+b is even and R is termed as ______
a) an equivalence relation with one equivalence class
b) an equivalence relation with two equivalence classes
c) an equivalence relation
d) an equivalence relation with three equivalence classes

Answer: b
Clarification: R is reflexive as (a+b) is even for any integer; R is symmetric as if (a+b) is even (b+a) is also even; R is transitive as if ((a+b)+c) is even, then (a+(b+c)) is also even.
So, R is an equivalence relation. For set of natural numbers, sum of even numbers always give even, sum of odd numbers always give even and sum of any even and any odd number always give odd. So, must have two equivalence classes -> one for even and one for odd.
{…, -4, -2, 0, 2, … } and {…, -3, -1, 1, 3, … }.

10. The binary relation U = Φ (empty set) on a set A = {11, 23, 35} is _____
a) Neither reflexive nor symmetric
b) Symmetric and reflexive
c) Transitive and reflexive
d) Transitive and symmetric

Answer: d
Clarification: U = Φ (empty set) on a set A = {11, 23, 35} need to be hold Irreflexive, symmetric, anti-symmetric, asymmetric and transitive closure property, but it is not Reflexive as it does not contain any self loop in itself.

Discrete Mathematics Multiple Choice Questions on “Tree Traversal”.

1. In preorder traversal of a binary tree the second step is ____________
a) traverse the right subtree
b) traverse the left subtree
c) traverse right subtree and visit the root
d) visit the root

Answer: b
Clarification: In a preorder traversal of a binary tree first is to visit the root, second traverse the left subtree of the tree and third traverse the right subtree of the tree.

2. An important application of binary tree is ______
a) Huffman coding
b) stack implementation
c) queue implementation
d) traverse a cyclic graph

Answer: a
Clarification: A binary tree is used to sort a list of elements; the inorder traversal will do this automatically. Better tree sorting algorithm will involve balancing the trees. The binary coding, in particular for the Huffman coding is an immediate application of binary trees.

3. From the following code identify the which traversal of a binary tree is this __________

//if node has left child
  order(node.left)
//if node has right child
  order(node.right)
  visit(node)

a) Inorder traversal
b) preorder traversal
c) postorder traversal
d) Euler tour traversal

Answer: c
Clarification: In a postorder traversal of a binary tree first is to traverse the left subtree, second traverse the right subtree of the tree and third is to visit the node.

4. What is the minimum height for a binary search tree with 60 nodes?
a) 1
b) 3
c) 4
d) 2

Answer: d
Clarification: If there are k nodes in a binary tree, maximum height of that tree should be k-1, and minimum height should be floor(log2k). By using the formula, minimum height must be 2 when there are 60 nodes in a tree.

5. From the following code identify the which traversal of a binary tree is this __________

function traversal(node)
{
    //Input:root node of the tree
    //Output:None
    visitLeft(node)
    //if node has left child
    traversal(node.left)
    visit_Below(node)
    //if node has right child
    traversal(node.right)
    visitRight(node)
}

a) Inorder traversal
b) Euler Tour traversal
c) Post-order traversal
d) Pre-order Traversal

Answer: b
Clarification: The code signifies Euler Tour traversal which is a generic traversal of a binary tree. In this tree traversal we have to walk around the tree and visit each node three times:
1. On the left (pre-order), 2. From below (in-order), 3. On the right (post-order) and Create subtrees for all the nodes.

6. For the expression (7-(4*5))+(9/3) which of the following is the post order tree traversal?
a) *745-93/+
b) 93/+745*-
c) 745*-93/+
d) 74*+593/-

Answer: c
Clarification: First build a binary tree for the expression then find out the postorder traversal of that tree and after that the answer will be 745*-93/+.

7. The time complexity of calculating the sum of all leaf nodes in an n-order binary tree is __________
a) O(n²)
b) O(n+1)
c) O(1)
d) O(n)

Answer: d
Clarification: The approach is to traverse the binary tree in any fashion and check if the node is the leaf node(child node)or not. After that, add node data to the sum variable. So, after summing up all leaf nodes, the time complexity of the operation should be O(n).

8. An immediate application of a Depth First Search traversal is __________
a) count the number of leaf nodes
b) perform Inorder traversal in easy way
c) count number of nodes
d) implement preorder traversal

Answer: a
Clarification: Given an n-ary binary tree, by performing DFS traversal on that tree number of leaf nodes can be calculated and for that we need to maintain an array for the leaf count.

9. Breadth First Search traversal of a binary tree finds its application in __________
a) Cloud computing
b) Peer to peer networks
c) Weighted graph
d) Euler path

Answer: b
Clarification: Breadth First Search traversal has diverse applications such as in the peer to peer networks like BitTorrent, BFS traversal is used to find all the neighbour nodes of the network.

10. Worst case complexity of Breadth First Search traversal __________
a) O(n*n)
b) O(nlogn)
c) O(n² logn)
d) O(n³)

Answer: b
Clarification: In an n-ary binary tree, we must have to visit all nodes from an adjacent node and repeat the same for next unvisited nodes. Hence, in worst case the time complexity should be O(nlogn).