MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 657 Mcqs, each offering curated multiple-choice questions to sharpen your Testing Subject knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity? |
| A. | true |
| B. | false |
| Answer» B. false | |
| 2. |
Floyd Warshall’s Algorithm can be applied on |
| A. | undirected and unweighted graphs |
| B. | undirected graphs |
| C. | directed graphs |
| D. | acyclic graphs |
| Answer» D. acyclic graphs | |
| 3. |
The concept of cross product is applied in the field of computer graphics. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 4. |
What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k? |
| A. | i + 2j + k |
| B. | i – j – 5k |
| C. | 2i – j – 5k |
| Answer» D. | |
| 5. |
An optimal solution satisfying men’s preferences is said to be? |
| A. | man optimal |
| B. | woman optimal |
| C. | pair optimal |
| D. | best optimal |
| Answer» B. woman optimal | |
| 6. |
Longest palindromic subsequence is an example of |
| A. | greedy algorithm |
| B. | 2d dynamic programming |
| C. | 1d dynamic programming |
| D. | divide and conquer |
| Answer» C. 1d dynamic programming | |
| 7. |
You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using |
| A. | greedy algorithm |
| B. | dynamic programming |
| C. | divide and conquer |
| D. | backtracking |
| Answer» C. divide and conquer | |
| 8. |
What is the LCM of 8 and 13? |
| A. | 8 |
| B. | 12 |
| C. | 20 |
| D. | 104 |
| Answer» E. | |
| 9. |
What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)? |
| A. | o(n log n) |
| B. | o(n2) |
| C. | o(2n) |
| D. | o(sum*n) |
| Answer» E. | |
| 10. |
Which of the following is true about the time complexity of the recursive solution of set partition problem? |
| A. | it has an exponential time complexity |
| B. | it has a linear time complexity |
| C. | it has a logarithmic time complexity |
| D. | it has a time complexity of o(n2) |
| Answer» B. it has a linear time complexity | |
| 11. |
Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity. |
| A. | true |
| B. | false |
| Answer» C. | |
| 12. |
What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)? |
| A. | o(n) |
| B. | o(sum) |
| C. | o(n2) |
| D. | o(sum*n) |
| Answer» E. | |
| 13. |
What is the set partition problem? |
| A. | finding a subset of a set that has sum of elements equal to a given number |
| B. | checking for the presence of a subset that has sum of elements equal to a given number |
| C. | checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result |
| D. | finding subsets with equal sum of elements |
| Answer» D. finding subsets with equal sum of elements | |
| 14. |
Which of the following is not true about subset sum problem? |
| A. | the recursive solution has a time complexity of o(2n) |
| B. | there is no known solution that takes polynomial time |
| C. | the recursive solution is slower than dynamic programming solution |
| D. | the dynamic programming solution has a time complexity of o(n log n) |
| Answer» E. | |
| 15. |
Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity. |
| A. | true |
| B. | false |
| Answer» C. | |
| 16. |
What is meant by the power set of a set? |
| A. | subset of all sets |
| B. | set of all subsets |
| C. | set of particular subsets |
| D. | an empty set |
| Answer» C. set of particular subsets | |
| 17. |
Subset sum problem is an example of NP- complete problem. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 18. |
Which of the following is true about the time complexity of the recursive solution of the subset sum problem? |
| A. | it has an exponential time complexity |
| B. | it has a linear time complexity |
| C. | it has a logarithmic time complexity |
| D. | it has a time complexity of o(n2) |
| Answer» B. it has a linear time complexity | |
| 19. |
What is a subset sum problem? |
| A. | finding a subset of a set that has sum of elements equal to a given number |
| B. | checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result |
| C. | finding the sum of elements present in a set |
| D. | finding the sum of all the subsets of a set |
| Answer» C. finding the sum of elements present in a set | |
| 20. |
Under what condition any set A will be a subset of B? |
| A. | if all elements of set b are also present in set a |
| B. | if all elements of set a are also present in set b |
| C. | if a contains more elements than b |
| D. | if b contains more elements than a |
| Answer» C. if a contains more elements than b | |
| 21. |
For a graph of degree three, in what time can a Hamiltonian path be found? |
| A. | o(0.251n) |
| B. | o(0.401n) |
| C. | o(0.167n) |
| D. | o(0.151n) |
| Answer» B. o(0.401n) | |
| 22. |
How many Hamiltonian paths does the following graph have? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| 23. |
In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 24. |
Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem? |
| A. | karp |
| B. | leonard adleman |
| C. | andreas bjorklund |
| D. | martello |
| Answer» D. martello | |
| 25. |
What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)? |
| A. | o(n!) |
| B. | o(n! * n) |
| C. | o(log n) |
| D. | o(n) |
| Answer» C. o(log n) | |
| 26. |
In what time can the Hamiltonian path problem can be solved using dynamic programming? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(n2 2n) |
| Answer» E. | |
| 27. |
Who formulated the first ever algorithm for solving the Hamiltonian path problem? |
| A. | martello |
| B. | monte carlo |
| C. | leonard |
| D. | bellman |
| Answer» B. monte carlo | |
| 28. |
Which of the following problems is similar to that of a Hamiltonian path problem? |
| A. | knapsack problem |
| B. | closest pair problem |
| C. | travelling salesman problem |
| D. | assignment problem |
| Answer» D. assignment problem | |
| 29. |
There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem. |
| A. | true |
| B. | false |
| Answer» C. | |
| 30. |
Hamiltonian path problem is |
| A. | np problem |
| B. | n class problem |
| C. | p class problem |
| D. | np complete problem |
| Answer» E. | |
| 31. |
The problem of finding a path in a graph that visits every vertex exactly once is called? |
| A. | hamiltonian path problem |
| B. | hamiltonian cycle problem |
| C. | subset sum problem |
| D. | turnpike reconstruction problem |
| Answer» B. hamiltonian cycle problem | |
| 32. |
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 |
| Answer» B. iterative improvement | |
| 33. |
The choice of polynomial class has led to the development of an extensive theory called |
| A. | computational complexity |
| B. | time complexity |
| C. | problem complexity |
| D. | decision complexity |
| Answer» B. time complexity | |
| 34. |
Which of the following problems is not NP complete? |
| A. | hamiltonian circuit |
| B. | bin packing |
| C. | partition problem |
| D. | halting problem |
| Answer» E. | |
| 35. |
How many steps are required to prove that a decision problem is NP complete? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 36. |
To which of the following class does a CNF-satisfiability problem belong? |
| A. | np class |
| B. | p class |
| C. | np complete |
| D. | np hard |
| Answer» D. np hard | |
| 37. |
How many conditions have to be met if an NP- complete problem is polynomially reducible? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 38. |
How many stages of procedure does a non- deterministic algorithm consist of? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 39. |
Halting problem is an example for? |
| A. | decidable problem |
| B. | undecidable problem |
| C. | complete problem |
| D. | trackable problem |
| Answer» C. complete problem | |
| 40. |
To which class does the Euler’s circuit problem belong? |
| A. | p class |
| B. | np class |
| C. | partition class |
| D. | complete class |
| Answer» B. np class | |
| 41. |
A non-deterministic algorithm is said to be non-deterministic polynomial if the time- efficiency of its verification stage is polynomial. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 42. |
The Euler’s circuit problem can be solved in? |
| A. | o(n) |
| B. | o( n log n) |
| C. | o(log n) |
| D. | o(n2) |
| Answer» E. | |
| 43. |
Problems that cannot be solved by any algorithm are called? |
| A. | tractable problems |
| B. | intractable problems |
| C. | undecidable problems |
| D. | decidable problems |
| Answer» D. decidable problems | |
| 44. |
                   is the class of decision problems that can be solved by non- deterministic polynomial algorithms? |
| A. | np |
| B. | p |
| C. | hard |
| D. | complete |
| Answer» B. p | |
| 45. |
The sum and composition of two polynomials are always polynomials. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 46. |
The worst-case efficiency of solving a problem in polynomial time is? |
| A. | o(p(n)) |
| B. | o(p( n log n)) |
| C. | o(p(n2)) |
| D. | o(p(m log n)) |
| Answer» B. o(p( n log n)) | |
| 47. |
Problems that can be solved in polynomial time are known as? |
| A. | intractable |
| B. | tractable |
| C. | decision |
| D. | complete |
| Answer» C. decision | |
| 48. |
Who was the first person to solve the maximum matching problem? |
| A. | jack edmonds |
| B. | hopcroft |
| C. | karp |
| D. | claude berge |
| Answer» B. hopcroft | |
| 49. |
From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm? |
| A. | 5 |
| B. | 4 |
| C. | 3 |
| D. | 2 |
| Answer» B. 4 | |
| 50. |
The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is? |
| A. | maximum- mass matching |
| B. | maximum bipartite matching |
| C. | maximum weight matching |
| D. | maximum node matching |
| Answer» D. maximum node matching | |