Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Logics – Inference”.

1. Which rule of inference is used in each of these arguments, “If it is Wednesday, then the Smartmart will be crowded. It is Wednesday. Thus, the Smartmart is crowded.”
a) Modus tollens
b) Modus ponens
c) Disjunctive syllogism
d) Simplification

Answer: b
Clarification: (M ∧ (M → N)) → N is Modus ponens.

2. Which rule of inference is used in each of these arguments, “If it hailstoday, the local office will be closed. The local office is not closed today. Thus, it did not hailed today.”
a) Modus tollens
b) Conjunction
c) Hypothetical syllogism
d) Simplification

Answer: a
Clarification: (¬N ∧ (M → N)) → ¬M is Modus tollens.

3. Which rule of inference is used, ”Bhavika will work in an enterprise this summer. Therefore, this summer Bhavika will work in an enterprise or he will go to beach.”
a) Simplification
b) Conjunction
c) Addition
d) Disjunctive syllogism

Answer: c
Clarification: p → (p ∨ q) argument is ‘Addition’.

4. What rule of inference is used here?
“It is cloudy and drizzling now. Therefore, it is cloudy now.”
a) Addition
b) Simplification
c) Resolution
d) Conjunction

Answer: b
Clarification: (p ∧ q) → p argument is Simplification.

5. What rule of inference is used in this argument?
“If I go for a balanced diet, then I will be fit. If I will be fit, then I will remain healthy. Therefore, if I go for a balanced diet, then I will remain healthy.”
a) Modus tollens
b) Modus ponens
c) Disjunctive syllogism
d) Hypothetical syllogism

Answer: d
Clarification: ((p → q) ∧ (q → r)) → (p → r) argument is ‘Hypothetical syllogism’.

6. What rules of inference are used in this argument?
“All students in this science class has taken a course in physics” and “Marry is a student in this class” imply the conclusion “Marry has taken a course in physics.”
a) Universal instantiation
b) Universal generalization
c) Existential instantiation
d) Existential generalization

Answer: a
Clarification: ∀xP (x), ∴ P (c) Universal instantiation.

7. What rules of inference are used in this argument?
“It is either colder than Himalaya today or the pollution is harmful. It is hotter than Himalaya today. Therefore, the pollution is harmful.”
a) Conjunction
b) Modus ponens
c) Disjunctive syllogism
d) Hypothetical syllogism

Answer: c
Clarification: ((p ∨ q) ∧ ¬p) → q argument is Disjunctive syllogism.

8. The premises (p ∧ q) ∨ r and r → s imply which of the conclusion?
a) p ∨ r
b) p ∨ s
c) p ∨ q
d) q ∨ r

Answer: b
Clarification: The premises (p ∧ q) ∨ r has two clauses: p ∨ r, and q ∨ r. We can also replace r → s with the equivalent clause r ∨ s. Using the two clauses p ∨ r and r ∨ s, we can conclude p ∨ s.

9. What rules of inference are used in this argument?
“Jay is an awesome student. Jay is also a good dancer. Therefore, Jay is an awesome student and a good dancer.”
a) Conjunction
b) Modus ponens
c) Disjunctive syllogism
d) Simplification

Answer: a
Clarification: ((p) ∧ (q)) → (p ∧ q) argument is conjunction.

10. “Parul is out for a trip or it is not snowing” and “It is snowing or Raju is playing chess” imply that __________
a) Parul is out for trip
b) Raju is playing chess
c) Parul is out for a trip and Raju is playing chess
d) Parul is out for a trip or Raju is playing chess

Answer: d
Clarification: Let p be “It is snowing,” q be “Parul is out for a trip,” and r the proposition “Raju is playing chess.” The hypotheses as ¬p ∨ q and p ∨ r, respectively. Using resolution, the proposition q ∨ r is, “Parul is out for a trip or Raju is playing chess.”

Discrete Mathematics Multiple Choice Questions on “Geometric Sequences”.

1. Let the sequence be 2, 8, 32, 128,……… then this sequence is _______________
a) An arithmetic sequence
b) A geometic progression
c) A harmonic sequence
d) None of the mentioned

Answer: b
Clarification: The ratio of any term with previous term is same.

2. In the given Geometric progression find the number of terms.

32, 256, 2048, 16384,.........,250.

a) 11
b) 13
c) 15
d) None of the mentioned

Answer: d
Clarification: n^th term = first term(ratio^{n – 1})., 2⁵⁰ = 2⁵(2^3(n-1)), n=15. This implies 16^th term.

3. In the given Geometric progression the term at position 11 would be ___________

