McqMate
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 Reading?