Home »
MCQs »
Discrete Mathematics MCQs
Discrete Mathematics | Algorithms and Functions MCQs
Discrete Mathematics | Algorithms and Functions MCQs: This section contains multiple-choice questions and answers on Algorithms and Functions in Discrete Mathematics.
Submitted by Anushree Goswami, on July 17, 2022
1. Which of the following is/are a/the characteristic(s) of Algorithm?
- Input
- Output
- Precision
- All of the above
Answer: D) All of the above
Explanation:
The characteristics of Algorithm are input, output, precision, etc.
2. How many quantities are externally supplied in input?
- Zero
- Zero or more
- One
- Atleast one
Answer: B) Zero or more
Explanation:
Zero or more quantities are externally supplied in input.
3. How many quantities are produced in output?
- One
- Atleast One
- Multiple
- Zero
Answer: B) Atleast One
Explanation:
Atleast one quantity is produced in output.
4. In precision, each instruction is -?
- Clear
- Unambigous
- Both A and B
- None of the above
Answer: C) Both A and B
Explanation:
In precision, each instruction is clear and unambiguous.
5. Which of the following is not the characteristic of algorithm?
- Feasibility
- Flexibility
- Generality
- Infiniteness
Answer: D) Infiniteness
Explanation:
Infiniteness is not the characteristic of algorithm.
6. A ____ number of instructions must be executed for the algorithm to complete?
- Multiple
- Finite
- Infinite
- None
Answer: B) Finite
Explanation:
A finite number of instructions must be executed for the algorithm to complete.
7. Flexibility refers that -?
- A change to the algorithm should also be possible without putting a great deal of effort into it.
- A change to the algorithm should not be possible without putting a great deal of effort into it.
- A change to the algorithm should also be possible putting a great deal of effort into it.
- None of the above
Answer: A) A change to the algorithm should also be possible without putting a great deal of effort into it.
Explanation:
Flexibility refers that a change to the algorithm should also be possible without putting a great deal of effort into it.
8. In algorithm analysis, _____ estimates are derived to determine how long an algorithm will take to execute?
- Time
- Space
- Both A and B
- None of the above
Answer: C) Both A and B
Explanation:
In algorithm analysis, time and space estimates are derived to determine how long an algorithm will take to execute.
9. An algorithm's _____ is the estimation of how much time and space will be required to execute it?
- Time complexity
- Space complexity
- Time and space complexity
- Time or space complexity
Answer: C) Time and space complexity
Explanation:
An algorithm's time and space complexity is the estimation of how much time and space will be required to execute it.
10. A ____ of the input determines how long an algorithm will take to execute?
- Value
- Function
- Log
- Queue
Answer: B) Function
Explanation:
A function of the input determines how long an algorithm will take to execute.
11. The size of the input is characterized by ____ rather than directly dealing with it?
- Functions
- Values
- Parameters
- None
Answer: C) Parameters
Explanation:
The size of the input is characterized by parameters rather than directly dealing with it.
12. An algorithm's time complexity can be determined in ____ cases, since this is a difficult process?
- Two
- Three
- Four
- Five
Answer: B) Three
Explanation:
An algorithm's time complexity can be determined in three cases, since this is a difficult process.
13. What is/are the case(s) the Q12 is referring to?
- Worst case
- Best case
- Average case
- All of the above
Answer: D) All of the above
Explanation:
The cases Q12 is referring to are worst, best and average case.
14. The Worst-Case is represented by f (n), which is the ____ number of steps on all instances of size n?
- Minimum
- Average
- Maximum
- None
Answer: C) Maximum
Explanation:
The Worst-Case is represented by f (n), which is the maximum number of steps on all instances of size n.
15. The Best-Case is represented by f (n), which is the ____ number of steps on all instances of size n
- Minimum
- Average
- Maximum
- None
Answer: A) Minimum
Explanation:
The Best-Case is represented by f (n), which is the minimum number of steps on all instances of size n.
16. Algorithm ____ times are described using asymptotic notations?
- Running
- Execution
- Stagnate
- Fragile
Answer: B) Execution
Explanation:
Algorithm execution times are described using asymptotic notations.
17. Notations indicate the ____ in which functions grow?
- Base
- Order
- Line
- Circle
Answer: B) Order
Explanation:
Notations indicate the order in which functions grow.
18. Which of the following is/are an/the asymptotic notation?
- θ
- Ω
- W
- All of the above
Answer: D) All of the above
Explanation:
θ, Ω,w are all asymptotic notation.
19. When c and n0 are positive constants, f (n) ≤ C x g (n) for all n, n ≥ n0 gives the function ____?
- f (n) =O ((n))
- f (n) = o (g (n))
- f (n) =O (g (n))
- f (n) =O (g (C))
Answer: C) f (n) =O (g (n))
Explanation:
When c and n0 are positive constants, f (n) ≤ C x g (n) for all n, n ≥ n0 gives the function f (n) =O (g (n)).
20. The function f (n) = Ω (g (n)) if and only if exist positive constant c and n0 such that ____ for all n, n ≥ n0?
- f (n) ≥ C* g (n)
- f (n) ≤ C* g (n)
- f (n) ≥ g (n)
- f (n) ≤ g (n)
Answer: A) f (n) ≥ C* g (n)
Explanation:
The function f (n) = Ω (g (n)) if and only if exist positive constant c and n0 such that f (n) ≥ C* g (n) for all n, n ≥ n0.
21. The function f (n) = θ (g (n)) [read as "f is the theta of g of n"] if and only if there exists positive constant k1, k2 and k0 such that ____ for all n, n≥n0?
- f (n) ≥ C* g (n)
- f (n) ≤ C* g (n)
- f (n) ≥ g (n)
- f (n) ≤ g (n)
Answer: B) f (n) ≤ C* g (n)
Explanation:
The function f (n) = θ (g (n)) [read as "f is the theta of g of n"] if and only if there exists positive constant k1, k2 and k0 such that k1* g (n) ≤ f (n)≤k2* g(n)for all n, n≥n0.