Category: Discrete Mathematics Objective Questions

Discrete Mathematics Objective Questions & Answers on “Different Path in a Graph”.

1. Which algorithm efficiently calculates the single source shortest paths in a Directed Acyclic Graph?
a) topological sort
b) hash table
c) binary search
d) radix sort

Answer: a
Clarification: For Directed Acyclic graph, single source shortest distances can be calculated in O(V+E) time. For that purpose Topological Sorting can be used. Topological Sorting of any graph represents a linear ordering of the graph.

2. The _______ of a graph G consists of all vertices and edges of G.
a) edge graph
b) line graph
c) path complement graph
d) eulerian circuit

Answer: d
Clarification: we know that he Eulerian circuit in a graph G is a circuit that includes all vertices and edges of G. A graph that can have Eulerian circuit, also can have a Eulerian graph.

3. A ______ in a graph G is a circuit which consists of every vertex (except first/last vertex) of G exactly once.
a) Euler path
b) Hamiltonian path
c) Planar graph
d) Path complement graph

Answer: b
Clarification: The Eulerian path in a graph say, G is a walk from one vertex to another, that can pass through all vertices of G as well as traverses exactly once every edge of G. Therefore, an Eulerian path can not be a circuit. A Hamiltonian path is a walk that contains every vertex of the graph exactly once. Hence, a Hamiltonian path is not a circuit.

4. A walk has Closed property if ____________
a) v₀=v_k
b) v₀>=v_k
c) v < 0
d) v_k > 1

Answer: a
Clarification: A walk in a graph is said to be closed if the starting vertex is the same as the ending vertex, that is v₀=v_k, it is described as Open otherwise.

5. A trail in a graph can be described as ______________
a) a walk without repeated edges
b) a cycle with repeated edges
c) a walk with repeated edges
d) a line graph with one or more vertices

Answer: a
Clarification: Suppose in a graph G a trail could be defined as a walk with no repeated edges. Suppose a walk can be defined as efgh. There are no repeated edges so this walk is a trail.

6. Let a graph can be denoted as ncfkedn a kind of ____________
a) cycle graph
b) line graph
c) hamiltonian graph
d) path graph

Answer: a
Clarification: In the graph ncfkedn, no edges are repeated in the walk, which makes it a trail and then start and end vertex n is same making it a cycle graph.

7. Determine the edge count of a path complement graph with 14 vertices.
a) 502
b) 345
c) 78
d) 69

Answer: c
Clarification: Let, an n-path complement graph P_n’ is the graph complement of the path graph P_n. Since P_n is self-complementary, P₄’ is isomorphic to P₄. Now, P_n’ has an edge count = ¹⁄₂(n-2)(n-1). So, the required edge count is=78.

8. The sum of an n-node graph and its complement graph produces a graph called _______
a) complete graph
b) bipartite graph
c) star graph
d) path-complement graph

Answer: a
Clarification: Suppose, the complement G’ of a graph G is known as edge-complement graph which consists of with the same vertex set but whose edge set contains the edges not present in G. The graph sum G+G’ on an n-node graph G is called the complete graph say, K_n.

9. In a directed weighted graph, if the weight of every edge is decreased by 10 units, does any change occur to the shortest path in the modified graph?
a) 209
b) 65
c) 57
d) 43

Answer: c
Clarification: The shortest path will change in the modified graph. Suppose that the shortest path is of weight 21 and has 7 edges and there is another path with 4 edges and total weight 17. Now, the weight of the first shortest path is increased by 7*10 and becomes 21 + 70 and the weight of the second path is increased by 4*10 and becomes 17 + 40. So the shortest path changes to the other path with weight as 57.

10. Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?
a) BFS
b) DFS
c) Binary search
d) Radix sort

Answer: a
Clarification: In BFS due to the least number of edges between two vertices and so if all the edges in a graph are of same weight, then to find the shortest path BFS can be used for efficiency. So we have to split all edges of weight 5 into two edges of weight 2 each and one edge of weight 1. In the worst case, all edges are of weight 1. To split all edges, O(E) operations can be done and so the time complexity becomes which is equal to O(V+E).

Discrete Mathematics Multiple Choice Questions on “Group Axioms”.

1. __________ are called group postulates.
a) Group lemmas
b) Group theories
c) Group axioms
d) Group

Answer: c
Clarification: The group axioms are also called the group postulates. A group with an identity (that is, a monoid) in which every element has an inverse is termed as semi group.

