1. Which logic gate corresponds to the 'AND' operation?
A. OR gate
B. NOT gate
C. AND gate
D. XOR gate
2. Which of the following is a property of Boolean algebra?
A. Associativity
B. Commutativity
C. Distributivity
D. All of the above
3. Which of the following is a tree?
A. A complete graph K_4
B. A cycle graph C_4
C. A connected acyclic graph
D. A graph with cycles
4. In set theory, what does the notation A ⊆ B mean?
A. A is a proper subset of B
B. A is a superset of B
C. A is a subset of B
D. A is not a subset of B
5. What is the number of vertices in a complete graph K_n with 'n' vertices?
A. n-1
B. n
C. n(n-1)/2
D. 2n
6. What is the chromatic number of a complete graph K_n?
7. What is the result of the bitwise AND operation between 10 (binary 1010) and 6 (binary 0110)?
A. 14 (binary 1110)
B. 0 (binary 0000)
C. 2 (binary 0010)
D. 16 (binary 10000)
8. What is the value of 5! (5 factorial)?
9. What is the principle of inclusion-exclusion used for in combinatorics?
A. To find the union of disjoint sets.
B. To count the number of elements in the union of sets.
C. To find the intersection of sets.
D. To count permutations.
10. Which of the following sets is countable?
A. The set of real numbers.
B. The set of irrational numbers.
C. The set of natural numbers.
D. The set of complex numbers.
11. Which of the following is NOT a property of a function?
A. Each input has exactly one output.
B. Each output has exactly one input.
C. Functions map elements from a domain to a codomain.
D. Functions can be represented as sets of ordered pairs.
12. What is the transitive closure of a relation R?
A. The inverse of relation R.
B. The smallest transitive relation containing R.
C. The largest transitive relation contained in R.
D. The symmetric closure of relation R.
13. Which of the following is a tautology?
A. p ∧ ¬p
B. p ∨ ¬p
C. p → q
D. p ↔ q
14. What is the sum of the degrees of all vertices in a graph G with 'm' edges?
15. What is the degree of a vertex in a graph?
A. The number of edges in the graph.
B. The number of vertices in the graph.
C. The number of loops connected to the vertex.
D. The number of edges incident to the vertex.
16. Which of the following proof techniques is often used to prove existential statements?
A. Direct Proof
B. Proof by Contradiction
C. Proof by Construction
D. Proof by Induction
17. Which of the following is a bipartite graph?
A. A complete graph K_3
B. A cycle graph C_5
C. A complete bipartite graph K_{2,3}
D. A wheel graph W_4
18. What is the cardinality of the power set of a set S, if S has 'n' elements?
19. What is the negation of the statement 'All students are attentive'?
A. No students are attentive.
B. Some students are not attentive.
C. All students are not attentive.
D. Some students are attentive.
20. In modular arithmetic, what is 7 mod 3?
21. Which of the following relations on the set of integers is an equivalence relation?
A. xRy if x < y
B. xRy if x ≤ y
C. xRy if x = y
D. xRy if x ≠ y
22. What is the purpose of Kruskal's algorithm?
A. To find the shortest path in a graph.
B. To find a minimum spanning tree in a graph.
C. To find the maximum flow in a network.
D. To detect cycles in a graph.
23. In propositional logic, what is the truth value of the statement 'P AND Q' if P is true and Q is false?
A. True
B. False
C. Cannot be determined
D. Depends on context
24. What is the purpose of Dijkstra's algorithm?
A. To find the maximum flow in a network.
B. To find the shortest path between two vertices in a graph.
C. To find a minimum spanning tree in a graph.
D. To check if a graph is planar.
25. What is the contrapositive of the statement 'If it is raining, then the ground is wet'?
A. If the ground is wet, then it is raining.
B. If it is not raining, then the ground is not wet.
C. If the ground is not wet, then it is not raining.
D. It is raining and the ground is not wet.
26. What is the principle of mathematical induction used for?
A. Solving differential equations.
B. Proving statements about recursive algorithms.
C. Proving statements for all positive integers.
D. Finding roots of polynomials.
27. Which of the following is NOT a type of graph in graph theory?
A. Directed graph
B. Undirected graph
C. Weighted graph
D. Linear graph
28. Which of the following is a valid conclusion from the premises: 'All cats are mammals' and 'Whiskers is a cat'?
A. Whiskers is not a mammal.
B. All mammals are cats.
C. Whiskers is a mammal.
D. Cats may or may not be mammals.
29. Which of the following is NOT a type of recurrence relation?
A. Linear homogeneous recurrence relation
B. Linear non-homogeneous recurrence relation
C. Quadratic recurrence relation
D. Divide and conquer recurrence relation
30. What is the Pigeonhole Principle?
A. If you have more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon.
B. If you have fewer pigeons than pigeonholes, then each pigeonhole can contain at most one pigeon.
C. Pigeons always prefer to stay in pigeonholes.
D. The number of pigeons must be equal to the number of pigeonholes.
