# 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

a) in, out

b) out, in

c) in, total

d) total, out

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

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

c) n*(n-1)

d) 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

a) 2, 3

b) 3, 2

c) 2, 2

d) 3, 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] ]

a) 2

b) 4

c) 6

d) 8

a) x=5, y=3

b) x=3, y=5

c) x=3, y=3

d) x=5, y=5

a) True

b) False

a) O(V*V)

b) O(V+E)

c) O(1)

d) 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

#### 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

a) True

b) 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

a) O(V)

b) O(E*E)

c) O(E)

d) O(E+V)

#### 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

a) True

b) False

a) O(n)

b) O(n1.25)

c) O(n2.25)

d) O(n*n)

a) O(E)

b) O(V*V)

c) O(E+V)

d) O(V)

a) True

b) False

a) O(V)

b) O(E)

c) O(1)

d) O(V+E)

a) n-2

b) n

c) 2

d) 0

a) True

b) False

a) O(E*E)

b) O(V*V)

c) O(E)

d) O(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)

a) 1

b) 2

c) 3

d) 4

#### 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

#### 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

a) 28

b) 64

c) 256

d) 56

a) 21

b) 7

c) 6

d) 49

a) True

b) 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

a) 2

b) 4

c) 5

d) 9

#### 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

a) True

b) 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

a) True

b) False

#### 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

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

a) True

b) False

a) True

b) False

#### 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

#### 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)

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

a) True

b) False

#### 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)

a) True

b) False

#### 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

50+ Multigraph and Hypergraph MCQs PDF Download

a) 24

b) 24-1

c) 25

d) 25-1

a) True

b) False

#### 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

a) True

b) False

#### 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

#### 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