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

2. Out of following which property algorithms does not share?

a) Input

b) Finiteness

c) Generality

d) Constancy

### View Answer

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

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

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

6. __________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.

a) (n^{2} + n + 2) / 2

b) (n^{3} + n – 2) / 2

c) (n^{2} + n – 2) / 2

d) (n^{2} – n – 2) / 2

### View Answer

^{2}+ 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

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

9. The operation of processing each element in the list is known as

a) Sorting

b) Merging

c) Inserting

d) Traversal

### View Answer

10. The complexity of Bubble sort algorithm is

a) O(n)

b) O(log n)

c) O(n^{2})

d) O(n log n)

### View Answer

^{2}).

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

2. The inverse of 3 modulo 7 is

a) -1

b) -2

c) -3

d) -4

### View Answer

3. The integer 561 is a Carmichael number.

a) True

b) False

### View Answer

^{560}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

5. The inverse of 7 modulo 26 is

a) 12

b) 14

c) 15

d) 20

### View Answer

6. The inverse of 19 modulo 141 is

a) 50

b) 51

c) 54

d) 52

### View Answer

7. The integer 2821 is a Carmichael number.

a) True

b) False

### View Answer

^{2820}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

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

10. The value of 5^{2003} mod 7 is

a) 3

b) 4

c) 8

d) 9

### View Answer

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

2. The complexity of linear search algorithm is

a) O(n)

b) O(log n)

c) O(n^{2})

d) O(n log n)

### View Answer

3. The complexity of Binary search algorithm is

a) O(n)

b) O(log )

c) O(n^{2})

d) O(n log n)

### View Answer

4. The complexity of merge sort algorithm is

a) O(n)

b) O(log n)

c) O(n^{2})

d) O(n log n)

### View Answer

5. The complexity of Bubble sort algorithm is

a) O(n)

b) O(log n)

c) O(n^{2})

d) O(n log n)

### View Answer

^{2})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

7. The worst case complexity for insertion sort is

a) O(n)

b) O(log n)

c) O(n^{2})

d) O(n log n)

### View Answer

8. The complexity of Fibonacci series is

a) O(2^{n})

b) O(log n)

c) O(n^{2})

d) O(n log n)

### View Answer

^{n}. 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

10. The worst case complexity of quick sort is

a) O(n)

b) O(log n)

c) O(n^{2})

d) O(n log n)

### View Answer

^{2}).

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

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

3. The value of ⌊1/2.⌊5/2⌋ ⌋ is ______________

a) 1

b) 2

c) 3

d) 0.5

### View Answer

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

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

^{+ }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

7. __________ bytes are required to encode 2000 bits of data.

a) 1

b) 2

c) 3

d) 8

### View Answer

8. The inverse of function f(x) = x^{3} + 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

^{ -1 }(y) = x.

9. The function f(x) = x^{3} is bijection from R to R. Is it True or False?

a) True

b) False

### View Answer

^{3}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

## Discrete Mathematics MCQ Set 5

1. If f(x) = (x^{3} – 1) / (3x + 1) then f(x) is

a) O(x^{2})

b) O(x)

c) O(x^{2} / 3)

d) O(1)

### View Answer

^{3}– 1) / (3x + 1) < x

^{2}.

2. If f(x) = 3x^{2} + x^{3}logx, then f(x) is

a) O(x^{2})

b) O(x^{3})

c) O(x)

d) O(1)

### View Answer

^{2}< x

^{3}, it follows that 0 < 3x

^{2}+ x

^{3}logx < x

^{3}. Consequently, f(x) = O(x

^{3}).

3. The big-O notation for f(n) = (nlogn + n^{2})(n^{3} + 2) is

a) O(n^{2})

b) O(3^{n})

c) O(n^{4})

d) O(n^{5})

### View Answer

^{3}+ 2 < n

^{3}, it follows that (nlogn + n

^{2})(n

^{3}+ 2) is less than equal to n

^{5}.

4. The big-theta notation for function f(n) = 2n^{3} + n – 1 is

a) n

b) n^{2}

c) n^{3}

d) n^{4}

### View Answer

^{3}+ n – 1 is less than equal to n

^{3}.

5. The big-theta notation for f(n) = nlog(n^{2} + 1) + n^{2}logn is

a) n^{2}logn

b) n^{2}

c) logn

d) nlog(n^{2})

### View Answer

^{2}logn < n

^{3}, it follows that nlog(n

^{2}+ 1) + n

^{2}logn is less than n

^{3}and greater than n

^{2}logn.

5. The big-omega notation for f(x, y) = x^{5}y^{3} + x^{4}y^{4} + x^{3}y^{5} is

a) x^{5}y^{3}

b) x^{5}y^{5}

c) x^{3}y^{3}

d) x^{4}y^{4}

### View Answer

^{5}y

