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