-
web.groovymark@gmail.com
- November 15, 2024
Question 21
Which of the following is true for the adjacency matrix of an undirected graph?
a) It is symmetric
b) It is always invertible
c) It is diagonal
d) It has all elements equal to zero
Correct Answer: a) It is symmetric
Explanation: The adjacency matrix of an undirected graph is symmetric because the graph has undirected edges, meaning the edge from A to B is the same as the edge from B to A.
Question 22
What is the degree of a vertex in a graph?
a) The number of edges incident to the vertex
b) The number of vertices adjacent to the vertex
c) The number of loops in the graph
d) The number of vertices in the graph
Correct Answer: a) The number of edges incident to the vertex
Explanation: The degree of a vertex is the number of edges that are incident to it, representing how many edges connect to that vertex.
Question 23
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 with both loops and parallel edges
Correct Answer: a) A graph with no loops or parallel edges
Explanation: A simple graph is a graph that contains no loops (edges that connect a vertex to itself) and no parallel edges (multiple edges connecting the same pair of vertices).
Question 24
What does the term “isolated vertex” refer to in graph theory?
a) A vertex that is not connected to any other vertex
b) A vertex that is connected to all other vertices
c) A vertex that has exactly one neighbor
d) A vertex that is part of a cycle
Correct Answer: a) A vertex that is not connected to any other vertex
Explanation: An isolated vertex is a vertex that has no edges connecting it to any other vertices in the graph.
Question 25
Which of the following describes an Euler circuit?
a) A circuit that visits every edge of a graph exactly once and returns to the starting vertex
b) A path that visits every vertex of a graph exactly once
c) A cycle that visits every vertex of a graph exactly once
d) A path that visits every edge of a graph exactly once but does not return to the starting vertex
Correct Answer: a) A circuit that visits every edge of a graph exactly once and returns to the starting vertex
Explanation: An Euler circuit is a closed path that visits every edge of a graph exactly once and returns to the starting vertex.
Question 26
Which of the following describes a Hamiltonian path?
a) A path that visits every vertex of a graph exactly once
b) A path that visits every edge of a graph exactly once
c) A path that starts and ends at the same vertex
d) A path that has no repeated vertices or edges
Correct Answer: a) A path that visits every vertex of a graph exactly once
Explanation: A Hamiltonian path is a path that visits every vertex of a graph exactly once without revisiting any vertices.
Question 27
Which of the following is a key property of a bipartite graph?
a) Its vertex set can be divided into two disjoint sets such that no two vertices within the same set are adjacent
b) It contains exactly two cycles
c) It contains parallel edges between two vertices
d) It has an equal number of edges and vertices
Correct Answer: a) Its vertex set can be divided into two disjoint sets such that no two vertices within the same set are adjacent
Explanation: A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
Question 28
What does the Pigeonhole Principle state?
a) If n+1 or more objects are placed into n boxes, at least one box must contain more than one object
b) If n+1 or more objects are placed into n boxes, each box will contain exactly one object
c) If n objects are placed into n+1 boxes, at least one box will contain more than one object
d) If n objects are placed into n+1 boxes, each box will contain at least one object
Correct Answer: a) If n+1 or more objects are placed into n boxes, at least one box must contain 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 29
Which of the following is true for a permutation of a set?
a) It is an ordered arrangement of all elements in the set
b) It is an unordered selection of elements from the set
c) It is a subset of the set
d) It is a multiset where elements may repeat
Correct Answer: a) It is an ordered arrangement of all elements in the set
Explanation: A permutation of a set is an ordered arrangement of all the elements in the set.
Question 30
Which of the following describes an r-combination of a set?
a) An unordered selection of r elements from the set
b) An ordered arrangement of r elements from the set
c) A subset of the set
d) A multiset where elements may repeat
Correct Answer: a) An unordered selection of rrr elements from the set
Explanation: An r-combination of a set is an unordered selection of r elements from the set, where order does not matter.
Question 31
Which of the following describes a power set?
a) The set of all subsets of a given set
b) The set of all elements in a universal set
c) The set of all proper subsets of a given set
d) The set of all ordered pairs in a Cartesian product
Correct Answer: a) The set of all subsets of a given set
Explanation: The power set of a set is the set of all its subsets, including the empty set and the set itself.
Question 32
Which of the following describes the union of two sets?
a) The set of all elements that are in either set or in both sets
b) The set of elements that are in both sets
c) The set of elements that are in the first set but not the second set
d) The set of elements that are in the second set but not the first set
Correct Answer: a) The set of all elements that are in either set or in both sets
Explanation: The union of two sets is the set of all elements that are in either set or in both sets.
Question 33
Which of the following describes the intersection of two sets?
a) The set of elements that are in both sets
b) The set of elements that are in either set
c) The set of elements that are in the first set but not the second set
d) The set of elements that are in the second set but not the first set
Correct Answer: a) The set of elements that are in both sets
Explanation: The intersection of two sets is the set of elements that are common to both sets.
Question 34
What is the complement of a set?
a) The set of all elements in the universal set that are not in the given set
b) The set of all elements in the given set that are also in another set
c) The set of all elements in both the given set and the universal set
d) The set of all elements that are in both the universal set and the complement set
Correct Answer: a) The set of all elements in the universal set that are not in the given set
Explanation: The complement of a set is the set of all elements in the universal set that are not in the given set.
Question 35
Which of the following describes a Cartesian product?
a) The set of all ordered pairs formed by taking one element from each of two sets
b) The set of all elements common to both sets
c) The set of all elements in the union of two sets
d) The set of all subsets of two sets
Correct Answer: a) The set of all ordered pairs formed by taking one element from each of two sets
Explanation: The Cartesian product of two sets is the set of all ordered pairs formed by taking one element from the first set and one from the second set.
Question 36
What is the principle of inclusion-exclusion?
a) A formula used to calculate the size of the union of two or more sets by subtracting the sizes of the intersections
b) A formula used to calculate the size of the union of two sets by adding the sizes of both sets
c) A formula used to calculate the size of the complement of a set
d) A formula used to calculate the size of a power set
Correct Answer: a) A formula used to calculate the size of the union of two or more sets by subtracting the sizes of the intersections
Explanation: The principle of inclusion-exclusion is a formula used to calculate the size of the union of two or more sets by subtracting the sizes of their intersections.
Question 37
Which of the following describes a free variable in a predicate?
a) A variable that is not bound by a quantifier
b) A variable that is bound by a quantifier
c) A variable that does not affect the truth value of the predicate
d) A variable that is always false
Correct Answer: a) A variable that is not bound by a quantifier
Explanation: A free variable in a predicate is a variable that is not bound by a quantifier, meaning it can take on any value within its domain.
Question 38
Which of the following describes a bound variable in a predicate?
a) A variable that is bound by a quantifier
b) A variable that is not bound by a quantifier
c) A variable that does not affect the truth value of the predicate
d) A variable that is always false
Correct Answer: a) A variable that is bound by a quantifier
Explanation: A bound variable in a predicate is a variable that is restricted by a quantifier, meaning it is associated with a specific condition or range of values.
Question 39
What does the term “tautology” mean in logic?
a) A proposition that is always true
b) A proposition that is always false
c) A proposition that is true only under certain conditions
d) A proposition that has no truth value
Correct Answer: a) A proposition that is always true
Explanation: A tautology is a proposition that is always true, regardless of the truth values of its individual components.
Question 40
Which of the following best describes a contradiction in logic?
a) A proposition that is always false
b) A proposition that is always true
c) A proposition that is sometimes true and sometimes false
d) A proposition that has no truth value
Correct Answer: a) A proposition that is always false
Explanation: A contradiction is a proposition that is always false, regardless of the truth values of its individual components.
