Analysis of Algorithms and Computational Complexity
Analysis of Algorithms and Computational Complexity
21. A sort which interactively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called
- insertion sort
- selection sort
- heap sort
- quick sort
22. A sort which uses the binary tree concept such that any number is larger than all the numbers in the subtree below it is called
- selection sort
- insertion sort
- heap sort
- quick sort
24. Let A be a sorted array of n=10 element. Assume that only one comparison is required to determine whether the target is equal to, less than, or greater than A[i]. Which of the following denotes the average successful time of finding an arbitrary element x in A using binary search ?
- 1.6
- 2.9
- 4.2
- 5.5
25. What is the minimum number of edges which must be removed from a complete bipartite graph of six nodes K(6), so that the remaining graph is planar ?
- 2
- 3
- 4
- 6
26. In a complete binary tree of n nodes, how far are the most distant two nodes. Assume that each edge in the path counts as 1. Assume log (n) as log base 2.
- about log (n)
- about 2 log (n)
- about 3 log (n)
- about 4 log (n)
27. Consider a sorted binary insertion tree. what must be done to produce a sorted array of numbers (for printing) from the sorted binary insertion tree ?
- pre-order traversal
- post-order traversal
- in-order traversal
- top-down traversal
28. How many comparisons are needed to sort an array of length 5 if a straight selection sort is used and array is already in the opposite order ?
- 1
- 10
- 15
- 20
29. If memory for the run-time stack is only 150 cells (words), how big can N be in Factorial (N) before encountering stack overflow ?
- 24
- 66
- 15
- 66
30. The number of nodes in the largest maximal independent set of the complete bipartite graph K(4,2) is
- 2
- 3
- 4
- 6