^{3}, x

^{4}y

^{4}and x

^{3}y

^{5}is greater than or equal to x

^{3}y

^{3}.

6. If f_{1}(x) is O(g(x)) and f_{2}(x) is o(g(x)), then f_{1}(x) + f_{2}(x) is

a) O(g(x))

b) o(g(x))

c) O(g(x)) + o(g(x))

d) None of the mentioned

### View Answer

_{2}(x) is less than O(g(x)). So, f

_{1}(x) + f

_{2}(x) upper bound is O(g(x)).

7. The little-o notation for f(x) = xlogx is

a) x

b) x^{3}

c) x^{2}

d) xlogx

### View Answer

^{2}as x tends to infinity.

8. The big-O notation for f(n) = 2log(n!) + (n^{2} + 1)logn is

a) n

b) n^{2}

c) nlogn

d) n^{2}logn

### View Answer

^{2}logn, it follows that 2log(n!) + (n

^{2}+ 1)logn is less than or equal n

^{2}logn.

9. The big-O notation for f(x) = 5logx is

a) 1

b) x

c) x^{2}

d) x^{3}

### View Answer

10. The big-Omega notation for f(x) = 2x^{4} + x^{2} – 4 is

a) x^{2}

b) x^{3}

c) x

d) x^{4}

### View Answer

^{4}+ x

^{2}– 4 is greater than or equal to x

^{4}.

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

^{0}+ 1*2

^{1}+ 1*2

^{2}+ 1*2

^{5}+ 1*2

^{6}+ 1*2

^{7}is equal to 231.

2. The decimal notation of 101010101 is

a) 340_{10}

b) 341_{10}

c) 342_{10}

d) 315_{10}

### View Answer

_{2}= 1*2

^{0}+1*2

^{2}+1*2

^{4}+1*2

^{6}+1*2

^{8}= 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

4. The hexadecimal notation of (1011 0111 1011)_{2} is

a) (B2B)_{16}

b) (B5B)_{16}

c) (B7B)_{16}

d) (A7B)_{16}

### View Answer

_{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

_{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

_{16}.

7. The greatest common divisor of 414 and 662 is

a) 4

b) 5

c) 2

d) 6

### View Answer

8. The greatest common divisor of 12 and 18 is

a) 2

b) 3

c) 4

d) 6

### View Answer

9. The decimal expansion of (2AE0B)_{16} is

a) (175627)_{10}

b) (175624)_{10}

c) (178566)_{10}

d) (175622)_{10}

### View Answer

_{16}= 2*16

_{4}+10*16

_{3}+14*16

_{2}+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

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

2. The remainder when 111 is divided by 12 is

a) 0

b) 1

c) 2

d) 3

### View Answer

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

4. The value of 12 mod 3 is

a) 0

b) 1

c) 2

d) 3

### View Answer

5. The value of 155 mod 9 is

a) 0

b) 1

c) 2

d) 3

### View Answer

6. Is 17 congruent to 4 modulo 6

a) True

b) False

### View Answer

7. If a|b and a|c, then

a) a|bc

b) c|a

c) a|(b+c)

d) b|a

### View Answer

8. Is 102 congruent to 6 modulo 16

a) True

b) False

### View Answer

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

10. The value of 15 mod 11 is

a) 1

b) 2

c) 3

d) 4

### View Answer

## Discrete Mathematics MCQ Set 8

1. The prime factorization of 7007 is __________

a) 7^{3}.11.13

b) 7^{2}.11.13

c) 7.11.13

d) 7.11^{3}.13

### View Answer

2. Out of following which one is Mersenne Primes?

a) 3

b) 7

c) 2047

d) 31

### View Answer

^{b}-1 form.

3. Out of the following which of these integers is not prime?

a) 21

b) 35

c) 71

d) 101

### View Answer

4. The prime factorization of 1001 is __________

a) 7^{3}.11.13

b) 7^{2}.11.13

c) 7.11.13

d) 7.11^{3}.13

### View Answer

5. Which positive integer less than 21 are relatively prime to 21?

a) 18

b) 19

c) 21

d) 24

### View Answer

6. Is 7, 8, 9, 11 are pairwise relatively prime. Is it True or False?

a) True

b) False

### View Answer

7. The greatest common divisor of 3^{13}.5^{17} and 2^{12}.3^{5} is __________

a) 3^{0}

b) 3^{1}

c) 3^{3}

d) 3^{5}

### View Answer

^{min(13, 5)}.5

^{min(17, 0)}.2

^{min(12, 0)}.

8. The greatest common divisor of 0 and 5 is ___________

a) 0

b) 1

c) 2

d) 5

### View Answer

^{min(1, 0)}.5

^{min(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

10. The least common multiple of 41.42 and 42.41 is ____________

a) 42

b) 41

c) 84

d) 41.42