Discrete Mathematics Multiple Choice s on “Algorithms”.
1. An algorithm is a _________ set of precise instructions for performing computation.
a) Infinite
b) Finite
c) Constant
d) None of the mentioned
Answer: b
Clarification: By the definition of an algorithm.
2. Out of the following which property algorithms does not share?
a) Input
b) Finiteness
c) Generality
d) Constancy
Answer: d
Clarification: All the others are the properties of algorithms.
3. In ________ search each element is compared with x till not found.
a) Binary
b) Sequential
c) Merge
d) None of the mentioned
Answer: b
Clarification: In linear or sequential search entire list is searched sequentially for x.
4. If the entire list is searched sequentially without locating x in linear search, the solution is __________
a) 0
b) -1
c) 1
d) 2
Answer: a
Clarification: If the element is not found in the entire list, then the solution is 0.
5. To sort a list with n elements, the insertion sort begins with the __________ element.
a) First
b) Second
c) Third
d) Fourth
Answer: b
Clarification: The insertion sort compares the second element with the first element to start sorting.
6. __________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.
a) (n2 + n + 2) / 2
b) (n3 + n – 2) / 2
c) (n2 + n – 2) / 2
d) (n2 – n – 2) / 2
Answer: c
Clarification: 2+3+4+….6n = (n2 + n – 2) / 2.
7. The Worst case occurs in linear search algorithm when ____________
a) Item is somewhere in the middle of the array
b) Item is not in the array at all
c) Item is the last element in the array
d) Item is the last element in the array or is not there at all
Answer: d
Clarification: The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.
8. List obtained in third pass of selection sort for list 3, 5, 4, 1, 2 is ___________
a) 1, 2, 4, 3, 5
b) 1, 2, 3, 4, 5
c) 1, 5, 4, 3, 2
d) 3, 5, 4, 1, 2
Answer: b
Clarification: The selection sort begins with finding the least element in the list. This element is moved to front and then the least element among the remaining elements. Is found and put into the second position and so on.
9. The operation of processing each element in the list is known as _________
a) Sorting
b) Merging
c) Inserting
d) Traversal
Answer: d
Clarification: The operation of processing each element in the list is known as Traversal.
10. The complexity of Bubble sort algorithm is _________
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
Answer: c
Clarification: The complexity of Bubble sort algorithm is O(n2).