This Graph (Data Structure) MCQs and answer with FREE PDF contains questions and answers on graph, adjacency matrix, incidence matrix, adjacency list, directed and undirected graph, directed acyclic graphs, multigraph and hypergraph, binary decision diagrams & and-inverter graph. We have the best collection of Graph (Data Structure) MCQs and answer with FREE PDF. These Graph (Data Structure) MCQs will help you to prepare for any competitive exams like: BCA, MCA, GATE, GRE, IES, PSC, UGC NET, DOEACC Exams at all levels – you just have to practice regularly.

## Graph (Data Structure) MCQs

**1. For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is the ________ degree.**

a) in, out

b) out, in

c) in, total

d) total, out

**Answer: **out, in

**2. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?**

a) (n*(n-1))/2

b) (n*(n+1))/2

c) n*(n-1)

d) n*(n+1)

**Answer: **n*(n-1)

**3. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?**

a) Depends on the number of edges

b) Depends on the number of vertices

c) Is independent of both the number of edges and vertices

d) It depends on both the number of edges and vertices

**Answer: **Is independent of both the number of edges and vertices

**4. In the given connected graph G, what is the value of rad(G) and diam(G)?**

a) 2, 3

b) 3, 2

c) 2, 2

d) 3, 3

**Answer: **2, 3

**5. Which of these adjacency matrices represents a simple graph?**

a) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ]

b) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]

c) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ]

d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]

**Answer: **[ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]

**6. Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________**

a) 2

b) 4

c) 6

d) 8

**Answer: **6

**7. 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: **x=5, y=3

**8. Two directed graphs(G and H) are isomorphic if and only if A=PBP-1, where P and A are adjacency matrices of G and H respectively.**

a) True

b) False

**Answer: **True

**50+ Adjacency Matrix MCQs PDF Download**

**9. Time complexity to check if an edge exists between two vertices would be ___________**

a) O(V*V)

b) O(V+E)

c) O(1)

d) O(E)

**Answer: **O(E)

**10. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?**

a) n-1

b) values greater than n are possible

c) values less than n-1 are possible

d) insufficient Information is given

**Answer: **n-1

**11. A Graph Structured Stack is a _____________**

a) Undirected Graph

b) Directed Graph

c) Directed Acyclic Graph

d) Regular Graph

**Answer: **Directed Acyclic Graph

**12. 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) Source – 4, Sink – 1,8

**Answer: **Source – 1, 8 Sink – 4

**13. Graph Structured Stack finds its application in _____________**

a) Bogo Sort

b) Tomita’s Algorithm

c) Todd–Coxeter algorithm

d) Heap Sort

**Answer: **Tomita’s Algorithm

**14. 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: **False

**15. The column sum in an incidence matrix for a simple graph is __________**

a) depends on number of edges

b) always greater than 2

c) equal to 2

d) equal to the number of edges

**Answer: **equal to 2

**16. What are the dimensions of an incidence matrix?**

a) Number of edges*number of edges

b) Number of edges*number of vertices

c) Number of vertices*number of vertices

d) Number of edges * (1⁄2 * number of vertices)

**Answer: **Number of edges*number of vertices

**50+ Incidence Matrix and Graph Structured Stack MCQs PDF Download**

**17. 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: **O(E)

**18. In which case adjacency list is preferred in front of an adjacency matrix?**

a) Dense graph

b) Sparse graph

c) Adjacency list is always preferred

d) Complete graph

**Answer: **Sparse graph

**19. To create an adjacency list C++’s map container can be used.**

a) True

b) False

**Answer: **True

**20. 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: **O(n1.25)

**21. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________**

a) O(E)

b) O(V*V)

c) O(E+V)

d) O(V)

**Answer: **O(E+V)

**22. For some sparse graph an adjacency list is more space efficient against an adjacency matrix.**

a) True

b) False

**Answer: **True

**23. Time complexity to find if there is an edge between 2 particular vertices is _________**

a) O(V)

b) O(E)

c) O(1)

d) O(V+E)

**Answer: **O(V)

**50+ Adjacency List MCQs PDF Download**

**24. 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: **n-2

**25. All trees with n vertices consists of n-1 edges.**

a) True

b) False

**Answer: **True

**26. 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: **O(V*V)

**27. 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: **2((n*n)/2)

**28. 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: **2

**29. 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: **either 0 or 2

**50+ Undirected Graph MCQs PDF Download**

**30. Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?**

a) add all values by 10

