# Design and Analysis of Algorithms mcq with answers sppu

## Design and Analysis of Algorithms mcq with answers

Below are the 60 most important frequently asked Design and Analysis of Algorithms (DAA) mcq with answers. Analysis and design of Algorithms is generally a third year Engineering subject. These DAA mcq questions are helpful for online exams of universities like SPPU, MU, Anna University and others.

## DAA mcq questions and answers

Q. 1. Which Data Structure is used to perform Recursion?
A : Array
B : queue
C : stack

stack

Q. 2. What is the objective of the knapsack problem?
A : To Get Maximum Total Value In The Knapsack
B : To Get Minimum Total Value In The Knapsack
C : To Get Maximum Weight In The Knapsack
D : To Get Minimum Weight In The Knapsack

To Get Maximum Total Value In The Knapsack

Q. 3. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
A : branch and bound
B : iterative improvement
C : divide and conquer
D : greedy algorithm

branch and bound

Q. 4. What is the worst case time complexity of merge sort?
A : O(N Log N)
B : O(n*n)
C : O(Log N)
D : O(Log Log N)

O(N Log N)

Q. 5. What is tail recursion?
A : A recursive function that has two base cases
B : A function where the recursive functions leads to an infinite loop
C : A recursive function where the function doesnâ€™t return anything and just prints the
values
D : A function where the recursive call is the last thing executed by the function

A function where the recursive call is the last thing executed by the function

Design and analysis of Algorithms multiple choice questions are also useful for interviews of IT companies. We have added DAA interview questions in the form of mcqs. Currently, we have provided only mcq for Design and Analysis of Algorithms but planning on adding DAA mcq pdf for download.

Q. 6. What is best case complexity of selection sort
A : n
B : n^2
C : nlogn
D :

n^2

Q. 7. In computer science, algorithm refers to a special method usable by a computer for the solution to a problem.
A : true
B : false
C :
D :

true

Q. 8. Fractional knapsack problem is also known as
A : 0/1 knapsack problem
B : Continuous knapsack problem
C : Divisible knapsack problem
D : Non continuous knapsack problem

Continuous knapsack problem

Q. 9. Algorithm can be represented as
A : Pseudocode
B : Flowchart
C : None of the above
D : both 1and 2

both 1and 2

Q. 10. What approach is being followed in Floyd Warshall Algorithm?
A : Greedy Technique
B : Dynamic Programming
C : Linear Programming
D : Backtracking

Dynamic Programming

## Design and Analysis of Algorithms (DAA) mcq with answers

Q. 11. Which of the following algorithms has worst time complexity?
A : insertion sort
B : binary search
C : linear search
D : merge sort

insertion sort

Q. 12. Which data structure is used for implementing a FIFO branch and bound strategy?
A : Stack
B : Queue
C : Array

Queue

Q. 13. What is the average case time complexity of merge sort?
A : O(N Log N)
B : O(n*n)
C : O(Log N)
D : O(Log Log N)

O(N Log N)

Q. 14. q29.jpeg
A : 111
B : 101
C : 110
D : 11

110

Q. 15. Alorithm should have finite number of steps
A : true
B : false
C :
D :

true

Q. 16. Two main measures for the efficiency of an algorithm are 1)time 2) space 3) lines of code
A : 1 and 2
B : 2 and 3
C : 1 and 3
D :

1 and 2

Q. 17. Fractional knapsack problem is solved most efficiently by which of the following algorithm?
A : Divide And Conquer
B : Dynamic Programming
C : Greedy Algorithm
D : Backtracking

Greedy Algorithm

Q. 18. What is adaline in neural networks?
B : Automatic Linear Element

Q. 19. What are dendrites?
A : Fibers Of Nerves
B : nuclear projections
C : Other Name For Nucleus
D : Twisted Network

Fibers Of Nerves

Q. 20. Hamiltonian path problem is _________
A : NP problem
B : N class problem
C : P class problem
D : NP complete problem

NP complete problem

Q. 21. Which of the following statements about loop invariants is false?
A : Loop invariants are used to show that algorithms produce the correct results.
B : A loop invariant is the opposite, that is the negation, of the condition of the loop.
C : To prove that a statement is a loop invariant, we use mathematical induction.
D : Loop invariants remain true each time a loop is executed.

