-
web.groovymark@gmail.com
- November 9, 2024
Question 21
What is a complete graph?
a) A graph where each vertex is connected to every other vertex
b) A graph where each vertex has at least two neighbors
c) A graph with no edges
d) A graph with parallel edges
Correct Answer: a) A graph where each vertex is connected to every other vertex
Explanation: A complete graph is one where every vertex is directly connected to every other vertex.
Question 22
What is the degree of a vertex in a graph?
a) The number of edges coming from it
b) The number of vertices in the graph
c) The number of loops in the graph
d) The number of paths in the graph
Correct Answer: a) The number of edges coming from it
Explanation: The degree of a vertex is the number of edges that are connected to it.
Question 23
Which of the following represents a bipartite graph?
a) A graph that can be divided into two groups, where no vertices in the same group are connected
b) A graph where every vertex is connected to every other vertex
c) A graph with parallel edges
d) A graph with loops
Correct Answer: a) A graph that can be divided into two groups, where no vertices in the same group are connected
Explanation: In a bipartite graph, the vertices can be split into two groups such that edges only connect vertices from different groups.
Question 24
What is the significance of Euler’s circuit in graph theory?
a) It is a circuit that visits every edge exactly once
b) It is a circuit that visits every vertex exactly once
c) It is a circuit that starts and ends at the same vertex
d) It is a circuit that does not repeat any vertex
Correct Answer: a) It is a circuit that visits every edge exactly once
Explanation: An Euler circuit is a closed path in a graph that travels along each edge exactly once.
Question 25
What is the Pigeonhole Principle?
a) If n items are put into m containers and n>m, then at least one container must contain more than one item
b) If n items are put into m containers and n=m, then all containers contain the same number of items
c) If n items are put into m containers and n<m, then all containers are empty
d) If n items are put into m containers, then at least one container must contain exactly one item
Correct Answer: a) If n items are put into m containers and n>m, then at least one container must contain more than one item
Explanation: The Pigeonhole Principle states that when there are more items than containers, at least one container must hold more than one item.
Question 26
Which of the following is true for a Boolean complement?
a) The complement of 1 is 1
b) The complement of 1 is 0
c) The complement of 0 is 0
d) The complement of 1 is undefined
Correct Answer: b) The complement of 1 is 0
Explanation: In Boolean algebra, the complement of 1 is 0, and the complement of 0 is 1.
Question 27
Which Boolean operation corresponds to the logical AND operation?
a) Boolean addition
b) Boolean multiplication
c) Boolean complement
d) Boolean XOR
Correct Answer: b) Boolean multiplication
Explanation: Boolean multiplication corresponds to the logical AND operation, where the result is true only if both operands are true.
Question 28
What is the Boolean exclusive OR (XOR) operation?
a) True when both inputs are true
b) False when both inputs are true
c) True when inputs have the same value
d) True when both inputs are false
Correct Answer: b) False when both inputs are true
Explanation: The XOR operation is true when the inputs differ and false when the inputs are the same.
Question 29
Which of the following best describes a conjunctive normal form (CNF)?
a) The product of sums of literals
b) The sum of products of literals
c) The negation of a product of literals
d) A Boolean expression with no complements
Correct Answer: a) The product of sums of literals
Explanation: In conjunctive normal form, a Boolean expression is represented as the product of sums of literals.
Question 30
Which of the following is true for a tautology in Boolean algebra?
a) The expression is always true
b) The expression is always false
c) The expression is true only when all variables are true
d) The expression is true only when all variables are false
Correct Answer: a) The expression is always true
Explanation: A tautology in Boolean algebra is an expression that is always true, regardless of the values of the variables.
Question 31
Which of the following is a method used to simplify Boolean expressions?
a) Pigeonhole Principle
b) De Morgan’s Law
c) Euler’s Theorem
d) Kruskal’s Algorithm
Correct Answer: b) De Morgan's Law
Explanation: De Morgan's Law is used to simplify Boolean expressions by transforming the negation of conjunctions and disjunctions.
Question 32
Which of the following statements is true for Kruskal’s algorithm?
a) It finds a minimum spanning tree by adding increasing cost arcs
b) It finds a shortest path between two vertices
c) It finds an Euler circuit in a graph
d) It finds a Hamiltonian path in a graph
Correct Answer: a) It finds a minimum spanning tree by adding increasing cost arcs
Explanation: Kruskal's algorithm is a greedy algorithm that finds the minimum spanning tree of a graph by adding edges in increasing order of cost.
Question 33
What is the result of adding two Boolean variables using Boolean addition?
a) The product of the variables
b) The exclusive OR of the variables
c) The logical OR of the variables
d) The logical AND of the variables
Correct Answer: c) The logical OR of the variables
Explanation: Boolean addition corresponds to the logical OR operation, where the result is true if at least one of the variables is true.
Question 34
What is the purpose of an adjacency matrix in graph theory?
a) To represent the degree of each vertex
b) To represent the edges between vertices in a graph
c) To calculate the shortest path between vertices
d) To find the Euler circuit in a graph
Correct Answer: b) To represent the edges between vertices in a graph
Explanation: An adjacency matrix is used to represent a graph by showing which pairs of vertices are connected by edges.
Question 35
Which of the following describes a matrix product in terms of dot product?
a) The dot product of row i from matrix A with column j from matrix B
b) The sum of all rows from matrix A
c) The product of matrix A and the transpose of matrix B
d) The inverse of matrix A
Correct Answer: a) The dot product of row i from matrix A with column j from matrix B
Explanation: The matrix product is computed by taking the dot product of rows from one matrix and columns from another.
Question 36
Which of the following is a characteristic of an injective function?
a) Every element in the domain maps to exactly one element in the codomain
b) Every element in the codomain has at least one element mapped to it
c) Each element in the domain maps to a unique element in the codomain
d) Each element in the codomain maps to a unique element in the domain
Correct Answer: c) Each element in the domain maps to a unique element in the codomain
Explanation: An injective function ensures that no two distinct elements in the domain map to the same element in the codomain.
Question 37
Which of the following is a bijective function?
a) A function that is neither injective nor surjective
b) A function that is injective and surjective
c) A function that is injective but not surjective
d) A function that is surjective but not injective
Correct Answer: b) A function that is injective and surjective
Explanation: A bijective function is both injective (one-to-one) and surjective (onto), meaning every element in the domain maps to a unique element in the codomain, and every element in the codomain is mapped.
Question 38
Which of the following is true for a surjective function?
a) Every element in the codomain has exactly one preimage
b) Every element in the codomain has at least one preimage
c) Every element in the domain has at least one image
d) Every element in the domain has exactly one image
Correct Answer: b) Every element in the codomain has at least one preimage
Explanation: A surjective function ensures that every element in the codomain is the image of at least one element from the domain.
Question 39
What is the range of a function?
a) The set of all elements in the codomain
b) The set of all elements in the domain
c) The set of all images of the elements in the domain
d) The set of all elements that are not in the codomain
Correct Answer: c) The set of all images of the elements in the domain
Explanation: The range of a function is the set of all images (outputs) of the elements in the domain.
Question 40
Which of the following describes the Principle of Mathematical Induction?
a) If a statement is true for a base case and holds for n+1 when it holds for n, then it is true for all n
b) If a statement is true for a base case, then it is true for all n
c) If a statement holds for one value of n, it holds for all values of n
d) If a statement is true for n+1, then it holds for n
Correct Answer: a) If a statement is true for a base case and holds for n+1 when it holds for n, then it is true for all n
Explanation: The Principle of Mathematical Induction is used to prove statements for all natural numbers by showing that the base case holds and that the statement holds for n+1 when it holds for nnn.