32, 256, 2048, 16384,.........,250.

a) 2³⁵
b) 2⁴⁵
c) 35
d) None of the mentioned

Answer: a
Clarification: n^th term = first term(ratio^{n – 1})., g_n = 2⁵(2^3(n-1)), n=11. This implies 2³⁵.

4. For the given Geometric progression find the position of first fractional term?

250, 247, 244,.........

a) 17
b) 20
c) 18
d) None of the mentioned

Answer: c
Clarification: Let n^th term=1, the next term would be first fractional term.
G_n = 1 = 2⁵⁰(2^3(-n+1)), n=17.66.. therfore at n = 18 the first fractional term would occur.

5. For the given geometric progression find the first fractional term?

250, 247, 244,.........

a) 2^-1
b) 2^-2
c) 2^-3
d) None of the mentioned

Answer: a
Clarification: Let n^th term=1, the next term would be first fractional term.
G_n = 1 = 2⁵⁰( 2 ^3(-n+1)), n=17.66. Therefore at n=18 the first fractional term would occur. G_n = 2⁵⁰( 2 ^3(-n+1)), G₁₈ = 2^-1.

6. State whether the given statement is true or false.

1, 1, 1, 1, 1........ is a GP series.

a) True
b) False

Answer: a
Clarification: The ratio of any term with previous term is same.

7. In the given Geometric progression, ‘2²⁵‘ would be a term in it.

32, 256, 2048, 16384,.........,250.

a) True
b) False

Answer: b
Clarification: n^th term = first term(ratio^{n – 1})., g_n = 2²⁵ = 2⁵ (2 ^3(n-1)), n=23/3, n=7.666 not an integer. Thus 2²⁵ is not a term in this series.

8. Which of the following sequeces in GP will have common ratio 3, where n is an Integer?
a) g_n = 2n² + 3n
b) g_n = 2n² + 3
c) g_n = 3n² + 3n
d) g_n = 6(3^n-1)

Answer: d
Clarification: g_n = 6( 3^n-1) it is a geometric expression with coefficient of constant as 3^n-1.So it is GP with common ratio 3.

9. If a, b, c are in GP then relation between a, b, c can be ___________
a) 2b = 2a + 3c
b) 2a = b+c
c) b =(ac)^1/2
d) 2c = a + c

Answer: c
Clarification: The term b should be the geometric mean of of term a and c.

10. Let the multiplication of the 3 consecutive terms in GP be 8 then midlle of those 3 terms would be _______
a) 2
b) 3
c) 4
d) 179

Answer: a
Clarification: Let a, b, c be three terms, then a/r * a * ar = 8, b = (ac)^1/2 (G M property), b³ = 8, b = 2.

Discrete Mathematics Multiple Choice Questions on “Algorithms – Integers and Division”.

1. The quotient when 19 is divided by 6 is?
a) 1
b) 2
c) 3
d) 0

Answer: c
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: By the Division algorithm 15 = 11(1) + 4. Where the remainder is 15 mod 11.

Discrete Mathematics Multiple Choice Questions 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

Answer: b
Clarification: 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

Answer: a
Clarification: 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

Answer: b
Clarification: 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

Answer: c
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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

Answer: b
Clarification: We can have recurrence relation for tower of hanoi and that is h_n = 2 h_n-1 + 1h₁ = 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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) 3⁵⁸
c) 56
d) 2⁵⁵

Answer: d
Clarification: 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 2^h+1 Null pointers as children.
h = 54
2⁵⁴⁺¹
2⁵⁵.

Discrete Mathematics Multiple Choice Questions on “Probability Distribution”.

1. Two fair coins are flipped. As a result of this, tails and heads runs occurred where a tail run is a consecutive occurrence of at least one head. Determine the probability function of number of tail runs.
a) (frac{1}{2})
b) (frac{5}{6})
c) (frac{32}{19})
d) (frac{6}{73})

Answer: a
Clarification: The sample space of the experiment is S = {HH, HT, TH, TT}. Let X is the number of tails and It takes up the values 0, 1 and 2. Now, P(no tail) = p(0) = (frac{1}{4}), P(one tail) = p(1) = (frac{2}{4}) and P(two tails) = p(2) = (frac{1}{4}). So, X is the number of tail runs and it takes up the values 0 and 1. P(X = 0) = p(0) = (frac{2}{4} = frac{1}{4}).

2. The length of alike metals produced by a hardware store is approximated by a normal distribution model having a mean of 7 cm and a standard deviation of 0.35 cm. Find the probability that the length of a randomly chosen metal is between 5.36 and 6.14 cm?
a) 0.562
b) 0.2029
c) 3.765
d) 1.576