A loop invariant is the opposite, that is the negation, of the condition of the loop.

Q. 22. An algorithm that always runs in polynomial time but possibly returns erroneous answers is called a â€¦â€¦â€¦â€¦
A : Las Vegas Algorithm
B : Monte Carlo Algorithm
C : Atlantic City Algorithm
D : Approximation algorithm

Monte Carlo Algorithm

Q. 23. Which algorithm startegy builds up a solution by choosing the option that looks the best at every step.
A : greedy method
B : branch and bound
C : dynamic programming
D : divide and conquer

greedy method

Q. 24. which is not the important aspect of Loop
A : Initial condition
B : nested loop
C : invariant relation
D : termination

nested loop

Q. 25. Choose the correct steps to prove if the vertex cover problem is NPComplete. I– Vertex Cover problem is in NP II–Clique problem is in NP III–Prove that Clique problem â‰¤ Vertex Cover Problem in polynomial time IV—Prove that Vertex Cover problem â‰¤ Clique Problem in polynomial time
A : I and III
B : I and IV
C : II and III
D : II and IV

I and III

Q. 26. Running the program many times is sufficient to prove the correctness of program
A : true
B : false
C :
D :

false

Q. 27. 0/1 knapsack is based on which method?
A : greedy method
B : branch and bound
C : dynamic programming
D : divide and conquer

dynamic programming

Q. 28. Dynamic programming is used to find:
A : All Optimal Solution Is Generated
B : One Solution Is Generated
C : No Optimal Solution Is Generated
D : Partial Solution Is Generated

All Optimal Solution Is Generated

Q. 29. What is the purpose of using randomized quick sort over standard quick sort?
A : To reduce worst case space complexity
B : To reduce worst case time complexity
C : To improve average case time complexity
D : To improve accuracy

To reduce worst case time complexity

Q. 30. which of the following is not basic control structure
A : the process
B : the decision
C : the loop
D : the sequential

the process

Q. 31. If T= abcabaabc & P= abaa then what will be the value of s?
A : 4
B : 2
C : 3
D : 1

3

Q. 32. Which data structure has a better amortized running time than others?
A : Queue
B : Stack
C : Priority Queue
D : List

Priority Queue

Q. 33. Which of the following statement about 0 1 knapsack and fractional knapsack problem is correct?
A : In 0 1 knapsack problem items are divisible and in fractional knapsack items are
indivisible
B : Both are the same
C : 0 1 knapsack is solved using a greedy algorithm and fractional knapsack is solved
using dynamic
programming
D : In 0 1 knapsack problem items are indivisible and in fractional knapsack items are
divisible

In 0 1 knapsack problem items are indivisible and in fractional knapsack items are divisible

Q. 34. Which data structure is most suitable for implementing best first branch and bound strategy?
A : Stack
B : Queue
C : Priority Queue

Priority Queue

Q. 35. Time taken in decreasing the node value in a binomial heap is
A : O(n)
B : O(1)
C : O(log n)
D : O(n log n)

O(log n)

Q. 36. Multithreaded computation can be better understood with the help of a
A : Computation undirected acyclic graph
B : Computation directed cyclic graph
C : Computation directed acyclic graph
D : Computation undirected cyclic graph

Computation directed acyclic graph

Q. 37. Which of the following is/are property/properties of a dynamic programming problem?
A : Evolutionary Approach
B : Require More Time
C : Greedy Approach
D : Optimal Substructure And Overlapping Subproblems

Optimal Substructure And Overlapping Subproblems

Q. 38.
A : 10
B : 1
C : 10 9 8 â€¦â€¦1 0
D : 10 9 8 â€¦â€¦1

10 9 8 â€¦â€¦1

Q. 39. What are desirable characteristics of Algorithm with efficiency 1)Generality 2) Availability 3) Simplicity
A : 1 and 2
B : 2 and 3
C : 1 and 3
D :

1 and 3

Q. 40. we can refere to the common sense/ intution while specifing the
algorithm
A : true
B : false
C :
D :

false

Q. 41. What are requirements should a problem satisfy in order to be suitable for solving it by a Genetic Algorithm?
A : The Fitness Function Cannot Be Wellâ€“Defined.
B : Solutions Should Be Decomposable Into Steps (Building Blocks) Which Could Be
Then Encoded As Chromosomes.
C : The Member Function Can Be Wellâ€“Defined.
D : Minimize Functions

