50 multiple-choice questions with answers and detailed explanations. Untimed — choose an answer to check it instantly.
0/50 answered0 correct
Question 1 of 50
What does the term “bijection” mean in the context of functions?
Correct answer: A) A function that is both injective and surjective
Explanation: A bijection is a function that 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 2 of 50
Which of the following is true for a function to be injective?
Correct answer: A) Distinct elements in the domain map to distinct elements in the codomain
Explanation: A function is injective if every distinct element in the domain maps to a distinct element in the codomain, meaning no two elements in the domain map to the same element in the codomain.
Question 3 of 50
What is the composition of two functions, f and g ?
Correct answer: A) The application of g followed by f
Explanation: The composition of two functions, denoted f(g(x)), involves applying function g first and then applying function f to the result of g.
Question 4 of 50
Which of the following is a property of a surjective function?
Correct answer: A) Every element in the codomain is mapped by at least one element in the domain
Explanation: A function is surjective (onto) if every element in the codomain is the image of at least one element from the domain.
Question 5 of 50
Which of the following statements about a function’s inverse is true?
Correct answer: A) The inverse undoes the effect of the original function
Explanation: A function's inverse undoes the effect of the original function, meaning that applying the function and then applying its inverse will return the original input.
Question 6 of 50
Which of the following is true for a function to have an inverse?
Correct answer: A) The function must be both injective and surjective
Explanation: For a function to have an inverse, it must be bijective, meaning it is both injective (one-to-one) and surjective (onto).
Question 7 of 50
Which of the following describes a predicate?
Correct answer: A) A logical statement whose truth value depends on one or more variables
Explanation: A predicate is a logical statement that involves variables, and its truth value depends on the values assigned to those variables.
Question 8 of 50
Which of the following is true for a relation to be an equivalence relation?
Correct answer: A) It must be reflexive, symmetric, and transitive
Explanation: An equivalence relation is a relation that is reflexive, symmetric, and transitive, meaning it satisfies these three properties.
Question 9 of 50
What is the difference between a reflexive and irreflexive relation?
Correct answer: A) A reflexive relation includes self-loops for every element, while an irreflexive relation has no self-loops
Explanation: A reflexive relation includes self-loops for every element in the set, while an irreflexive relation has no self-loops for any element.
Question 10 of 50
Which of the following is a key characteristic of a symmetric relation?
Correct answer: A) If a is related to b, then b is related to a
Explanation: A relation is symmetric if whenever one element is related to another, the reverse relation also holds.
Question 11 of 50
Which of the following describes an antisymmetric relation?
Correct answer: A) If a is related to b and b is related to a, then a=b
Explanation: A relation is antisymmetric if for all elements a and b, if a is related to b and b is related to a, then a=b.
Question 12 of 50
Which of the following describes the property of transitivity in a relation?
Correct answer: A) If a is related to b, and b is related to c, then a is related to c
Explanation: A relation is transitive if, whenever a is related to b and b is related to c, it follows that a is related to c.
Question 13 of 50
Which of the following describes a directed graph?
Correct answer: A) A graph where edges have a direction from one vertex to another
Explanation: A directed graph, also known as a digraph, has edges with directions, meaning that an edge from vertex a to vertex b is not necessarily the same as an edge from b to a.
Question 14 of 50
Which of the following is a property of an undirected graph?
Correct answer: A) All edges have no direction, meaning connections between vertices are mutual
Explanation: In an undirected graph, the edges do not have a direction, so if there is an edge between two vertices, the connection is mutual.
Question 15 of 50
Which of the following is true about a cycle in graph theory?
Correct answer: A) It is a path that starts and ends at the same vertex with no repeated edges
Explanation: In graph theory, a cycle is a path that starts and ends at the same vertex without repeating any edges.
Question 16 of 50
Which of the following best describes a walk in graph theory?
Correct answer: A) A sequence of vertices connected by edges, where vertices and edges can be repeated
Explanation: A walk in graph theory is a sequence of vertices and edges where both vertices and edges can be repeated.
Question 17 of 50
Which of the following is true for a spanning tree?
Correct answer: A) It is a subgraph that contains all vertices of the original graph and is acyclic
Explanation: A spanning tree is a subgraph that contains all the vertices of the original graph, but it has no cycles.
Question 18 of 50
What is a leaf in a tree graph?
Correct answer: A) A vertex with no children
Explanation: In a tree graph, a leaf is a vertex that has no children, meaning it has no further vertices connected to it.
Question 19 of 50
What is the height of a tree graph?
Correct answer: A) The number of edges from the root to the deepest leaf
Explanation: The height of a tree graph is the length of the longest path from the root to any leaf, measured in the number of edges.
Question 20 of 50
What does it mean for a graph to be k-vertex connected?
Correct answer: A) The graph remains connected even after any k−1 vertices are removed
Explanation: A graph is k-vertex connected if it remains connected after any k−1 vertices are removed, meaning it is resilient to the removal of vertices.
Question 21 of 50
What is the degree sequence of a 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 of 50
What is an isomorphism between two graphs?
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 of 50
What is the chromatic number of a 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 of 50
Which of the following describes a graph with a cut-vertex?
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 of 50
Which of the following describes a Hamiltonian cycle?
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 of 50
Which of the following best describes the pigeonhole principle?
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 of 50
Which of the following describes an Euler path?
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 of 50
Which of the following describes an equivalence class?
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 of 50
What does it mean for a set to be countable?
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 of 50
Which of the following best describes a binary relation from set A to set B?
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 of 50
Which of the following is true for a function to be bijective?
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 of 50
What is the result of applying De Morgan’s law to the expression ¬(p∧q)\neg(p \land q)¬(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 of 50
Which of the following describes the associative property of Boolean algebra?
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 of 50
What does the absorption law in Boolean algebra state?
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 of 50
Which of the following describes a simple graph?
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 of 50
What does the principle of strong mathematical induction involve?
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 of 50
Which of the following is true for a minimal element in a partially ordered 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 of 50
Which of the following best describes a matrix product?
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 of 50
Which of the following best describes a diagonal matrix?
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 of 50
What is the identity matrix?
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.
Question 41 of 50
Which of the following is true for a square matrix to be invertible?
Correct answer: A) It must have a non-zero determinant
Explanation: A square matrix is invertible if and only if its determinant is non-zero, meaning it has a unique inverse matrix.
Question 42 of 50
Which of the following best describes a singular matrix?
Correct answer: A) A matrix that has no inverse
Explanation: A singular matrix is a square matrix that does not have an inverse, typically because its determinant is zero.
Question 43 of 50
What is Gaussian elimination used for?
Correct answer: A) Solving systems of linear equations by reducing a matrix to row echelon form
Explanation: Gaussian elimination is a method used to solve systems of linear equations by reducing a matrix to row echelon form through a series of row operations.
Question 44 of 50
What is the pigeonhole principle used for in combinatorics?
Correct answer: A) Proving that if more items than containers are available, at least one container must contain more than one item
Explanation: The pigeonhole principle is used to demonstrate that if there are more items than containers, at least one container must hold more than one item.
Question 45 of 50
Which of the following best describes a path in graph theory?
Correct answer: A) A sequence of vertices connected by edges, with no repeated vertices
Explanation: A path in graph theory is a sequence of vertices connected by edges, where no vertices are repeated.
Question 46 of 50
Which of the following describes a non-connected graph?
Correct answer: A) A graph where there is at least one vertex that cannot be reached from any other vertex
Explanation: A non-connected graph contains at least one vertex that cannot be reached from any other vertex, indicating the presence of separate components.
Question 47 of 50
What is the primary use of a depth-first search (DFS) algorithm in graph theory?
Correct answer: C) To explore as far as possible along each branch before backtracking
Explanation: Depth-first search (DFS) is used to explore a graph by going as deep as possible down one path before backtracking, effectively visiting vertices and edges in a depthward motion.
Question 48 of 50
Which of the following is true for a breadth-first search (BFS) algorithm?
Correct answer: A) It explores the graph layer by layer, visiting all neighbors at the present depth before moving on
Explanation: Breadth-first search (BFS) explores a graph by visiting all vertices at the current depth level before moving on to vertices at the next depth level, effectively traversing the graph in a layer-by-layer fashion.
Question 49 of 50
In the context of graph theory, what is a clique?
Correct answer: A) A subset of vertices such that every two distinct vertices are adjacent
Explanation: In graph theory, a clique is defined as a subset of vertices in which every two distinct vertices are adjacent, meaning there is an edge connecting every pair of vertices within the clique.
Question 50 of 50
Which of the following statements about trees is true?
Correct answer: A) A tree is a connected graph with no cycles
Explanation: A tree is defined as a connected graph that does not contain any cycles, making it a special type of acyclic graph.
Set 5 complete
You scored 0%
0 correct out of 0 answered (50 questions in this set).