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?