McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) .
| 301. |
How many spanning trees does a complete bipartite graph contain? |
| A. | nm |
| B. | mn-1 * nn-1 |
| C. | 1 |
| D. | 0 |
| Answer» B. mn-1 * nn-1 | |
| Explanation: spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having minimum number of edges. so, there are a total of mn-1 | |
| 302. |
What does Maximum flow problem involve? |
| A. | finding a flow between source and sink that is maximum |
| B. | finding a flow between source and sink that is minimum |
| C. | finding the shortest path between source and sink |
| D. | computing a minimum spanning tree |
| Answer» A. finding a flow between source and sink that is maximum | |
| Explanation: the maximum flow problem involves finding a feasible flow between a source and a sink in a network that is maximum and not minimum. | |
| 303. |
A network can have only one source and one sink. |
| A. | false |
| B. | true |
| Answer» B. true | |
| Explanation: a network can have only one source and one sink inorder to find the feasible flow in a weighted connected graph. | |
| 304. |
What is the source? |
| A. | vertex with no incoming edges |
| B. | vertex with no leaving edges |
| C. | centre vertex |
| D. | vertex with the least weight |
| Answer» A. vertex with no incoming edges | |
| Explanation: vertex with no incoming edges is called as a source. vertex with no leaving edges is called as a sink. | |
| 305. |
Which algorithm is used to solve a maximum flow problem? |
| A. | prim’s algorithm |
| B. | kruskal’s algorithm |
| C. | dijkstra’s algorithm |
| D. | ford-fulkerson algorithm |
| Answer» D. ford-fulkerson algorithm | |
| Explanation: ford-fulkerson algorithm is used to compute the maximum feasible flow between a source and a sink in a network. | |
| 306. |
Does Ford- Fulkerson algorithm use the idea of? |
| A. | naïve greedy algorithm approach |
| B. | residual graphs |
| C. | minimum cut |
| D. | minimum spanning tree |
| Answer» B. residual graphs | |
| Explanation: ford-fulkerson algorithm uses the idea of residual graphs which is an extension of naïve greedy approach allowing undo operations. | |
| 307. |
Under what condition can a vertex combine and distribute flow in any manner? |
| A. | it may violate edge capacities |
| B. | it should maintain flow conservation |
| C. | the vertex should be a source vertex |
| D. | the vertex should be a sink vertex |
| Answer» B. it should maintain flow conservation | |
| Explanation: a vertex can combine and distribute flow in any manner but it should not violate edge capacities and it should maintain flow conservation. | |
| 308. |
Find the maximum flow from the following graph. |
| A. | 22 |
| B. | 17 |
| C. | 15 |
| D. | 20 |
| Answer» C. 15 | |
| Explanation: initially, zero flow is computed. then, computing flow= 7+1+5+2=15. hence, maximum flow=15. | |
| 309. |
A simple acyclic path between source and sink which pass through only positive weighted edges is called? |
| A. | augmenting path |
| B. | critical path |
| C. | residual path |
| D. | maximum path |
| Answer» A. augmenting path | |
| Explanation: augmenting path between source and sink is a simple path without cycles. path consisting of zero slack edges is called critical path. | |
| 310. |
Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: dinic’s algorithm includes construction of level graphs and reslidual graphs and finding of augmenting paths along with blocking flow and is faster than the | |
| 311. |
Who is the formulator of Maximum flow problem? |
| A. | lester r. ford and delbert r. fulkerson |
| B. | t.e. harris and f.s. ross |
| C. | y.a. dinitz |
| D. | kruskal |
| Answer» B. t.e. harris and f.s. ross | |
| Explanation: the first ever people to | |
| 312. |
How many constraints does flow have? |
| A. | one |
| B. | three |
| C. | two |
| D. | four |
| Answer» C. two | |
| Explanation: a flow is a mapping which follows two constraints- conservation of flows and capacity constraints. | |
| 313. |
Stable marriage problem is an example of? |
| A. | branch and bound algorithm |
| B. | backtracking algorithm |
| C. | greedy algorithm |
| D. | divide and conquer algorithm |
| Answer» B. backtracking algorithm | |
| Explanation: stable marriage problem is an example for recursive algorithm because it recursively uses backtracking algorithm to find an optimal solution. | |
| 314. |
Which of the following algorithms does Stable marriage problem uses? |
| A. | gale-shapley algorithm |
| B. | dijkstra’s algorithm |
| C. | ford-fulkerson algorithm |
| D. | prim’s algorithm |
| Answer» A. gale-shapley algorithm | |
| Explanation: stable marriage problem uses gale-shapley algorithm. maximum flow problem uses ford-fulkerson algorithm. | |
| 315. |
An optimal solution satisfying men’s preferences is said to be? |
| A. | man optimal |
| B. | woman optimal |
| C. | pair optimal |
| D. | best optimal |
| Answer» A. man optimal | |
| Explanation: an optimal solution satisfying men’s preferences are said to be man optimal. an optimal solution satisfying woman’s preferences are said to be woman optimal. | |
| 316. |
When a free man proposes to an available woman, which of the following happens? |
| A. | she will think and decide |
| B. | she will reject |
| C. | she will replace her current mate |
| D. | she will accept |
| Answer» D. she will accept | |
| Explanation: when a man proposes to an available woman, she will accept his proposal irrespective of his position on his preference list. | |
| 317. |
If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: if there are n couples such that a man and a woman are not married, and if they prefer each other to their actual partners, the assignment is unstable. | |
| 318. |
How many 2*2 matrices are used in this problem? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: two 2*2 matrices are used. one for men representing corresponding woman and ranking and the other for women. | |
| 319. |
What happens when a free man approaches a married woman? |
| A. | she simply rejects him |
| B. | she simply replaces her mate with him |
| C. | she goes through her preference list and accordingly, she replaces her current mate with him |
| D. | she accepts his proposal |
| Answer» C. she goes through her preference list and accordingly, she replaces her current mate with him | |
| Explanation: if the preference of the man is greater, she replaces her current mate with him, leaving her current mate free. | |
| 320. |
In case of stability, how many symmetric possibilities of trouble can occur? |
| A. | 1 |
| B. | 2 |
| C. | 4 |
| D. | 3 |
| Answer» B. 2 | |
| Explanation: possibilities- there might be a woman pw, preferred to w by m, who herself prefers m to be her husband and the same applies to man as well. | |
| 321. |
Which of the following happens? |
| A. | w2 replaces m1 with m2 |
| B. | w2 rejects m2 |
| C. | w2 accepts both m1 and m2 |
| D. | w2 rejects both m1 and m2 |
| Answer» A. w2 replaces m1 with m2 | |
| Explanation: w2 is married to m1. but the preference of w2 has m2 before m1. hence, w2 replaces m1 with m2. | |
| 322. |
Who formulated a straight forward backtracking scheme for stable marriage problem? |
| A. | mcvitie and wilson |
| B. | gale |
| C. | ford and fulkerson |
| D. | dinitz |
| Answer» A. mcvitie and wilson | |
| Explanation: mcvitie and wilson formulated a much faster straight forward backtracking scheme for stable marriage problem. ford and fulkerson formulated maximum flow problem. | |
| 323. |
Can stable marriage cannot be solved using branch and bound algorithm. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: stable marriage problem can be solved using branch and bound approach because branch and bound follows backtracking scheme with a limitation factor. | |
| 324. |
What is the prime task of the stable marriage problem? |
| A. | to provide man optimal solution |
| B. | to provide woman optimal solution |
| C. | to determine stability of marriage |
| D. | to use backtracking approach |
| Answer» C. to determine stability of marriage | |
| Explanation: the prime task of stable marriage problem is to determine stability of marriage (i.e) finding a man and a woman who prefer each other to others. | |
| 325. |
Which of the following problems is related to stable marriage problem? |
| A. | choice of school by students |
| B. | n-queen problem |
| C. | arranging data in a database |
| D. | knapsack problem |
| Answer» A. choice of school by students | |
| Explanation: choice of school by students is the most related example in the given set of options since both school and students will have a preference list. | |
| 326. |
What is the efficiency of Gale-Shapley algorithm used in stable marriage problem? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(log n) |
| Answer» C. o(n2) | |
| Explanation: the time efficiency of gale- shapley algorithm is mathematically found to be o(n2) where n denotes stable marriage problem. | |
| 327. |
is a matching with the largest number of edges. |
| A. | maximum bipartite matching |
| B. | non-bipartite matching |
| C. | stable marriage |
| D. | simplex |
| Answer» A. maximum bipartite matching | |
| Explanation: maximum bipartite matching matches two elements with a property that no two edges share a vertex. | |
| 328. |
Maximum matching is also called as maximum cardinality matching. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges. | |
| 329. |
How many colours are used in a bipartite graph? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: a bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours. | |
| 330. |
What is the simplest method to prove that a graph is bipartite? |
| A. | it has a cycle of an odd length |
| B. | it does not have cycles |
| C. | it does not have a cycle of an odd length |
| D. | both odd and even cycles are formed |
| Answer» C. it does not have a cycle of an odd length | |
| Explanation: it is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length. | |
| 331. |
A matching that matches all the vertices of a graph is called? |
| A. | perfect matching |
| B. | cardinality matching |
| C. | good matching |
| D. | simplex matching |
| Answer» A. perfect matching | |
| Explanation: a matching that matches all the vertices of a graph is called perfect matching. | |
| 332. |
In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called? |
| A. | bipartite matching |
| B. | cardinality matching |
| C. | augmenting |
| D. | weight matching |
| Answer» C. augmenting | |
| Explanation: a simple path from a free vertex in v to a free vertex in u whose edges alternate between edges not in m and edges in m is called a augmenting path. | |
| 333. |
A matching M is maximal if and only if there exists no augmenting path with respect to M. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: according to the theorem discovered by the french mathematician claude berge, it means that the current matching is maximal if there is no augmenting path. | |
| 334. |
Which one of the following is an application for matching? |
| A. | proposal of marriage |
| B. | pairing boys and girls for a dance |
| C. | arranging elements in a set |
| D. | finding the shortest traversal path |
| Answer» B. pairing boys and girls for a dance | |
| Explanation: pairing boys and girls for a dance is a traditional example for matching. proposal of marriage is an application of stable marriage problem. | |
| 335. |
Which is the correct technique for finding a maximum matching in a graph? |
| A. | dfs traversal |
| B. | bfs traversal |
| C. | shortest path traversal |
| D. | heap order traversal |
| Answer» B. bfs traversal | |
| Explanation: the correct technique for finding a maximum matching in a bipartite graph is by using a breadth first search(bfs). | |
| 336. |
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» C. maximum weight matching | |
| Explanation: the problem is called as maximum weight matching which is similar to a bipartite matching. it is also called as assignment problem. | |
| 337. |
Who was the first person to solve the maximum matching problem? |
| A. | jack edmonds |
| B. | hopcroft |
| C. | karp |
| D. | claude berge |
| Answer» A. jack edmonds | |
| Explanation: jack edmonds was the first person to solve the maximum matching problem in 1965. | |
| 338. |
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» A. 5 | |
| Explanation: one of the solutions of the matching problem is given by a-w,b-v,c-x,d- y,e-z. hence the answer is 5. | |
| 339. |
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» A. o(p(n)) | |
| Explanation: the worst-case efficiency of solving an problem in polynomial time is o(p(n)) where p(n) is the polynomial time of input size. | |
| 340. |
Problems that can be solved in polynomial time are known as? |
| A. | intractable |
| B. | tractable |
| C. | decision |
| D. | complete |
| Answer» B. tractable | |
| Explanation: problems that can be solved in polynomial time are known as tractable. | |
| 341. |
The sum and composition of two polynomials are always polynomials. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: one of the properties of polynomial functions states that the sum and composition of two polynomials are always polynomials. | |
| 342. |
is the class of decision problems that can be solved by non- deterministic polynomial algorithms? |
| A. | np |
| B. | p |
| C. | hard |
| D. | complete |
| Answer» A. np | |
| Explanation: np problems are called as non- deterministic polynomial problems. they are a class of decision problems that can be solved using np algorithms. | |
| 343. |
Problems that cannot be solved by any algorithm are called? |
| A. | tractable problems |
| B. | intractable problems |
| C. | undecidable problems |
| D. | decidable problems |
| Answer» C. undecidable problems | |
| Explanation: problems cannot be solved by any algorithm are called undecidable problems. problems that can be solved in polynomial time are called tractable problems. | |
| 344. |
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» D. o(n2) | |
| Explanation: mathematically, the run time of euler’s circuit problem is determined to be o(n2). | |
| 345. |
To which class does the Euler’s circuit problem belong? |
| A. | p class |
| B. | np class |
| C. | partition class |
| D. | complete class |
| Answer» A. p class | |
| Explanation: euler’s circuit problem can be solved in polynomial time. it can be solved in o(n2). | |
| 346. |
Halting problem is an example for? |
| A. | decidable problem |
| B. | undecidable problem |
| C. | complete problem |
| D. | trackable problem |
| Answer» B. undecidable problem | |
| Explanation: halting problem by alan turing cannot be solved by any algorithm. hence, it is undecidable. | |
| 347. |
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» A. true | |
| Explanation: one of the properties of np class problems states that a non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial. | |
| 348. |
How many conditions have to be met if an NP- complete problem is polynomially reducible? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: a function t that maps all yes instances of decision problems d1 and d2 and t should be computed in polynomial time are the two conditions. | |
| 349. |
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» C. np complete | |
| Explanation: the cnf satisfiability problem belongs to np complete class. it deals with boolean expressions. | |
| 350. |
How many steps are required to prove that a decision problem is NP complete? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: first, the problem should be np. next, it should be proved that every problem in np is reducible to the problem in question in polynomial time. | |
Done Studing? Take A Test.
Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.