Answer: b
Clarification: Let L be the random variable that represents the length of the component. It has a mean of 7 cm and a standard deviation of 0.35 cm. To find P( 5.36 < x < 6.14). For x = 5.36, z = (frac{5.36 – 6}{0.35}) = -1.82. For x = 6.14, z = (frac{6.14 – 6}{0.35}) = 0.4 ⇒ P(5.36 < x < 6.14) = P( -1.82 < z < 0.4) = 0.2029.

3. A personal computer has the length of time between charges of the battery is normally distributed with a mean of 66 hours and a standard deviation of 20 hours. What is the probability when the length of time will be between 58 and 75 hours?
a) 0.595
b) 3.44
c) 0.0443
d) 1.98

Answer: c
Clarification: Suppose x be the random variable that represents the length of time. It has a mean of 66 and a standard deviation of 20. Find the probability that x is between 70 and 90 or P(70 < x < 90). For x = 70, z = (frac{58 – 66}{20}) = -4. For x = 75, z = (frac{75 – 66}{20}) = 0.45. P(70 < x < 90) = P(-4 < z < 0.75) = [area to the left of z = 0.75] – [area to the left of z = -4] = 0.0443. The required probability when the length of time between 58 and 75 hours is 0.0443.

4. The length of life of an instrument produced by a machine has a normal distribution with a mean of 9.4 months and a standard deviation of 3.2 months. What is the probability that an instrument produced by this machine will last between 6 and 11.6 months?
a) 0.642
b) 0.4098
c) 0.16
d) 0.326

Answer: d
Clarification: We have to find P(6 < x < 11.6). Now, for x = 6, z becomes -1.062 and for z = 11.6, z = 0.687. So, P(6 < x < 11.6) = P(-1.062 < z < 0.687) = 0.326.

5. The speeds of a number of bicycles have a normal distribution model with a mean of 83 km/hr and a standard deviation of 9.4 km/hr. Find the probability that a bicycle picked at random is travelling at more than 95 km/hr?
a) 0.1587
b) 0.38
c) 0.49
d) 0/278

Answer: b
Clarification: Let x be the random variable that represents the speed of bicycle. x has μ = 90 and σ = 9.5. We have to find the probability that x is higher than 95 or P(x > 95). For x = 95, z = (frac{95 – 83}{9.4}) = 1.27, P(x > 95) = P(z > 1.27) = [total area] – [area to the left of z = 1] = 1 – 0.620 = 0.38. The probability that a car selected at a random has a speed greater than 100 km/hr is equal to 0.38.

6. Let us say that X is a normally distributed variable with mean(μ) of 43 and standard deviation (σ) of 6.4. Determine the probability of X<32.
a) 0.341
b) 0.962
c) 6.231
d) 0.44

Answer: a
Clarification: The area is defined as the area under the standard normal curve.Now, for x = 32, z becomes (frac{32 – 43}{6.4}) = -1.71. Hence, the required probability is P(x < 32) = P(z < -1.71) = 0.341.

7. The time taken to assemble a machine in a certain plant is a random variable having a normal distribution of 32 hours and a standard deviation of 3.6 hours. What is the probability that a machine can be assembled at this plant in less than 25.4 hours?
a) 0.61
b) 0.674
c) 0.298
d) 1.823

Answer: c
Clarification: We have to find P(x < 25.4). Now, for x = 25.4, z becomes (frac{25.4 – 32}{3.6}) = -1.83. Hence, P(z < -1.83) = 0.298.

8. The scores on an admission test are normally distributed with a mean of 640 and a standard deviation of 105.7. A student wants to be admitted to this university. He takes the test and scores 755. What is the probability of him to be admitted to this university?
a) 65.9%
b) 84.6%
c) 40.9%
d) 54%.

Answer: b
Clarification: Let k be the random variable that represents the scores. k is normally distributed with a mean of 640 and a standard deviation of 124.7. The total area under the normal curve represents the total number of students who take the test. If we multiply the values of the areas under the curve by 124.7, we obtain percentages. Now, for k = 755, z = (frac{755 – 640}{105.7}) = 1.087. The proportion of the students who scored below 755 is given by, P = [area to the left of z = 1.087] = 0.846. Hence, the required probability is 84.6 %.

9. The annual salaries of workers in a large manufacturing factory are normally distributed with a mean of Rs. 48,000 and a standard deviation of Rs. 1500. Find the probability of workers who earn between Rs. 35,000 and Rs. 52,000.
a) 64%
b) 76.2%
c) 42.1%
d) 20%

