Analysis of Algorithms and Computational Complexity Questions and Answers
Understanding the Analysis of Algorithms and Computational Complexity questions with answers is crucial for students preparing for GATE, TCS, Infosys, and Wipro placement exams. This topic focuses on evaluating the efficiency of algorithms based on time and space complexity, which forms the foundation of advanced computer programming and system design. By solving programming questions and answers related to algorithm analysis, you can strengthen your logical thinking, optimize code performance, and make informed design decisions. In this section, we cover detailed MCQs and explanations to help you master Big O notation, asymptotic analysis, and algorithmic trade-offs. Perfect for both academic and placement preparation, this guide ensures clarity with well-explained examples.
Questions on algorithmic analysis for computer science aspirants can be complemented by data structure algorithms and software engineering MCQ
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