b) subtract 10 from all the values

c) multiply all values by 10

d) in both the cases of multiplying and adding by 10

**Answer: **multiply all values by 10

**31. What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices?**

a) 28

b) 64

c) 256

d) 56

**Answer: **56

**32. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph?**

a) 21

b) 7

c) 6

d) 49

**Answer: **6

**33. Dijkstra’s Algorithm will work for both negative and positive weights?**

a) True

b) False

**Answer: **False

**34. A graph having an edge from each vertex to every other vertex is called a ___________**

a) Tightly Connected

b) Strongly Connected

c) Weakly Connected

d) Loosely Connected

**Answer: **Tightly Connected

**35. What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?**

a) 2

b) 4

c) 5

d) 9

**Answer: **4

**50+ Directed Graph MCQs PDF Download**

**36. 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: **No Hamiltonian path is possible

**37. 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 hace non topological sortings

**Answer: **All the cyclic directed graphs hace non topological sortings

**38. 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: **False

**39. 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: **Will always be zero

**40. Every Directed Acyclic Graph has at least one sink vertex.**

a) True

b) False

**Answer: **True

**41. 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: **(V*(V-1))/2

**50+ Directed Acyclic Graph MCQs PDF Download**

**42. In which of the following case does a Propositional Directed Acyclic Graph is used for?**

a) Representation of Boolean Functions

b) String Matching

c) Searching

d) Sorting of number

**Answer: **Representation of Boolean Functions

**43. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.**

a) True

b) False

**Answer: **True

**44. In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.**

a) True

b) False

**Answer: **True

**45. In which of the following does a Directed Acyclic Word Graph finds its application in?**

a) String Matching

b) Number Sorting

c) Manipulations on numbers

d) Pattern Printing

**Answer: **String Matching

**46. Consider the following symbols and choose which of the symbols represent nodes having atleast one child?**

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥

a) iv) and v)

b) iii) iv) and v)

c) i) and ii)

d) i) and iii)

**Answer: **i) and ii)

**47. Which of the following symbols represent nodes having exactly one child?**

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥

a) iv) and v)

b) v)

c) i) and iii)

d) iii)

**Answer: **iii)

**50+ Propositional and Directed Acyclic Word Graph MCQs PDF Download**

**48. 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: **i) and iii)

**49. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?**

a) 3, Infinite, 4

b) 4, 3, Infinite

c) 4, Infinite, infinite

d) 4, Infinite, Infinite

**Answer: **4, Infinite, Infinite

**50. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?**

a) V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}

b) V = {v1, v2} E = {e1} = {{v1, v2}}

c) V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}

d) All of the mentioned

**Answer: **All of the mentioned

**51. 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: **3,2,2,2,1,1

**52. MultiGraphs having self-loops are called PseudoGraphs?**

a) True

b) False

**Answer: **True

**53. 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: **i) and iii)

**54. All undirected Multigraphs contain eulerian cycles.**

a) True

b) False

**Answer: **True

**55. Determine the number of vertices for the given Graph or Multigraph?**

G is a 4-regular Graph having 12 edges.

a) 3

b) 6

c) 4

d) Information given is insufficient

**Answer: **6

**50+ Multigraph and Hypergraph MCQs PDF Download**

**56. How many nodes are required to create a Binary Decision Tree having 4 variables?**

a) 24

b) 24-1

c) 25

d) 25-1

**Answer: **25-1

**57. Two or more And Inverter Graphs can represent same function.**

a) True

b) False

**Answer: **True

**58. Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.**

a) AND, AND, average

b) AND, OR, longest

c) OR, OR, shortest

d) AND, AND, longest

**Answer: **AND, AND, longest

**59. And Inverter Graph is a type of __________**

a) Multigraph

b) Cyclic Graph

c) Directed Acyclic Graph

d) Directed Acyclic Word Graph

**Answer: **Directed Acyclic Graph

**60. The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram.**

a) True

b) False

**Answer: **True

**61. Which of the following logical operation can’t be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?**

a) Conjunction

b) Disjunction

c) Negation

d) Tautology Checking

**Answer: **Tautology Checking

**62. Binary Decision Diagram is a type of __________**

a) Multigraph

b) Cyclic Graph

c) Directed Acyclic Graph

d) Directed Acyclic Word Graph

**Answer: **Directed Acyclic Graph

**63. 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: **Representation of Boolean Functions

**50+ Binary Decision Diagrams and Inverter Graph MCQs PDF Download**