Solutions Should Be Decomposable Into Steps (Building Blocks) Which Could Be Then Encoded As Chromosomes.

Q. 42. What is the feature of ANNs due to which they can deal with noisy, fuzzy, inconsistent data?
A : Non Associative Nature Of Networks
B : Distributive Nature Of Networks
C : Non Distributive Nature Of Networks
D : Is A Meta Heuristic Search Method

Distributive Nature Of Networks

Q. 43. Basic operations like insertion, look-up and removal in splay trees are performed in â€¦â€¦. time.
A : O(1)
B : O(n)
C : O(log n)
D : O(n log n)

O(log n)

Q. 44. Mathematical induction can be used to prove that, for any positive integer n, “Summation of first 1 to n numbers ” is
A : n(n+1)/2
B : n^2(n+1)^2/2
C : n(n-1)/2
D :

n(n+1)/2

Q. 45. Which of the following methods can be used to solve the Knapsack problem?
A : Divide And Conquer
B : Sorting Algorithm
C : Monte-Carlo Algorithm
D : Brute Force, Recursion And Dynamic Programming

Brute Force, Recursion And Dynamic Programming

Q. 46. Identify incorrect statement
A : f(n) = Î˜(g(n)) and g(n) = Î˜(h(n)), then f(n) = Î˜(h(n))
B : f(n) = Î˜(g(n)) if and only if g(n) = Î˜(f(n))
C : f(n) = O(g(n)) if and only if g(n) = Î©(f(n))
D : If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) â‰  O(h(n))

If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) â‰  O(h(n))

Q. 47. Tabu search is
A : A Binary Search Method
B : Mathematical Optimization Method
C : Non Associative
D : The Acceptance Probability Function Is Used

Mathematical Optimization Method

Q. 48. Core of soft Computing is
A : Fuzzy Computing, Neural Computing, Genetic Algorithms
B : Fuzzy Networks And Artificial Intelligence
C : Artificial Intelligence And Neural Science
D : Neural Science And Genetic Science

Fuzzy Computing, Neural Computing, Genetic Algorithms

Q. 49. algorithms performance is characterized by
A : size of a computation
B : computing resources required
C : actual time required
D : actual memory required

size of a computation

Q. 50. Find out one solution store it in solution set again find out another solution store in it solution set, again find out the another solution store into the solution set, now from the solution set we find out the best solution, which maybe best solution for optimal solution, this is which type of solution strategy?
A : Dynamic programming
B : Greedy method
C : backtracking
D : Neither Dynamic Nor Greedy

Greedy method

Q. 51. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.
A : 10080
B : 11070
C : 130110
D : 11080

11080

Q. 52. Time complexity of LCS Select one:
A : O(M!)
B : O(Mn)
C : O(N!)
D : O(N)

O(Mn)

Q. 53. In greedy method which type of solution is generated
A : Optimal solution
B : Best solution
C : Worst solution
D : All solutions

Optimal solution

Q. 54. What are the issues on which biological networks proves to be superior than AI networks?
A : Robustness & Fault Tolerance
B : Inflexibility
C : Single Computation
D : No Computation

Robustness & Fault Tolerance

Q. 55. What is time complexity of fun()? int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
A : O(nlog n)
B : O(n^2 )
C : O( n)
D : O(log n)

O( n)

Q. 56. The name backtrack was first coined by _________
A : D.H.Lehmer
B : L.Baumert
C : R.J.Walker
D : S. Golomb

D.H.Lehmer

Q. 57. Assertion is
A : statement that is true all the time
B : statement about state of program
C : statement describing program statement
D :

Q. 58. what are the ways to remove the redundant computation outside the
loop
A : Code motion
B : frequency reduction
C : Strength reduction
D : All of these

All of these

Q. 59. If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.
A : Overlapping Subproblems
B : Optimal Substructure
C : Memoization
D : Greedy

Overlapping Subproblems

Q. 60. Given items I = (I1,I2,I3,I4,I5), w = (5, 10, 20, 30, 40) and v = (30, 20, 100, 90,160). The capacity of knapsack W = 60. Find the maximum profit using fractional knapsack.
A : 250
B : 270
C : 290
D : 130