Discrete Mathematics
1. Which of the following is not a type of discrete structure?
a) Sets
b) Graphs
c) Continuous functions
Answer: c) Continuous functions
2. Which of the following is a discrete set?
a) All real numbers between 0 and 1
b) All integers greater than or equal to 0
c) All irrational numbers
Answer: b) All integers greater than or equal to 0
3. Which of the following is an example of a countably infinite set?
a) The set of all real numbers between 0 and 1
b) The set of all integers
c) The set of all irrational numbers
Answer: b) The set of all integers
4. Which of the following is not a property of a well-defined set?
a) It is clear what elements are in the set
b) It is clear what elements are not in the set
c) It is infinite in size
Answer: c) It is infinite in size
5. Which of the following is an example of a directed graph?
a) A tree
b) A cycle
c) A flow network
Answer: c) A flow network
6. Which of the following is a property of a complete graph?
a) Every vertex is adjacent to every other vertex
b) It is acyclic
c) It is bipartite
Answer: a) Every vertex is adjacent to every other vertex
7. Which of the following is an example of a bipartite graph?
a) A complete graph
b) A cycle
c) A star
Answer: c) A star
8. Which of the following is not a type of graph traversal algorithm?
a) Depth-first search
b) Breadth-first search
c) Selection sort
Answer: c) Selection sort
9. Which of the following is not a type of graph algorithm?
a) Shortest path algorithm
b) Maximum flow algorithm
c) Merge sort
Answer: c) Merge sort
10. Which of the following is not a type of graph coloring algorithm?
a) Greedy algorithm
b) Backtracking algorithm
c) Dijkstra’s algorithm
Answer: c) Dijkstra’s algorithm
11. Which of the following is an example of a discrete function?
a) A continuous function
b) A step function
c) A rational function
Answer: b) A step function
12. Which of the following is not a type of combinatorial problem?
a) Permutation
b) Combination
c) Integration
Answer: c) Integration
13. Which of the following is not a property of a permutation?
a) Order matters
b) Repetition is allowed
c) Every element is used exactly once
Answer: b) Repetition is allowed
14. Which of the following is not a property of a combination?
a) Order matters
b) Repetition is not allowed
c) Every element is used at least once
Answer: a) Order matters
15. Which of the following is not a type of recurrence relation?
a) Linear recurrence relation
b) Homogeneous recurrence relation
c) Exponential recurrence relation
Answer: c) Exponential recurrence relation
16. Which of the following is not a method for solving a recurrence relation?
a) Direct substitution
b) Characteristic equation
c) Differentiation
Answer: c) Differentiation
17. Which of the following is not a property of a generating function?
a) It can be used to solve recurrence relations
b) It is a polynomial or a power series
c) It is a continuous function
Answer: c) It is a continuous function
18. Which of the following is not a type of propositional logic connective?
a) Conjunction
b) Disjunction
c) Differentiation
Answer: c) Differentiation
19. Which of the following is the truth table for the implication connective?
a)
p | q | p -> q
T | T | T
T | F | F
F | T | T
F | F | T
b)
p | q | p -> q
T | T | T
T | F | F
F | T | T
F | F | F
c)
p | q | p -> q
T | T | F
T | F | T
F | T | F
F | F | T
Answer: a)
20. Which of the following is the negation of the proposition “p and q”?
a) p or q
b) not p or not q
c) not p and not q
Answer: b) not p or not q
21. Which of the following is not a property of a tautology?
a) It is always true
b) It is always false
c) It is logically equivalent to the proposition “true”
Answer: b) It is always false
22. Which of the following is not a type of inference rule in propositional logic?
a) Modus ponens
b) Modus tollens
c) Substitution rule
Answer: c) Substitution rule
23. Which of the following is not a type of proof technique in discrete mathematics?
a) Direct proof
b) Induction proof
c) Approximation proof
Answer: c) Approximation proof
24. Which of the following is not a type of graph property?
a) Connectivity
b) Planarity
c) Density
Answer: c) Density
25. Which of the following is a property of a planar graph?
a) It can be embedded on a sphere
b) It can be embedded on a torus
c) It cannot be embedded on any surface
Answer: a) It can be embedded on a sphere
26. Which of the following is not a type of planar graph?
a) Tree
b) Planar bipartite graph
c) Planar multigraph
Answer: a) Tree
27. Which of the following is not a type of Euler’s formula?
a) V – E + F = 2
b) V + E – F = 2
c) V – E + F = 0
Answer: b) V + E – F = 2
28. Which of the following is a property of a Hamiltonian cycle?
a) It is a cycle that visits every vertex exactly once
b) It is a cycle that visits every edge exactly once
c) It is a cycle that visits every vertex and edge exactly once
Answer: a) It is a cycle that visits every vertex exactly once
29. Which of the following is not a type of combinatorial object?
a) Permutation
b) Partition
c) Polynomial
Answer: c) Polynomial