Answer: c
Clarification: For x = 45000, z = -2 and for x = 52000, z = 0.375. Now, area between z = -2 and z = 0.375 is equal to 0.421 or 42.1% earn between Rs. 45,000 and Rs. 52,000.

10. Discrete probability distribution depends on the properties of ___________
a) data
b) machine
c) discrete variables
d) probability function

Answer: a
Clarification: We know that discrete probability function largely depends on the properties and types of data such as Binomial distribution can lead to model binary data such as flipping of coins.

Discrete Mathematics Multiple Choice Questions on “Graphs Properties”.

1. In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be ______
a) 728
b) 450
c) 360
d) 260

Answer: c
Clarification: A Hamiltonian cycle in a connected graph G is defined as a closed path that traverses every vertex of G exactly once except the starting vertex, at which the path also terminates. In an n-complete graph, there are (n-1)!/2 hamiltonian cycles and so the answer is 360.

2. If each and every vertex in G has degree at most 23 then G can have a vertex colouring of __________
a) 24
b) 23
c) 176
d) 54

Answer: a
Clarification: A vertex colouring of a graph G = (V’,E’) with m colours is a mapping f:V’ -> {1,…,m} such that f(u)!=f(v) for every (u,v) belongs to E’. Since in worst case the graph can be complete, d+1 colours are necessary for graph containing vertices with degree at most ‘d’. So, the required answer is 24.

3. Triangle free graphs have the property of clique number is __________
a) less than 2
b) equal to 2
c) greater than 3
d) more than 10

Answer: d
Clarification: In an undirected triangle-free graph no three vertices can form a triangle of edges. It can be described as graphs with clique number less than 2 and the graphs with girth greater than 4.

4. Berge graph is similar to ______ due to strong perfect graph theorem.
a) line graph
b) perfect graph
c) bar graph
d) triangle free graph

Answer: b
Clarification: In a perfect graph, the chromatic number of each and every induced subgraph is equal to the size of the largest clique of that subgraph. These perfect graphs are same as Berge graphs due to strong perfect graph theorem.

5. Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?
a) 4
b) 0
c) 2
d) 5

Answer: c
Clarification: We know that sum of degrees of all vertices = 2X no of edges. Say number of edges is E. Degree of last vertex is x, 1+2+3+4+5+6+7++8+9+x = 2XE
=>45+x = 2XE
Now putting options we get answer 0 or 5
But one vertex of degree 9 means it connected to all other vertexes. So, the degree must be 5.

6. A ______ is a graph which has the same number of edges as its complement must have number of vertices congruent to 4m or 4m modulo 4(for integral values of number of edges).
a) Subgraph
b) Hamiltonian graph
c) Euler graph
d) Self complementary graph

Answer: d
Clarification: It is the definition of self complementary graph. It is a graph that is isomorphic to its complement.

7. In a ______ the vertex set and the edge set are finite sets.
a) finite graph
b) bipartite graph
c) infinite graph
d) connected graph

Answer: b
Clarification: In graph theory, most common graphs are considered to be finite otherwise it is an infinite graph. Now, a finite graph is a graph in which the vertex set and the edge set are described as the finite sets.

8. If G is the forest with 54 vertices and 17 connected components, G has _______ total number of edges.
a) 38
b) 37
c) 17/54
d) 17/53

Answer: b
Clarification: Here we are given a forest with 54 vertices and 17 components. A component is itself a tree and since there are 17 components means that every component has a root, therefore we have 17 roots. Each new vertex of the forest contributes to a single edge to a forest. So for remaining 54-17 = 37 vertices we can have m-n=37 edges. Hence, answer is 37.

9. The number of edges in a regular graph of degree 46 and 8 vertices is ____________
a) 347
b) 230
c) 184
d) 186

Answer: c
Clarification: In a complete graph which is (n-1) regular (where n is the number of vertices) has edges n*(n-1)/2. In the graph n vertices are adjacent to n-1 vertices and an edge contributes two degree so dividing by 2. Hence, in a d regular graph number of edges will be n*d/2 = 46*8/2 = 184.

10. An undirected graph G has bit strings of length 100 in its vertices and there is an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position. Determine the ratio of the chromatic number of G to the diameter of G?
a) 1/2¹⁰¹
b) 1/50
c) 1/100
d) 1/20

Answer: b
Clarification: For the given condition we can simply design a K-Map and mark an edge between every two adjacent cells in K-map. Hence, that will give us a Bipartite graph and chromatic number for this = 2. Hence the ratio is 2/n=2/100=1/50 and the given graph is actually a hypercube graph.