2. A subgroup has the properties of ________
a) Closure, associative
b) Commutative, associative, closure
c) Inverse, identity, associative
d) Closure, associative, Identity, Inverse

Answer: d
Clarification: A subgroup S is a subset of a group G (denoted by S <= G) if it holds the four properties simultaneously – Closure, Associative, Identity and Inverse element.

3. If a * b = a such that a ∗ (b ∗ c) = a ∗ b = a and (a * b) * c = a * b = a then ________
a) * is associative
b) * is commutative
c) * is closure
d) * is abelian

Answer: a
Clarification: ‘∗’ can be defined by the formula a∗b = a for any a and b in S. Hence, (a ∗ b)∗c = a∗c = a and a ∗(b ∗ c)= a ∗ b = a. Therefore, ”∗” is associative. Hence (S, ∗) is a semigroup. On the contrary, * is not associative since, for example, (b•c)•c = a•c = c but b•(c•c) = b•a = b Thus (S,•) is not a semigroup.

4. The set of odd and even positive integers closed under multiplication is ________
a) a free semigroup of (M, ×)
b) a subsemigroup of (M, ×)
c) a semigroup of (M, ×)
d) a subgroup of (M, ×)

Answer: b
Clarification: Let C and D be the set of even and odd positive integers. Then, (C, ×) and (D, ×) are subsemigroups of (M, ×) since A and B are closed under multiplication. On the other hand, (A, +) is a subsemigroup of (N, +) since A is closed under addition, but (B, +) is not a subsemigroup of (N, +) since B is not closed under addition.

5. If F is a free semigroup on a set S, then the concatenation of two even words is ________
a) a semigroup of F
b) a subgroup of F
c) monoid of F
d) cyclic group of F

Answer: b
Clarification: Let F be the free semigroup on the set S = {m,n}. Let, E consist of all even words, i.e, words with even length and the concatenation of two such words is also even. Thus E is a subsemigroup of F.

6. The set of rational numbers form an abelian group under _________
a) Association
b) Closure
c) Multiplication
d) Addition

Answer: c
Clarification: The set of nonzero rational numbers form an abelian group under multiplication. The number 1 is the identity element and q/p is the multiplicative inverse of the rational number p/q.

7. Condition of semigroup homomorphism should be ____________
a) f(x * x) = f(x * y)
b) f(x) = f(y)
c) f(x) * f(y) = f(y)
d) f(x * y) = f(x) * f(y)

Answer: d
Clarification: Consider two semigroups (S,∗) and (S’,∗’). A function f: S -> S’ is called a semigroup homomorphism if f(a∗b) = f(a)∗f(b). Suppose f is also one-to-one and onto. Then f is called an isomorphism between S and S’ and S and S’ are said to be isomorphic semigroups.

8. A function f:(M,∗)→(N,×) is a homomorphism if ______
a) f(a, b) = a*b
b) f(a, b) = a/b
c) f(a, b) = f(a)+f(b)
d) f(a, b) = f(a)*f(a)

Answer: b
Clarification: The function f is a homomorphism since f(x∗y)= f(ac, bd)= (ac)/(bd) = (a/b)(c/d) = f(x)f(y).

9. A function defined by f(x)=2*x such that f(x+y)=2x+y under the group of real numbers, then ________
a) Isomorphism exists
b) Homomorphism exists
c) Heteromorphic exists
d) Association exists

Answer: b
Clarification: Let T be the group of real numbers under addition, and let T’ be the group of positive real numbers under multiplication. The mapping f: T -> T’ defined by f(a)=2*a is a homomorphism because f(a+b)=2a+b = 2a*2b = f(a)*f(b). Again f is also one-to-one and onto T and T’ are isomorphic.

10. If x * y = x + y + xy then (G, *) is _____________
a) Monoid
b) Abelian group
c) Commutative semigroup
d) Cyclic group

Answer: c
Clarification: Let x and y belongs to a group G.Here closure and associativity axiom holds simultaneously. Let e be an element in G such that x * e = x then x+e+xe=a => e(1+x)=0 => e = 0/(1+x) = 0. So, identity axiom does not exist but commutative property holds. Thus, (G,*) is a commutative semigroup.

Discrete Mathematics Multiple Choice Questions on “Set Operations”.

1. The union of the sets {1, 2, 5} and {1, 2, 6} is the set _______________
a) {1, 2, 6, 1}
b) {1, 2, 5, 6}
c) {1, 2, 1, 2}
d) {1, 5, 6, 3}

