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.
| 201. |
Every Perfect graph has forbidden graph characterization. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 202. |
It is possible to have a negative chromatic number of bipartite graph. |
| A. | true |
| B. | false |
| Answer» C. | |
| 203. |
Which of the following has maximum clique size 2? |
| A. | perfect graph |
| B. | tree |
| C. | histogram |
| D. | cartesian |
| Answer» B. tree | |
| 204. |
What is the clique size of the line graph of bipartite graph? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» D. 3 | |
| 205. |
What is the chromatic number of compliment of line graph of bipartite graph? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» D. 3 | |
| 206. |
Which of the following is not a property of perfect graph? |
| A. | compliment of line graph of bipartite graph |
| B. | compliment of bipartite graph |
| C. | line graph of bipartite graph |
| D. | line graph |
| Answer» E. | |
| 207. |
Which graph has a size of minimum vertex cover equal to maximum matching? |
| A. | cartesian |
| B. | tree |
| C. | heap |
| D. | bipartite |
| Answer» E. | |
| 208. |
Which theorem gives the relation between the minimum vertex cover and maximum matching? |
| A. | konig’s theorem |
| B. | kirchhoff’s theorem |
| C. | kuratowski’s theorem |
| D. | kelmans theorem |
| Answer» B. kirchhoff’s theorem | |
| 209. |
Which one of the following is the chromatic number of bipartite graph? |
| A. | 1 |
| B. | 4 |
| C. | 3 |
| D. | 5 |
| Answer» B. 4 | |
| 210. |
Which of the following is not a property of the bipartite graph? |
| A. | no odd cycle |
| B. | symmetric spectrum |
| C. | chromatic number is less than or equal to 2 |
| D. | asymmetric spectrum |
| Answer» E. | |
| 211. |
Which of the following is the correct type of spectrum of the bipartite graph? |
| A. | symmetric |
| B. | anti – symmetric |
| C. | circular |
| D. | exponential |
| Answer» B. anti – symmetric | |
| 212. |
What type of graph has chromatic number less than or equal to 2? |
| A. | histogram |
| B. | bipartite |
| C. | cartesian |
| D. | tree |
| Answer» C. cartesian | |
| 213. |
Which type of graph has no odd cycle in it? |
| A. | bipartite |
| B. | histogram |
| C. | cartesian |
| D. | pie |
| Answer» B. histogram | |
| 214. |
A graph is found to be 2 colorable. What can be said about that graph? |
| A. | the given graph is eulerian |
| B. | the given graph is bipartite |
| C. | the given graph is hamiltonian |
| D. | the given graph is planar |
| Answer» C. the given graph is hamiltonian | |
| 215. |
Can there exist a graph which is both eulerian and is bipartite? |
| A. | yes |
| B. | no |
| C. | yes if it has even number of edges |
| D. | nothing can be said |
| Answer» B. no | |
| 216. |
Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite? |
| A. | yes |
| B. | no |
| Answer» B. no | |
| 217. |
A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite) |
| A. | 100 |
| B. | 140 |
| C. | 80 |
| D. | 20 |
| Answer» B. 140 | |
| 218. |
Are trees bipartite? |
| A. | yes |
| B. | no |
| C. | yes if it has even number of vertices |
| D. | no if it has odd number of vertices |
| Answer» B. no | |
| 219. |
When is a graph said to be bipartite? |
| A. | if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b |
| B. | if the graph is connected and it has odd number of vertices |
| C. | if the graph is disconnected |
| D. | if the graph has at least n/2 vertices whose degree is greater than n/2 |
| Answer» B. if the graph is connected and it has odd number of vertices | |
| 220. |
A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is? |
| A. | n |
| B. | n/2 |
| C. | n/4 |
| D. | data insufficient |
| Answer» C. n/4 | |
| 221. |
A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them? |
| A. | number of vertices in u=number of vertices in v |
| B. | number of vertices in u not equal to number of vertices in v |
| C. | number of vertices in u always greater than the number of vertices in v |
| D. | nothing can be said |
| Answer» B. number of vertices in u not equal to number of vertices in v | |
| 222. |
Find the maximum value output assuming items to be divisible and nondivisible respectively. |
| A. | 100, 80 |
| B. | 110, 70 |
| C. | 130, 110 |
| D. | 110, 80 |
| Answer» E. | |
| 223. |
Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them? |
| A. | number of vertices in u = number of vertices in v |
| B. | sum of degrees of vertices in u = sum of degrees of vertices in v |
| C. | number of vertices in u > number of vertices in v |
| D. | nothing can be said |
| Answer» C. number of vertices in u > number of vertices in v | |
| 224. |
The main time taking step in fractional knapsack problem is |
| A. | breaking items into fraction |
| B. | adding items into knapsack |
| C. | sorting |
| D. | looping through sorted items |
| Answer» D. looping through sorted items | |
| 225. |
The result of the fractional knapsack is greater than or equal to 0/1 knapsack. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 226. |
Fractional knapsack problem can be solved in time O(n). |
| A. | true |
| B. | false |
| Answer» B. false | |
| 227. |
Find the maximum value output assuming items to be divisible. |
| A. | 60 |
| B. | 80 c) 100 |
| C. | d) 40 |
| Answer» B. 80 c) 100 | |
| 228. |
Time complexity of fractional knapsack problem is |
| A. | o(n log n) |
| B. | o(n) |
| C. | o(n2) |
| D. | o(nw) |
| Answer» B. o(n) | |
| 229. |
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 |
| Answer» E. | |
| 230. |
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 |
| Answer» B. to get minimum total value in the knapsack | |
| 231. |
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 |
| Answer» D. backtracking | |
| 232. |
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 |
| Answer» C. divisible knapsack problem | |
| 233. |
Consider the graph shown below. Which of the following are the edges in the MST of the given graph? |
| A. | (a-c)(c-d)(d-b)(d-b) |
| B. | (c-a)(a-d)(d-b)(d-e) |
| C. | (a-d)(d-c)(d-b)(d-e) |
| D. | (c-a)(a-d)(d-c)(d-b)(d-e) |
| Answer» D. (c-a)(a-d)(d-c)(d-b)(d-e) | |
| 234. |
Which of the following edges form minimum spanning tree on the graph using kruskals algorithm? |
| A. | (b-e)(g-e)(e-f)(d-f) |
| B. | (b-e)(g-e)(e-f)(b-g)(d-f) |
| C. | (b-e)(g-e)(e-f)(d-e) |
| D. | (b-e)(g-e)(e-f)(d-f)(d-g) |
| Answer» B. (b-e)(g-e)(e-f)(b-g)(d-f) | |
| 235. |
Prim’s algorithm resembles Dijkstra’s algorithm. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 236. |
What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true? |
| A. | nth catalan number |
| B. | n factorial |
| C. | n cube |
| D. | n square |
| Answer» B. n factorial | |
| 237. |
Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms? |
| A. | n factorial |
| B. | n square |
| C. | n cube |
| D. | nth catalan number |
| Answer» E. | |
| 238. |
Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» D. 3 | |
| 239. |
There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved? |
| A. | 0 |
| B. | 2 |
| C. | 4 |
| D. | 8 |
| Answer» B. 2 | |
| 240. |
There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together? |
| A. | 1 |
| B. | f*f |
| C. | n*n |
| D. | n*f |
| Answer» E. | |
| 241. |
There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together? |
| A. | 1 |
| B. | f |
| C. | n |
| D. | n*f |
| Answer» D. n*f | |
| 242. |
You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together? |
| A. | 27 |
| B. | 36 |
| C. | 216 |
| D. | 81 |
| Answer» D. 81 | |
| 243. |
You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» D. 3 | |
| 244. |
You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem? |
| A. | brute force |
| B. | recursion |
| C. | dynamic programming |
| D. | brute force, recursion and dynamic programming |
| Answer» E. | |
| 245. |
You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together? |
| A. | n*n*n…f times |
| B. | f*f*f…n times |
| C. | n*n*n…n times |
| D. | f*f*f…f times |
| Answer» C. n*n*n…n times | |
| 246. |
In which of the following cases, it is not possible to have two subsets with equal sum? |
| A. | when the number of elements is odd |
| B. | when the number of elements is even |
| C. | when the sum of elements is odd |
| D. | when the sum of elements is even |
| Answer» D. when the sum of elements is even | |
| 247. |
What is the time complexity of the brute force algorithm used to solve the balanced partition problem? |
| A. | o(1) |
| B. | o(n) |
| C. | o(n2) |
| D. | o(2n) |
| Answer» E. | |
| 248. |
Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem? |
| A. | dynamic programming |
| B. | recursion |
| C. | brute force |
| D. | dynamic programming, recursion, brute force |
| Answer» E. | |
| 249. |
What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}? |
| A. | 16 |
| B. | 32 |
| C. | 64 |
| Answer» B. 32 | |
| 250. |
The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm? |
| A. | hirschberg’s algorithm |
| B. | needleman-wunsch algorithm |
| C. | kadane’s algorithm |
| D. | wagner fischer algorithm |
| Answer» D. wagner fischer algorithm | |