Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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)

View 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

View 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

View 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

View 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

View 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

View 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

View Answer

Answer: d [Reason:] By using the Euclidean algorithm.

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

View 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)

View 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

View 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

View 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

View 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)

View 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)

View 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)

View 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)

View 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

View 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)

View 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)

View 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

View 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)

View 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

View 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

View 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

View 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

View 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+

View 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

View 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

View 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)

View 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

View 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}

View 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)

View 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)

View 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)

View 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

View 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)

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View 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

View Answer

Answer: d [Reason:] lcm(41 * 42, 42 * 42) = 41.42.42.41 / 41.42 = 41.42.