Answer: b
Clarification: The union of the sets A and B, is the set that contains those elements that are either in A or in B.

2. The intersection of the sets {1, 2, 5} and {1, 2, 6} is the set _____________
a) {1, 2}
b) {5, 6}
c) {2, 5}
d) {1, 6}

Answer: a
Clarification: The intersection of the sets A and B, is the set containing those elements that are in both A and B.

3. Two sets are called disjoint if there _____________ is the empty set.
a) Union
b) Difference
c) Intersection
d) Complement

Answer: c
Clarification: By the definition of the disjoint set.

4. Which of the following two sets are disjoint?
a) {1, 3, 5} and {1, 3, 6}
b) {1, 2, 3} and {1, 2, 3}
c) {1, 3, 5} and {2, 3, 4}
d) {1, 3, 5} and {2, 4, 6}

Answer: d
Clarification: Two sets are disjoint if the intersection of two sets is the empty set.

5. The difference of {1, 2, 3} and {1, 2, 5} is the set ____________
a) {1}
b) {5}
c) {3}
d) {2}

Answer: c
Clarification: The difference of the sets A and B denoted by A-B, is the set containing those elements that are in A not in B.

6. The complement of the set A is _____________
a) A – B
b) U – A
c) A – U
d) B – A

Answer: b
Clarification: The complement of the set A is the complement of A with respect to U.

7. The bit string for the set {2, 4, 6, 8, 10} (with universal set of natural numbers less than or equal to 10) is ____________________
a) 0101010101
b) 1010101010
c) 1010010101
d) 0010010101

Answer: a
Clarification: The bit string for the set has a one bit in second, fourth, sixth, eighth, tenth positions, and a zero elsewhere.

8. Let Ai = {i, i+1, i+2, …..}. Then set {n, n+1, n+2, n+3, …..} is the _________ of the set Ai.
a) Union
b) Intersection
c) Set Difference
d) Disjoint

Answer: b
Clarification: By the definition of the generalized intersection of the set.

9. The bit strings for the sets are 1111100000 and 1010101010. The union of these sets is ___________
a) 1010100000
b) 1010101101
c) 1111111100
d) 1111101010

Answer: d
Clarification: The bit string for the union is the bitwise OR of the bit strings.

10. The set difference of the set A with null set is __________
a) A
b) null
c) U
d) B

Answer: a
Clarification: The set difference of the set A by the null set denoted by A – {null} is A.

Discrete Mathematics Questions and Answers for Aptitude test on “Cardinality of Sets”.

1. The cardinality of the set A = {1, 2, 3, 4, 6} is?
a) 5
b) 6
c) Integer
d) None of the mentioned

Answer: a
Clarification: 5, it is a number of elements in the sets.

2. For two equal sets there ___________
a) Cardinality is same
b) Cardinality is different
c) May be same or different
d) None of the mentioned

Answer: a
Clarification: Two equal sets should have the same number of elements.

3. If A is a subset of B then _______
a) The cardinality of A is greater than B
b) The cardinality of B is greater than A
c) Can’t say
d) None of the mentioned

Answer: b
Clarification: B contains all the elements of A, as well as other elements.

4. If there is a bijection between two sets A and B then _______
a) Cardinality of A is greater than B
b) Cardinality of B is greater than A
c) Cardinality of B is equal to A
d) None of the mentioned

Answer: c
Clarification: If there is bijection then two sets A and B will be equinumerous and thus will have same cardinality.

5. Let a set E ={0,2,4,6,8….} of non-negative even numbers and O = {1, 3, 5, 7, 9,…..} of non-negative odd numbers then?
a) Cardinality of set E is greater than that of O
b) Cardinality of set O is greater than that of E
c) Cardinality of set E is equal to that of O
d) None of the mentioned

Answer: c
Clarification: There is bijection then two sets E and O and they will be equinumerous and thus will have same cardinality.

6. Cardinality of the set of lower letter english alphabets is 26.
a) True
b) False

Answer: a
Clarification: From a, b, c…z there will be 26 elements.

7. Cardinality of the set of even prime number under 10 is 4.
a) True
b) False

Answer: b
Clarification: Since 2 is only even prime thus cardinality should be 1.

8. If for sets A and B there exists an injective function but not bijective function from A to B then?
a) Cardinality of A is strictly greater than B
b) Cardinality of B is strictly greater than A
c) Cardinality of B is equal to A
d) None of the mentioned

