Discrete Mathematics

Algorithms

Question 1
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 2
Marks : +2 | -2
Pass Ratio : 100%
Is 17 congruent to 4 modulo 6.
True
False
Explanation:
6 does not divide 17 – 4 = 13.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
The quotient when 19 is divided by 6 is?
1
2
3
0
Explanation:
According to the Division Algorithm 19 = 6(3) + 1. Hence, quotient when 19 divided by 6 is 3 = 19 div 6.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
The complexity of Binary search algorithm is _________
O(n)
O(log)
O(n2)
O(n log n)
Explanation:
The compexity of binary search is O(logn).
Question 5
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 6
Marks : +2 | -2
Pass Ratio : 100%
The quotient and remainder when -1 is divided by 3 is?
-1 and -1
-1 and 2
1 and 2
-1 and -2
Explanation:
According to the Division Algorithm -1 = 3(-1) + 2. Hence, quotient when -1 divided by 3 is -1 = -1 div 3 and remainder when -1 divided by 3 is 2 = -1 mod 3.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
Is 102 congruent to 6 modulo 16.
True
False
Explanation:
16 divide 102 – 6 = 96.
Question 8
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 9
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 10
Marks : +2 | -2
Pass Ratio : 100%
The worst case complexity of quick sort is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
The worst case complexity of quick sort is O(n2).