MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 117 Mcqs, each offering curated multiple-choice questions to sharpen your Data Structures and Algorithms knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
The spectrum of a graph is _______ if and only if it is _______ graph. |
| A. | symmetry, bipartite |
| B. | transitive, bipartite |
| C. | cyclic, Euler |
| D. | reflexive, planar |
| Answer» B. transitive, bipartite | |
| 2. |
Every complete bipartite graph must not be _______ |
| A. | planar graph |
| B. | line graph |
| C. | complete graph |
| D. | subgraph |
| Answer» D. subgraph | |
| 3. |
All closed walks are of ______ length in a bipartite graph. |
| A. | infinite |
| B. | even |
| C. | odd |
| D. | odd prime |
| Answer» C. odd | |
| 4. |
Bipartite graphs are used in ________ |
| A. | modern coding theory |
| B. | colouring graphs |
| C. | neural networks |
| D. | chemical bonds |
| Answer» B. colouring graphs | |
| 5. |
In a complete bipartite graph, the intersection of two sub graphs is ______ |
| A. | 1 |
| B. | null |
| C. | 210 |
| D. | 412 |
| Answer» C. 210 | |
| 6. |
What is the maximum number of edges in a bipartite graph on 14 vertices? |
| A. | 78 |
| B. | 15 |
| C. | 214 |
| D. | 49 |
| Answer» E. | |
| 7. |
The partition V = V1 ∪ V2 in a bipartite graph G1 is called ________ |
| A. | bipartition of G1 |
| B. | 2-vertex set of G1 |
| C. | sub bipartite graphs |
| D. | disjoint vertex set |
| Answer» C. sub bipartite graphs | |
| 8. |
The time complexity to test whether a graph is bipartite or not is said to be _______ using depth first search. |
| A. | O(n3) |
| B. | linear time |
| C. | O(1) |
| D. | O(nlogn) |
| Answer» C. O(1) | |
| 9. |
In a ______ the degree of each and every vertex is equal. |
| A. | regular graph |
| B. | point graph |
| C. | star graph |
| D. | euler graph |
| Answer» D. euler graph | |
| 10. |
The maximum number of edges in a bipartite graph on 14 vertices is ___________ |
| A. | 56 |
| B. | 14 |
| C. | 49 |
| D. | 87 |
| Answer» D. 87 | |
| 11. |
What would be the output of the following C++ program if the given input is0 0 0 1 10 0 0 0 10 0 0 1 01 0 1 0 01 1 0 0 0 |
| A. | 0 2 3 1 4 |
| B. | 0 3 2 4 1 |
| C. | 0 2 3 4 1 |
| D. | 0 3 2 1 4 |
| Answer» C. 0 2 3 4 1 | |
| 12. |
What would be the value of the distance matrix, after the execution of the given code? |
| A. | a |
| B. | b |
| C. | c |
| D. | d |
| Answer» C. c | |
| 13. |
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. | None of the given statements is true |
| Answer» B. All the Acyclic Directed Graphs have topological sortings | |
| 14. |
Dijkstra’s Algorithm will work for both negative and positive weights? |
| A. | True |
| B. | False |
| C. | May be |
| D. | Can't say |
| Answer» C. May be | |
| 15. |
Complete the given snippet of code for the adjacency list representation of a weighted directed graph. |
| A. | vertex, vertex |
| B. | neighbor, vertex |
| C. | neighbor, neighbor |
| D. | vertex, neighbor |
| Answer» D. vertex, neighbor | |
| 16. |
What would be the time complexity of the following function which adds an edge between two vertices i and j, with some weight ‘weigh’ to the graph having V vertices? |
| A. | O(1) |
| B. | O(V) |
| C. | O(V*V) |
| D. | O(log V) |
| Answer» B. O(V) | |
| 17. |
To create an adjacency list C++’s map container can be used. |
| A. | True |
| B. | False |
| C. | May be |
| D. | Can't say |
| Answer» B. False | |
| 18. |
A connected graph T without any cycles is called ........ |
| A. | free graph |
| B. | no cycle graph |
| C. | non cycle graph |
| D. | circular graph |
| Answer» B. no cycle graph | |
| 19. |
For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to |
| A. | 2n |
| B. | (2n-1)/2 |
| C. | 2e |
| D. | 4n |
| Answer» D. 4n | |
| 20. |
Let A be an adjacency matrix of a graph G. The ij th entry in the matrix Ak , gives |
| A. | The number of paths of length K from vertex Vi to vertex Vj. |
| B. | Shortest path of K edges from vertex Vi to vertex Vj. |
| C. | Length of a Eulerian path from vertex Vi to vertex Vj. |
| D. | Length of a Hamiltonian cycle from vertex Vi to vertex Vj. |
| Answer» C. Length of a Eulerian path from vertex Vi to vertex Vj. | |
| 21. |
A …………… is an acyclic digraph, which has only one node with indegree 0, and other nodes have in-degree 1. |
| A. | Directed tree |
| B. | Undirected tree |
| C. | Dis-joint tree |
| D. | Direction oriented tree |
| Answer» B. Undirected tree | |
| 22. |
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» B. (n*n+n+2*m)/2 | |
| 23. |
A connected graph T without any cycles is called |
| A. | a tree graph |
| B. | free tree |
| C. | a tree |
| D. | All of above |
| Answer» E. | |
| 24. |
The number of edges in a simple, n-vertex, complete graph is |
| A. | n*(n-2) |
| B. | n*(n-1) |
| C. | n*(n-1)/2 |
| D. | n*(n-1)*(n-2) |
| Answer» D. n*(n-1)*(n-2) | |
| 25. |
Graph traversal is different from a tree traversal, because: |
| A. | trees are not connected |
| B. | graphs may have loops |
| C. | trees have root |
| D. | None of these |
| Answer» D. None of these | |
| 26. |
The spanning tree of connected graph with 10 vertices contains .............. |
| A. | 9 edges |
| B. | 11 edges |
| C. | 10 edges |
| D. | 9 vertices |
| Answer» B. 11 edges | |
| 27. |
A complete graph can have ............... |
| A. | n^2 spanning trees |
| B. | n^(n-2) spanning trees |
| C. | n^(n+1) spanning trees |
| D. | n^n spanning trees |
| Answer» C. n^(n+1) spanning trees | |
| 28. |
What is the number of words that can be formed from the given Directed Acyclic Word Graph? |
| A. | 2 |
| B. | 4 |
| C. | 12 |
| D. | 7 |
| Answer» C. 12 | |
| 29. |
In the given graph which edge should be removed to make it a Bipartite Graph? |
| A. | A-C |
| B. | B-E |
| C. | C-D |
| D. | D-E |
| Answer» B. B-E | |
| 30. |
What is the maximum number of edges in a bipartite graph having 10 vertices? |
| A. | 24 |
| B. | 21 |
| C. | 25 |
| D. | 16 |
| Answer» D. 16 | |
| 31. |
What would be the DFS traversal of the given Graph? |
| A. | ABCED |
| B. | AEDCB |
| C. | EDCBA |
| D. | ADECB |
| Answer» B. AEDCB | |
| 32. |
Time Complexity of DFS is? (V – number of vertices, E – number of edges) |
| A. | O(V + E) |
| B. | O(V) |
| C. | O(E) |
| D. | None of the mentioned |
| Answer» B. O(V) | |
| 33. |
The maximum degree of any vertex in a simple graph with n vertices is |
| A. | n–1 |
| B. | n+1 |
| C. | 2n–1 |
| D. | n |
| Answer» B. n+1 | |
| 34. |
The graphs G1 and G2 with their incidences matrices given are Isomorphic. e1 e2 e3 e4 e5 e6 v1 1 0 0 0 0 0 v2 1 1 0 0 0 1 v3 0 1 1 0 1 0 v4 0 0 1 1 0 0 v5 0 0 0 1 1 1 e1 e2 e3 e4 e5 e6 v1 0 0 1 0 0 0 v2 1 0 1 0 1 0 v3 1 1 0 1 0 0 v4 0 1 0 0 0 1 v5 0 0 0 1 1 1 |
| A. | True |
| B. | False |
| C. | May be |
| D. | Can't say |
| Answer» B. False | |
| 35. |
Given the following adjacency matrix of a graph(G) determine the number of components in the G. [0 1 1 0 0 0], [1 0 1 0 0 0], [1 1 0 0 0 0], [0 0 0 0 1 0], [0 0 0 1 0 0], [0 0 0 0 0 0]. |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» D. 4 | |
| 36. |
For which type of graph, the given program would run infinitely? The Input would be in the form of an adjacency Matrix and n is its dimension (1 |
| A. | All Fully Connected Graphs |
| B. | All Empty Graphs |
| C. | All Bipartite Graphs |
| D. | None of the Mentioned |
| Answer» C. All Bipartite Graphs | |
| 37. |
Given the following program, what will be the 3rd number that’d get printed in the output sequence for the given input? |
| A. | 2 |
| B. | 6 |
| C. | 8 |
| D. | 4 |
| Answer» D. 4 | |
| 38. |
What is the maximum number of edges in a bipartite graph having 10 vertices? |
| A. | 24 |
| B. | 21 |
| C. | 25 |
| D. | 16 |
| Answer» D. 16 | |
| 39. |
Which of the following graphs are isomorphic to each other? |
| A. | fig 1 and fig 2 |
| B. | fig 2 and fig 3 |
| C. | fig 1 and fig 3 |
| D. | fig 1, fig 2 and fig 3 |
| Answer» E. | |
| 40. |
Graphs are represented using ............ |
| A. | Adjacency tree |
| B. | Adjacency linked list |
| C. | Adjacency graph |
| D. | Adjacency queue |
| Answer» C. Adjacency graph | |
| 41. |
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. | |
| 42. |
In a graph if e=[u, v], Then u and v are called |
| A. | endpoints of e |
| B. | adjacent nodes |
| C. | neighbors |
| D. | all of above |
| Answer» E. | |
| 43. |
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity. |
| A. | A |
| B. | B |
| C. | C |
| D. | D |
| Answer» D. D | |
| 44. |
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» B. (n*n+n+2*m)/2 | |
| 45. |
A ……….. is a graph that has weights of costs associated with its edges. |
| A. | Network |
| B. | Weighted graph |
| C. | Both A and B |
| D. | None of the above |
| Answer» D. None of the above | |
| 46. |
In the given graph identify the cut vertices. |
| A. | B and E |
| B. | C and D |
| C. | A and E |
| D. | C and B |
| Answer» E. | |
| 47. |
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. | None of the mentioned |
| Answer» C. v + 1 = e | |
| 48. |
Which of the following is useful in traversing a given graph by breadth first search? |
| A. | set |
| B. | List |
| C. | stacks |
| D. | Queue |
| Answer» E. | |
| 49. |
The minimum number of edges in a connected cyclic graph on n vertices is |
| A. | n |
| B. | n+1 |
| C. | n-1 |
| D. | none of the above |
| Answer» B. n+1 | |
| 50. |
The given Graph is regular. |
| A. | True |
| B. | False |
| C. | May be |
| D. | Can't say |
| Answer» B. False | |