McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) .
| 251. |
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» A. nth catalan number | |
| Explanation: the number of ways will be maximum when all the possible | |
| 252. |
Which of the following is true? |
| A. | prim’s algorithm can also be used for disconnected graphs |
| B. | kruskal’s algorithm can also run on the disconnected graphs |
| C. | prim’s algorithm is simpler than kruskal’s algorithm |
| D. | in kruskal’s sort edges are added to mst in decreasing order of their weights |
| Answer» B. kruskal’s algorithm can also run on the disconnected graphs | |
| Explanation: prim’s algorithm iterates from one node to another, so it can not be applied for disconnected graph. kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest. kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm. | |
| 253. |
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» C. (a-d)(d-c)(d-b)(d-e) | |
| Explanation: the minimum spanning tree of the given graph is shown below. it has cost 56. | |
| 254. |
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» B. continuous knapsack problem | |
| Explanation: fractional knapsack problem is also called continuous knapsack problem. | |
| 255. |
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» C. greedy algorithm | |
| Explanation: greedy algorithm is used to solve this problem. we first sort items according to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. at the end, we add the next item as much as we can. | |
| 256. |
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» A. to get maximum total value in the knapsack | |
| Explanation: the objective is to fill the knapsack of some given volume with different materials such that the value of selected items is maximized. | |
| 257. |
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» D. in 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible | |
| Explanation: in fractional knapsack problem we can partially include an item into the knapsack whereas in 0/1 knapsack we have to either include or exclude the item wholly. | |
| 258. |
Time complexity of fractional knapsack problem is |
| A. | o(n log n) |
| B. | o(n) |
| C. | o(n2) |
| D. | o(nw) |
| Answer» A. o(n log n) | |
| Explanation: as the main time taking a step is of sorting so it defines the time complexity of our code. so the time complexity will be o(n log n) if we use quick sort for sorting. | |
| 259. |
Fractional knapsack problem can be solved in time O(n). |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: it is possible to solve the problem in o(n) time by adapting the algorithm for finding weighted medians. | |
| 260. |
Find the maximum value output assuming items to be divisible. |
| A. | 60 |
| B. | 80 |
| C. | 100 |
| D. | 40 |
| Answer» A. 60 | |
| Explanation: the value/weight ratio are- | |
| 261. |
The result of the fractional knapsack is greater than or equal to 0/1 knapsack. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: as fractional knapsack gives extra liberty to include the object partially which is not possible with 0/1 knapsack, thus | |
| 262. |
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» C. sorting | |
| Explanation: the main time taking step is to sort the items according to their value/weight ratio. it defines the time complexity of the code. | |
| 263. |
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» D. 110, 80 | |
| Explanation: assuming items to be divisible- the value/weight ratio are {3, 2, 4}.so we include third and first items wholly. so, now only 15 units of volume are left for second item. so we include it partially. | |
| 264. |
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» B. sum of degrees of vertices in u = sum of degrees of vertices in v | |
| Explanation: we can prove this by induction. by adding one edge, the degree of vertices in u is equal to 1 as well as in v. let us assume that this is true for n-1 edges and add one more edge. since the given edge adds exactly once to both u and v we can tell that this statement is true for all n vertices. | |
| 265. |
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» A. number of vertices in u=number of vertices in v | |
| Explanation: we know that in a bipartite graph sum of degrees of vertices in u=sum of degrees of vertices in v. given that the graph is a k-regular bipartite graph, we have k* (number of vertices in u)=k*(number of vertices in v). | |
| 266. |
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» B. n/2 | |
| Explanation: we can prove this by calculus. let x be the total number of vertices on set x. therefore set y will have n-x. we have to maximize x*(n-x). this is true when x=n/2. | |
| 267. |
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» 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 | |
| Explanation: a graph is said to be bipartite if it can be divided into two independent sets a and b such that each edge connects a vertex from a to b. | |
| 268. |
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» A. yes | |
| Explanation: condition needed is that there should not be an odd cycle. but in a tree there are no cycles at all. hence it is bipartite. | |
| 269. |
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» A. 100 | |
| Explanation: let the given bipartition x have x vertices, then y will have 20-x vertices. we need to maximize x*(20-x). this will be maxed when x=10. | |
| 270. |
Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite? |
| A. | yes |
| B. | no |
| Answer» A. yes | |
| Explanation: it is required that the graph is connected also. if it is not then it cannot be called a bipartite graph. | |
| 271. |
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» A. yes | |
| Explanation: if a graph is such that there exists a path which visits every edge atleast once, then it is said to be eulerian. taking an example of a square, the given question evaluates to yes. | |
| 272. |
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» B. the given graph is bipartite | |
| Explanation: a graph is said to be colorable if two vertices connected by an edge are never of the same color. 2 colorable mean that this can be achieved with just 2 colors. | |
| 273. |
Which type of graph has no odd cycle in it? |
| A. | bipartite |
| B. | histogram |
| C. | cartesian |
| D. | pie |
| Answer» A. bipartite | |
| Explanation: the graph is known as bipartite if the graph does not contain any odd length cycle in it. odd length cycle means a cycle with the odd number of vertices in it. | |
| 274. |
What type of graph has chromatic number less than or equal to 2? |
| A. | histogram |
| B. | bipartite |
| C. | cartesian |
| D. | tree |
| Answer» B. bipartite | |
| Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is chromatic number. | |
| 275. |
Which of the following is the correct type of spectrum of the bipartite graph? |
| A. | symmetric |
| B. | anti – symmetric |
| C. | circular |
| D. | exponential |
| Answer» A. symmetric | |
| Explanation: the spectrum of the bipartite graph is symmetric in nature. the spectrum is the property of graph that are related to polynomial, eigen values, eigen vectors of the matrix related to graph. | |
| 276. |
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» D. asymmetric spectrum | |
| Explanation: a graph is known to be bipartite if it has odd length cycle number. it also has symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2. | |
| 277. |
Which one of the following is the chromatic number of bipartite graph? |
| A. | 1 |
| B. | 4 |
| C. | 3 |
| D. | 5 |
| Answer» A. 1 | |
| Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is the chromatic number. | |
| 278. |
Which graph has a size of minimum vertex cover equal to maximum matching? |
| A. | cartesian |
| B. | tree |
| C. | heap |
| D. | bipartite |
| Answer» D. bipartite | |
| Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching. | |
| 279. |
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» A. konig’s theorem | |
| Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching. | |
| 280. |
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» D. line graph | |
| Explanation: tthe compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is known as a perfect graph in graph theory. normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph. | |
| 281. |
Which of the following has maximum clique size 2? |
| A. | perfect graph |
| B. | tree |
| C. | histogram |
| D. | cartesian |
| Answer» A. perfect graph | |
| Explanation: the perfect bipartite graph has clique size 2. also, the clique size of compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is 2. | |
| 282. |
What is the chromatic number of compliment of line graph of bipartite graph? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» C. 2 | |
| Explanation: the perfect bipartite graph has chromatic number 2. so the compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph has chromatic number 2. | |
| 283. |
What is the clique size of the line graph of bipartite graph? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» C. 2 | |
| Explanation: the perfect bipartite graph has clique size 2. so the clique size of compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is 2. | |
| 284. |
It is possible to have a negative chromatic number of bipartite graph. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is the chromatic number. but the chromatic number cannot be negative. | |
| 285. |
Every Perfect graph has forbidden graph characterization. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: berge theorem proves the forbidden graph characterization of every perfect graphs. because of that reason every bipartite graph is perfect graph. | |
| 286. |
Which structure can be modelled by using Bipartite graph? |
| A. | hypergraph |
| B. | perfect graph |
| C. | hetero graph |
| D. | directed graph |
| Answer» A. hypergraph | |
| Explanation: a combinatorial structure such as hypergraph can be made using the bipartite graphs. a hypergraph in graph | |
| 287. |
Which type of graph has all the vertex of the first set connected to all the vertex of the second set? |
| A. | bipartite |
| B. | complete bipartite |
| C. | cartesian |
| D. | pie |
| Answer» B. complete bipartite | |
| Explanation: the graph is known as bipartite if the graph does not contain any odd length cycle in it. the complete bipartite graph has all the vertex of first set connected to all the vertex of second set. | |
| 288. |
Which graph is also known as biclique? |
| A. | histogram |
| B. | complete bipartite |
| C. | cartesian |
| D. | tree |
| Answer» B. complete bipartite | |
| Explanation: a graph is known as complete bipartite graph if and only if it has all the vertex of first set connected to all the vertex of second set. complete bipartite graph is also known as biclique. | |
| 289. |
Which term defines all the complete bipartite graph that are trees? |
| A. | symmetric |
| B. | anti – symmetric |
| C. | circular |
| D. | stars |
| Answer» D. stars | |
| Explanation: star is a complete bipartite graph with one internal node and k leaves. therefore, all complete bipartite graph which is trees are known as stars in graph theory. | |
| 290. |
How many edges does a n vertex triangle free graph contains? |
| A. | n2 |
| B. | n2 + 2 |
| C. | n2 / 4 |
| D. | n3 |
| Answer» C. n2 / 4 | |
| Explanation: a n vertex triangle free graph contains a total of n2 / 4 number of edges. this is stated by mantel’s theorem which is a special case in turan’s theorem for r=2. | |
| 291. |
Which graph is used to define the claw free graph? |
| A. | bipartite graph |
| B. | claw graph |
| C. | star graph |
| D. | cartesian graph |
| Answer» B. claw graph | |
| Explanation: star is a complete bipartite graph with one internal node and k leaves. star with three edges is called a claw. hence this graph is used to define claw free graph. | |
| 292. |
What is testing of a complete bipartite subgraph in a bipartite graph problem called? |
| A. | p problem |
| B. | p-complete problem |
| C. | np problem |
| D. | np-complete problem |
| Answer» D. np-complete problem | |
| Explanation: np stands for nondeterministic polynomial time. in a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an np-complete problem. | |
| 293. |
Which graph cannot contain K3, 3 as a minor of graph? |
| A. | planar graph |
| B. | outer planar graph |
| C. | non planar graph |
| D. | inner planar graph |
| Answer» A. planar graph | |
| Explanation: minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off | |
| 294. |
Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph? |
| A. | (nm)1/2 |
| B. | (-nm)1/2 |
| C. | 0 |
| D. | nm |
| Answer» D. nm | |
| Explanation: the adjacency matrix is a square matrix that is used to represent a finite graph. therefore, the eigen values for the complete bipartite graph is found to be (nm)1/2, (-nm)1/2, 0. | |
| 295. |
Which complete graph is not present in minor of Outer Planar Graph? |
| A. | k3, 3 |
| B. | k3, 1 |
| C. | k3, 2 |
| D. | k1, 1 |
| Answer» C. k3, 2 | |
| Explanation: minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. hence outer planar graph cannot contain k3, 2 as a minor graph. | |
| 296. |
Is every complete bipartite graph a Moore Graph. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: in graph theory, moore graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a moore graph. | |
| 297. |
What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value? |
| A. | 1 |
| B. | n + m – 2 |
| C. | 0 |
| D. | 2 |
| Answer» B. n + m – 2 | |
| Explanation: the adjacency matrix is a square matrix that is used to represent a finite graph. the multiplicity of the adjacency matrix off complete bipartite graph with eigen value 0 is n + m – 2. | |
| 298. |
Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph? |
| A. | n + m |
| B. | n |
| C. | 0 |
| D. | n*m |
| Answer» D. n*m | |
| Explanation: the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. therefore, the eigen values for the complete bipartite graph is found to be n + m, n, m, 0. | |
| 299. |
What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value? |
| A. | 1 |
| B. | m-1 |
| C. | n-1 |
| D. | 0 |
| Answer» B. m-1 | |
| Explanation: the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. the multiplicity of the laplacian matrix of complete bipartite graph with eigen value n is m-1. | |
| 300. |
Is it true that every complete bipartite graph is a modular graph. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: yes, the modular graph in graph theory is defined as an undirected | |
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.