Discrete Mathematics Quizzes: Test Your Knowledge

Question 1

Which of the following is a necessary condition for a graph to be bipartite?

Accepted Answer

The graph must be able to be colored with only two colors

Answer

The graph must be connected

Answer

The graph must have an odd number of vertices

Question 2

A tree is a connected graph with n vertices. How many edges does it have?

Accepted Answer

n-1

Answer

n

Answer

n+1

Answer

2n

Question 3

Which concept is NOT a core pillar of discrete mathematics?

Accepted Answer

Calculus

Answer

Logic

Answer

Set Theory

Answer

Graph Theory

Question 4

Which logical connective symbolizes the logical operation 'AND'?

Accepted Answer

AND

Answer

NOT

Answer

OR

Answer

IMPLIES

Question 5

In graph theory, what is the relationship between the number of vertices (n) and edges (m) in a graph?

Accepted Answer

m is less than or equal to n

Answer

n is equal to m

Answer

n is greater than m

Answer

n is less than or equal to m

Question 6

Which combinatorial principle determines the number of ways to select r distinct objects from a set of n distinct objects, without replacement?

Accepted Answer

Combination principle

Answer

Fundamental counting principle

Answer

Permutation principle

Answer

Pigeonhole principle

Question 7

Which graph traversal algorithm is utilized to find the shortest path between two vertices in a weighted graph?

Accepted Answer

Dijkstra's algorithm

Answer

Breadth-first search (BFS)

Answer

Depth-first search (DFS)

Answer

Bellman-Ford algorithm

Question 8

The number of ways to select 5 objects from a set of 10 distinct objects is given by:

Accepted Answer

10P5

Answer

5!

Answer

10!

Answer

5P10

Question 9

The negation of the statement 'All students are engineers' is:

Accepted Answer

No students are engineers

Answer

Some students are engineers

Answer

All engineers are students

Answer

Some engineers are students

Question 10

A tree with n vertices has:

Accepted Answer

n-1 edges

Answer

n edges

Answer

n+1 edges

Answer

2n edges

Question 11

Which of the following is a valid mathematical induction step?

Accepted Answer

Assume P(k) is true, then prove P(k+1) is true

Answer

Assume P(k+1) is true, then prove P(k) is true

Answer

Assume P(k) is true, then prove P(k) is false

Answer

Assume P(k+1) is false, then prove P(k) is true

Question 12

In set theory, a set with no elements is called a:

Accepted Answer

Empty set

Answer

Finite set

Answer

Infinite set

Answer

Universal set

Question 13

In graph theory, the number of edges connected to a vertex is known as its:

Accepted Answer

Degree

Answer

Order

Answer

Weight

Answer

Size

Question 14

Which counting technique is used to calculate the number of ways to select a subset of objects from a set, without regard to order, and without replacement?

Accepted Answer

Combination

Answer

Permutation

Answer

Cross-multiplication

Answer

Factorial

Question 15

In a directed graph, an edge that starts and ends at the same vertex is called a:

Accepted Answer

Loop

Answer

Chain

Answer

Bridge

Answer

Cycle

Question 16

Which of the following logical equivalences is **not** valid?

Accepted Answer

P ∨ (Q → R) ≡ (P ∨ Q) → R

Answer

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

Answer

(P → Q) ≡ (¬P ∨ Q)

Answer

¬(P ↔ Q) ≡ (P → ¬Q) ∧ (¬P → Q)

Question 17

Which of the following counting techniques is used to calculate the number of ways to select r objects from a set of n distinct objects, **without** replacement?

Accepted Answer

Combination

Answer

Permutation

Answer

Variation

Answer

Factorial

Question 18

What is the minimum number of edges that a simple graph with n vertices must have to be connected?

Accepted Answer

n - 1

Answer

n

Answer

n + 1

Answer

2n

Question 19

Which of the following is an example of a **continuous** probability distribution?

Accepted Answer

Exponential distribution

Answer

Binomial distribution

Answer

Poisson distribution

Answer

Chi-squared distribution

Question 20

Consider the set S = {a, b, c}. What is the cardinality of the power set of S?

Accepted Answer

6

Answer

3

Answer

8

Answer

12

Question 21

Which of the following graphs has a chromatic number of 3?

Accepted Answer

Star graph S4

Answer

Complete graph K4

Answer

Cycle graph C5

Answer

Wheel graph W5

Question 22

Consider the statement 'If it is raining, then the streets are wet.' Which of the following is the contrapositive of this statement?

Accepted Answer

If the streets are not wet, then it is not raining

Answer

If it is not raining, then the streets are not wet

Answer

If it is raining, then the streets are dry

Answer

If the streets are wet, then it is raining

Question 23

