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).

O(n^3)

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).

O(n)

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).

O(n)

4. Recursive algorithms are based on

Divideand conquer approach

Top-down approach

Bottom-up approach

Hierarchical approach

Heuristic approach.

Bottom-up 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.

By the sum of the costs of the edges of the tree

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).

O(n^2), O(n^2)

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.

N-1 times

9. The Sorting methodwhich is used for external sort is