# 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