# Data structure MCQ Set-8

1. For the bubble sort algorithm, what is the time complexity of the best/worst case? (assume that the computation stops as soon as no more swaps in one pass)
• best case: O(n) worst case: O(n*n)
• best case: O(n) worst case: O(n*log(n))
• best case: O(n*log(n)) worst case: O(n*log(n))
• best case: O(n*log(n)) worst case: O(n*n)
2. For the quick sort algorithm, what is the time complexity of the best/worst case?
• best case: O(n) worst case: O(n*n)
• best case: O(n) worst case: O(n*log(n))
• best case: O(n*log(n)) worst case: O(n*log(n))
• best case: O(n*log(n)) worst case: O(n*n)
3. In an arbitrary tree ( not a search tree) of order M. Its size is N, and its height is K. The computation time needed to find a data item on T is
• O(K*K)
• O(M*M)
• O(N)
• O(K)
4. Which of the following belongs to the algorithm paradigm?
• Minimum & Maximum problem
• Knapsack problem
• Selection problem
• Merge sort
• Quick sort.
5. If f,t: N→ R+, then t (n)  Ω (f (n)), iff f(n)  O (t (n)) is known as
• Limit rule
• Rule of inference
• Duality rule
• Rule of consequences
6. The time taken by NP-class sorting algorithm is
• O(1)
• O(log n)
• O(n2)
• O(n)
7. Find the odd one out from the following categories of algorithms.
• TVSP
• N-Queens
• 15-Puzzle
• Bin-Packing.
8. The time complexity of binary search in best, worst cases for an array of size N is
• N, N2
• 1, Log N
• Log N, N2
• 1, N log N
9. Which of following algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of desired order?
• Insertion sort
• Quick sort
• Shell sort
• Bubble sort
10. The mathematical definition for Omega can be defined as, provided f,g:NR+ and c is a positive constant and n > n0,
• f(n) ≥ c. g(n) n
• f(n) = c. g(n) n
• f(n) ≥ c + g(n) n
• f(n) = c + g(n) n