MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 397 Mcqs, each offering curated multiple-choice questions to sharpen your Computer Science Engineering (CSE) knowledge and support exam preparation. Choose a topic below to get started.
| 101. |
Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity? |
| A. | true |
| B. | false |
| Answer» B. false | |
| 102. |
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 | |
| 103. |
The concept of cross product is applied in the field of computer graphics. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 104. |
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. | |
| 105. |
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 | |
| 106. |
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 | |
| 107. |
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 | |
| 108. |
What is the LCM of 8 and 13? |
| A. | 8 |
| B. | 12 |
| C. | 20 |
| D. | 104 |
| Answer» E. | |
| 109. |
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. | |
| 110. |
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 | |
| 111. |
Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity. |
| A. | true |
| B. | false |
| Answer» C. | |
| 112. |
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. | |
| 113. |
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 | |
| 114. |
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. | |
| 115. |
Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity. |
| A. | true |
| B. | false |
| Answer» C. | |
| 116. |
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 | |
| 117. |
Subset sum problem is an example of NP- complete problem. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 118. |
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 | |
| 119. |
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 | |
| 120. |
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 | |
| 121. |
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) | |
| 122. |
How many Hamiltonian paths does the following graph have? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| 123. |
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 | |
| 124. |
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 | |
| 125. |
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) | |
| 126. |
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. | |
| 127. |
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 | |
| 128. |
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 | |
| 129. |
There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem. |
| A. | true |
| B. | false |
| Answer» C. | |
| 130. |
Hamiltonian path problem is |
| A. | np problem |
| B. | n class problem |
| C. | p class problem |
| D. | np complete problem |
| Answer» E. | |
| 131. |
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 | |
| 132. |
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 | |
| 133. |
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 | |
| 134. |
Which of the following problems is not NP complete? |
| A. | hamiltonian circuit |
| B. | bin packing |
| C. | partition problem |
| D. | halting problem |
| Answer» E. | |
| 135. |
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 | |
| 136. |
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 | |
| 137. |
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 | |
| 138. |
How many stages of procedure does a non- deterministic algorithm consist of? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 139. |
Halting problem is an example for? |
| A. | decidable problem |
| B. | undecidable problem |
| C. | complete problem |
| D. | trackable problem |
| Answer» C. complete problem | |
| 140. |
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 | |
| 141. |
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 | |
| 142. |
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. | |
| 143. |
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 | |
| 144. |
                   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 | |
| 145. |
The sum and composition of two polynomials are always polynomials. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 146. |
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)) | |
| 147. |
Problems that can be solved in polynomial time are known as? |
| A. | intractable |
| B. | tractable |
| C. | decision |
| D. | complete |
| Answer» C. decision | |
| 148. |
Who was the first person to solve the maximum matching problem? |
| A. | jack edmonds |
| B. | hopcroft |
| C. | karp |
| D. | claude berge |
| Answer» B. hopcroft | |
| 149. |
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 | |
| 150. |
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 | |