Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Bipartite Graphs”.

1. The maximum number of edges in a bipartite graph on 14 vertices is ___________
a) 56
b) 14
c) 49
d) 87

Answer: c
Clarification: Maximum number of edges occur in a complete bipartite graph when every vertex has an edge to every opposite vertex in the graph. Number of edges in a complete bipartite graph is a*b, where a and b are no. of vertices on each side. This quantity is maximum when a = b i.e. when there are 7 vertices on each side. So answer is 7 * 7 = 49.

2. In a ______ the degree of each and every vertex is equal.
a) regular graph
b) point graph
c) star graph
d) euler graph

Answer: c
Clarification: A regular graph has the same degree in each of its vertices. In a regular bipartite graph, if the common degree of each vertices is 1, the two parts are of the same size.

3. The time complexity to test whether a graph is bipartite or not is said to be _______ using depth first search.
a) O(n³)
b) linear time
c) O(1)
d) O(nlogn)

Answer: b
Clarification: It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time i.e, O(n) using depth first search. In case of the intersection of n line segments or other simple shapes in the Euclidean graph, it is possible to test whether the graph is bipartite and it will return either a two-coloring or an odd cycle in time O(nlogn), even though the graph itself has up to O(n²) edges.

4. The partition V = V₁ ∪ V₂ in a bipartite graph G₁ is called ________
a) bipartition of G₁
b) 2-vertex set of G₁
c) sub bipartite graphs
d) disjoint vertex set

Answer: b
Clarification: A graph G₁(V, E) is called bipartite if its vertex set V(G) can be decomposed into two non-empty disjoint subsets V₁(G₁) and V2(G₁) in such a way that each edge e ∈ E(G) has its one end joint in V₁(G₁) and other endpoint in V₂(G₁). The partition V = V₁ ∪ V₂ in a bipartite graph G₁ is called bipartition of G₁.

5. What is the maximum number of edges in a bipartite graph on 14 vertices?
a) 78
b) 15
c) 214
d) 49

Answer: d
Clarification: By definition, the maximum possible number of edges in a bipartite graph on ‘n’ vertices = (1/4) x n².
Substituting n = 14, we get maximum number of edges in a bipartite graph on 14 vertices,= (1/4) x (14)²
= (1/4) x 14 x 14
= 49
∴ Maximum number of edges in a bipartite graph on 14 vertices = 49.

6. In a complete bipartite graph, the intersection of two sub graphs is ______
a) 1
b) null
c) 2¹⁰
d) 412

Answer: b
Clarification: In a complete Bipartite graph, there must exist a partition say, V(G)=X∪Y and X∩Y=∅, that means all edges share a vertex from both set X and Y.

7. Bipartite graphs are used in ________
a) modern coding theory
b) colouring graphs
c) neural networks
d) chemical bonds

Answer: a
Clarification: All types of cyclic graphs are examples of cyclic graphs. A cyclic graph is considered bipartite if all the cycles involved are of even length. Bipartite graphs are widely used in modern coding theory apart from being used in modeling relationships.

8. All closed walks are of ______ length in a bipartite graph.
a) infinite
b) even
c) odd
d) odd prime

Answer: b
Clarification: In a bipartite graph G all closed walks must be of even length as well as all cycles in G are of even length. Then only the graph is considered a bipartite graph.

9. The spectrum of a graph is _______ if and only if it is _______ graph.
a) symmetry, bipartite
b) transitive, bipartite
c) cyclic, Euler
d) reflexive, planar

Answer: a
Clarification: A graph is bipartite if and only if it does not contain an odd cycle. The spectrum of a graph is symmetric if and only if it is a bipartite graph. These are the characteristics of the graph.

Discrete Mathematics Multiple Choice Questions on “Boolean Algebra – Interconversion of Gates”.

1. In order to make a luggage security alarm, a single _____ is used.
a) NOR gate
b) NAND gate
c) X-NOR gate
d) XOR gate

Answer: b
Clarification: The NAND gate consists of two inputs and if both of them are high the output is low. A luggage security alarm circuit is a system which is based on the NAND gate. It is used to generate an alarm when any authorized person tries to steal the luggage.

2. In Boolean algebra, the data is a bit-representation of information consists of _________
a) 0 and 1
b) 2 and 5
c) 1 and 15
d) 4 and 8

Answer: a
Clarification: The data, in boolean algebra must be in a bit-representation form which can be in between two values 0 and 1.

3. Using which component a shift register is implemented?
a) register
b) transistor
c) latch
d) flip-flop

Answer: d
Clarification: A shift register, in digital circuitry, is a combination of two or more flip-flops to share the bits of information by using the same clock. A shift register can have both parallel and serial inputs and outputs.

4. How many NAND gates are required to make an XOR gate?
a) 7
b) 12
c) 4
d) 8

Answer: c
Clarification: An XOR gate is created by using four NAND gates. This construction gives a propagation delay three times to that of a single NAND gate.

5. In Multiplexer gate, for selecting the inputs, two bits named _____ and _____ are required generally.
a) selector bit, data bit
b) parity bit. Generator bit
c) input bit, inverted bit
d) raising bit, sinking bit

Answer: a
Clarification: In multiplexer gate for selecting the inputs say, for 3 input bits, one bit is required as selector bit and two other bits are required as data bits.

6. A NOR gate can be derived from ______
a) NAND gate
b) XOR gate
c) AND gate
d) OR gate

Answer: a
Clarification: NAND and NOR gates are called universal gates. As we can generate any of the basic gates as well as other gates from these two gates. So, a NOR gate can be made by a NAND gate.

7. In which logic gate the output state is usually the complement of the input state?
a) NOT gate
b) NOR gate
c) X-NOR gate
d) OR gate

Answer: a
Clarification: NOT gate is the simplest digital logic circuit which is also called an inverter because it takes the input in 0 or 1 form and gives the output as the complement of the input.

8. In OR gate for 13 numbers of inputs what are the stages possible for it?
a) 1239
b) 213
c) 13
d) 1387

Answer: b
Clarification: OR gate works in a way such that if any of the input is binary low(or 0), the output of the gate is binary 1(or high). Here, the number of stage possible = 2ⁿ = 2¹³.

9. Which of the following is built exclusively from NOR gate?
a) Plant guard machine
b) Apollo Guidance Computer
c) Street market app
d) Dish washer

Answer: b
Clarification: The first embedded system is the Apollo Guidance Computer which was built exclusively from NOR gates. A logically inverted OR gate is a NOR gate and it can have two or more inputs.

10. Which of the following gates is used to implement a logical conditional?
a) OR gate
b) Magnetic logic gate
c) XOR gate
d) IMPLY gate

Answer: d
Clarification: The IMPLY gate is a digital logic gate that is used to implements logical conditional. Two symbols are used to represent the IMPLY gates → the traditional symbol and the IEEE symbol. IMPLY gate can be made by two memristors.

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⁵⁵.