McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) , Information Technology Engineering (IT) , Bachelor of Science in Computer Science FY (BSc CS) , Bachelor of Science in Information Technology FY (BSc IT) , Bachelor of Computer Applications (BCA) .
Chapters
| 1. |
Which of the following statements for a simple graph is correct? |
| A. | Every path is a trail |
| B. | Every trail is a path |
| C. | Every trail is a path as well as every path is a trail |
| D. | Path and trail have no relation |
| Answer» A. Every path is a trail | |
| 2. |
For the given graph(G), which of the following statements is true? |
| A. | G is a complete graph |
| B. | G is not a connected graph |
| C. | The vertex connectivity of the graph is 2 |
| D. | none |
| Answer» C. The vertex connectivity of the graph is 2 | |
| 3. |
What is the number of edges present in a complete graph having n vertices? |
| A. | (n*(n+1))/2 |
| B. | (n*(n-1))/2 |
| C. | n |
| D. | Information given is insufficient |
| Answer» B. (n*(n-1))/2 | |
| 4. |
The given Graph is regular. |
| A. | True |
| B. | False |
| C. | none |
| D. | none |
| Answer» A. True | |
| 5. |
A connected planar graph having 6 vertices, 7 edges contains regions. |
| A. | 15 |
| B. | 3 |
| C. | 1 |
| D. | 11 |
| Answer» B. 3 | |
| 6. |
If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is |
| A. | (n*n-n-2*m)/2 |
| B. | (n*n+n+2*m)/2 |
| C. | (n*n-n-2*m)/2 |
| D. | (n*n-n+2*m)/2 |
| Answer» A. (n*n-n-2*m)/2 | |
| 7. |
Which of the following properties does a simple graph not hold? |
| A. | Must be connected |
| B. | Must be unweighted |
| C. | Must have no loops or multiple edges |
| D. | Must have no multiple edges |
| Answer» A. Must be connected | |
| 8. |
What is the maximum number of edges in a bipartite graph having 10 vertices? |
| A. | 24 |
| B. | 21 |
| C. | 25 |
| D. | 16 |
| Answer» C. 25 | |
| 9. |
Which of the following is true? |
| A. | A graph may contain no edges and many vertices |
| B. | A graph may contain many edges and no vertices |
| C. | A graph may contain no edges and no vertices |
| D. | A graph may contain no vertices and many edges |
| Answer» B. A graph may contain many edges and no vertices | |
| 10. |
For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true? |
| A. | v=e |
| B. | v = e+1 |
| C. | v + 1 = e |
| D. | v = e-1 |
| Answer» B. v = e+1 | |
| 11. |
For which of the following combinations of the degrees of vertices would the connected graph be eulerian? |
| A. | 1,2,3 |
| B. | 2,3,4 |
| C. | 2,4,5 |
| D. | 1,3,5 |
| Answer» A. 1,2,3 | |
| 12. |
A graph with all vertices having equal degree is known as a |
| A. | Multi Graph |
| B. | Regular Graph |
| C. | Simple Graph |
| D. | Complete Graph |
| Answer» B. Regular Graph | |
| 13. |
Which of the following ways can be used to represent a graph? |
| A. | Adjacency List and Adjacency Matrix |
| B. | Incidence Matrix |
| C. | Adjacency List, Adjacency Matrix as well as Incidence Matrix |
| D. | No way to represent |
| Answer» C. Adjacency List, Adjacency Matrix as well as Incidence Matrix | |
| 14. |
The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is |
| A. | 2((n*(n-1))/2) |
| B. | 2((n*(n+1))/2) |
| C. | 2((n-1)*(n-1))/2) |
| D. | 2((n*n)/2) |
| Answer» D. 2((n*n)/2) | |
| 15. |
Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| 16. |
Number of vertices with odd degrees in a graph having a eulerian walk is |
| A. | 0 |
| B. | Can’t be predicted |
| C. | 2 |
| D. | either 0 or 2 |
| Answer» D. either 0 or 2 | |
| 17. |
How many of the following statements are correct? |
| A. | All cyclic graphs are complete graphs. |
| B. | All complete graphs are cyclic graphs. |
| C. | All paths are bipartite. |
| D. | All cyclic graphs are bipartite. |
| Answer» B. All complete graphs are cyclic graphs. | |
| 18. |
What is the number of vertices of degree 2 in a path graph having n vertices,here n>2. |
| A. | n-2 |
| B. | n |
| C. | 2 |
| D. | 0 |
| Answer» A. n-2 | |
| 19. |
What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix? |
| A. | O(E*E) |
| B. | O(V*V) |
| C. | O(E) |
| D. | O(V) |
| Answer» B. O(V*V) | |
| 20. |
With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess? |
| A. | (V*(V-1))/2 |
| B. | (V*(V+1))/2 |
| C. | (V+1)C2 |
| D. | (V-1)C2 |
| Answer» A. (V*(V-1))/2 | |
| 21. |
The topological sorting of any DAG can be done in time. |
| A. | cubic |
| B. | quadratic |
| C. | linear |
| D. | logarithmic |
| Answer» C. linear | |
| 22. |
If there are more than 1 topological sorting of a DAG is possible, which of the following is true. |
| A. | Many Hamiltonian paths are possible |
| B. | No Hamiltonian path is possible |
| C. | Exactly 1 Hamiltonian path is possible |
| D. | Given information is insufficient to comment anything |
| Answer» B. No Hamiltonian path is possible | |
| 23. |
Which of the given statement is true? |
| A. | All the Cyclic Directed Graphs have topological sortings |
| B. | All the Acyclic Directed Graphs have topological sortings |
| C. | All Directed Graphs have topological sortings |
| D. | All the cyclic directed graphs have non topological sortings |
| Answer» D. All the cyclic directed graphs have non topological sortings | |
| 24. |
What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph? |
| A. | Depends on a Graph |
| B. | Will always be zero |
| C. | Will always be greater than zero |
| D. | May be zero or greater than zero |
| Answer» B. Will always be zero | |
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.