Discrete Mathematics MCQ Set 1
1. An algorithm is a _________ set of precise instructions for performing computation.
a) Infinite
b) Finite
c) Constant
d) None of the mentioned
Answer
Answer: b [Reason:] By the definition of algorithm.
2. Out of following which property algorithms does not share?
a) Input
b) Finiteness
c) Generality
d) Constancy
Answer
Answer: d [Reason:] 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
Answer
Answer: b [Reason:] 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
Answer
Answer: a [Reason:] 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
Answer
Answer: b [Reason:] The insertion sort compares second element with 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
Answer
Answer: c [Reason:] 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
Answer
Answer: d [Reason:] 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
Answer
Answer: b [Reason:] 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
Answer
Answer: d [Reason:] 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)
Answer
Answer: c [Reason:] The complexity of Bubble sort algorithm is O(n2).
Discrete Mathematics MCQ Set 2
1. The linear combination of gcd(252, 198) = 18 is
a) 252*4 – 198*5
b) 252*5 – 198*4
c) 252*5 – 198*2
d) 252*4 – 198*4
Answer
Answer: a [Reason:] By using the Euclidean algorithm.
2. The inverse of 3 modulo 7 is
a) -1
b) -2
c) -3
d) -4
Answer
Answer: b [Reason:] By using the Euclidean algorithm, 7 = 2*3 + 1. From this we see that -2*3 + 1*7 = 1. This show that -2 is an inverse.
3. The integer 561 is a Carmichael number.
a) True
b) False
Answer
Answer: a [Reason:] 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
Answer
Answer: a [Reason:] By using the Euclidean algorithm.
5. The inverse of 7 modulo 26 is
a) 12
b) 14
c) 15
d) 20
Answer
Answer: c [Reason:] By using the Euclidean algorithm.
6. The inverse of 19 modulo 141 is
a) 50
b) 51
c) 54
d) 52
Answer
Answer: d [Reason:] By using the Euclidean algorithm.
7. The integer 2821 is a Carmichael number.
a) True
b) False
Answer
Answer: a [Reason:] 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)
Answer
Answer: b [Reason:] The inverse of 5 modulo 9 is -2. Multiply by (-2) on both sides in equation 4x = 5(mod 9), it follows that x is congruent to 8(mod 9).
9. The linear combination of gcd(10 ,11) = 1 can be written as
a) (-1)*10 + 1*11
b) (-2)*10 + 2*11
c) 1*10 + (-1)*11
d) (-1)*10 + 2*11
Answer
Answer: a [Reason:] 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
Answer
Answer: a [Reason:] By using the Fermat’s theorem.
Discrete Mathematics MCQ Set 3
1. Which of the following case does not exist in complexity theory?
a) Best case
b) Worst case
c) Average case
d) Null case
Answer
Answer: d [Reason:] Null case does not exist in complexity Theory.
2. The complexity of linear search algorithm is
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
Answer
Answer: a [Reason:] The worst case complexity of linear search is O(n).
3. The complexity of Binary search algorithm is
a) O(n)
b) O(log )
c) O(n2)
d) O(n log n)
Answer
Answer: b [Reason:] The compexity of binary search is O(logn).
4. The complexity of merge sort algorithm is
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
Answer
Answer: d [Reason:] The worst case complexity for merge sort is O(nlogn).
5. The complexity of Bubble sort algorithm is
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
Answer
Answer: c [Reason:] The worst case complexity for Bubble sort is O(n2)ans best case is O(n).
6. The Worst case occur 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
Answer
Answer: d [Reason:] The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.
7. The worst case complexity for insertion sort is
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
Answer
Answer: c [Reason:] In worst case nth comparison are required to insert the nth element into correct position.
8. The complexity of Fibonacci series is
a) O(2n)
b) O(log n)
c) O(n2)
d) O(n log n)
Answer
Answer: a [Reason:] Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2n. Now prove inductively that f(n) > = g(n).
9. The worst case occur in quick sort when
a) Pivot is the median of the array
b) Pivot is the smallest element
c) Pivot is the middle element
d) None of the mentioned
Answer
Answer: b [Reason:] This happens when the pivot is the smallest (or the largest) element. Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.
10. The worst case complexity of quick sort is
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
Answer
Answer: c [Reason:] The worst case complexity of quick sort is O(n2).
Discrete Mathematics MCQ Set 4
1. A function is said to be ______________ if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f.
a) One-to-many
b) One-to-one
c) Many-to-many
d) Many-to-one
Answer
Answer: b [Reason:] A function is one-to-one if and only if f(a)≠f(b) whenever a≠b.
2. The function f(x)=x+1 from the set of integers to itself is onto. Is it True or False?
a) True
b) False
Answer
Answer: a [Reason:] For every integer “y” there is an integer “x ” such that f(x) = y.
3. The value of ⌊1/2.⌊5/2⌋ ⌋ is ______________
a) 1
b) 2
c) 3
d) 0.5
Answer
Answer: a [Reason:] The value of ⌊5/2⌋ is 2 so, the value of ⌊1/2.2⌋ is 1.
4. Which of the following function f: Z X Z → Z is not onto?
a) f(a, b) = a + b
b) f(a, b) = a
c) f(a, b) = |b|
d) f(a, b) = a – b
Answer
Answer: c [Reason:] The function is not onto as f(a)≠b.
5. The domain of the function that assign to each pair of integers the maximum of these two integers is ___________
a) N
b) Z
c) Z +
d) Z+ X Z+
Answer
Answer: d [Reason:] The domain of the integers is Z+ X Z+ .
6. Let f and g be the function from the set of integers to itself, defined by f(x) = 2x + 1 and g(x) = 3x + 4. Then the composition of f and g is ____________
a) 6x + 9
b) 6x + 7
c) 6x + 6
d) 6x + 8
Answer
Answer: a [Reason:] The composition of f and g is given by f(g(x)) which is equal to 2(3x + 4) + 1.
7. __________ bytes are required to encode 2000 bits of data.
a) 1
b) 2
c) 3
d) 8
Answer
Answer: b [Reason:] Two bytes are required to encode 2000 (actually with 2 bytes you can encode up to and including 65,535.
8. The inverse of function f(x) = x3 + 2 is ____________
a) f -1 (y) = (y – 2) 1/2
b) f -1 (y) = (y – 2) 1/3
c) f -1 (y) = (y) 1/3
d) f -1 (y) = (y – 2)
Answer
Answer: b [Reason:] To find the inverse of the function equate f(x) then find the value of x in terms of y such that f -1 (y) = x.
9. The function f(x) = x3 is bijection from R to R. Is it True or False?
a) True
b) False
Answer
Answer: a [Reason:] The function f(x) = x3 is one to one as no two values in domain are assigned the same value of the function and it is onto as all R of the co domain is images of elements in domain.
10. The g -1({0}) for the function g(x)= ⌊x⌋ is ___________
a) {x | 0 ≤ x < 1}
b) {x | 0 < x ≤ 1}
c) {x | 0 < x < 1}
d) {x | 0 ≤ x ≤ 1}
Answer
Answer: d [Reason:] g({0}) for the function g(x) is {x | 0 ≤ x ≤ 1}. Put g(x) = y and find the value of x in terms of y such that ⌊x⌋ = y.
Discrete Mathematics MCQ Set 5
1. If f(x) = (x3 – 1) / (3x + 1) then f(x) is
a) O(x2)
b) O(x)
c) O(x2 / 3)
d) O(1)
Answer
Answer: a [Reason:] 0 < (x3 – 1) / (3x + 1) < x2.
2. If f(x) = 3x2 + x3logx, then f(x) is
a) O(x2)
b) O(x3)
c) O(x)
d) O(1)
Answer
Answer: b [Reason:] 0 < 3x2 < x3, it follows that 0 < 3x2 + x3logx < x3. Consequently, f(x) = O(x3).
3. The big-O notation for f(n) = (nlogn + n2)(n3 + 2) is
a) O(n2)
b) O(3n)
c) O(n4)
d) O(n5)
Answer
Answer: d [Reason:] 0 < n3 + 2 < n3, it follows that (nlogn + n2)(n3 + 2) is less than equal to n5.
4. The big-theta notation for function f(n) = 2n3 + n – 1 is
a) n
b) n2
c) n3
d) n4
Answer
Answer: c [Reason:] 2n3 + n – 1 is less than equal to n3.
5. The big-theta notation for f(n) = nlog(n2 + 1) + n2logn is
a) n2logn
b) n2
c) logn
d) nlog(n2)
Answer
Answer: a [Reason:] n2logn < n3, it follows that nlog(n2 + 1) + n2logn is less than n3 and greater than n2logn.
5. The big-omega notation for f(x, y) = x5y3 + x4y4 + x3y5 is
a) x5y3
b) x5y5
c) x3y3
d) x4y4
Answer
Answer: c [Reason:] x5y3, x4y4 and x3y5 is greater than or equal to x3y3.
6. If f1(x) is O(g(x)) and f2(x) is o(g(x)), then f1(x) + f2(x) is
a) O(g(x))
b) o(g(x))
c) O(g(x)) + o(g(x))
d) None of the mentioned
Answer
Answer: a [Reason:] f2(x) is less than O(g(x)). So, f1(x) + f2(x) upper bound is O(g(x)).
7. The little-o notation for f(x) = xlogx is
a) x
b) x3
c) x2
d) xlogx
Answer
Answer: c [Reason:] Find the limit for xlogx / x2 as x tends to infinity.
8. The big-O notation for f(n) = 2log(n!) + (n2 + 1)logn is
a) n
b) n2
c) nlogn
d) n2logn
Answer
Answer: d [Reason:] log(n!) < n2logn, it follows that 2log(n!) + (n2 + 1)logn is less than or equal n2logn.
9. The big-O notation for f(x) = 5logx is
a) 1
b) x
c) x2
d) x3
Answer
Answer: b [Reason:] logx < x, it follows that 5logx < x.
10. The big-Omega notation for f(x) = 2x4 + x2 – 4 is
a) x2
b) x3
c) x
d) x4
Answer
Answer: d [Reason:] 2x4 + x2 – 4 is greater than or equal to x4.
Discrete Mathematics MCQ Set 6
1. The binary notation of 231 is
a) (11010111)2
b) (10111011)2
c) (11100011)2
d) (11100111)2
Answer
Answer: d [Reason:] By binary Expansion of 11100111 is 1*20 + 1*21 + 1*22 + 1*25 + 1*26 + 1*27 is equal to 231.
2. The decimal notation of 101010101 is
a) 34010
b) 34110
c) 34210
d) 31510
Answer
Answer: b [Reason:] (101010101)2 = 1*20+1*22+1*24+1*26+1*28 = 341.
3. The binary notation of ABBA is
a) 1010 1011 1011 1010
b) 1010 1001 1011 1011
c) 1011 1000 1010 1001
d) 1001 1000 1000 1111
Answer
Answer: a [Reason:] By the base conversion algorithm.
4. The hexadecimal notation of (1011 0111 1011)2 is
a) (B2B)16
b) (B5B)16
c) (B7B)16
d) (A7B)16
Answer
Answer: c [Reason:] (1011)2 = 11 and (0111)2 = 7, 11 in hexadecimal notation represents B. So it is (B7B)16.
5. The octal expansion of (10 1011 1011)2 is
a) (1245)8
b) (1276)8
c) (1275)8
d) (1273)8
Answer
Answer: d [Reason:] (10 1011 1011)2 = (699)10. Using base conversion algorithm, (699)10 = (1273)8.
6. The hexadecimal expansion of (177130)10 is
a) (2B3EB)16
b) (2B3EA)16
c) (2C3AA)16
d) (2B2AA)16
Answer
Answer: b [Reason:] Successively divide 177130 by 16 to obtain remainder they are (2B3EA)16.
7. The greatest common divisor of 414 and 662 is
a) 4
b) 5
c) 2
d) 6
Answer
Answer: c [Reason:] By using Euclid Lemma.
8. The greatest common divisor of 12 and 18 is
a) 2
b) 3
c) 4
d) 6
Answer
Answer: d [Reason:] By using Euclid Lemma, 6 divides 12 and 18.
9. The decimal expansion of (2AE0B)16 is
a) (175627)10
b) (175624)10
c) (178566)10
d) (175622)10
Answer
Answer: a [Reason:] (2AE0B)16 = 2*164+10*163+14*162+0*16+11=(175627)10.
10. The greatest common divisor of 7 and 5 is
a) 1
b) 2
c) 5
d) 7
Answer
Answer: a [Reason:] Two numbers 7 and 5 are relatively prime, so gcd(7, 5) = 1.
Discrete Mathematics MCQ Set 7
1. The quotient when 19 is divided by 6 is
a) 1
b) 2
c) 3
d) 0
Answer
Answer: c [Reason:] According to the Division Algorithm 19 = 6(3) + 1. Hence, quotient when 19 divided by 6 is 3 = 19 div 6.
2. The remainder when 111 is divided by 12 is
a) 0
b) 1
c) 2
d) 3
Answer
Answer: d [Reason:] According to the Division Algorithm 111 = 12(9) + 3. Hence, remainder when 111 divided by 12 is 3 = 111 mod 12.
3. The quotient and remainder when -1 is divided by 3 is
a) -1 and -1
b) -1 and 2
c) 1 and 2
d) -1 and -2
Answer
Answer: b [Reason:] According to the Division Algorithm -1 = 3(-1) + 2. Hence, quotient when -1 divided by 3 is -1 = -1 div 3 and remainder when -1 divided by 3 is 2 = -1 mod 3.
4. The value of 12 mod 3 is
a) 0
b) 1
c) 2
d) 3
Answer
Answer: a [Reason:] By the Division algorithm 12 = 3(4) + 0. Where remainder is 12 mod 3.
5. The value of 155 mod 9 is
a) 0
b) 1
c) 2
d) 3
Answer
Answer: c [Reason:] By the Division algorithm 155 = 9(17) + 2. Where remainder is 155 mod 9.
6. Is 17 congruent to 4 modulo 6
a) True
b) False
Answer
Answer: b [Reason:] 6 does not divide 17 – 4 = 13.
7. If a|b and a|c, then
a) a|bc
b) c|a
c) a|(b+c)
d) b|a
Answer
Answer: c [Reason:] If a|b and a|c then b = am and c = an for some integer m and n. Hence, b + c = a(m + n). Therefore, a|(b+c).
8. Is 102 congruent to 6 modulo 16
a) True
b) False
Answer
Answer: a [Reason:] 16 divide 102 – 6 = 96.
9. The quotient and remainder when 18 is divided by 5 is
a) 2 and 3
b) 1 and 2
c) 3 and 2
d) 3 and 3
Answer
Answer: d [Reason:] According to the Division Algorithm 18 = 5(3) + 3. Hence, quotient when 18 divided by 5 is 3 = 18 div 5 and remainder when 18 divided by 5 is 3 = 18 mod 5.
10. The value of 15 mod 11 is
a) 1
b) 2
c) 3
d) 4
Answer
Answer: d [Reason:] By the Division algorithm 15 = 11(1) + 4. Where remainder is 15 mod 11.
Discrete Mathematics MCQ Set 8
1. The prime factorization of 7007 is __________
a) 73.11.13
b) 72.11.13
c) 7.11.13
d) 7.113.13
Answer
Answer: b [Reason:] Perform successive division beginning with 2.
2. Out of following which one is Mersenne Primes?
a) 3
b) 7
c) 2047
d) 31
Answer
Answer: c [Reason:] 2047 = 23.89 also not in form of 2b-1 form.
3. Out of the following which of these integers is not prime?
a) 21
b) 35
c) 71
d) 101
Answer
Answer: b [Reason:] 35 = 5.7 which is the product of two prime numbers.
4. The prime factorization of 1001 is __________
a) 73.11.13
b) 72.11.13
c) 7.11.13
d) 7.113.13
Answer
Answer: c [Reason:] Perform successive division beginning with 2.
5. Which positive integer less than 21 are relatively prime to 21?
a) 18
b) 19
c) 21
d) 24
Answer
Answer: b [Reason:] gcd(19,21) = 1. According to the definition of relatively prime gcd of two numbers is 1.
6. Is 7, 8, 9, 11 are pairwise relatively prime. Is it True or False?
a) True
b) False
Answer
Answer: a [Reason:] gcd(7, 9) = gcd(8, 9) = gcd(9, 11) = gcd(11, 7) = 1. The numbers 7 and 11 are prime and numbers 8 and 9 are relatively prime.
7. The greatest common divisor of 313.517 and 212.35 is __________
a) 30
b) 31
c) 33
d) 35
Answer
Answer: d [Reason:] gcd(a, b) = 3min(13, 5).5min(17, 0).2min(12, 0).
8. The greatest common divisor of 0 and 5 is ___________
a) 0
b) 1
c) 2
d) 5
Answer
Answer: b [Reason:] gcd(0, 5) = 0min(1, 0).5min(0, 1).
9. The lcm of 3 and 21 is ________ if gcd(3,21)=3.
a) 3
b) 12
c) 21
d) 42
Answer
Answer: c [Reason:] 3 * lcm(3, 21) = 63 hence, lcm(3, 21) = 63 / 3 = 21.
10. The least common multiple of 41.42 and 42.41 is ____________
a) 42
b) 41
c) 84
d) 41.42
Answer
Answer: d [Reason:] lcm(41 * 42, 42 * 42) = 41.42.42.41 / 41.42 = 41.42.
