We have the best collection of Incidence Matrix and Graph Structured Stack MCQs and answer with FREE PDF. These Incidence Matrix and Graph Structured Stack 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.

## Incidence Matrix and Graph Structured Stack MCQs

**1. The column sum in an incidence matrix for a directed graph having no self loop is __________**

a) 0

b) 1

c) 2

d) equal to the number of edges

**Answer: **0

**2. 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)

**3. 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

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

a) Undirected Graph

b) Directed Graph

c) Directed Acyclic Graph

d) Regular Graph

**Answer: **Directed Acyclic Graph

**6. 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

**7. 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

**8. 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

**9. 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

**10. 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