Data structure MCQ Set-5

1. If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
  • O(n log n)
  • O(n^3)
  • O(n^2)
  • O(log n)
  • O(n^4).
2. The upper bound on the time complexity of the nondeterministic sorting algorithm is
  • O(n)
  • O(n log n)
  • O(1)
  • O( log n)
  • O(n^2).
3. The worst case time complexity of the nondeterministic dynamic knapsack algorithm is
  • O(n log n)
  • O( log n)
  • O(n^2)
  • O(n)
  • O(1).
4. Recursive algorithms are based on
  • Divideand conquer approach
  • Top-down approach
  • Bottom-up approach
  • Hierarchical approach
  • Heuristic approach.
5. What do you call the selected keys in the quick sort method?
  • Outer key
  • Inner Key
  • Partition key
  • Pivot key
  • Recombine key.
6. How do you determine the cost of a spanning tree?
  • By the sum of the costs of the edges of the tree
  • By the sum of the costs of the edges and vertices of the tree
  • By the sum of the costs of the vertices of the tree
  • By the sum of the costs of the edges of the graph
  • By the sum of thecosts of the edges and vertices of the graph.
7. The time complexity of the normal quick sort, randomized quick sort algorithms in the worst case is
  • O(n^2), O(n log n)
  • O(n^2), O(n^2)
  • O(n log n), O(n^2)
  • O(n log n), O(n log n)
  • O(n log n), O(n^2 log n).
8. Let there be an array of length ‘N’, and the selection sort algorithm is used to sort it, how many times a swap function is called to complete the execution?
  • N log N times
  • log N times
  • N2 times
  • N-1 times
  • N times.
9. The Sorting methodwhich is used for external sort is
  • Bubble sort
  • Quick sort
  • Merge sort
  • Radix sort
  • Selection sort.