Select Page
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

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: 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: 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: 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: 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: 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: 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: 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: 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: 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: a [Reason:] By using the Euclidean algorithm.

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

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: 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: a [Reason:] By using the Euclidean algorithm.

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

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: d [Reason:] By using the Euclidean algorithm.

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

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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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