Discrete Mathematics

Algorithms

Question 1
Marks : +2 | -2
Pass Ratio : 100%
The complexity of linear search algorithm is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
The worst case complexity of linear search is O(n).
Question 2
Marks : +2 | -2
Pass Ratio : 100%
__________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.
(n2 + n + 2) / 2
(n3 + n – 2) / 2
(n2 + n – 2) / 2
(n2 – n – 2) / 2
Explanation:
2+3+4+….6n = (n2 + n – 2) / 2.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
The value of 12 mod 3 is?
0
1
2
3
Explanation:
By the Division algorithm 12 = 3(4) + 0. Where remainder is 12 mod 3.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
List obtained in third pass of selection sort for list 3, 5, 4, 1, 2 is ___________
1, 2, 4, 3, 5
1, 2, 3, 4, 5
1, 5, 4, 3, 2
3, 5, 4, 1, 2
Explanation:
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.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
The Worst case occurs in linear search algorithm when ____________
Item is somewhere in the middle of the array
Item is not in the array at all
Item is the last element in the array
Item is the last element in the array or is not there at all
Explanation:
The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
Is 17 congruent to 4 modulo 6.
True
False
Explanation:
6 does not divide 17 – 4 = 13.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
The operation of processing each element in the list is known as _________
Sorting
Merging
Inserting
Traversal
Explanation:
The operation of processing each element in the list is known as Traversal.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
The worst case complexity for insertion sort is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
In worst case nth comparison are required to insert the nth element into correct position.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
Out of the following which property algorithms does not share?
Input
Finiteness
Generality
Constancy
Explanation:
All the others are the properties of algorithms.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
Which of the following case does not exist in complexity theory?
Best case
Worst case
Average case
Null case
Explanation:
Null case does not exist in complexity Theory.