Answer: b
Clarification: If there doesnot exist a bijective function from A to B that means there are some elements in B whose preimage is not in A, thus cardinality of B is strictly greater than A.

9. If cardinality of (A U B) = cardinality of A+ cardinality of B. This means ____________
a) A is a subset of B
b) B is a subset of A
c) A and B are disjoint
d) None of the mentioned

Answer: c
Clarification: Thus if the cardinality of (A U B) = cardinality of A+ cardinality of B, it means they don’t have any element in common, n(A∩B) = 0.

10. If A is a subset of B and B is a subset of C, then cardinality of A U B U C is equal to ____________
a) Cardinality of C
b) Cardinality of B
c) Cardinality of A
d) None of the mentioned

Answer: a
Clarification: A U B U C = C, since a, b are subsets to C.

Discrete Mathematics Questions and Answers for Campus interviews on “Number Theory – Highest Common Factors”.

1. A Highest Common Factor of a, b is defined as ___________
a) It is the smallest integer divisible by both a and b
b) It is the greatest integer divisor of both a and b
c) It is the sum of the number a and b
d) None of the mentioned

Answer: b
Clarification: Defination of HCF(a, b)-greatest integer divisor of both a and b.

2. The HCF of two number 1, b(integer) are _________
a) b + 2
b) 1
c) b
d) None of the mentioned

Answer: b
Clarification: Since 1 is the greatest integer divisor of both 1 and b.

3. If a,b are integers such that a > b then hcf(a, b) lies in _________
a) a> hcf(a, b)>b
b) a>b> = hcf(a, b)
c) hcf(a, b)> = a>b
d) None of the mentioned

Answer: b
Clarification: Hcf of number is either equal to smallest number or is least among all.

4. HCF of 6, 10 is?
a) 60
b) 30
c) 10
d) 2

Answer: d
Clarification: Since 2 is the greatest integer divisor of both 6 and 10.

5. The product of two numbers are 12 and there LCM is 6 then HCF is?
a) 12
b) 2
c) 6
d) None of the mentioned

Answer: b
Clarification: The hcf of two number a and b is given by
(hcf(a, b)) = ab/ lcm(a, b).

6. If LCM of two number is 10 and GCD is 5 then the product of two numbers is?
a) 45
b) 50
c) 7
d) 49

Answer: b
Clarification: The lcm of two number a and b is given by
lcm(a,b) = ab/(GCD(a, b)), this implies ab = lcm(a, b) * gcd(a, b).

7. If a number is 2² x 3¹ x 5⁰ and b is 2² x 3¹ x 5¹ then hcf of a, b is?
a) 2² x 3¹ x 5¹
b) 2² x 3² x 5²
c) 2¹ x 3¹ x 5⁰
d) 2² x 3² x 5⁰

Answer: c
Clarification: Hcf is the product of sets having least exponent value among a and b.

8. State whether the given statement is True or False.

HCF (a, b, c, d) = HCF(a,(HCF(b,(HCF(c, d)))).

a) True
b) False

Answer: a
Clarification: HCF function can be reursively defined.

9. HCF(a, b) is equals to _________
a) ab/(LCM(a, b))
b) (a + b)/(LCM(a, b))
c) (LCM(a, b))/ab
d) None of the mentioned

Answer: a
Clarification: ab = lcm(a, b)*hcf(a, b), which implies
HCF(a,b) = ab/(LCM(a, b)).

10. The HCF of two prime numbers a and b is _________
a) ^a⁄_b
b) ab
c) a + b
d) 1

Answer: d
Clarification: Since they doesnot have any factor in common other than 1.

Discrete Mathematics Multiple Choice Questions on “Counting – Circular Permutations”.

1. In a playground, 3 sisters and 8 other girls are playing together. In a particular game, how many ways can all the girls be seated in a circular order so that the three sisters are not seated together?
a) 457993
b) 3386880
c) 6544873
d) 56549

Answer: b
Clarification: There are 3 sisters and 8 other girls in total of 11 girls. The number of ways to arrange these 11 girls in a circular manner = (11– 1)! = 10!. These three sisters can now rearrange themselves in 3! ways. By the multiplication theorem, the number of ways so that 3 sisters always come together in the arrangement = 8! × 3!. Hence, the required number of ways in which the arrangement can take place if none of the 3 sisters is seated together: 10! – (8! × 3!) = 3628800 – (40320 * 6) = 3628800 – 241920 = 3386880.

