This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Logics – Propositions”.
1. Which of the following statement is a proposition?

c) What is the time now?
d) The only odd prime number is 2
View Answer
Answer: d
Explanation: Only this statement has got the truth value which is false.
2. The truth value of ‘4+3=7 or 5 is not prime’.
a) False
b) True
View Answer
Answer: b
Explanation: Compound statement with ‘or’ is true when either of the statement is true. Here the first part of the statement is true, hence the whole is true.
3. Which of the following option is true?
a) If the Sun is a planet, elephants will fly
b) 3 +2 = 8 if 5-2 = 7
c) 1 > 3 and 3 is a positive integer
d) -2 > 3 or 3 is a negative integer
View Answer
Answer: a
Explanation: Hypothesis is false, thus the whole statement is true.
4. What is the value of x after this statement, assuming the initial value of x is 5?
‘If x equals to one then x=x+2 else x=0’.
a) 1
b) 3
c) 0
d) 2
View Answer
Answer: c
Explanation: If condition is false so value decided according to else condition.
5. Let P: I am in Bangalore.; Q: I love cricket.; then q -> p(q implies p) is?
a) If I love cricket then I am in Bangalore
b) If I am in Bangalore then I love cricket
c) I am not in Bangalore
d) I love cricket
View Answer
Answer: a
Explanation: Q is hypothesis and P is conclusion. So the compound statement will be if hypothesis then conclusion.
6. Let P: If Sahil bowls, Saurabh hits a century.; Q: If Raju bowls, Sahil gets out on first ball. Now if P is true and Q is false then which of the following can be true?
a) Raju bowled and Sahil got out on first ball
b) Raju did not bowled
c) Sahil bowled and Saurabh hits a century
d) Sahil bowled and Saurabh got out
View Answer
Answer: c
Explanation: Either hypothesis should be false or both (hypothesis and conclusion) should be true.
7. The truth value ‘9 is prime then 3 is even’.
a) False
b) True
View Answer
Answer: b
Explanation: The first part of the statement is false, hence whole is true.
8. Let P: I am in Delhi.; Q: Delhi is clean.; then q ^ p(q and p) is?
a) Delhi is clean and I am in Delhi
b) Delhi is not clean or I am in Delhi
c) I am in Delhi and Delhi is not clean
d) Delhi is clean but I am in Mumbai
View Answer
Answer: a
Explanation: Connector should be ‘and’, that is q and p.
9. Let P: This is a great website, Q: You should not come back here. Then ‘This is a great website and you should come back here.’ is best represented by?
a) ~P V ~Q
b) P ∧ ~Q
c) P V Q
d) P ∧ Q
View Answer
Answer: b
Explanation: The second part of the statement is negated, hence negation operator is used.
10. Let P: We should be honest., Q: We should be dedicated., R: We should be overconfident. Then ‘We should be honest or dedicated but not overconfident.’ is best represented by?
a) ~P V ~Q V R
b) P ∧ ~Q ∧ R
c) P V Q ∧ R
d) P V Q ∧ ~R
View Answer
Answer: d
Explanation: The third part of the statement is negated, hence negation operator is used, for (‘or’ –V) is used and for(’but’- ∧).
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Logics – Types of Statements”.
1. The contrapositive of p → q is the proposition of ____________
a) ¬p → ¬q
b) ¬q → ¬p
c) q → p
d) ¬q → p
View Answer
Answer: b
Explanation: Definition of contrapositive.
2. The inverse of p → q is the proposition of ____________
a) ¬p → ¬q
b) ¬q → ¬p
c) q → p
d) ¬q → p
View Answer
Answer: a
Explanation: Definition of inverse.
3. The converse of p → q is the proposition of _______________
a) ¬p → ¬q
b) ¬q → ¬p
c) q → p
d) ¬q → p
View Answer
Answer: c
Explanation: Definition of converse.
4. What is the contrapositive of the conditional statement? “The home team misses whenever it is drizzling?”
a) If it is drizzling, then home team misses
b) If the home team misses, then it is drizzling
c) If it is not drizzling, then the home team does not misses
d) If the home team wins, then it is not drizzling
View Answer
Answer: d
Explanation: q whenever p contrapositive is ¬q → ¬p.
5. What is the converse of the conditional statement “If it ices today, I will play ice hockey tomorrow.”
a) “I will play ice hockey tomorrow only if it ices today.”
b) “If I do not play ice hockey tomorrow, then it will not have iced today.”
c) “If it does not ice today, then I will not play ice hockey tomorrow.”
d) “I will not play ice hockey tomorrow only if it ices today.”
View Answer
Answer: a
Explanation: If p, then q has converse q → p.
6. What are the contrapositive of the conditional statement “I come to class whenever there is going to be a test.”
a) “If I come to class, then there will be a test.”
b) “If I do not come to class, then there will not be a test.”
c) “If there is not going to be a test, then I don’t come to class.”
d) “If there is going to be a test, then I don’t come to class.”
View Answer
Answer: b
Explanation: q whenever p, has contrapositive ¬q → ¬p.
7. What are the inverse of the conditional statement “ A positive integer is a composite only if it has divisors other than 1 and itself.”
a) “A positive integer is a composite if it has divisors other than 1 and itself.”
b) “If a positive integer has no divisors other than 1 and itself, then it is not composite.”
c) “If a positive integer is not composite, then it has no divisors other than 1 and itself.”
d) None of the mentioned
View Answer
Answer: c
Explanation: p only if q has inverse ¬p → ¬q.
8. What are the converse of the conditional statement “When Raj stay up late, it is necessary that Raj sleep until noon.”
a) “If Raj stay up late, then Raj sleep until noon.”
b) “If Raj does not stay up late, then Raj does not sleep until noon.”
c) “If Raj does not sleep until noon, then Raj does not stay up late.”
d) “If Raj sleep until noon, then Raj stay up late.”
View Answer
Answer: d
Explanation: Necessary condition for p is q has converse q → p.
9. What are the contrapositive of the conditional statement “Medha will find a decent job when she labour hard.”?
a) “If Medha labour hard, then she will find a decent job.”
b) “If Medha will not find a decent job, then she not labour hard.”
c) “If Medha will find a decent job, then she labour hard.”
d) “If Medha not labour hard, then she will not find a decent job.”
View Answer
Answer: b
Explanation: The statement q when p has its contrapositive as ¬q → ¬p.
10. What are the inverse of the conditional statement “If you make your notes, it will be a convenient in exams.”
a) “If you make notes, then it will be a convenient in exams.”
b) “If you do not make notes, then it will not be a convenient in exams.”
c) “If it will not be a convenient in exams, then you did not make your notes.”
d) “If it will be a convenient in exams, then you make your notes
View Answer
Answer: b
Explanation: If p then q has inverse ¬p → ¬q.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Types of Set”.
1. {x: x is an integer neither positive nor negative} is ________
a) Empty set
b) Non-empty set
c) Finite set
d) Non- empty and Finite set
View Answer
Answer: d
Explanation: Set = {0} non-empty and finite set.
2. {x: x is a real number between 1 and 2} is an ________
a) Infinite set
b) Finite set
c) Empty set
d) None of the mentioned
View Answer
Answer: a
Explanation: It is an infinite set as there are infinitely many real number between any two different real numbers.
3. Write set {1, 5, 15, 25,…} in set-builder form.
a) {x: either x=1 or x=5n, where n is a real number}
b) {x: either x=1 or x=5n, where n is a integer}
c) {x: either x=1 or x=5n, where n is an odd natural number}
d) {x: x=5n, where n is a natural number}
View Answer
Answer: c
Explanation: Set should include 1 or an odd multiple of 5.
4. Express {x: x= n/ (n+1), n is a natural number less than 7} in roster form.
a) {1⁄2, 2⁄3, 4⁄5, 6⁄7}
b) {1⁄2, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 7⁄8}
c) {1⁄2, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 6⁄7}
d) Infinite set
View Answer
Answer: c
Explanation: n/(n+1) = 1/(1+1) = 1⁄2 and n>7.
5. Number of power set of {a, b}, where a and b are distinct elements.
a) 3
b) 4
c) 2
d) 5
View Answer
Answer: b
Explanation: Power set of {a, b} = {∅, {a, b}, {a}, {b}}.
6. Which of the following is subset of set {1, 2, 3, 4}?
a) {1, 2}
b) {1, 2, 3}
c) {1}
d) All of the mentioned
View Answer
Answer: d
Explanation: There are total 16 subsets.
7. A = {∅,{∅},2,{2,∅},3}, which of the following is true?
a) {{∅,{∅}} ∈ A
b) {2} ∈ A
c) ∅ ⊂ A
d) 3 ⊂ A
View Answer
Answer: c
Explanation: Empty set is a subset of every set.
8. Subset of the set A= { } is?
a) A
b) {}
c) ∅
d) All of the mentioned
View Answer
Answer: d
Explanation: Every set is subset of itself and Empty set is subset of each set.
9. {x: x ∈ N and x is prime} then it is ________
a) Infinite set
b) Finite set
c) Empty set
d) Not a set
View Answer
Answer: a
Explanation: There is no extreme prime, number of primes is infinite.
10. Convert set {x: x is a positive prime number which divides 72} in roster form.
a) {2, 3, 5}
b) {2, 3, 6}
c) {2, 3}
d) {∅}
View Answer
Answer: c
Explanation: 2 and 3 are the divisors of 72 which are prime.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Questions and Answers for Entrance exams focuses on “Inverse of a Function”.
1. For an inverse to exist it is necessary that a function should be __________
a) injection
b) bijection
c) surjection
d) none of the mentioned
View Answer
Answer: b
Explanation: Inverse exist only for those functions which are one one and onto.
2. If f(x) = y then f-1(y) is equal to __________
a) y
b) x
c) x2
d) none of the mentioned
View Answer
Answer: b
Explanation: On giving inverse, image the function returns preimage thus f-1 (y) = x.
3. A function f(x) is defined from A to B then f -1 is defined __________
a) from A to B
b) from B to A
c) depends on the inverse of function
d) none of the mentioned
View Answer
Answer: b
Explanation: Inverse associate each element in B with corresponding element in A.
4. If f is a function defined from R to R, is given by f(x) = 3x – 5 then f –1(x) is given by __________
a) 1/(3x-5)
b) (x+5)/3
c) does not exist since it is not a bijection
d) none of the mentioned
View Answer
Answer: b
Explanation: y = 3x-5, x = (y+5)/3, f -1(x) = (x+5)/3.
5. For some bijective function inverse of that function is not bijective.
a) True
b) False
View Answer
Answer: b
Explanation: If f(x) is a bijection than f -1(x) is also a bijection.
6. f(x) is a bijection than f -1(x) is a mirror image of f(x) around y = x.
a) True
b) False
View Answer
Answer: a
Explanation: Inverse of a function is the mirror image of function in line y = x.
7. If f is a function defined from R to R, is given by f(x) = x2 then f -1(x) is given by?
a) 1/(3x-5)
b) (x+5)/3
c) does not exist since it is not a bijection
d) none of the mentioned
View Answer
Answer: c
Explanation: It is not a one one function hence Inverse does not exist.
8. For any function fof -1(x) is equal to?
a) x
b) 1
c) x2
d) none of the mentioned
View Answer
Answer: a
Explanation:Compostion of a function with its inverse gives x.
9. The solution to f(x) = f -1(x) are __________
a) no solutions in any case
b) same as solution to f(x) = x
c) infinite number of solution for every case
d) none of the mentioned
View Answer
Answer: b
Explanation: Inverse of a function is the mirror image of function in line y = x.
10. Let f(x) = x then number of solution to f(x) = f -1(x) is zero.
a) True
b) False
View Answer
Answer: b
Explanation: Since inverse of a function is the mirror image of function in line y = x, therefore in this case infinte solution will exist.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics for Entrance exams, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice s & Answers (MCQs) focuses on “Algorithms”.
1. An algorithm is a _________ set of precise instructions for performing computation.
a) Infinite
b) Finite
c) Constant
d) None of the mentioned
View Answer
Answer: b
Explanation: By the definition of an algorithm.
2. Out of the following which property algorithms does not share?
a) Input
b) Finiteness
c) Generality
d) Constancy
View Answer
Answer: d
Explanation: All the others are the properties of algorithms.
3. In ________ search each element is compared with x till not found.
a) Binary
b) Sequential
c) Merge
d) None of the mentioned
View Answer
Answer: b
Explanation: In linear or sequential search entire list is searched sequentially for x.
4. If the entire list is searched sequentially without locating x in linear search, the solution is __________
a) 0
b) -1
c) 1
d) 2
View Answer
Answer: a
Explanation: If the element is not found in the entire list, then the solution is 0.
5. To sort a list with n elements, the insertion sort begins with the __________ element.
a) First
b) Second
c) Third
d) Fourth
View Answer
Answer: b
Explanation: The insertion sort compares the second element with the first element to start sorting.
6. __________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.
a) (n2 + n + 2) / 2
b) (n3 + n – 2) / 2
c) (n2 + n – 2) / 2
d) (n2 – n – 2) / 2
View Answer
Answer: c
Explanation: 2+3+4+….6n = (n2 + n – 2) / 2.
7. The Worst case occurs in linear search algorithm when ____________
a) Item is somewhere in the middle of the array
b) Item is not in the array at all
c) Item is the last element in the array
d) Item is the last element in the array or is not there at all
View Answer
Answer: d
Explanation: The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.
8. List obtained in third pass of selection sort for list 3, 5, 4, 1, 2 is ___________
a) 1, 2, 4, 3, 5
b) 1, 2, 3, 4, 5
c) 1, 5, 4, 3, 2
d) 3, 5, 4, 1, 2
View Answer
Answer: b
Explanation: The selection sort begins with finding the least element in the list. This element is moved to front and then the least element among the remaining elements. Is found and put into the second position and so on.
9. The operation of processing each element in the list is known as _________
a) Sorting
b) Merging
c) Inserting
d) Traversal
View Answer
Answer: d
Explanation: The operation of processing each element in the list is known as Traversal.
10. The complexity of Bubble sort algorithm is _________
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
View Answer
Answer: c
Explanation: The complexity of Bubble sort algorithm is O(n2).
Sanfoundry Global Education & Learning Series – Discrete Mathematics
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Questions and Answers for Freshers focuses on “Algorithms – Complexity-2”.
1. Which is used to measure the Time complexity of an algorithm Big O notation?
a) describes limiting behaviour of the function
b) characterises a function based on growth of function
c) upper bound on growth rate of the function
d) all of the mentioned
View Answer
Answer: d
Explanation: Big O notation describes limiting behaviour, and also gives upper bound on growth rate of a function.
2. If for an algorithm time complexity is given by O(1) then the complexity of it is ____________
a) constant
b) polynomial
c) exponential
d) none of the mentioned
View Answer
Answer: a
Explanation: The growth rate of that function will be constant.
3. If for an algorithm time complexity is given by O(log2n) then complexity will be ___________
a) constant
b) polynomial
c) exponential
d) none of the mentioned
View Answer
Answer: d
Explanation: The growth rate of that function will be logarithmic therefore complexity will be logarithmic.
4. If for an algorithm time complexity is given by O(n) then the complexity of it is ___________
a) constant
b) linear
c) exponential
d) none of the mentioned
View Answer
Answer: b
Explanation: The growth rate of that function will be linear.
5. If for an algorithm time complexity is given by O(n2) then complexity will ___________
a) constant
b) quadratic
c) exponential
d) none of the mentioned
View Answer
Answer: b
Explanation: The growth rate of that function will be quadratic therefore complexity will be quadratic.
6. If for an algorithm time complexity is given by O((3⁄2)n) then complexity will be ___________
a) constant
b) quardratic
c) exponential
d) none of the mentioned
View Answer
Answer: c
Explanation: The growth rate of that function will be exponential therefore complexity will be exponential.
7. The time complexity of binary search is given by ___________
a) constant
b) quardratic
c) exponential
d) none of the mentioned
View Answer
Answer: d
Explanation: It is O(log2n), therefore complexity will be logarithmic.
8. The time complexity of the linear search is given by ___________
a) O(log2n)
b) O(1)
c) exponential
d) none of the mentioned
View Answer
Answer: d
Explanation: It is O(n), therefore complexity will be linear.
9. Which algorithm is better for sorting between bubble sort and quicksort?
a) bubble sort
b) quick sort
c) both are equally good
d) none of the mentioned
View Answer
Answer: b
Explanation: Running time of quicksort is logarithmic whereas for bubble sort it is quadratic.
10. Time complexity of the binary search algorithm is constant.
a) True
b) False
View Answer
Answer: b
Explanation: It is O(log2n), therefore complexity will be logarithmic.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics for Freshers, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Number Theory – Prime Numbers”.
1. The number of factors of prime numbers are ___________
a) 2
b) 3
c) Depends on the prime number
d) None of the mentioned
View Answer
Answer: a
Explanation: A prime number is only divisible by 1 and itself.
2. What is the number ‘ 1’?
a) Prime number
b) Composite number
c) Neither Prime nor Composite
d) None of the mentioned
View Answer
Answer: c
Explanation: 1 is neither prime number nor composite.
3. All prime numbers are odd.
a) True
b) False
View Answer
Answer: b
Explanation: 2 is even as well as prime.
4. 3 is the smallest prime number possible.
a) True
b) False
View Answer
Answer: b
Explanation: 2 is also a prime number.
5. How many prime numbers are there between 1 to 20?
a) 5
b) 6
c) 7
d) None of the mentioned
View Answer
Answer: d
Explanation: The prime numbers between 1 to 20 are 2, 3, 5, 7, 11, 13, 17, 19.
6. There are finite number of prime numbers.
a) True
b) False
View Answer
Answer: b
Explanation: There are infinite numbers of primes.
7. Sum of two different prime number is a ____________
a) Prime number
b) Composite number
c) Either Prime or Composite
d) None of the mentioned
View Answer
Answer: c
Explanation: Eg:- 2 + 3 = 5 a prime, 3 + 7 = 10 a composite.
8. Difference of two distinct prime numbers is?
a) Odd and prime
b) Even and composite
c) None of the mentioned
d) All of the mentioned
View Answer
Answer: c
Explanation: 3 – 2 = 1 is neither prime nor composite.
9. If a, b, c, d are distinct prime numbers with an as smallest prime then a * b * c * d is a ___________
a) Odd number
b) Even number
c) Prime number
d) None of the mentioned
View Answer
Answer: b
Explanation: Since a is 2, 2 * b * c * d = Even number.
10. If a, b are two distinct prime number than a highest common factor of a, b is ___________
a) 2
b) 0
c) 1
d) ab
View Answer
Answer: c
Explanation: HCF of two prime numbers is 1.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Answer: a
Explanation: By using the Euclidean algorithm.
2. The inverse of 3 modulo 7 is?
a) -1
b) -2
c) -3
d) -4
View Answer
Answer: b
Explanation: 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
View Answer
Answer: a
Explanation: By using the Fermat’s theorem, it follows that b560 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
View Answer
Answer: a
Explanation: By using the Euclidean algorithm.
5. The inverse of 7 modulo 26 is?
a) 12
b) 14
c) 15
d) 20
View Answer
Answer: c
Explanation: By using the Euclidean algorithm.
6. The inverse of 19 modulo 141 is?
a) 50
b) 51
c) 54
d) 52
View Answer
Answer: d
Explanation: By using the Euclidean algorithm.
7. The integer 2821 is a Carmichael number.
a) True
b) False
View Answer
Answer: a
Explanation: By using the Fermat’s theorem, it follows that b2820 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)
View Answer
Answer: b
Explanation: 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
View Answer
Answer: a
Explanation: By using the Euclidean theorem, it follows that 1 = (-1)*10 + 1*11.
10. The value of 52003 mod 7 is?
a) 3
b) 4
c) 8
d) 9
View Answer
Answer: a
Explanation: By using the Fermat’s theorem.
Sanfoundry Global Education & Learning Series – Discrete Mathematics
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Principle of Mathematical Induction”.
1. What is the base case for the inequality 7n > n3, where n = 3?
a) 652 > 189
b) 42 < 132
c) 343 > 27
d) 42 <= 431
View Answer
Answer: c
Explanation: By the principle of mathematical induction, we have 73 > 33 ⇒ 343 > 27 as a base case and it is true for n = 3.
2. In the principle of mathematical induction, which of the following steps is mandatory?
a) induction hypothesis
b) inductive reference
c) induction set assumption
d) minimal set representation
View Answer
Answer: a
Explanation: The hypothesis of Step is a must for mathematical induction that is the statement is true for n = k, where n and k are any natural numbers, which is also called induction assumption or induction hypothesis.
3. For m = 1, 2, …, 4m+2 is a multiple of ________
a) 3
b) 5
c) 6
d) 2
View Answer
Answer: d
Explanation: For n = 1, 4 * 1 + 2 = 6, which is a multiple of 2. Assume that 4m+2 is true for m=k and so 4k+2 is true based on the assumption. Now, to prove that 4k+2 is also a multiple of 2 ⇒ 4(k+1)+2 ⇒ 2 * 4k – 4k + 6 ⇒ 2*4k+4 – 4k+2 ⇒ 2(4k+2) – 2(2k+1). Here, the first term 2(4k+2) is true as per assumption and the second term 2(4k+2) is must to be a multiple of 2. Hence, 4(k+1)+2 is a multiple of 2. So, by induction hypothesis, (4m+2) is a multiple of 2, for m = 1,2,3,…
4. For any integer m>=3, the series 2+4+6+…+(4m) can be equivalent to ________
a) m2+3
b) m+1
c) mm
d) 3m2+4
View Answer
Answer: a
Explanation: The required answer is m2+3. Now, by induction assumption, we have to prove 2+4+6+…+4(k+1) = (k+1)2+3 also can be true, 2+4+6+…+4(k+1) = 2+4+6+⋯+(4k+4) and by the subsequent steps, we can prove that (m+1)2+3 also holds for m=k. So, it is proved.
5. For every natural number k, which of the following is true?
a) (mn)k = mknk
b) m*k = n + 1
c) (m+n)k = k + 1
d) mkn = mnk
View Answer
Answer: a
Explanation: In the first step, for k = 1, (mn)1 = m1n1 = mn, hence it is true. Let us assume the statement is true for k = l, Now by induction assumption, (mn)1 = m1n1 is true. So, to prove, (mn)l+1 = ml + 1nl+1, we have (mn)l = mlnl and multiplying both sides by (mn) ⇒ (mn)1(mn)=(m1n1)(mn)
⇒ (mn)l+1 = (mm1)(nn1) ⇒ (mn)l+1 = (ml+1nl+1). Hence, it is proved. So, (mn)k = mknk is true for every natural number k.
6. By induction hypothesis, the series 12 + 22 + 32 + … + p2 can be proved equivalent to ____________
a) \(\frac{p^2+2}{7}\)
b) \(\frac{p*(p + 1)*(2p + 1)}{6}\)
c) \(\frac{p*(p+1)}{4}\)
d) p+p2
View Answer
Answer: b
Explanation: By principle of mathematical induction, we now assume that p (b) is true 12 + 22 + 32 + … + b2 = \(\frac{b (b + 1) (2b + 1)}{6}\)
so to prove P(b+1): 12 + 22 + 32 + … + b2 + (b + 1)2 = \(\frac{b (b + 1) (2b + 1)}{6}\) + (b + 1)2
By induction assumption it is shown that 12 + 22 + 32 + … + b2 + (b + 1)2 = \(\frac{(b + 1) [(b + 2) (2b + 3)]}{6}\). Hence it is proved that 12 + 22 + 32 + … + p2 = \(\frac{p*(p + 1)*(2p + 1)}{6}\).
7. For any positive integer m ______ is divisible by 4.
a) 5m2 + 2
b) 3m + 1
c) m2 + 3
d) m3 + 3m
View Answer
Answer: d
Explanation: The required answer is, m3 + 3m. Now, by induction hypothesis, we have to prove for m=k, k3+3k is divisible by 4. So, (k + 1)3 + 3 (k + 1) = k3 + 3 k2 + 6 k + 4
= [k3 + 3 k] + [3 k2 + 3 k + 4] = 4M + (12k2 + 12k) – (8k2 + 8k – 4), both the terms are divisible by 4. Hence (k + 1)3 + 3 (k + 1) is also divisible by 4 and hence it is proved for any integer m.
8. According to principle of mathematical induction, if P(k+1) = m(k+1) + 5 is true then _____ must be true.
a) P(k) = 3m(k)
b) P(k) = m(k) + 5
c) P(k) = m(k+2) + 5
d) P(k) = m(k)
View Answer
Answer: b
Explanation: By the principle of mathematical induction, if a statement is true for any number m = k, then for its successor m = k + 1, the statement also satisfies, provided the statement is true for m = 1. So, the required answer is p(k) = mk + 5.
9. Which of the following is the base case for 4n+1 > (n+1)2 where n = 2?
a) 64 > 9
b) 16 > 2
c) 27 < 91
d) 54 > 8
View Answer
Answer: a
Explanation: Statement By principle of mathematical induction, for n=2 the base case of the inequation 4n+1 > (n+1)2 should be 64 > 9 and it is true.
10. What is the induction hypothesis assumption for the inequality m ! > 2m where m>=4?
a) for m=k, k+1!>2k holds
b) for m=k, k!>2k holds
c) for m=k, k!>3k holds
d) for m=k, k!>2k+1 holds
View Answer
Answer: b
Explanation: By the induction hypothesis, assume that p (k) = k! > 2k is true, for m=k and we need to prove this by the principle of mathematical induction.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Recursion”.
1. Which of the following is contained in a recursive grammar?
a) semantic rules
b) production rules
c) recursive language
d) recursive function
View Answer
Answer: b
Explanation: In natural language semantics, recursive grammar plays a vital role as well as in syntax. A recursive grammar in a context free language is a formal grammar which consists of recursive production rules.
2. ________ is the consequence of dynamic programming.
a) Bellman equation
b) Frobenius equation
c) Linear equation
d) Boolean expression
View Answer
Answer: a
Explanation: Dynamic programming can lead to recursive optimization that can restate a multistep optimization problem in its recursive form. The Bellman equation that writes the value of the optimization problem at an earlier time in terms of its value at a later time is the result of dynamic programming.
3. How many types of self-referential recursive data are there in computer programs?
a) 6
b) 2
c) 10
d) 4
View Answer
Answer: b
Explanation: There are two types of self-referential definitions and these are inductive and coinductive definitions. An inductively defined recursive data definition must have to specify how to construct instances of the data. For example, linked lists are defined as an inductively recursive data definition.
4. _______ recursion consists of multiple self-references.
a) binary recursion
b) single recursion
c) multiple recursion
d) coinductive recursion
View Answer
Answer: c
Explanation: A recursion which consists of multiple self-references and requires exponential time and space is called multiple recursion. Multiple recursions include tree traversal of a graph, such as in a depth-first search. However, single recursion is more efficient than multiple recursion.
5. The argument of each recursive call is the content of a field of the original output. This definite characteristic belongs to which of the following function?
a) Structurally recursive function
b) Generativity recursive function
c) General function
d) Indirect recursive function
View Answer
Answer: a
Explanation: A structurally recursive function has a characteristic that the argument to each recursive call is the content of a field of the original input. This recursion function includes mostly all tree traversals which includes binary tree creation and search, XML processing etc.
6. The mutual recursion is also termed as ______
a) indirect recursion
b) constructive recursion
c) generative recursion
d) definitive recursion
View Answer
Answer: a
Explanation: When a function is not called by itself but by another function which it has called either directly or indirectly is termed as Indirect recursion. Mutual recursion is a more symmetric term of Indirect recursion.
7. In which of the following problems recurrence relation holds?
a) Optimal substructure
b) Tower of Hanoi
c) Hallmark substitution
d) Longest common subsequence
View Answer
Answer: b
Explanation: We can have recurrence relation for tower of hanoi and that is hn = 2 hn-1 + 1h1 = 1, for n number of disks in one peg.
8. Which of the following functions generates new data at each step of a method?
a) corecursive function
b) structural recursive function
c) unirecursive function
d) indirect function
View Answer
Answer: a
Explanation: The generatively recursive functions or corecursive functions is defined as generation of the new data at each step that is successive approximation in Regula Falsi method. In terms of loop variants, there is no such loop variant, and termination depends on error of approximation.
9. Every recursive algorithm must have the problem of ________
a) overhead of repeated function calls
b) collision of different function calls
c) searching for all duplicate elements
d) make only two recursive calls
View Answer
Answer: a
Explanation: Due to the overhead of repeated function calls and returns, recursive algorithms may be inefficient for small data. Any recursion can be replaced by iteration with an explicit call stack whereas iteration can be replaced with tail recursion.
10. If the height of a binary tree is 54, how many null pointers are there as children?
a) 1267
b) 358
c) 56
d) 255
View Answer
Answer: d
Explanation: Depth-first search (DFS) algorithm of a binary tree, is a trivial example of short-circuiting. We can have a standard recursive algorithm in case of DFS. Now, a perfect binary tree of height h has 2h+1 Null pointers as children.
h = 54
254+1
255.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Fundamental Principle of Counting”.
1. How many even 4 digit whole numbers are there?
a) 1358
b) 7250
c) 4500
d) 3600
View Answer
Answer: c
Explanation: The thousands digit cannot be zero, so there are 9 choices. There are 10 possibilities for the hundreds digit and 10 possibilities for the tens digit. The units digit can be 0, 2, 4, 6 or 8, so there are 5 choices. By the basic counting principle, the number of even five digit whole numbers is 9 × 10 × 10 × 5 = 45,00.
2. In a multiple-choice question paper of 15 questions, the answers can be A, B, C or D. The number of different ways of answering the question paper are ________
a) 65536 x 47
b) 194536 x 45
c) 23650 x 49
d) 11287435
View Answer
Answer: a
Explanation: There are 415 = 65536 x 47 different ways of answering the exam paper of 15 MCQs.
3. How many words with seven letters are there that start with a vowel and end with an A? Note that they don’t have to be real words and letters can be repeated.
a) 45087902
b) 64387659
c) 12765800
d) 59406880
View Answer
Answer: d
Explanation: The first letter must be a vowel, so there are 5 choices. The second letter can be any one of 26, the third letter can be any one of 26, the fourth letter can be any one of 26 and fifth and sixth letters can be any of 26 choices. The last letter must be an A, so there is only 1 choice. By the basic counting principle, the number of ‘words’ is 5 × 26 × 26 × 26 × 26 × 26 × 1 = 59406880.
4. Neela has twelve different skirts, ten different tops, eight different pairs of shoes, three different necklaces and five different bracelets. In how many ways can Neela dress up?
a) 50057
b) 14400
c) 34870
d) 56732
View Answer
Answer: b
Explanation: By the basic counting principle, the number of different ways = 12 × 10 × 8 × 3 × 5 = 14400. Note that shoes come in pairs. So she must choose one pair of shoes from ten pairs, not one shoe from twenty.
5. How many five-digit numbers can be made from the digits 1 to 7 if repetition is allowed?
a) 16807
b) 54629
c) 23467
d) 32354
View Answer
Answer: a
Explanation: 75 = 16807 ways of making the numbers consisting of five digits if repetition is allowed.
6. For her English literature course, Ruchika has to choose one novel to study from a list of ten, one poem from a list of fifteen and one short story from a list of seven. How many different choices does Rachel have?
a) 34900
b) 26500
c) 12000
d) 10500
View Answer
Answer: d
Explanation: By the Basic Counting Principle, the number of different choices is 10 × 15 × 7 = 10500.
7. There are two different Geography books, five different Natural Sciences books, three different History books and four different Mathematics books on a shelf. In how many different ways can they be arranged if all the books of the same subjects stand together?
a) 353450
b) 638364
c) 829440
d) 768700
View Answer
Answer: c
Explanation: There are four groups of books which can be arranged in 4! different ways. Among those books, two are Geography books, five are Natural Sciences books, three are History books and four are Mathematics books. Therefore, there are 4! × 2! × 5! × 3! × 4! = 829440 ways to arrange the books.
8. The code for a safe is of the form PPPQQQQ where P is any number from 0 to 9 and Q represents the letters of the alphabet. How many codes are possible for each of the following cases? Note that the digits and letters of the alphabet can be repeated.
a) 874261140
b) 537856330
c) 549872700
d) 456976000
View Answer
Answer: d
Explanation: 103 × 264 = 456976000 possible codes are formed for the safe with the alphanumeric digits.
9. Amit must choose a seven-digit PIN number and each digit can be chosen from 0 to 9. How many different possible PIN numbers can Amit choose?
a) 10000000
b) 9900000
c) 67285000
d) 39654900
View Answer
Answer: a
Explanation: By the basic counting principle, the total number of PIN numbers Amit can choose is 10 × 10 × 10 × 10 × 10 × 10 × 10 = 10,000000.
10.  In how many ways can they are chosen?
a) 98072
b) 27384
c) 36428
d) 44389
View Answer
Answer: b
Explanation: There are 16 × 15 × 14 + 14 × 13 × 12 × 11 = 27384 ways to choose from a student council.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Counting – Division of Objects”.
1. For a gaming competition, 8 girls are planning on splitting up into 3 (non-empty) groups. How many ways can they split up into these groups?
a) 465
b) 1056
c) 966
d) 3215
View Answer
Answer: c
Explanation: Using the inclusion-exclusion principle, the total number of ways of splitting the girls into 3 groups is 38 + 3.(28) + 3.(18). However, since the three groups are identical we need to divide by 3!. Hence, the answer is 966.
2. In a picnic with 20 persons where 6 chocolates will be given to the top 8 children(the chocolates are distinct: first, second). How many ways can this be done?
a) 18C6
b) 20P6
c) 25C4 * 6!
d) 19P5
View Answer
Answer: b
Explanation: This is a permutation problem since the chocolates are distinct. The answer is P(20, 6) -> the number of ways to arrange 20 things taken 6 at a time -> which is \(\frac{20!}{(20-6)!}\) = 20*19*18*17*16*15.
3. How many ways can one choose 20 cookies from 45 different types (assuming there are at least 20 of each type)?
a) 64C21 * 15
b) 64C20
c) 44C20 * 2!
d) 65C22
View Answer
Answer: b
Explanation: Imagine the 20 cookies one is choosing are indistinguishable dots. The 45 different types of cookies are like 45 distinguishable boxes and so the answer is C(45 + 20-1, 20) = 64C20.
4. Assume that it is an afternoon. What is the time on the 24 hour clock after 146 hours?
a) 12:10 pm
b) 8:30 am
c) 3 am
d) 2 pm
View Answer
Answer: d
Explanation: Divide 146 with 24. The remainder is the time on the 24 hour clock. So, 146 = 6*24 + 2 and the result is 2pm.
5. There are 28 identical oranges that are to be distributed among 8 distinct girls. How many ways are there to distribute the oranges?
a) 22P7
b) 34C6
c) 35C7
d) 28C8
View Answer
Answer: c
Explanation: By the definition of star and bar problem, there are n+r-1Cr-1 possible distributions of n identical objects among r distinct bins. Now, there are n = 28 identical objects and r = 8 distinct bins. Using the formula above, there are 35C7 ways to distribute the oranges.
6. There are 5 distinct fruits. How many ways can they be planted into identical fruit plants?
a) 87
b) 52
c) 76
d) 128
View Answer
Answer: b
Explanation: These fruits can be placed into 1, 2, 3, 4 or 5 fruit plants. The number of distributions of fruits into fruit plants will thus be the sum of Stirling numbers of the second kind: S(5,1) + S(5,2) + S(5,3) + S(5,4) + S(5,5) = 1 + 15 + 25 + 10 + 1 = 52.
7. A woman has 14 identical pens to distribute among a group of 10 distinct students. How many ways are there to distribute the 14 pens such that each student gets at least one pencil?
a) 15C10
b) 10C5 * 11
c) 15C8 * 4!
d) 13C9
View Answer
Answer: d
Explanation: For this type of problem, n>=r must be true and so according to stars and bars model, the number of possible arrangements of stars and bars is n-1Cr-1 or equivalently, there are n-1Cr-1 distributions of n identical objects into r distinct non-empty bins. In this example, there are n = 14 identical objects to be distributed among r=10 distinct bins. Using the above formula, the number of possible distributions is 13C9.
8. Suppose that M is the product of k distinct primes. Find the number of ways to write N as the product of positive integers(>1), where the order of terms does not matter.
a) MCN-k
b) NCM
c) N * Bk
d) Bk
View Answer
Answer: d
Explanation: To solve the problem first find the prime factorization of each term of the product, and place the factors of each term into a box. Then, since N is the product of distinct prime factors, each prime factor appears in a unique box. Since the product of all of these terms is N, each prime factor must be in a box. Conversely, for any arrangement of these n distinct primes into r identical boxes, multiply the primes in a box to create a term and the product of these terms results in N. This establishes the bijection and the number of ways is Bk which is Bell number.
9. How many ways are there to place 7 differently colored toys into 5 identical urns if the urns can be empty?
a) 320
b) 438
c) 1287
d) 855
View Answer
Answer: d
Explanation: The problem can be described as distinct objects into any number of identical bins and this number can be found with B7 = ∑S(7,k), where S(7,k) is the number of distributions of 5 distinct objects into k identical non-empty bins, so that S(7,1) = 1, S(7,2) = 63, S(7,3) = 301, S(7,4) = 350 and S(7,5) = 140. These values can be found using the recurrence relation identity for Stirling numbers of the second kind. Thus, B7 = 1 + 63 + 301 + 350 + 140 = 855.
10. Suppose, there are 7 of your friends who want to eat pizza (8 distinct people in total). You order a 16-cut pizza (16 identical slices). How many distributions of pizza slices are there if each person gets at least one slice of pizza?
a) 346
b) 6435
c) 3214
d) 765
View Answer
Answer: b
Explanation: This problem can be viewed as identical objects distributed into distinct non-empty bins. Using the formula for these kind of distributions n-1Cr-1 = 15C7 = 6435. Thus, there are distributions of the pizza slices.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Addition Theorem on Probability”.
1. Neha has 4 yellow t-shirts, 6 black t-shirts, and 2 blue t-shirts to choose from for her outfit today. She chooses a t-shirt randomly with each t-shirt equally likely to be chosen. Find the probability that a black or blue t-shirt is chosen for the outfit.
a) \(\frac{8}{13}\)
b) \(\frac{5}{6}\)
c) \(\frac{1}{2}\)
d) \(\frac{7}{12}\)
View Answer
Answer: c
Explanation: Define the events A and B as follows: A=Neha chooses a black t-shirt. B= Neha chooses a blue skirt. Neha cannot choose both a black t-shirt and a blue t-shirt, so the addition theorem of probability applies:
P(A U B) = P(A) + P(B) = \((\frac{6}{12}) + (\frac{2}{12}) = \frac{3}{6} = \frac{1}{2}\).
2. If a fair 15-sided dice is rolled, then is the probability that the roll is an odd number or prime number or both?
a) \(\frac{3}{20}\)
b) \(\frac{4}{19}\)
c) \(\frac{9}{20}\)
d) \(\frac{17}{20}\)
View Answer
Answer: c
Explanation: There are 7 even numbers on the 20-sided dice: 1, 3, 5, 7, 9, 13, 15. There are 6 prime numbers on the 20-sided dice: 2, 3, 5, 7, 11, 13. There are 4 numbers that are both odd and prime: 3, 5, 7, 13. By the rule of sum, the probability that an odd or prime number is rolled is \((\frac{7}{20}) + (\frac{6}{20}) – (\frac{4}{20}) = \frac{9}{20}\).
3. There are a total of 50 distinct books on a shelf such as 20 math books, 16 physics books, and 14 chemistry books. Find is the probability of getting a book that is not a chemistry book or not a physics book.
a) \(\frac{4}{17}\)
b) \(\frac{43}{50}\)
c) \(\frac{12}{31}\)
d) 1
View Answer
Answer: d
Explanation: The probability of not getting chemistry book = 1 – (probability of chemistry book)
= 1 – \(\frac{14}{30} = \frac{16}{30}\) and the probability of not getting chemistry book = 1 – (probability of physics book) = 1 – \(\frac{16}{30} = \frac{14}{30}\). So, the required probability is = \(\frac{16}{30} + \frac{14}{30}\) = 1.
4. A number is selected from the first 20 natural numbers. Find the probability that it would be divisible by 3 or 7?
a) \(\frac{19}{46}\)
b) \(\frac{24}{67}\)
c) \(\frac{12}{37}\)
d) \(\frac{7}{20}\)
View Answer
Answer: d
Explanation: Let X be the event that the number selected would be divisible by 3 and Y be the event that the selected number would be divisible by 7. Then A u B denotes the event that the number would be divisible by 3 or 7. Now, X = {3, 9, 12, 15, 18} and Y = {7, 14} whereas S = {1, 2, 3, …,20}. Since A n B = Null set, so that the two events A and B are mutually exclusive and as such we have,
P(A u B) = P(A) + P(B) ⇒ P(A u B) = \(\frac{5}{20} + \frac{2}{20}\)
Therefore, P(A u B) = \(\frac{7}{20}\).
5. There are 24 red marbles in a bag 68 marbles, and 8 of those marbles are both red and white striped. 27 marbles are white striped and of those marbles, the same 8 marbles would be both red and white striped). Find the probability of drawing out a marble from the bag that is either red or white striped.
a) \(\frac{12}{35}\)
b) \(\frac{43}{68}\)
c) \(\frac{26}{68}\)
d) \(\frac{32}{55}\)
View Answer
Answer: b
Explanation: The “or” indicates finding the probability of a union of events. Let R be the event that a red marble is drawn and W be the event that a striped marble is drawn.  By the rule of sum of probability,
P(R U W) = P(R) + P(W) – p(R ⋂ W) = \(\frac{24}{68} + \frac{27}{68} – \frac{8}{68} = \frac{43}{68}\).
Hence, the probability of drawing a red or white striped marble is \(\frac{43}{68}\).
6. If spinner has 3 equal sectors colored yellow, blue and red, then the probability of landing on red or yellow after spinning this spinner is _______
a) \(\frac{2}{3}\)
b) \(\frac{4}{7}\)
c) \(\frac{6}{17}\)
d) \(\frac{23}{47}\)
View Answer
Answer: a
Explanation: We can have, P(red) = \(\frac{1}{3}\), P(yellow) = \(\frac{1}{3}\), P(red or yellow) = P(red) + P(yellow) = \(\frac{1}{3} + \frac{1}{3} = \frac{2}{3}\).
7. In a secondary examination, 75% of the students have passed in History and 65% in Mathematics, while 50% passed in both History and Mathematics. If 35 candidates failed in both the subjects, what is the total number of candidates sit for that exam?
a) 658
b) 398
c) 764
d) 350
View Answer
Answer: d
Explanation: 50% passed in both the subjects, (75-50)% or 25% passed only in History and (65-50)% or 15% passed only in Mathematics, (50 + 25 + 15)% or 90% passed in both the subjects and 10% failed in both subjects. From the question, 10% of total candidates = 35. So, total candidates = 350.
8. In a Press Conference, there are 450 foreign journalists. 275 people can speak German, 250 people can speak English, 200 people can speak Chinese and 260 people can speak Japanese. Find the maximum number of foreigners who cannot speak at least one language.
a) 401
b) 129
c) 324
d) 415
View Answer
Answer: d
Explanation: The total number of journalists = 350.People who speak German = 275 -> people who do not speak German = 75, people who speak English = 250-> people who do not speak English = 100,people who speak Chinese = 200 -> people who do not speak Chinese = 150, people who speak Japanese = 260 -> people who do not speak Japanese = 90. The total number of people who do not know at least one language will be maximum when the sets of people not knowing a particular language are mutually exclusive. Hence, the maximum number of people who do not know at least one language = 75 + 100 + 150 + 90 = 415.
9. There is a class of 40 students out of which 16 are girls. There are 27 students who are right-handed. How many minimum numbers of girls who are left-handed in this class?
a) 17
b) 56
c) 23
d) 3
View Answer
Answer: d
Explanation: Number of girls in the class is 16. Number of left-handed pupils + Number of right-handed pupils = 40. So, Number of left-handed pupils + 27 = 40, Number of left-handed pupils = 13. Therefore, the minimum number of right-handed girls is 16 – 13 = 3.
10. How many positive integers less than or equal to 100 are divisible by 2, 4 or 5?
a) 12.3
b) 87.2
c) 45.3
d) 78.2
View Answer
Answer: d
Explanation: To count the number of integers = \(\frac{100}{2} + \frac{100}{4} + \frac{100}{5} – \frac{100}{8} – \frac{100}{20} + \frac{100}{100}\)
= 50 + 25 + 20 – 12.8 – 5 + 1 = 78.2.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Discrete Probability – Bayes Theorem”.
1. A single card is drawn from a standard deck of playing cards. What is the probability that the card is a face card provided that a queen is drawn from the deck of cards?
a) \(\frac{3}{13}\)
b) \(\frac{1}{3}\)
c) \(\frac{4}{13}\)
d) \(\frac{1}{52}\)
View Answer
Answer: b
Explanation: The probability that the card drawn is a queen = \(\frac{4}{52}\), since there are 4 queens in a standard deck of 52 cards. If the event is “this card is a queen” the prior probability P(queen) = \(\frac{4}{52} = \frac{1}{13}\). The posterior probability P(queen|face) can be calculated using Bayes theorem: P(king|face) = P(face|king)/P(face)*P(king).  The probability of a face card is P(face) = (\(\frac{3}{13}\)). [since there are 3 face cards in each suit (Jack, Queen, King)]. Using Bayes theorem gives P(queen|face) = \(\frac{13}{3}*\frac{1}{13} = \frac{1}{3}\).
2. Naina receives emails that consists of 18% spam of those emails.  If a mail marked spam by her spam filter, determine the probability that it is really spam.
a) 50%
b) 84%
c) 39%
d) 63%
View Answer
Answer: a
Explanation: 18% email are spam and 82% email are not spam. Now, 18% of mail marked as spam is spam and 82% mail marked as spam are not spam. By Bayes theorem the probability that a mail marked spam is really a spam = (Probability of being spam and being detected as spam)/(Probability of being detected as spam) = (0.18 * 0.82)/(0.18 * 0.82) + (0.18 * 0.82) = 0.5 or 50%.
3. A meeting has 12 employees. Given that 8 of the employees is a woman, find the probability that all the employees are women?
a) \(\frac{11}{23}\)
b) \(\frac{12}{35}\)
c) \(\frac{2}{9}\)
d) \(\frac{1}{8}\)
View Answer
Answer: c
Explanation: Assume that the probability of an employee being a man or woman is (\(\frac{1}{2}\)). By using Bayes’ theorem: let B be the event that the meeting has 3 employees who is a woman and let A be the event that all employees are women. We want to find P(A|B) = \(\frac{P(B|A)*P(A)}{P(B)}\). P(B|A) = 1, P(A) = \(\frac{1}{12}\) and P(B) = \(\frac{8}{12}\). So, P(A|B) = \(\frac{1*\frac{1}{12}}{\frac{8}{12}} = \frac{1}{8}\).
4. A cupboard A has 4 red carpets and 4 blue carpets and a cupboard B has 3 red carpets and 5 blue carpets. A carpet is selected from a cupboard and the carpet is chosen from the selected cupboard such that each carpet in the cupboard is equally likely to be chosen. Cupboards A and B can be selected in \(\frac{1}{5}\) and \(\frac{3}{5}\) ways respectively. Given that a carpet selected in the above process is a blue carpet, find the probability that it came from the cupboard B.
a) \(\frac{2}{5}\)
b) \(\frac{15}{19}\)
c) \(\frac{31}{73}\)
d) \(\frac{4}{9}\)
View Answer
Answer: b
Explanation: The probability of selecting a blue carpet = \(\frac{1}{5} * \frac{4}{8} + \frac{3}{5} * \frac{5}{8} = \frac{4}{40} + \frac{15}{40} = \frac{19}{40}\). Probability of selecting a blue carpet from cupboard, P(B) = \(\frac{3}{5} * \frac{5}{8} = \frac{15}{40}\). Given that a carpet selected in the above process is a blue carpet, the probability that it came from the cupboard A is = \(\frac{\frac{15}{40}}{\frac{19}{40}} = \frac{15}{19}\).
5. Mangoes numbered 1 through 18 are placed in a bag for delivery. Two mangoes are drawn out of the bag without replacement. Find the probability such that all the mangoes have even numbers on them?
a) 43.7%
b) 34%
c) 6.8%
d) 9.3%
View Answer
Answer: c
Explanation: The events are not independent. There will be a \(\frac{10}{18} = \frac{5}{9}\) chance that any of the mangoes in the bag is even. The probability that the first one is even is \(\frac{1}{2}\), for the second mango, given that the first one was even, there are only 9 even numbered balls that could be drawn from a total of 17 balls, so the probability is \(\frac{9}{17}\). For the third mango, since the first two are both odd, there are 8 even numbered mangoes that could be drawn from a total of 16 remaining balls and so the probability is \(\frac{8}{16}\) and for fourth mango, the probability is = \(\frac{7}{15}\). So the probability that all 4 mangoes are even numbered is \(\frac{10}{18}*\frac{9}{17}*\frac{8}{16}*\frac{7}{16}\) = 0.068 or 6.8%.
6. A family has two children. Given that one of the children is a girl and that she was born on a Monday, what is the probability that both children are girls?
a) \(\frac{13}{27}\)
b) \(\frac{23}{54}\)
c) \(\frac{12}{19}\)
d) \(\frac{43}{58}\)
View Answer
Answer: a
Explanation: We let Y be the event that the family has one child who is a girl born on Tuesday and X be the event that both children are boys, and apply Bayes’ Theorem. Given that there are 7 days of the week and there are 49 possible combinations for the days of the week the two girls were born on and 13 of these have a girl who was born on a Monday, so P(Y|X) = \(\frac{13}{49}\). P(X) remains unchanged at \(\frac{1}{4}\). To calculate P(Y), there are 142 = 196 possible ways to select the gender and the day of the week the child was born on. There are 132 = 169 ways which do not have a girl born on Monday and which 196 – 169 = 27 which do, so P(Y) = \(\frac{27}{196}\). This gives is that P(X|Y) = \(\frac{\frac{13}{19}*\frac{1}{4}}{\frac{27}{196}} = \frac{13}{27}\).
7. Suppose a fair eight-sided die is rolled once. If the value on the die is 1, 3, 5 or 7 the die is rolled a second time. Determine the probability that the sum of values that turn up is at least 8?
a) \(\frac{32}{87}\)
b) \(\frac{12}{43}\)
c) \(\frac{6}{13}\)
d) \(\frac{23}{64}\)
View Answer
Answer: d
Explanation: Sample space consists of 8*8=64 events. While (8) has \(\frac{1}{8}\) probability of occurrence, (1,7) has only \(\frac{1}{64}\) probability. So, the required probability = \(\frac{1}{6} + (9 * \frac{1}{64}) = \frac{69}{192} = \frac{23}{64}\).
8. A jar containing 8 marbles of which 4 red and 4 blue marbles are there. Find the probability of getting a red given the first one was red too.
a) \(\frac{4}{13}\)
b) \(\frac{2}{11}\)
c) \(\frac{3}{7}\)
d) \(\frac{8}{15}\)
View Answer
Answer: c
Explanation: Suppose, P (A) = getting a red marble in the first turn, P (B) = getting a black marble in the second turn. P (A) = \(\frac{4}{8}\) and P (B) = \(\frac{3}{7}\) and P (A and B) = \(\frac{4}{8}*\frac{3}{7} = \frac{3}{14}\) P(B/A) = \(\frac{P(A \,and \,B)}{P(A)} = \frac{\frac{3}{14}}{\frac{1}{2}} = \frac{3}{7}\).
9.  Find the probability such that both are of the same color.
a) \(\frac{10}{28}\)
b) \(\frac{1}{5}\)
c) \(\frac{1}{10}\)
d) \(\frac{4}{7}\)
View Answer
Answer: b
Explanation: Total no of balls = 10. Number of ways drawing 3 balls at random out of 10 = 10C3 = 120. Probability of drawing 3 balls of same colour = 4C3 + 6C3 = 24. Hence, the required probability is \(\frac{24}{120} = \frac{1}{5}\).
10. A bucket contains 6 blue, 8 red and 9 black pens. If six pens are drawn one by one without replacement, find the probability of getting all black pens?
a) \(\frac{8}{213}\)
b) \(\frac{8}{4807}\)
c) \(\frac{5}{1204}\)
d) \(\frac{7}{4328}\)
View Answer
Answer: b
Explanation: Total number of pens = 23, number of pens we have chosen = 6, total number of black pens = 9. According to the combination probability formula it states that nCr = \(\frac{n!}{r! (n-r)!}\),
where n = total number of outcomes, r = random selection, P = \(\frac{^9C_6}{^{23}C_6} = \frac{8}{4807}\).
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Number of Relations”.
1. How many binary relations are there on a set S with 9 distinct elements?
a) 290
b) 2100
c) 281
d) 260
View Answer
Answer: c
Explanation: S is the set with 9 elements. A relation on S is defined as S x S. There are 92 number of ordered pairs in relation. So, the number of binary relations is 2(9*9) = 281.
2. _________ number of reflexive relations are there on a set of 11 distinct elements.
a) 2110
b) 3121
c) 290
d) 2132
View Answer
Answer: a
Explanation: Let A be a set consists of n distinct elements. There are 2(n*n)-n number of reflexive relations that can be formed. So, here the answer is 2(11*11)-11 = 2110.
3. The number of reflexive as well as symmetric relations on a set with 14 distinct elements is __________
a) 4120
b) 270
c) 3201
d) 291
View Answer
Answer: d
Explanation: Let A be a set consists of n distinct elements. There are 2(n*(n-1))/2 number of reflexive and symmetric relations that can be formed. So, here the answer is 214*(14-1)/2 = 291.
4. The number of symmetric relations on a set with 15 distinct elements is ______
a) 2196
b) 250
c) 2320
d) 278
View Answer
Answer: a
Explanation: Let S be a set consists of n distinct elements. There are 2(n-1)*(n-1) number of reflexive and symmetric relations that can be formed. So, here the answer is 2(15-1)*(15-1) = 2196.
5. Suppose S is a finite set with 7 elements. How many elements are there in the largest equivalence relation on S?
a) 56
b) 78
c) 49
d) 100
View Answer
Answer: c
Explanation: Let R is an equivalence relation on the set S and so it satisfies the reflexive, symmetric and transitive property. The largest equivalence relation means it should contain the largest number of ordered pairs. Since we can have n2 ordered pairs in R x R where n belongs to S and all these ordered pairs are present in this relation; its the largest equivalence relation.So there are n2 elements i.e 72 = 49 elements in the largest equivalence relation.
6. ________ is the rank of the largest equivalence relation on a set of 20 elements.
a) 320
b) 2400
c) 20
d) 1
View Answer
Answer: d
Explanation: The rank of an equivalence relation is the number of an equivalence classes. If we have a1, a2, a3, …, an elements then a1 and a2 will be in the same equivalence class because everything is related and so on. In this case, there is only one equivalence class.
7. How many elements are there in the smallest equivalence relation on a set with 8 elements?
a) 102
b) 8
c) 48
d) 32
View Answer
Answer: b
Explanation: Let R is an equivalence relation on the set S with n elements and so it satisfies reflexive, symmetric and transitive properties. The smallest equivalence relation means it should contain minimum number of ordered pairs i.e along with symmetric and transitive properties it must always satisfy reflexive property. So, the smallest equivalence relation will have n ordered pairs and so the answer is 8.
8. The rank of smallest equivalence relation on a set with 12 distinct elements is _______
a) 12
b) 144
c) 136
d) 79
View Answer
Answer: a
Explanation: In the case of smallest equivalence relation, each element is in one equivalence class like {a1}, {a2}, … are equivalence classes. So, the rank or number of equivalence classes is n for a set with n elements and so the answer is 12.
9. If a set A has 8 elements and a set B has 10 elements, how many relations are there from A to B?
a) 290
b) 380
c) 164
d) 280
View Answer
Answer: d
Explanation: Let, a relation R from A to B is a subset of A×B. As the maximum number of subsets (Elements in the powerset) is 2mn, there are 2mn number of relations from A to B and so the answer is 280.
10. Synonym for binary relation is _______
a) equivalence relation
b) dyadic relation
c) orthogonal relation
d) one to many relations
View Answer
Answer: b
Explanation: A binary relation on a set S is a set of ordered pairs of elements of S. It is a subset of the cartesian product S2 = S x S. The terms correspondence, dyadic relation and 2-place relation are synonyms for the binary relation.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Relations – Partial Orderings”.
1. Let a set S = {2, 4, 8, 16, 32} and <= be the partial order defined by S <= R if a divides b. Number of edges in the Hasse diagram of is ______
a) 6
b) 5
c) 9
d) 4
View Answer
Answer: b
Explanation: Hasse Diagram is:
32
/
16
/
8
/ \
2 4
So, the number of edges should be: 4.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Graphs – Diagraph”.
1. A directed graph or digraph can have directed cycle in which ______
a) starting node and ending node are different
b) starting node and ending node are same
c) minimum four vertices can be there
d) ending node does not exist
View Answer
Answer: b
Explanation: If the start node and end node are same in the path of a graph then it is termed as directed cycle i.e, c0 = cn. For instance, a c b a is a simple cycle in which start and end nodes are same(a). But, a c b b a is not a simple cycle as there is a loop <b,b>.
2. Let, D = <A, R> be a directed graph or digraph,then D’ = <A’, R’> is a subgraph if ___________
a) A’ ⊂ A and R’ = R ∩ (A’ x A’)
b) A’ ⊂ A and R ⊂ R’ ∩ (A’ x A’)
c) R’ = R ∩ (A’ x A’)
d) A’ ⊆ A and R ⊆ R’ ∩ (A’ x A’)
View Answer
Answer: a
Explanation: A directed graph or digraph is an ordered pair D<A, R> where A(is a set of nodes of D) is a set and R(the elements of R are the arcs of D) is a binary relation on A. The relation R is called the incidence relation on D. Now, a digraph is a subgraph of D if i)A’ ⊂ A and ii)R’ = R ∩ (A’ x A’). If D’ D, D’ is a proper subgraph of D.
3. The graph representing universal relation is called _______
a) complete digraph
b) partial digraph
c) empty graph
d) partial subgraph
View Answer
Answer: a
Explanation: Consider, A is a graph with vertices {a, b, c, d} and the universal relation is A x A. The graph representing universal relation is called a complete graph and all ordered pairs are present there.
4. What is a complete digraph?
a) connection of nodes without containing any cycle
b) connecting nodes to make at least three complete cycles
c) start node and end node in a graph are same having a cycle
d) connection of every node with every other node including itself in a digraph
View Answer
Answer: d
Explanation: Every node should be connected to every other node including itself in a digraph is the complete digraph. Now, graphs are connected, strongly connected and disconnected
5. Disconnected components can be created in case of ___________
a) undirected graphs
b) partial subgraphs
c) disconnected graphs
d) complete graphs
View Answer
Answer: c
Explanation: By the deletion of one edge from either connected or strongly connected graphs the graph obtained is termed as a disconnected graph. It can have connected components separated by the deletion of the edges. The edge that has to be deleted called cut edge.
6. A simple graph can have _______
a) multiple edges
b) self loops
c) parallel edges
d) no multiple edges, self-loops and parallel edges
View Answer
Answer: d
Explanation: If a graph say G = <V, E> has no parallel or multiple edges and no self loops contained in it is called a simple graph. An undirected graph may have multiple edges and self-loops.
7. Degree of a graph with 12 vertices is _______
a) 25
b) 56
c) 24
d) 212
View Answer
Answer: c
Explanation: Number of edges incident on a graph is known as degree of a vertex. Sum of degrees of each vertex is called total degree of the graph. Total degree = 2 * number of vertices. So, if there are 24 vertices then total degree is 24.
8. In a finite graph the number of vertices of odd degree is always ______
a) even
b) odd
c) even or odd
d) infinite
View Answer
Answer: a
Explanation: In any finite graph, sum of degree of all the vertices = 2 * number of edges.
Sum of degree of all the vertices with even degree + sum of degree of all the vertices with odd degree = 2 * number of edges. Now, even number + sum of degree of all the vertices with odd degree = even number. It is possible if and only if number of odd degree vertices are even.
9. An undirected graph has 8 vertices labelled 1, 2, …,8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?
a) 15
b) 8
c) 5
d) 23
View Answer
Answer: b
Explanation: Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. By definition, sum of degree= 2 * No of edges
Let x = degree of vertex 8
8 + 7 + 8 + 7 + 8 + 7 + 8 + x = 2 * 31
53 + x = 61
x = 8
Hence, degree of vertex 8 is 8.
10. G is an undirected graph with n vertices and 26 edges such that each vertex of G has a degree at least 4. Then the maximum possible value of n is ___________
a) 7
b) 43
c) 13
d) 10
View Answer
Answer: c
Explanation: Let m be min degree and M be a max degree of a graph, then m ≤ 2E/V ≤ M. Here, m=4, E=26, v=?
So, 4 ≤ (2*26)/V
V ≤ (52/4)
V ≤ 13 ⇒ V = 13.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Tricky Discrete Mathematics Questions and Answers focuses on “Complete and Connected Graphs”.
1. A bridge can not be a part of _______
a) a simple cycle
b) a tree
c) a clique with size ≥ 3 whose every edge is a bridge
d) a graph which contains cycles
View Answer
Answer: a
Explanation: In a connected graph, a bridge is an edge whose removal disconnects the graph. In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle. A clique is any complete subgraph of a graph.
2. Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______
a) subgraph
b) tree
c) hamiltonian cycle
d) grid
View Answer
Answer: b
Explanation: If all the edge weights of an undirected graph are positive, any subset of edges that connects all the vertices and has minimum total weight is termed as a tree. In this case, we need to have a minimum spanning tree need to be exact.
3. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______
a) Complete bipartite graph
b) Hamiltonian cycle
c) Regular graph
d) Euler graph
View Answer
Answer: d
Explanation: In any simple undirected graph, total degree of all vertices is even (since each edge contributes 2 degrees). So number of vertices having odd degrees must be even, otherwise, their sum would have been odd, making total degree also odd. Now single vertex n is connected to all these even number of vertices (which have odd degrees). So, degree of n is also even. Moreover, now degree of all vertices which are connected to v is increased by 1, hence earlier vertices which had odd degree now have even degree. So now, all vertices in the graph have even degree, which is necessary and sufficient condition for euler graph.
4. Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
a) 98
b) 13
c) 6
d) 34
View Answer
Answer: c
Explanation: Edge set consists of edges from i to j using either 1) j = i+1 OR 2) j=3i. The trick to solving this question is to think in a reverse way. Instead of finding a path from 1 to 50, try to find a path from 100 to 1. The edge sequence with the minimum number of edges is 1 – 3 – 9 – 10 – 11 – 33 which consists of 6 edges.
5. What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?
a) 11
b) 14
c) 18
d) 19
View Answer
Answer: c
Explanation: We know that, sum of degree of all the vertices = 2 * number of edges
2*7 + 5*2 + 6*x = 39*2
x=9
Number of vertices = 7 + 2 + 9 = 18.
6. ______ is the maximum number of edges in an acyclic undirected graph with k vertices.
a) k-1
b) k2
c) 2k+3
d) k3+4
View Answer
Answer: a
Explanation: This is possible with spanning trees since, a spanning tree with k nodes has k – 1 edges.
7. The minimum number of edges in a connected cyclic graph on n vertices is _____________
a) n – 1
b) n
c) 2n+3
d) n+1
View Answer
Answer: b
Explanation: For making a cyclic graph, the minimum number of edges have to be equal to the number of vertices. SO, the answer should be n minimum edges.
8. The maximum number of edges in a 8-node undirected graph without self loops is ____________
a) 45
b) 61
c) 28
d) 17
View Answer
Answer: c
Explanation: In a graph of n vertices we can draw an edge from a vertex to n-1 vertex we will do it for n vertices and so total number of edges is n*(n-1). Now each edge is counted twice so the required maximum number of edges is n*(n-1)/2. Hence, 8*(8-1)/2 = 28 edges.
9.  If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____
a) n-1 and n+1
b) v and k
c) k+1 and v-k
d) k-1 and v-1
View Answer
Answer: d
Explanation: If a vertex is removed from the graph, lower bound: number of components decreased by one = k-1 (remove an isolated vertex which was a component) and upper bound: number of components = v-1 (consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other (v-1) vertices isolated making (v-1) components.
10. The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n>=4. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G can be ___________
a) n+2
b) 3n/2
c) n2
d) 2n
View Answer
Answer: b
Explanation: n+1(subsets of size < 2 are all disconnected) (subsets of size >= 2 are all connected)+1(subset of size >= 2 are all connected)=n+2 is the number of connected components in G.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice Tricky questions and answers on all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Properties of Tree”.
1. An undirected graph G which is connected and acyclic is called ____________
a) bipartite graph
b) cyclic graph
c) tree
d) forest
View Answer
Answer: c
Explanation: An undirected graph G which is connected and acyclic is termed as a tree. G contains no cycles and if any edge is added to G a simple cycle is formed.
2. An n-vertex graph has ______ edges.
a) n2
b) n-1
c) n*n
d) n*(n+1)/2
View Answer
Answer: b
Explanation: Suppose G is a connected graph which has no cycles. Every subgraph of G includes at least one vertex with zero or one incident edges. It has n vertices and n-1 edges. Generally, the order-zero graph is not considered to be a tree.
3.
a) A tree having a single internal vertex and n-1 leaves
b) A tree having n vertices arranged in a line
c) A tree which has 0 or more connected subtrees
d) A tree which contains n vertices and n-1 cycles
View Answer
Answer: a
Explanation: A star tree of order n is a tree with as many leaves as possible or in other words a star tree is a tree that consists of a single internal vertex and n-1 leaves. However, an internal vertex is a vertex of degree at least 2.
4.  In other words, a directed tree is a directed graph which would be tree if the directions on the edges were ignored.
5. The tree elements are called __________
a) vertices
b) nodes
c) points
d) edges
View Answer
Answer: b
Explanation: Every tree element is called a node and the lines connecting the elements are called branches. A finite tree structure has a member that has no superior and is called the “root” Or root node. Nodes that have no child are called leaf nodes.
6. In an n-ary tree, each vertex has at most ______ children.
a) n
b) n4
c) n*n
d) n-1
View Answer
Answer: a
Explanation: An n-ary tree is a rooted tree in which each vertex has at most n children. 2-ary trees are termed as binary trees, 3-ary trees are sometimes called ternary trees.
7. A linear graph consists of vertices arranged in a line.
a) false
b) true
c) either true or false
d) cannot determined
View Answer
Answer: b
Explanation: A linear graph also known as a path graph is a graph which consists of k vertices arranged in a line, so that vertices from i and i+1 are connected by an edge for i=0,…, k-1.
8. Two labeled trees are isomorphic if ____________
a) graphs of the two trees are isomorphic
b) the two trees have same label
c) graphs of the two trees are isomorphic and the two trees have the same label
d) graphs of the two trees are cyclic
View Answer
Answer: c
Explanation: The number of labeled trees of k number of vertices is kn-2. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding points of the two trees have the same labels.
9. A graph which consists of disjoint union of trees is called ______
a) bipartite graph
b) forest
c) caterpillar tree
d) labeled tree
View Answer
Answer: b
Explanation: A forest is an undirected acyclic graph in which all the connected components are individual trees. This graph contains a disjoint union of trees.
10. What is a bipartite graph?
a) a graph which contains only one cycle
b) a graph which consists of more than 3 number of vertices
c) a graph which has odd number of vertices and even number of edges
d) a graph which contains no cycles of odd length
View Answer
Answer: d
Explanation: A graph is called a bipartite graph if and only if it contains no cycle of odd length. Every tree is a bipartite graph and a median graph.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Question Paper focuses on “Trees – Interconversion for Prefix Postfix Infix Notations”.
1. Evaluation of expression a/b+c*d-e in postfix notation.
a) ab+cd/*-e
b) ab/cd*+e-
c) abc/+d*-e
d) abcd/+*-e
View Answer
Answer: b
Explanation: The expression=a/b+c*d-e
={(ab/)+(cd*)}-e
={(ab/)(cd*)+}-e
={(ab/)(cd*)+}e-
So the output is: ab/cd*+e-
2. Evaluation of 4*5+3/2-9 in prefix notation.
a) *45-/32+9
b) *+453/-29
c) -+*45/329
d) *+/45932
View Answer
Answer: c
Explanation: The expression=4*5+3/2-9
={(4*5)+(3/2)-9}
={(*45)+(/32)-9}
={+(*45)(/32)}-9
=-{+(*45)(/32)9
So the output is; -+*45/329.
3. What is the output of the following if funct1(7)?
Void main()
{
int n;
long int func;
scanf(“%d”,&n);
func=func1 (n)
printf(“%ld!=%ld”,n,func);
}
long int func1(int n)
{
if(n==0)
{
Return 1;
}
else
{
return(n*func1(n-1));
}
}
a) 128
b) 4320
c) 720
d) 5040
View Answer
Answer: d
Explanation: This is a factorial function of an integer using recursive approach. By running the function on integer 7 we get 5040.
4. Infix to prefix conversion can be done using __________
a) two queues
b) two stacks
c) one stack and two queues
d) one stack
View Answer
Answer: b
Explanation: In the infix expression, the operator appears between the operands and in infix notation if the operator appears before the operands in the expression. For the conversion between them two stacks are used efficiently. The idea is to use one stack for operators and other to store operands.
5. Conversion from prefix to postfix expression can be done _______________
a) using bubble sort
b) using radix sort
c) using two queues
d) in a direct manner
View Answer
Answer: d
Explanation: In a postfix expression, the operators appear after the operands. Conversion from prefix to postfix is done directly which is better than converting the prefix expression in infix and then infix to postfix expression. It gives better efficiency.
6. What is the postfix expression of 9+3*5/(10-4)?
a) 9 3 + * 5 / 10 4 –
b) 9 3 5 + * / 10 4 –
c) 9 3 + 5 * / 10 4 –
d) 9 3 5 * / + 10 – 4
View Answer
Answer: c
Explanation: The expression, 9+3*5/(10-4)
= 9+3*5/(10 4-)
= 9+35/*(10 4-)
= 935/*+(10 4-)
So the output is:9 3 5 / * + 10 4 -.
7. What is the postfix expression of (A+B)-C*(D/E))+F?
a) A B + C D E / * – F +
b) A B C D E + / * F – +
c) A B C + * D E / F + –
d) A B + C – * D E / F +
View Answer
Answer: a
Explanation: The expression is (A+B)-C*(D/E))+F
= (A+B)-C*(DE/)+F
= (A+B)-C*(DE/)F+
= (A+B)-C(DE/)*F+
= (A+B)C(DE/)*-F+
= (AB+)C(DE/)*-F+
So the output is: AB+CDE/*-F+.
8. Convert the following expression into prefix notation.
(g-(f^e/d+c)-ba)
a) ^-/gfed+c-ab
b) -ab/+-ec^dgf
c) -ab-+c/d^efg
d) ab/+-^cde-fg
View Answer
Answer: c
Explanation: Convert it first in postfix notation, we can have
(g-(f^e/d+c)-ba)
= (g-(f^e/dc+)-ba)
= (g-(f^ed/c+)-ba)
= (g-(fe^d/c+)-ba)
= (g-(fe^d/c+)ba-)
= (gfe^d/c+-ba-)
By reversing this expression gives the prefix expression, i.e
-ab-+c/d^efg.
9. What is the postfix expression of the given expression, (2*4-(5+7/3^4)-8)10?
a) 2 4 5 * 7 3 4 ^ / + 8 – – 10
b) 2 4 * ^ 5 7 3 4 / + 8 10 – –
c) 2 4 * 5 7 ^ 3 4 / + – 8 10 –
d) 2 4 * 5 7 3 4 ^ / + – 8 – 10
View Answer
Answer: d
Explanation: By solving we can have,
(2*4-(5+7/3^4)-8)10
= (2*4-(5+7/34^)-8)10
= (2*4-(5+734^/)-8)10
= (2*4-(5734^/+)-8)10
= (2*45734^/+–8)10
= 2*45734^/+-8-10
= 24*5734^/+-8-10
So the output is: 2 4 * 5 7 3 4 ^ / + – 8 – 10.
10. Prefix expression can be evaluated _________
a) from right to left
b) from left to right
c) from the exact middle
d) from second right element
View Answer
Answer: b
Explanation: Expressions are usually evaluated from left to right manner. Prefix expressions follow the normal rule i.e from left to right. Postfix expressions can be evaluated from right to left.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all questions papers on Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Boolean Algebra”.
1. Algebra of logic is termed as ______________
a) Numerical logic
b) Boolean algebra
c) Arithmetic logic
d) Boolean number
View Answer
Answer: c
Explanation: The variables that can have two discrete values False(0) and True(1) and the operations of logical significance are dealt with Boolean algebra.
2. Boolean algebra can be used ____________
a) For designing of the digital computers
b) In building logic symbols
c) Circuit theory
d) Building algebraic functions
View Answer
Answer: a
Explanation: For designing digital computers and building different electronic circuits boolean algebra is accepted widely.
3. What is the definition of Boolean functions?
a) An arithmetic function with k degrees such that f:Y–>Yk
b) A special mathematical function with n degrees such that f:Yn–>Y
c) An algebraic function with n degrees such that f:Xn–>X
d) A polynomial function with k degrees such that f:X2–>Xn
View Answer
Answer: b
Explanation: A Boolean function is a special mathematical function with n degrees and where Y = {0,1} is the Boolean domain with being a non-negative integer. It helps in describing the way in which the Boolean output is derived from Boolean inputs.
4. F(X,Y,Z,M) = X`Y`Z`M`. The degree of the function is ________
a) 2
b) 5
c) 4
d) 1
View Answer
Answer: c
Explanation: This is a function of degree 4 from the set of ordered pairs of Boolean variables to the set {0,1}.
5. A ________ value is represented by a Boolean expression.
a) Positive
b) Recursive
c) Negative
d) Boolean
View Answer
Answer: d
Explanation: A Boolean value is given by a Boolean expression which is formed by combining Boolean variables and logical connectives.
6. Which of the following is a Simplification law?
a) M.(~M+N) = M.N
b) M+(N.O) = (M+N)(M+O)
c) ~(M+N) = ~M.~N
d) M.(N.O) = (M.N).O
View Answer
Answer: a
Explanation: By Simplification Law we can have X.(~X+Y) = X.Y and X+(~X.Y) = X+Y. By, De’ Morgan’s law ~(X+Y) = ~X.~Y. By commutative law we can say that A.(B.C) = (A.B).C.
7. What are the canonical forms of Boolean Expressions?
a) OR and XOR
b) NOR and XNOR
c) MAX and MIN
d) SOM and POM
View Answer
Answer: d
Explanation: There are two kinds of canonical forms for a Boolean expression-> 1)sum of minterms(SOM) form and
2)product of maxterms(SOM) form.
8. Which of the following is/are the universal logic gates?
a) OR and NOR
b) AND
c) NAND and NOR
d) NOT
View Answer
Answer: c
Explanation: NAND and NOR gates are known as the universal logic gates. A universal gate is a gate which can implement any Boolean function without the help of 3 basic gate types.
9. The logic gate that provides high output for same inputs ____________
a) NOT
b) X-NOR
c) AND
d) XOR
View Answer
Answer: b
Explanation: The logic gate which gives high output for the same inputs, otherwise low output is known as X-NOR or Exclusive NOR gate.
10. The ___________ of all the variables in direct or complemented from is a maxterm.
a) addition
b) product
c) moduler
d) subtraction
View Answer
Answer: a
Explanation: The Boolean function is expressed as a sum of the 1-minterms and the inverse of function is represented as 0-minterms.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Boolean Algebra – Interconversion of Gates”.
1. In order to make a luggage security alarm, a single _____ is used.
a) NOR gate
b) NAND gate
c) X-NOR gate
d) XOR gate
View Answer
Answer: b
Explanation: The NAND gate consists of two inputs and if both of them are high the output is low. A luggage security alarm circuit is a system which is based on the NAND gate. It is used to generate an alarm when any authorized person tries to steal the luggage.
2. In Boolean algebra, the data is a bit-representation of information consists of _________
a) 0 and 1
b) 2 and 5
c) 1 and 15
d) 4 and 8
View Answer
Answer: a
Explanation: The data, in boolean algebra must be in a bit-representation form which can be in between two values 0 and 1.
3. Using which component a shift register is implemented?
a) register
b) transistor
c) latch
d) flip-flop
View Answer
Answer: d
Explanation: A shift register, in digital circuitry, is a combination of two or more flip-flops to share the bits of information by using the same clock. A shift register can have both parallel and serial inputs and outputs.
4. How many NAND gates are required to make an XOR gate?
a) 7
b) 12
c) 4
d) 8
View Answer
Answer: c
Explanation: An XOR gate is created by using four NAND gates. This construction gives a propagation delay three times to that of a single NAND gate.
5. In Multiplexer gate, for selecting the inputs, two bits named _____ and _____ are required generally.
a) selector bit, data bit
b) parity bit. Generator bit
c) input bit, inverted bit
d) raising bit, sinking bit
View Answer
Answer: a
Explanation: In multiplexer gate for selecting the inputs say, for 3 input bits, one bit is required as selector bit and two other bits are required as data bits.
6. A NOR gate can be derived from ______
a) NAND gate
b) XOR gate
c) AND gate
d) OR gate
View Answer
Answer: a
Explanation: NAND and NOR gates are called universal gates. As we can generate any of the basic gates as well as other gates from these two gates. So, a NOR gate can be made by a NAND gate.
7. In which logic gate the output state is usually the complement of the input state?
a) NOT gate
b) NOR gate
c) X-NOR gate
d) OR gate
View Answer
Answer: a
Explanation: NOT gate is the simplest digital logic circuit which is also called an inverter because it takes the input in 0 or 1 form and gives the output as the complement of the input.
8. In OR gate for 13 numbers of inputs what are the stages possible for it?
a) 1239
b) 213
c) 13
d) 1387
View Answer
Answer: b
Explanation: OR gate works in a way such that if any of the input is binary low(or 0), the output of the gate is binary 1(or high). Here, the number of stage possible = 2n = 213.
9. Which of the following is built exclusively from NOR gate?
a) Plant guard machine
b) Apollo Guidance Computer
c) Street market app
d) Dish washer
View Answer
Answer: b
Explanation: The first embedded system is the Apollo Guidance Computer which was built exclusively from NOR gates. A logically inverted OR gate is a NOR gate and it can have two or more inputs.
10. Which of the following gates is used to implement a logical conditional?
a) OR gate
b) Magnetic logic gate
c) XOR gate
d) IMPLY gate
View Answer
Answer: d
Explanation: The IMPLY gate is a digital logic gate that is used to implements logical conditional. Two symbols are used to represent the IMPLY gates → the traditional symbol and the IEEE symbol. IMPLY gate can be made by two memristors.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Group Theory”.
1. A non empty set A is termed as an algebraic structure ________
a) with respect to binary operation *
b) with respect to ternary operation ?
c) with respect to binary operation +
d) with respect to unary operation –
View Answer
Answer: a
Explanation: A non empty set A is called an algebraic structure w.r.t binary operation “*” if (a*b) belongs to S for all (a*b) belongs to S. Therefore “*” is closure operation on ‘A’.
2. An algebraic structure _________ is called a semigroup.
a) (P, *)
b) (Q, +, *)
c) (P, +)
d) (+, *)
View Answer
Answer: a
Explanation: An algebraic structure (P,*) is called a semigroup if a*(b*c) = (a*b)*c for all a,b,c belongs to S or the elements follow associative property under “*”. (Matrix,*) and (Set of integers,+) are examples of semigroup.
3. Condition for monoid is __________
a) (a+e)=a
b) (a*e)=(a+e)
c) a=(a*(a+e)
d) (a*e)=(e*a)=a
View Answer
Answer: d
Explanation: A Semigroup (S,*) is defined as a monoid if there exists an element e in S such that (a*e) = (e*a) = a for all a in S. This element is called identity element of S w.r.t *.
4. A monoid is called a group if _______
a) (a*a)=a=(a+c)
b) (a*c)=(a+c)
c) (a+c)=a
d) (a*c)=(c*a)=e
View Answer
Answer: d
Explanation: A monoid(B,*) is called Group if to each element there exists an element c such that (a*c)=(c*a)=e. Here e is called an identity element and c is defined as the inverse of the corresponding element.
5. A group (M,*) is said to be abelian if ___________
a) (x+y)=(y+x)
b) (x*y)=(y*x)
c) (x+y)=x
d) (y*x)=(x+y)
View Answer
Answer: b
Explanation: A group (M,*) is said to be abelian if (x*y) = (x*y) for all x, y belongs to M. Thus Commutative property should hold in a group.
6. Matrix multiplication is a/an _________ property.
a) Commutative
b) Associative
c) Additive
d) Disjunctive
View Answer
Answer: b
Explanation: The set of two M*M non-singular matrices form a group under matrix multiplication operation. Since matrix multiplication is itself associative, it holds associative property.
7. A cyclic group can be generated by a/an ________ element.
a) singular
b) non-singular
c) inverse
d) multiplicative
View Answer
Answer: a
Explanation: A singular element can generate a cyclic group. Every element of a cyclic group is a power of some specific element which is known as a generator ‘g’.
8. How many properties can be held by a group?
a) 2
b) 3
c) 5
d) 4
View Answer
Answer: c
Explanation: A group holds five properties simultaneously –
i) Closure
ii) associative
iii) Commutative
iv) Identity element
v) Inverse element.
9. A cyclic group is always _________
a) abelian group
b) monoid
c) semigroup
d) subgroup
View Answer
Answer: a
Explanation: A cyclic group is always an abelian group but every abelian group is not a cyclic group. For instance, the rational numbers under addition is an abelian group but is not a cyclic one.
10. {1, i, -i, -1} is __________
a) semigroup
b) subgroup
c) cyclic group
d) abelian group
View Answer
Answer: c
Explanation: The set of complex numbers {1, i, -i, -1} under multiplication operation is a cyclic group. Two generators i and -i will covers all the elements of this group. Hence, it is a cyclic group.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Groups – Cosets”.
1. a * H is a set of _____ coset.
a) right
b) left
c) sub
d) semi
View Answer
Answer: b
Explanation: Let (H, *) be the semigroup of the group (G, *). Let a belongs to G. (a * H) is the set of a left coset of H in G and (H * a) be the set of a right coset of H in G.
2. a * H = H * a relation holds if __________
a) H is semigroup of an abelian group
b) H is monoid of a group
c) H is a cyclic group
d) H is subgroup of an abelian group
View Answer
Answer: d
Explanation: If h is the subgroup of an abelian group G, then the set of left cosets of H in G is to be set of right cosets i.e, a * H = H * a. Hence, subgroup is called the normal subgroup.
3. Lagrange’s theorem specifies __________
a) the order of semigroup is finite
b) the order of the subgroup divides the order of the finite group
c) the order of an abelian group is infinite
d) the order of the semigroup is added to the order of the group
View Answer
Answer: b
Explanation: Lagrange’s theorem satisfies that the order of the subgroup divides the order of the finite group.
4. A function is defined by f(x)=2x and f(x + y) = f(x) + f(y) is called _____________
a) isomorphic
b) homomorphic
c) cyclic group
d) heteromorphic
View Answer
Answer: a
Explanation: Let (G,*) and (G’,+) are two groups. The mapping f:G->G’ is said to be isomorphism if two conditions are satisfied 1) f is one-to-one function and onto function and 2) f satisfies homomorphism.
5. An isomorphism of a group onto itself is called ____________
a) homomorphism
b) heteromorphism
c) epimorphism
d) automorphism
View Answer
Answer: d
Explanation: An automorphism is defined as an isomorphism of a group onto itself. Similarly, the homomorphism of a group onto itself is defined as the endomorphism of the group.
6. The elements of a vector space form a/an ____________ under vector addition.
a) abelian group
b) commutative group
c) associative group
d) semigroup
View Answer
Answer: a
Explanation: An example of a coset is associated with the theory of vector spaces. The elements (vectors) form an abelian group under the vector addition in a vector space. Subspaces of a vector space are subgroups of this group.
7. A set of representatives of all the cosets is called _________
a) transitive
b) reversal
c) equivalent
d) transversal
View Answer
Answer: d
Explanation: A coset representative is a representative in the equivalence class. In all cosets, a set of the representative is always transversal.
8. Which of the following statement is true?
a) The set of all rational negative numbers forms a group under multiplication
b) The set of all matrices forms a group under multiplication
c) The set of all non-singular matrices forms a group under multiplication
d) The set of matrices forms a subgroup under multiplication
View Answer
Answer: c
Explanation: Since multiplication of two negative rational numbers gives a positive number. Hence, closure property is not satisfied. Singular matrices do not form a group under multiplication. Matrices have to be non-singular (determinant !=0) for the inverse to exist. Hence the set of all non-singular matrices forms a group under multiplication is a true option.
9. How many different non-isomorphic Abelian groups of order 8 are there?
a) 5
b) 4
c) 2
d) 3
View Answer
Answer: c
Explanation: The number of Abelian groups of order Pm (let, P is prime) is the number of partitions of m. Here order is 8 i.e. 23 and so partition of 3 are {1, 1} and {3, 0}. So number of different abelian groups are 2.
10. Consider the set B* of all strings over the alphabet set B = {0, 1} with the concatenation operator for strings ________
a) does not form a group
b) does not have the right identity element
c) forms a non-commutative group
d) forms a group if the empty string is removed from
View Answer
Answer: a
Explanation: Identity element for concatenation is an empty string. Now, we cannot concatenate any string with a given string to get empty string there is no inverse for string concatenation. Only other 3 group properties such as closure, associative and existence of identity are satisfied.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!


The clicks
Plugin tracks all clicks on a page and beacons them to a dedicated endpoint on your beacon-server.
The clicks
API is encapsulated in the BOOMR.plugins.clicks
namespace
The clicks plugin configuration is contained in the clicks
namespace in the initial Boomerang configuration Object.
See "Howto #6 — Configuring boomerang" for more information on how to configure Boomerang
true
clicks will be sent when the site is being closed
so as to not interfere with the normal control flow and network events sent during the lifecycle of the page.
Otherwise click events are sent immediately as they occur
Called by the BOOMR.init() method to configure the clicks plugin.
BOOMR.init({ clicks: { click_url: "http://<your beacon server>/clicks", onbeforeunload: false } });
BOOMR.init()
. See the Configuration section for details.
a reference to the BOOMR.plugins.clicks
object, so you can chain methods.
The following parameters are sent when a click event is triggered.
id
of the element if specified otherwise ""
. ""
. The latest code and docs is available on github.com/SOASTA/boomerang


This intention adds a
kotlin.ReplaceWith
argument to a
kotlin.deprecated
annotation on a function or a property based on its body.


Essential information such as the segment count, trap status, zoom factor, drawing scale, graphic tabs and cursor position are displayed on an overlay report that does not interfere with the drawing. You get to use the whole screen all the time!


Our volunteer teams work to help the needy and people with limited income in maintenance work and some special services. To request any service, you should fill in the required form, and our teams will work to progress your request as soon as possible.