Unit-I
Q1.
An algorithm is .............
[A] a set of rules for carrying out
calculation either by hand or on a machine
[B]
a sequence of computational steps that transform the input into the output
[C]
a sequence of operations performed on data organized in data structure [D] All
of these
[D] All of these
Q.2
An algorithm must have the following Properties
[A]Finiteness
[B]
Effectiveness
[C]
Termination
[D]All
of these
Q.3 Asymptotic notation (s) is (are)….
[A] Big-oh notation
[B]
Big-A notation
[C]
Both A and B
[D]
None of these
Correct answer
[A]
Big-oh notation
Q.4
What is the best case running time of an insertion sort algorithm?
[A]
O[N]
[B]
O[N log N]
[C]
O[log N]
[D]
O[N²]
Q.5 What is the worst case efficiency of bubble
sort?
[A] O[nlogn]
[B]
O[logn]
[C]
O[n]
[D] O[n²]
Q.6
For the worst case input, the running time of an insertion sort algorithm is?
A]
Linear
[B]
Binary
[C] Quadratic
[D]
Depends on the input
Q.7
What is the running time of an insertion sort algorithm if the input is
reverse-sorted?
[A] O[N²]
[B]
O[N log N]
[C]
O[N]
[D]
O[M log N]
Q.8 Running merge sort on an array of size n
which is already sorted is
[A]
O(n)
[B] O(nlogn)
[C]
O(n²)
[D]
None
Q.9
If the given input array is sorted or nearly sorted, which of the following
algorithm gives the best performance?
[A] Insertion sort
[B]
Selection sort
[C]
Quick sort
[D]
Merge sort
Q.10
Time complexity of bubble sort in best case is
[A] θ (n)
[B]
θ (nlogn)
[C]
θ (n²)
[D]
θ (n(logn) ²)
Q.11
Solve the following recurrence using Master’s theorem. T[n] = 9T [n/3] + n
[A] T[n] = O[n]
[B]
T[n] = O[log n]
[C]
T[n] = O[n2log n]
[D] T[n] = O[n2]
Q.12 Identify variables by Master Therom for T[n]=
3T[n/4]+nlogn
[A]
T[n] = O[n]
[B] T[n] = O[nlog n]
[C]
T[n] = O[n²log n]
[D]
T[n] = O[n²]
Q.13 I. Time complexity is time taken by an
algorithm to run
II. Space Complexity is space taken
by an algorithm to store.
[A] Only I is correct
[B]
Only II is correct
[C]
Both are correct
[D] both are wrong.
Q.14 The __________of an algorithm is an upper
bound on the running time for any input.
[A] Worst case running time
[B]
Average case running time
[C]
best case running time
[D]
Amortized running time
Q.15
The __________of an algorithm to perform a sequence of operations is averaged
over all the operations performed.
A]
Worst case running time
[B]
Average case running time
[C]
best case running time
[D] Amortized running time
Q.16
If for an algorithm time complexity is given by O(n) then complexity of it is:
[A]
constant
[B] linear
[C]
exponential
[D]
none of the mentioned
Q.17 Master’s theorem is used for?
[A] solving recurrences
[B]
solving iterative relations
[C]
analysing loops
[D]
calculating the time complexity of any code
Q.18
How many cases are there under Master’s theorem?
[A]
2
[B] 3
[C]
4
[D]
5
Q.19 Solve the following recurrence using Master’s
theorem. T(n) = 4T (n/2) + n²
[A]
T(n) = O(n)
[B]
T(n) = O(log n)
[C] T(n) = O(n²log n)
[D]
T(n) = O(n²)
Q.20
Solve the following recurrence using Master’s theorem. T(n) = T (n/2) + 2n
[A]
T(n) = O(n2)
[B]
T(n) = O(n2 log n)
[C] T(n) = O(2n)
[D]
Cannot be solved
Q.21
Solve the following recurrence using Master’s theorem. T(n) = 16T (n/4) + n
[A] T(n) = O(n)
[B]
T(n) = O(log n)
[C]
T(n) = O(n²log n)
[D] T(n) = O(n²)
Q.22
Solve the following recurrence using Master’s theorem.T(n) = 2T (n/2) + n/ log
n
[A]
T(n) = O(n)
[B]
T(n) = O(log n)
[C]
T(n) = O(n2log n)
[D]
cannot be solved using master’s theorem
Q.23 Which of the following examples represent the
worst case input for an insertion sort?
[A]
Array in sorted order
[B] Array sorted in reverse order
[C]
Normal unsorted array
[D]
Large array
Q.24 How many passes does an insertion sort
algorithm consist of?
[A]
N
[B] N-1
[C]
N+1
[D]
N²
Q.25
What is the worst case complexity of bubble sort?
[A] O(nlogn)
[B]
O(logn)
[C]
O(n)
[D] O(n²)
Q.26 What is the average case complexity of
bubble sort?
[A] O(nlogn)
[B]
O(logn)
[C]
O(n)
[D] O(n²)
Q.27
An Algorithm is ___________
[A] A procedure for solving a
problem
[B]
A problem
[C]
A real life mathematical problem
[D]
None of the mentioned
Q.28
A Complexity of algorithm depends upon _________
[A]
Time only
[B]
Space only
[C] Both Time and Space
[D]
None of the mentioned
Q.29
An algorithm: can be represented through _________
[A] flow charts
[B]
pseudo codes
[C]
instructions in common language
[D] all of the mentioned
Q.30
There are two algorithms suppose A takes 1.41 milli seconds while B takes 0.9
milliseconds, which one of them is better considering all other things the
same?
[A]
A is better than B
[B] B is better than A
[C]
Both are equally good
[D]
None of the mentioned
No comments:
Post a Comment