MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 792 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.
| 751. |
Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph. |
| A. | True |
| B. | False |
| Answer» B. False | |
| 752. |
How many edges does a n vertex triangle free graph contains? |
| A. | n2 |
| B. | n2 + 2 |
| C. | n2 / 4 |
| D. | n3 |
| Answer» D. n3 | |
| 753. |
Which theorem gives the relation between the minimum vertex cover and maximum matching? |
| A. | Konig's Theorem |
| B. | Kirchhoff's Theorem |
| C. | Kuratowski's Theorem |
| D. | Kelmans Theorem |
| Answer» D. Kelmans Theorem | |
| 754. |
Which graph has a size of minimum vertex cover equal to maximum matching? |
| A. | Cartesian |
| B. | Tree |
| C. | Heap |
| D. | Bipartite |
| Answer» E. | |
| 755. |
If in a DAG N sink vertices and M source vertices exists, then the number of possible stacks in the Graph Structured Stack representation would come out to be N*M. |
| A. | True |
| B. | False |
| Answer» C. | |
| 756. |
A Graph Structured Stack is a _____________ |
| A. | Undirected Graph |
| B. | Directed Graph |
| C. | Directed Acyclic Graph |
| D. | Regular Graph |
| Answer» D. Regular Graph | |
| 757. |
Binary Decision Diagram is a type of __________ |
| A. | Multigraph |
| B. | Cyclic Graph |
| C. | Directed Acyclic Graph |
| D. | Directed Acyclic Word Graph |
| Answer» D. Directed Acyclic Word Graph | |
| 758. |
For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v? |
| A. | True |
| B. | False |
| Answer» C. | |
| 759. |
What is the degree sequence of the given HyperGraph, in non-increasing order.V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}} |
| A. | 3,2,1,1,1,1 |
| B. | 3,2,2,2,1,1 |
| C. | 3,2,2,2,2,1 |
| D. | 3,2,2,1,1,1 |
| Answer» C. 3,2,2,2,2,1 | |
| 760. |
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 | |
| 761. |
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) | |
| 762. |
MultiGraphs having self-loops are called PseudoGraphs? |
| A. | True |
| B. | False |
| Answer» B. False | |
| 763. |
And Inverter Graph is a type of __________ |
| A. | Multigraph |
| B. | Cyclic Graph |
| C. | Directed Acyclic Graph |
| D. | Directed Acyclic Word Graph |
| Answer» D. Directed Acyclic Word Graph | |
| 764. |
In a Binary Decision Diagram, how many types of terminal exists? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 765. |
If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y. |
| A. | x=5, y=3 |
| B. | x=3, y=5 |
| C. | x=3, y=3 |
| D. | x=5, y=5 |
| Answer» B. x=3, y=5 | |
| 766. |
If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC? |
| A. | Source – 1, 8 Sink – 7,4 |
| B. | Source – 1 Sink – 8,4 |
| C. | Source - 1, 8 Sink - 4 |
| D. | None of the Mentioned |
| Answer» D. None of the Mentioned | |
| 767. |
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) | |
| 768. |
Which of the following logical operation can be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams? |
| A. | Conjunction |
| B. | Disjunction |
| C. | Negation |
| D. | All of the mentioned |
| Answer» E. | |
| 769. |
In which of the following case does a Binary Decision Diagram is used for? |
| A. | Representation of Boolean Functions |
| B. | String Matching |
| C. | Searching |
| D. | Sorting of number |
| Answer» B. String Matching | |
| 770. |
Dijkstra's Algorithm will work for both negative and positive weights? |
| A. | True |
| B. | False |
| Answer» C. | |
| 771. |
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» C. Will always be greater than zero | |
| 772. |
What would be the time complexity of the BFS traversal of a graph with n vertices and n1.25 edges? |
| A. | O(n) |
| B. | O(n1.25) |
| C. | O(n2.25) |
| D. | O(n*n) |
| Answer» C. O(n2.25) | |
| 773. |
Which of the given symbols represent may represent leaf nodes? |
| A. | iv) and v) |
| B. | v) |
| C. | i) and iii) |
| D. | ii) |
| Answer» B. v) | |
| 774. |
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 | |
| 775. |
Which of the following is the correct type of spectrum of the bipartite graph? |
| A. | Symmetric |
| B. | Anti – Symmetric |
| C. | Circular |
| D. | Exponential |
| Answer» B. Anti – Symmetric | |
| 776. |
There are four students in a class namely A, B, C and D. A tells that a triangle is a bipartite graph. B tells pentagon is a bipartite graph. C tells square is a bipartite graph. D tells heptagon is a bipartite graph. Who among the following is correct? |
| A. | A |
| B. | B |
| C. | C |
| D. | D |
| Answer» D. D | |
| 777. |
Which of the following has maximum clique size 2? |
| A. | Perfect graph |
| B. | Tree |
| C. | Histogram |
| D. | Cartesian |
| Answer» B. Tree | |
| 778. |
A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is? |
| A. | n |
| B. | n/2 |
| C. | n/4 |
| D. | data insufficient |
| Answer» C. n/4 | |
| 779. |
Is it true that the perfect graph has forbidden graph characterization? |
| A. | True |
| B. | False |
| Answer» B. False | |
| 780. |
Which type of graph has no odd cycle in it? |
| A. | Bipartite |
| B. | Histogram |
| C. | Cartesian |
| D. | Pie |
| Answer» B. Histogram | |
| 781. |
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 | |
| 782. |
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. | None of the mentioned |
| Answer» C. A graph may contain no edges and no vertices | |
| 783. |
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 | |
| 784. |
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. | None of the mentioned |
| Answer» D. None of the mentioned | |
| 785. |
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» C. Simple Graph | |
| 786. |
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» B. 2,3,4 | |
| 787. |
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 | |
| 788. |
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 | |
| 789. |
A connected planar graph having 6 vertices, 7 edges contains _____________ regions. |
| A. | 15 |
| B. | 3 |
| C. | 1 |
| D. | 11 |
| Answer» C. 1 | |
| 790. |
In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices. |
| A. | True |
| B. | False |
| Answer» C. | |
| 791. |
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» C. n | |
| 792. |
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. | None of the mentioned |
| Answer» B. Every trail is a path | |