MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 657 Mcqs, each offering curated multiple-choice questions to sharpen your Testing Subject knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
A graph is said to be ……………… if the vertices can be split into two sets V1 and V2 such there are no edges between two vertices of V1 or two vertices of V2. |
| A. | Partite |
| B. | Bipartite |
| C. | Rooted |
| D. | Bisects |
| Answer» C. Rooted | |
| 2. |
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? |
| A. | In adjacency list representation, space is saved for sparse graphs. |
| B. | DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V²) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively. |
| C. | Adding a vertex in adjacency list representation is easier than adjacency matrix representation. |
| D. | All of the above |
| Answer» E. | |
| 3. |
In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack. |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» D. 4 | |
| 4. |
A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes. |
| A. | vertices, edges |
| B. | edges, vertices |
| C. | vertices, paths |
| D. | graph node, edges |
| Answer» B. edges, vertices | |
| 5. |
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. | All of the mentioned |
| Answer» B. Must be unweighted | |
| 6. |
The data structure required for Breadth First Traversal on a graph is |
| A. | queue |
| B. | stack |
| C. | array |
| D. | tree |
| Answer» B. stack | |
| 7. |
Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________ |
| A. | O(V) |
| B. | O(E*E) |
| C. | O(E) |
| D. | O(E+V) |
| Answer» D. O(E+V) | |
| 8. |
If locality is a concern, you can use ................ to traverse the graph. |
| A. | Breadth First Search |
| B. | Depth First Search |
| C. | Either BFS or DFS |
| D. | None of these |
| Answer» C. Either BFS or DFS | |
| 9. |
In a graph if e=(u, v) means |
| A. | u is adjacent to v but v is not adjacent to u |
| B. | e begins at u and ends at v |
| C. | u is processor and v is successor |
| D. | both b and c |
| Answer» E. | |
| 10. |
Other name for directed graph is .......... |
| A. | Direct graph |
| B. | Bigraph |
| C. | Dir-graph |
| D. | Digraph |
| Answer» E. | |
| 11. |
In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable. |
| A. | True |
| B. | False |
| C. | May be |
| D. | Can't say |
| Answer» B. False | |
| 12. |
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. | The edge connectivity of the graph is 1 |
| Answer» D. The edge connectivity of the graph is 1 | |
| 13. |
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» E. | |
| 14. |
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any distinct. Consider the following statements:I. Minimum Spanning Tree of G is always unique.II. Shortest path between any two vertices of G is always unique.Which of the above statements is/are necessarily true? |
| A. | I only |
| B. | II only |
| C. | both I and II |
| D. | neither I and II |
| Answer» B. II only | |
| 15. |
Given Adjacency matrices determine which of them are PseudoGraphs?i) {{1,0} {0,1}}ii) {{0,1}{1,0}}iii) {{0,0,1}{0,1,0}{1,0,0}} |
| A. | only i) |
| B. | ii) and iii) |
| C. | i) and iii) |
| D. | i) ii) and iii) |
| Answer» D. i) ii) and iii) | |
| 16. |
An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components? |
| A. | O (n) |
| B. | O (e) |
| C. | O (e+n) |
| D. | O (e-n) |
| Answer» D. O (e-n) | |
| 17. |
How many of the following statements are correct?i) All cyclic graphs are complete graphs.ii) All complete graphs are cyclic graphs.iii) All paths are bipartite.iv) All cyclic graphs are bipartite.v) There are cyclic graphs which are complete. |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 18. |
In a Binary Decision Diagrams 0 values by a _________ line and the 1 values are represented by a _________ line. |
| A. | dashed, bold |
| B. | bold, dashed |
| C. | dotted, bold |
| D. | dotted, dashed |
| Answer» D. dotted, dashed | |
| 19. |
Which of the following algorithms solves the all-pair shortest path problem? |
| A. | Floyd's algorithm |
| B. | Prim's algorithm |
| C. | Dijkstra's algorithm |
| D. | Warshall's algorithm |
| Answer» B. Prim's algorithm | |
| 20. |
Graph G is .............. if for any pair u, v of nodes in G there is a path from u to v or path from v to u. |
| A. | Leterally connected |
| B. | Widely Connected |
| C. | Unliterally connected |
| D. | Literally connected |
| Answer» D. Literally connected | |
| 21. |
The number of edges in a regular graph of degree d and n vertices is |
| A. | nd |
| B. | n+d |
| C. | nd/2 |
| D. | maximum of n,d |
| Answer» D. maximum of n,d | |
| 22. |
A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are |
| A. | more than n |
| B. | more than n |
| C. | more than (n+1)/2 |
| D. | more than n(n-1)/2 |
| Answer» E. | |
| 23. |
The minimum number of colors needed to color a graph having n (>3) vertices and 2 edges is |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 24. |
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» C. O(E) | |
| 25. |
Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices? |
| A. | 3, Infinite, 4 |
| B. | 4, 3, Infinite |
| C. | 4, Infinite |
| D. | 4, Infinite, Infinite |
| Answer» E. | |
| 26. |
If every node u in G is adjacent to every other node v in G, A graph is said to be |
| A. | isolated |
| B. | complete |
| C. | finite |
| D. | strongly connected |
| Answer» C. finite | |
| 27. |
The minimum number of edges required to create a cyclid graph of n vertices is |
| A. | n |
| B. | n+1 |
| C. | n-1 |
| D. | 2n |
| Answer» B. n+1 | |
| 28. |
A directed graph is ………………. if there is a path from each vertex to every other vertex in the digraph. |
| A. | Weakly connected |
| B. | Strongly Connected |
| C. | Tightly Connected |
| D. | Linearly Connected |
| Answer» C. Tightly Connected | |
| 29. |
Minimum number of spanning tree in a connected graph is |
| A. | n |
| B. | n(n - 1) |
| C. | 1 |
| D. | 0 |
| Answer» D. 0 | |
| 30. |
State True of False.i) Network is a graph that has weights or costs associated with it.ii) An undirected graph which contains no cycles is called a forest.iii) A graph is said to be complete if there is no edge between every pair of vertices. |
| A. | True, False, True |
| B. | True, True, False |
| C. | True, True, True |
| D. | False, True, True |
| Answer» C. True, True, True | |
| 31. |
What will be the running-time of Dijkstra's single source shortest path algorithm, if the graph G(V,E) is stored in form of adjacency list and binary heap is used − |
| A. | Ο(|V|2) |
| B. | Ο(|V| log |V|) |
| C. | Ο(|E|+|V| log |V|) |
| D. | None of these |
| Answer» D. None of these | |
| 32. |
State True or False.i) An undirected graph which contains no cycles is called forest.ii) A graph is said to be complete if there is an edge between every pair of vertices. |
| A. | True, True |
| B. | False, True |
| C. | False, False |
| D. | True, False |
| Answer» B. False, True | |
| 33. |
If the data collection is in sorted form and equally distributed then the run time complexity of interpolation search is − |
| A. | Ο(n) |
| B. | Ο(1) |
| C. | Ο(log n) |
| D. | Ο(log (log n)) |
| Answer» E. | |
| 34. |
Find the odd out |
| A. | Prim's Minimal Spanning Tree Algorithm |
| B. | Kruskal's Minimal Spanning Tree Algorithm |
| C. | Floyd-Warshall's All pair shortest path Algorithm |
| D. | Dijkstra's Minimal Spanning Tree Algorithm |
| Answer» D. Dijkstra's Minimal Spanning Tree Algorithm | |
| 35. |
From a complete graph, by removing maximum _______________ edges, we can construct a spanning tree. |
| A. | e-n+1 |
| B. | n-e+1 |
| C. | n+e-1 |
| D. | e-n-1 |
| Answer» B. n-e+1 | |
| 36. |
Maximum degree of any vertex in a simple graph of vertices n is |
| A. | 2n - 1 |
| B. | n |
| C. | n + 1 |
| D. | n - 1 |
| Answer» E. | |
| 37. |
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» B. No | |
| 38. |
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» B. If the graph is connected and it has odd number of vertices | |
| 39. |
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» C. Number of vertices in U > Number of vertices in V | |
| 40. |
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» B. Number of vertices in U not equal to number of vertices in V | |
| 41. |
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» B. 140 | |
| 42. |
Which of the following is the property of the bipartite graph? |
| A. | No Odd Cycle |
| B. | Symmetric spectrum |
| C. | Chromatic Number Is Less Than or Equal to 2 |
| D. | All of the mentioned |
| Answer» E. | |
| 43. |
Which one of the following is the chromatic number of bipartite graph? |
| A. | 1 |
| B. | 4 |
| C. | 3 |
| D. | 5 |
| Answer» B. 4 | |
| 44. |
Which graph has chromatic number 2? |
| A. | Compliment of Line Graph of Bipartite Graph |
| B. | Compliment of Bipartite Graph |
| C. | Line Graph of Bipartite Graph |
| D. | All of the mentioned |
| Answer» E. | |
| 45. |
Which of the following is the perfect graph? |
| A. | Compliment of Line Graph of Bipartite Graph |
| B. | Compliment of Bipartite Graph |
| C. | Line Graph of Bipartite Graph |
| D. | All of the mentioned |
| Answer» E. | |
| 46. |
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» C. The given graph is hamiltonian | |
| 47. |
What type of graph has chromatic number less than or equal to 2? |
| A. | Histogram |
| B. | Bipartite |
| C. | Cartesian |
| D. | Tree |
| Answer» C. Cartesian | |
| 48. |
Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite? |
| A. | Yes |
| B. | No |
| Answer» B. No | |
| 49. |
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» B. No | |
| 50. |
Is it possible to have a negative chromatic number of bipartite graph? |
| A. | True |
| B. | False |
| Answer» C. | |