500+ Graph (Data Structure) MCQs with FREE PDF

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

Graph (Data Structure) MCQs PDF Download

1000+ Data Structure MCQs

Abstract Data Types
Application of Stacks
Arrays Types
Types of Lists
Binary Trees
B Trees
Trees
Heap
Trie
Hash Tables
Graph

Comments