COT 3100 Applications of Discrete
Structures
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1.
In graph theory, a connected graph has an Euler circuit if and only if
A) Every vertex has an even degree.
B) The graph is planar.
C) The graph is complete.
D) Every vertex has an odd degree.
ANS: A
Rationale: A classic theorem in graph theory states that a connected
graph possesses an Euler circuit if all of its vertices have even degrees.
This condition guarantees that every time you enter a vertex via an edge,
you can leave via another edge.
---
Question 2.
The chromatic number of a graph is defined as:
A) The number of vertices in the graph.
B) The minimum number of colors needed to color the vertices so that no
two adjacent vertices share the same color.
C) The maximum degree of any vertex.
D) The number of distinct cycles in the graph.
ANS: B
Rationale: The chromatic number is the least number of colors required
to color a graph's vertices such that adjacent vertices have different
colors—a fundamental concept in scheduling and resource allocation
problems.
---
Question 3.
Consider the recurrence relation
©2025
, T(n) = 2T(n/2) + n.
Using the Master Theorem, what is the time complexity of its solution?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
ANS: B
Rationale: The recurrence T(n) = 2T(n/2) + n fits the Master Theorem
with a = 2, b = 2, and f(n) = n. Since f(n) = Θ(n^(log_b a)), the solution is
T(n) = Θ(n log n).
---
Question 4.
A relation on a set is said to be a partial order if it is:
A) Reflexive, symmetric, and transitive
B) Reflexive, antisymmetric, and transitive
C) Symmetric and transitive only
D) Irreflexive and antisymmetric
ANS: B
Rationale: A partial order must satisfy reflexivity (each element relates
to itself), antisymmetry (if a is related to b and b to a, then a and b are
identical), and transitivity (if a relates to b and b relates to c, then a
relates to c).
---
Question 5.
Let p be an odd prime. An integer a (not divisible by p) is a quadratic
residue modulo p if and only if
A) a^((p–1)/2) ≡ 1 (mod p).
B) a^((p–1)/2) ≡ –1 (mod p).
C) There exists an integer x such that x^2 ≡ 0 (mod p).
©2025
Structures
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1.
In graph theory, a connected graph has an Euler circuit if and only if
A) Every vertex has an even degree.
B) The graph is planar.
C) The graph is complete.
D) Every vertex has an odd degree.
ANS: A
Rationale: A classic theorem in graph theory states that a connected
graph possesses an Euler circuit if all of its vertices have even degrees.
This condition guarantees that every time you enter a vertex via an edge,
you can leave via another edge.
---
Question 2.
The chromatic number of a graph is defined as:
A) The number of vertices in the graph.
B) The minimum number of colors needed to color the vertices so that no
two adjacent vertices share the same color.
C) The maximum degree of any vertex.
D) The number of distinct cycles in the graph.
ANS: B
Rationale: The chromatic number is the least number of colors required
to color a graph's vertices such that adjacent vertices have different
colors—a fundamental concept in scheduling and resource allocation
problems.
---
Question 3.
Consider the recurrence relation
©2025
, T(n) = 2T(n/2) + n.
Using the Master Theorem, what is the time complexity of its solution?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
ANS: B
Rationale: The recurrence T(n) = 2T(n/2) + n fits the Master Theorem
with a = 2, b = 2, and f(n) = n. Since f(n) = Θ(n^(log_b a)), the solution is
T(n) = Θ(n log n).
---
Question 4.
A relation on a set is said to be a partial order if it is:
A) Reflexive, symmetric, and transitive
B) Reflexive, antisymmetric, and transitive
C) Symmetric and transitive only
D) Irreflexive and antisymmetric
ANS: B
Rationale: A partial order must satisfy reflexivity (each element relates
to itself), antisymmetry (if a is related to b and b to a, then a and b are
identical), and transitivity (if a relates to b and b relates to c, then a
relates to c).
---
Question 5.
Let p be an odd prime. An integer a (not divisible by p) is a quadratic
residue modulo p if and only if
A) a^((p–1)/2) ≡ 1 (mod p).
B) a^((p–1)/2) ≡ –1 (mod p).
C) There exists an integer x such that x^2 ≡ 0 (mod p).
©2025
