-
web.groovymark@gmail.com
- November 15, 2024
Question 21
What is the degree sequence of a graph?
a) A list of vertex degrees in non-increasing order
b) A list of vertex degrees in non-decreasing order
c) The total number of edges in the graph
d) The total number of vertices in the graph
Correct Answer: a) A list of vertex degrees in non-increasing order
Explanation: The degree sequence of a graph is a list of the degrees of its vertices arranged in non-increasing order.
Question 22
What is an isomorphism between two graphs?
a) A one-to-one correspondence between the vertices and edges of two graphs that preserves adjacency
b) A transformation that reduces the number of vertices in one graph
c) A mapping that changes the direction of edges in a directed graph
d) A relation that allows for multiple edges between vertices
Correct Answer: a) A one-to-one correspondence between the vertices and edges of two graphs that preserves adjacency
Explanation: An isomorphism between two graphs is a mapping between their vertices and edges that preserves the adjacency relationships.
Question 23
What is the chromatic number of a graph?
a) The minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color
b) The total number of edges in the graph
c) The number of connected components in the graph
d) The number of cycles in the graph
Correct Answer: a) The minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color
Explanation: The chromatic number of a graph is the smallest number of colors required to color the vertices such that no two adjacent vertices are the same color.
Question 24
Which of the following describes a graph with a cut-vertex?
a) A graph where the removal of one vertex disconnects the graph
b) A graph where the removal of one edge disconnects the graph
c) A graph where every vertex is connected to every other vertex
d) A graph where no vertex has any edges
Correct Answer: a) A graph where the removal of one vertex disconnects the graph
Explanation: A cut-vertex is a vertex whose removal would disconnect the graph, splitting it into separate components.
Question 25
Which of the following describes a Hamiltonian cycle?
a) A cycle that visits every vertex of the graph exactly once and returns to the starting vertex
b) A path that visits every edge of the graph exactly once
c) A cycle that visits every edge of the graph exactly once
d) A path that visits every vertex of the graph exactly once but does not return to the starting vertex
Correct Answer: a) A cycle that visits every vertex of the graph exactly once and returns to the starting vertex
Explanation: A Hamiltonian cycle is a closed path that visits every vertex of a graph exactly once and returns to the starting vertex.
Question 26
Which of the following best describes the pigeonhole principle?
a) If more objects than containers are available, at least one container must hold more than one object
b) If fewer objects than containers are available, each container will hold one object
c) If more objects than containers are available, at least one object will be left out
d) If the same number of objects and containers are available, every container holds one object
Correct Answer: a) If more objects than containers are available, at least one container must hold more than one object
Explanation: The pigeonhole principle states that if more objects than containers are available, at least one container must hold more than one object.
Question 27
Which of the following describes an Euler path?
a) A path that visits every edge of a graph exactly once but does not necessarily return to the starting vertex
b) A path that visits every vertex of a graph exactly once
c) A path that visits every edge of a graph exactly once and returns to the starting vertex
d) A path that visits every vertex of a graph exactly once but does not return to the starting vertex
Correct Answer: a) A path that visits every edge of a graph exactly once but does not necessarily return to the starting vertex
Explanation: An Euler path is a path that visits every edge of a graph exactly once, but unlike an Euler circuit, it does not necessarily return to the starting vertex.
Question 28
Which of the following describes an equivalence class?
a) A subset of a set where all elements are equivalent under a given equivalence relation
b) A subset of a set where no elements are equivalent under a given relation
c) A subset of a set where all elements are distinct
d) A subset of a set where every element is related to every other element
Correct Answer: a) A subset of a set where all elements are equivalent under a given equivalence relation
Explanation: An equivalence class is a subset of a set where all elements are equivalent to each other under a given equivalence relation.
Question 29
What does it mean for a set to be countable?
a) A set is countable if it is finite or has the same cardinality as the natural numbers
b) A set is countable if it is infinite and has no upper bound
c) A set is countable if it has the same cardinality as the real numbers
d) A set is countable if it contains more elements than the natural numbers
Correct Answer: a) A set is countable if it is finite or has the same cardinality as the natural numbers
Explanation: A set is countable if it is either finite or if its elements can be put into one-to-one correspondence with the natural numbers.
Question 30
Which of the following best describes a binary relation from set A to set B?
a) A subset of the Cartesian product of A and B
b) A subset of A that includes elements from B
c) A function from A to B
d) A set of ordered pairs from B to A
Correct Answer: a) A subset of the Cartesian product of A and B
Explanation: A binary relation from set A to set B is a subset of the Cartesian product A×B, which consists of ordered pairs where the first element is from A and the second is from B.
Question 31
Which of the following is true for a function to be bijective?
a) It must be both injective and surjective
b) It must be neither injective nor surjective
c) It must be injective but not surjective
d) It must be surjective but not injective
Correct Answer: a) It must be both injective and surjective
Explanation: A bijective function is both injective (one-to-one) and surjective (onto), meaning every element of the domain maps to a unique element of the codomain, and all elements of the codomain are covered.
Question 32
What is the result of applying De Morgan’s law to the expression ¬(p∧q)\neg(p \land q)¬(p∧q)?
a) ¬p∨¬q
b) ¬p∧¬q
c) p∨q
d) ¬(p∨q)
Correct Answer: a) ¬p∨¬q
Explanation: De Morgan's law states that ¬(p∧q) is equivalent to ¬p∨¬q, which distributes the negation across the conjunction and changes it to a disjunction.
Question 33
Which of the following describes the associative property of Boolean algebra?
a) Rearranging the parentheses in an expression does not change the result
b) Changing the order of the terms in an expression does not change the result
c) Complementing both sides of an expression does not change the result
d) Adding the same term to both sides of an expression does not change the result
Correct Answer: a) Rearranging the parentheses in an expression does not change the result
Explanation: The associative property of Boolean algebra states that the result of a Boolean expression remains the same regardless of how the parentheses are arranged, as long as the operation remains the same.
Question 34
What does the absorption law in Boolean algebra state?
a) p∧(p∨q)=p
b) p∧(p∧q)=p
c) p∨(p∧q)=p
d) p∧(p∨q)=p∨q
Correct Answer: a) p∧(p∨q)=p
Explanation: The absorption law in Boolean algebra states that p∧(p∨q) is equal to p, meaning that the term p "absorbs" the disjunction with q.
Question 35
Which of the following describes a simple graph?
a) A graph with no loops or parallel edges
b) A graph with loops but no parallel edges
c) A graph with parallel edges but no loops
d) A graph where all vertices are adjacent
Correct Answer: a) A graph with no loops or parallel edges
Explanation: A simple graph is a graph that has no loops (edges that connect a vertex to itself) and no parallel edges (multiple edges connecting the same pair of vertices).
Question 36
What does the principle of strong mathematical induction involve?
a) Assuming the statement is true for all previous cases up to the current one and proving it for the next case
b) Assuming the statement is true for only the first case and proving it for the next case
c) Proving a statement by dividing the domain into multiple cases
d) Proving a statement by assuming the negation and deriving a contradiction
Correct Answer: a) Assuming the statement is true for all previous cases up to the current one and proving it for the next case
Explanation: Strong mathematical induction involves assuming that the statement is true for all previous cases up to the current one, and then proving it for the next case.
Question 37
Which of the following is true for a minimal element in a partially ordered set?
a) There is no other element in the set that is smaller
b) There is no other element in the set that is larger
c) It is the only element in the set
d) It is the largest element in the set
Correct Answer: a) There is no other element in the set that is smaller
Explanation: A minimal element in a partially ordered set is one for which there is no other element in the set that is smaller in the ordering.
Question 38
Which of the following best describes a matrix product?
a) The dot product of each row of the first matrix with each column of the second matrix
b) The sum of each row of the first matrix and each column of the second matrix
c) The difference of each row of the first matrix and each column of the second matrix
d) The division of each row of the first matrix by each column of the second matrix
Correct Answer: a) The dot product of each row of the first matrix with each column of the second matrix
Explanation: The matrix product involves taking the dot product of each row in the first matrix with each column in the second matrix to form the resulting matrix.
Question 39
Which of the following best describes a diagonal matrix?
a) A matrix where all non-diagonal elements are zero
b) A matrix where all diagonal elements are zero
c) A matrix where all rows are identical
d) A matrix where all columns are identical
Correct Answer: a) A matrix where all non-diagonal elements are zero
Explanation: A diagonal matrix is a square matrix in which all the elements not on the main diagonal are zero.
Question 40
What is the identity matrix?
a) A diagonal matrix where all diagonal elements are 1
b) A diagonal matrix where all diagonal elements are 0
c) A matrix where all elements are 1
d) A matrix where all elements are 0
Correct Answer: a) A diagonal matrix where all diagonal elements are 1
Explanation: The identity matrix is a diagonal matrix in which all the diagonal elements are 1, and all other elements are 0.