Which of the following is a valid Hamiltonian cycle in graph theory?

Accepted Answer

A cycle that visits every vertex in a graph exactly once

Answer

A cycle that visits every vertex in a graph at least once

Answer

A cycle that does not repeat any edges

Answer

A cycle that starts and ends at the same vertex

Question 24

Given the statement "If x is even, then x is divisible by 2," which of the following is the contrapositive?

Accepted Answer

If x is not even, then x is not divisible by 2.

Answer

If x is divisible by 2, then x is even.

Answer

If x is not divisible by 2, then x is not even.

Answer

If x is odd, then x is divisible by 2.

Question 25

How many different 5-element subsets can be formed from a set with 10 elements?

Accepted Answer

252

Answer

120

Answer

210

Answer

302

Question 26

Which of the following is a characteristic of a bipartite graph?

Accepted Answer

It can be divided into two sets of vertices such that no two vertices in the same set are adjacent.

Answer

It has at least one cycle.

Answer

It is a connected graph.

Answer

It is a regular graph.

Question 27

What is the truth table value of the following expression: (P ∨ Q) → ¬R, given that P is true, Q is false, and R is true?

Accepted Answer

True

Answer

False

Answer

Cannot be determined

Question 28

What is the time complexity of a nested loop that iterates over n elements in the outer loop and m elements in the inner loop?

Accepted Answer

O(n × m)

Answer

O(n)

Answer

O(m)

Answer

O(n + m)

Question 29

Which operation is not applicable to sets?

Accepted Answer

Multiplication

Answer

Union

Answer

Intersection

Answer

Complement

Question 30

Which of the following is considered a valid way to colour a graph?

Accepted Answer

Each vertex is assigned a unique colour.

Answer

Each edge is assigned a unique colour.

Answer

Each connected component is assigned a unique colour.

Answer

Each cycle is assigned a unique colour.

Question 31

Which type of probability distribution is commonly used in discrete scenarios?

Accepted Answer

Binomial distribution

Answer

Normal distribution

Answer

Exponential distribution

Answer

Uniform distribution

Question 32

Which characteristic is essential to a finite state machine?

Accepted Answer

A finite number of states

Answer

Handling an infinite number of inputs

Answer

Generating an infinite number of outputs

Answer

Being Turing-complete

Question 33

Which limitation is inherent to discrete mathematics?

Accepted Answer

It cannot model continuous processes.

Answer

It can only handle finite sets.

Answer

It has no real-world applications.

Answer

It requires advanced mathematical knowledge.

Question 34

Which of the following is an example of a complete graph?

Accepted Answer

A graph with n vertices and n(n-1)/2 edges

Answer

A graph with n vertices and n edges

Answer

A graph with n vertices and n-1 edges

Question 35

What is the cardinality of the set of all subsets of a set with n elements?

Accepted Answer

2^n

Answer

n

Answer

n^2

Answer

2^(n-1)

Question 36

Which of the following best defines a bijection?

Accepted Answer

A function that maps each element of a set to a unique element of another set, and vice versa.

Answer

A function that maps each element of a set to a unique element of another set.

Answer

A function that maps each element of a set to any element of another set.

Answer

A function that maps each element of a set to a unique element of another set, but not vice versa.

Question 37

What is the cardinality of the power set of a set with n elements?

Accepted Answer

2^n

Answer

n

Answer

n^2

Answer

n!

Question 38

Which of the following is a tree?

Accepted Answer

A connected graph with no cycles.

Answer

A graph with exactly one cycle.

Answer

A graph with at least two cycles.

Answer

A graph with no vertices.

Question 39

What is the formula for the number of ways to select r objects from a set of n objects without replacement?

Accepted Answer

C(n, r)

Answer

P(n, r)

Answer

P(r, n)

Answer

C(r, n)

Question 40

Which of the following is a Hamiltonian cycle?

Accepted Answer

A cycle that visits every vertex in a graph exactly once.

Answer

A cycle that visits every vertex in a graph at least once.

Answer

A cycle that visits some vertices in a graph more than once.

Answer

A path that visits every vertex in a graph exactly once.

Question 41

When is mathematical induction a valid method of proof?

Accepted Answer

To prove that a statement is true for all positive integers.

Answer

To prove that a statement is true for the first few positive integers.

Answer

To disprove a statement by finding a single counterexample.

Answer

To guess a formula for the nth term of a sequence.

Question 42

In a disconnected graph, what defines a connected component?

Accepted Answer

A subgraph where a path exists between any two vertices.

Answer

The smallest subgraph containing all the graph's edges.

Answer

The largest subgraph isolated from all other subgraphs.

Question 43

Given a finite set X with n elements, how many distinct functions can be defined from X to the set {0, 1}?

