Design and analysis of algorithms multiple choice questions with answers pdf for the preparation of BCA, MCA & other IT examinations.
Design and Analysis of Algorithms is a crucial concept for Computer Science students. Having a deep understanding of this topic is essential for excelling in any software engineering or computing-related field.
This article provides you with multiple choice questions (MCQs) on the topic of Design and Analysis of Algorithms, along with answers to help you understand the concepts better.
Design and analysis of algorithms MCQs with answers
1. Each of the cities is connected to another city by a road a complete ___ is obtained.
2. The worst-case efficiency of the brute force algorithm is ___.
3. The searching requires ___ comparisons to in the worst case when the array is sorted first.
Ans. [log2 n] +1
4. Gaussian elimination is an algorithm for solving systems of ___ equations.
5. In Gaussian elimination we make the ___ coefficient matrix zero.
Ans. Lower triangular
6. Gaussian elimination can be used to find the ___ of a matrix.
7. An AVL tree is a ___ tree.
Ans. Binary search
8. The ___ is the mirror image of the RL-rotation.
9. The two nodes of 2-3 tree are ___ and ___.
Ans. 2-node, 3-node
10. ___ heap construction algorithm is less efficient than its counterpart.
11. A heap can be defined as ___ with keys assigned to its nodes.
Ans. Binary trees
12. The time efficiency of heapsort is ___ in both worst and average cases.
Ans. O(n log n)
13. Greatest common divisor can be computed easily by ___.
Ans. Euclid’s algorithm
14. The problem of counting graph’s paths can be solved with an algorithm for an appropriate power of its ___.
Ans. Adjacent matrix
16. Input enhancement is based on ___ the instance.
17. The cities are represented by ___ and the roads between them are shown as edges.
18. Collision occurs when a hash function maps two or more keys to the ___.
Ans. Same hash value
19. When the interval between probes is computed by another hash function it is ___.
Ans. Double hashing
20. As the ___ increases the height of the tree decreases thus speeding access.
Ans. Branching factor
21. Access time increases slowly as the number of records ___.
22. The insertions in a B-Tree start from a ___.
Ans. Leaf node
23. Sorting is an example of input enhancement that achieves ___.
Ans. Time efficiency
24. Input enhancement is to ___ the input pattern.
25. In Horspool’s algorithm, the characters from the pattern are matched ___.
Ans. Right to left
26. The two heuristics in the Boyre-Moore algorithm are ___ and ___.
Ans. Good suffix and bad character shift
27. Each slot of a hash table is often called a ___.
28. The information which is used to place the elements at proper positions is the accumulated sum of frequencies which is called ___.
29. The ___ and ___ are the two approaches to dynamic programming.
Ans. Top-down, bottom-up
30. ___ is a technique to store answers to sub-problems in a table.
31. The ___ algorithm is similar to the dynamic approach.
Ans. Divide and conquer
32. ___, a mathematician, invented the Principle of Optimality.
Ans. Richard Ernest Bellman
33. All optimization problems tend to minimize cost, time and maximizing ___.
34. ___are node-based data structures used in many system programming applications for managing dynamic sets.
Ans. Binary search trees
35. The Insertion, deletion and search operations of a binary search tree has an average-case complexity of ___.
Ans. O(log n)
36. The time taken to perform operations on a binary search tree is directly proportional to the ___ of the tree.
37. The ___ expresses the problem using its sub-instances.
Ans. Recurrence relation
38. ___ is an NP-hard optimization problem.
Ans. Bounded Knapsack problem
39. The Knapsack problem minimizes the total ___ and maximizes the total value.
40. The goal of using ___ is to solve only the subproblems which are necessary.
Ans. Memory functions
41. Memory functions use a dynamic programming technique called ___ in order to reduce the inefficiency of recursion that might occur.
42. Memory functions method solves the problem using ___ approach.
43. To carry out an insertion sort, begin at the ___ most element of the array.
44. The asymptotic running time when we first run to calculate the nth Fibonacci number is ___.
45. To compute the nth Fibonacci number we followed the ___ dynamic approach.
46. DFS uses the ___ technique.
47. Theoretically, the travelling salesman problem can always be solved by specifying all ___ Hamiltonian circuits.
48. Binomial coefficients are a study of ___.
49. Both Warshall’s and Floyd’s algorithms have the run time as ___.
50. Warshall’s algorithm is used to solve ___ problems.
Ans. Transitive closure
51. Floyd’s algorithm is used to solve ___ problems.
Ans. Shortest path
52. The ___ is greedy in the sense that at each iteration it approximates the residual possible by a single function.
Ans. Pure greedy algorithm
53. A greedy strategy usually progresses in a ___ fashion.
54. The ___ is obtained by selecting the adjacent vertices of already selected vertices.
Ans. Minimum spanning tree
55. Each ___ generated by prim’s algorithm is a part of some other minimum spanning tree.
56. The greedy strategy in prim’s algorithm is greedy since the tree is added with an edge that contributes the ___ amount possible to the tree’s weight.
57. In Kruskal’s algorithm if the graph is not connected, then the algorithm yields a___.
Ans. Minimum spanning forest
58. The Union-Find data structure is helpful for managing ___ which is vital for Kruskal’s algorithm.
Ans. Equivalence classes
59. Correctness of Kruskal’s algorithm can be proved by saying that the constructed spanning tree is of ___.
Ans. Minimal weight
60. Dijkstra’s algorithm solves the single-source ___ problem for a tree.
Ans. Shortest path
61. The algorithm finds the path with the lowest cost between the ___ vertex and every other vertex.
62. The time complexity of Dijkstra’s algorithm can be improved for ___ graphs.
63. Huffman codes are digital ___ codes.
Ans. Data compression
64. The Huffman Encoding scheme falls in the category of ___.
Ans. Variable-length encoding
65. Static Huffman coding is done with the help of ___ tables.
Ans. Statistical symbol frequency
66. Principle of ___ is defined as a basic dynamic programming principle that helps us to view problems as a sequence of subproblems.
67. The choices made in a greedy algorithm cannot depend on ___ choices.
68. ___ means calculating the minimum amount of work required to solve the problem.
Ans. Lower – bound
69. Trivial lower bound is obtained by the count of the input data that the algorithm reads and the output it produces.
70. ___ method defines the lower bound of an algorithm based on the number of comparisons the algorithm makes.
71. We can implement Backtracking by constructing the ___.
Ans. State-space tree
72. Backtracking, in the ___ case, may have to generate all possible candidates in a problem state that is growing exponentially.
73. The n-Queens problem, the ___ circuit and the Subset-Sum problem are some examples of problems that can be solved by Backtracking.
74. ___ organizes details of all candidate solutions and discards large subsets of fruitless candidate solutions.
Ans. Branch and Bound
75. A ___ is a solution that satisfies all the constraints of a problem.
Test Your IQ on Design and Analysis of Algorithms MCQs
Q1: What is an algorithm?
Ans: An algorithm is a set of instructions used to solve a problem or complete a task. It is a step-by-step process that takes an input, performs certain operations on it, and produces an output.
Algorithms are used in many areas of computer science, including search engines, image processing, machine learning, and artificial intelligence.
Q2: How do algorithms work?
Ans: Algorithms are a set of instructions that tell a computer how to perform a task. They are made up of a sequence of steps, which can include calculations, comparisons, and other operations.
The inputs for an algorithm can be data or user-defined parameters, and the output is usually the result of the algorithm’s execution. Algorithms are used in many areas such as machine learning, data analysis, and artificial intelligence.
Q3: What are the benefits of using algorithms?
Ans: Algorithms provide a number of benefits. They allow for efficient problem solving, help reduce manual effort and human error, automate repetitive tasks, and enable scalability.
Algorithms can also be used to identify patterns in data, make predictions and recommendations, and increase the accuracy of decisions.
Q4: What are the different types of algorithms?
Ans: Algorithms can be broadly classified into four types: Search algorithms, Sort algorithms, Path-finding algorithms, and Randomized algorithms. Search algorithms are used to locate specific data or items in a collection.
Sort algorithms arrange elements in a certain order. Path-finding algorithms determine the shortest path between two points. Randomized algorithms use randomness to solve a problem.
Design and analysis of algorithms is a complex yet fascinating subject. With the multiple choice questions and answers provided in this article, you can now confidently answer questions on algorithms in exams or interviews.
It is important to remember that deep understanding and knowledge of the topic is also essential for success. Therefore, it is recommended to practice solving algorithm problems as much as possible before attempting an exam or interview.