2. How many numbers of three digits can be formed with digits 1, 3, 5, 7 and 9?
a) 983
b) 120
c) 345
d) 5430

Answer: b
Clarification: Here number of digits, n = 5 and number of places to be filled-up r = 3. Hence, the required number is ⁵P₃ = 5!/2!*3! = 120.

3. The size of a multiset is 6 which is equal to the number of elements in it with counting repetitions (a multiset is an unordered collection of elements where the elements may repeat any number of times). Determine the number of multisets can be grouped from n distinct elements so that at least one element occurs exactly twice?
a) 326
b) 28
c) 45
d) 62

Answer: c
Clarification: There are six places to be filled in the multiset using the n distinct elements. At least one element has to occur exactly twice and that would leave 4 more places in the multiset means that at most four elements can occur exactly once. Thus there are two mutually exclusive cases as follows: 1) Exactly one element occurs exactly twice and select this element in n ways. Fill up the remaining four spots using 5 distinct elements from the remaining n−1 elements in ^n-1C₄ ways. 2) Exactly four elements that occur at least once each. Hence, the total number of ways to form the multiset is
ⁿC₂ + n * ^n-1C₄ = ⁶C₂ + 6 * ^6-1C₄ = 45.

4. How many words can be formed with the letters of the word ‘CASTLE’ when ‘O’ and ‘A’ occupying end places.
a) 217
b) 48
c) 75
d) 186

Answer: b
Clarification: When ‘O’ and ‘A’ are occupying end-places => A.S.T.L. (CE). We can see that (CE) are fixed, hence A, S, T, L can be arranged in 4! Ways and (C, E) can be arranged themselves is 2! ways. So, the number of words formed = 4! x 2! = 48 ways.

5. Determine the number of ways of choosing a cricket team (consists of 11 players) out of 18 players if a particular player is never chosen.
a) 12798
b) 22800
c) 31824
d) 43290

Answer: c
Clarification: If a particular player is never chosen that would mean 11 players are selected out of 18 players. Hence, required number of ways = ¹⁸C₁₁ = 31824.

6. How many different choices can be made from 5 roses, 4 marigold and 8 sunflowers if at least one flower is to be chosen for making of garland?
a) 269
b) 270
c) 281
d) 320

Answer: a
Clarification: Number of ways of selecting roses = (5+1) = 6 ways, number of ways of selecting marigold = (4+1) = 5 ways, and the number of ways of selecting sunflowers = (8+1) = 9 ways. Total number of ways of selecting flowers= 6 * 5 * 9 = 270. But this includes when no flowers or zero flowers is selected (There is no flowers of a different type, hence n=0 => 2ⁿ = 2⁰ = 1). Hence, the number of ways of selecting at least one fruit = 270 – 1 = 269.

7. In how many ways 6 pens can be selected from 15 identical black pens?
a) 9*3!
b) 21
c) 14!
d) 1

Answer: d
Clarification: Here the pens are identical, the total number of ways of selecting 6 pens is 1.

8. Determine the number of ways of selecting one or more letters from the letters BBBBBB?
a) 6
b) 73
c) 23
d) 56

Answer: a
Clarification: The number of ways of selecting one ‘B’s = 1, selecting two ‘B’s = 1, selecting three ‘B’s = 1, selecting four ‘B’s = 1, selecting five ‘B’s = 1 and selecting six ‘B’s = 1. Hence, the required number of ways = 6.

9. Determine the number of ways such that 5 men and 5 women be seated at a round table if no two women are seated together.
a) 654870
b) 144521
c) 362160
d) 5634

Answer: c
Clarification: The men and women can be seated alternately so that no two women will sit together. Hence, 4 women can be seated on alternate seats at a round table in (4 – 1)! or 6
ways. Now, the 5 men can be seated in the remaining seats in 5! or 120 ways. Therefore the total number of ways in this case will be (10-1)! – (120 * 6) = 362160.

10. Find the number of ways in which 4 people E, F, G, H, A, C can be seated at a round table, such that E and F must always sit together.
a) 32
b) 290
c) 124
d) 48

Answer: d
Clarification: E and F can sit together in all arrangements in 2! Ways. Now, the arrangement of the 5 people in a circle can be done in (5 – 1)! or 24 ways. Therefore, the total number of ways will be 24 x 2 = 48.