Accepted Answer

2^n

Answer

n

Answer

n^2

Answer

2

Question 44

Which type of graph has all its vertices connected by at most one edge?

Accepted Answer

Simple graph

Answer

Complete graph

Answer

Directed graph

Answer

Weighted graph

Question 45

Which of these is NOT a standard set operation?

Accepted Answer

Multiplication

Answer

Union

Answer

Intersection

Answer

Complement

Question 46

Which operation is NOT applicable to sets?

Accepted Answer

Multiplication

Answer

Union

Answer

Intersection

Answer

Complement

Question 47

Which function is bijective?

Accepted Answer

f(x) = 2x + 1

Answer

f(x) = x^2

Answer

f(x) = |x|

Answer

f(x) = sin(x)

Question 48

What is the definition of the intersection of sets A and B?

Accepted Answer

The intersection of sets A and B contains elements that are in both A and B.

Answer

The intersection of sets A and B includes elements that are in either A or B.

Answer

The intersection of sets A and B consists of elements that are not in either A or B.

Answer

The intersection of sets A and B always results in an empty set.

Question 49

Which of the following is NOT a valid logical operator?

Accepted Answer

EX-OR

Answer

AND

Answer

OR

Answer

NOT

Question 50

Which of the following is a necessary condition for a set to be a power set?

Accepted Answer

It contains all subsets of the original set

Answer

It has the same number of elements as the original set

Answer

It is a subset of the original set

Answer

It is the union of all subsets of the original set

Question 51

Which of the following is a proof technique that involves showing that if a statement is false, then a contradiction arises?

Accepted Answer

Proof by contradiction

Answer

Mathematical induction

Answer

Direct proof

Answer

Constructive proof

Question 52

In a graph with n vertices and m edges, what is the maximum possible number of edges?

Accepted Answer

n(n-1)/2

Answer

n^3

Answer

n^2

Answer

n

Question 53

Which of the following is a Hamiltonian path?

Accepted Answer

A path that visits every vertex of a graph exactly once.

Answer

A path that visits some vertices of a graph more than once.

Answer

A path that visits every vertex of a graph at least once.

Question 54

What is the recurrence relation for the Fibonacci sequence?

Accepted Answer

F(n) = F(n-1) + F(n-2)

Answer

F(n) = F(n-1)^2

Answer

F(n) = F(n-1) - F(n-2)

Answer

F(n) = 2F(n-1)

Question 55

Which of the following is an application of discrete mathematics in computer science?

Accepted Answer

Design of algorithms

Answer

Linear algebra

Answer

Probability and statistics

Answer

Calculus

Question 56

Which of the following is the complement of the set {1, 3, 5} in the universal set {1, 2, 3, 4, 5, 6}?

Accepted Answer

{2, 4, 6}

Answer

{3, 4, 5}

Answer

{1, 2, 3}

Answer

{1, 2, 4}

Question 57

Which of the following is the probability of rolling a 6 on a fair six-sided die?

Accepted Answer

1/6

Answer

1/3

Answer

1/2

Answer

1/4

Question 58

Which of the following is a property of a Hamiltonian path?

Accepted Answer

Visits each vertex exactly once

Answer

Does not visit any vertex more than once (property of Eulerian path)

Answer

Does not visit any edge more than once (property of Eulerian path)

Answer

Visits each edge exactly once (property of Eulerian circuit)

Question 59

Which of the following is the cardinality of the power set of a set with n elements?

Accepted Answer

2^n

Answer

n

Answer

n!

Answer

n^2

Question 60

Which of the following is a valid algorithm design paradigm?

Accepted Answer

Divide and Conquer

Answer

Random Guessing (not a paradigm, it's an ineffective approach)

Answer

Brute Force (not a paradigm, it's a simple approach)

Answer

Trial and Error (not a paradigm, it's an ineffective approach)

Question 61

Which of the following is the chromatic number of a graph with k independent sets?

Accepted Answer

k

Answer

k+1 (not a valid chromatic number)

Answer

k-1 (not a valid chromatic number)

Answer

2k (chromatic number of a bipartite graph)

Question 62

Which of the following is NOT a fundamental concept of discrete mathematics?

Accepted Answer

Calculus

Answer

Combinatorics

Answer

Set theory

Answer

Graph theory

Question 63

Which of the following is a subset of the set of all even numbers?

Accepted Answer

The set of all multiples of 6

Answer

The set of all rational numbers

Answer

The set of all negative integers

Answer

The set of all prime numbers

Question 64

Which of the following is a definition of a Hamiltonian path in graph theory?

Accepted Answer

A path that visits every vertex of a graph exactly once.

Answer

A path that uses every edge of a graph.

Answer

A path that starts and ends at the same vertex.