Data Structure Questions and Answers – Incidence Matrix and Graph Structured Stack

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Incidence Matrix and Graph Structured Stack”.

1. Incidence matrix and Adjacency matrix of a graph will always have same dimensions?
a) True
b) False
View Answer

2. 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
View Answer

3. 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 * (¹⁄₂ * number of vertices)
View Answer

4. 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
View Answer

5. 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)
View Answer

6. The graphs G1 and G2 with their incidences matrices given are Isomorphic.

		e1 	e2 	e3 	e4 	e5 	e6
	v1	1	0	0	0	0	0
	v2	1	1	0	0	0	1
	v3	0	1	1	0	1	0
	v4	0	0	1	1	0	0
	v5	0	0	0	1	1	1
 
 
 
		e1 	e2 	e3 	e4 	e5 	e6
	v1	0	0	1	0	0	0
	v2	1	0	1	0	1	0
	v3	1	1	0	1	0	0
	v4	0	1	0	0	0	1
	v5	0	0	0	1	1	1

a) True
b) False
View Answer

7. 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
View Answer

8. In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.

a) 1
b) 2
c) 3
d) 4
View Answer

9. A Graph Structured Stack is a _____________
a) Undirected Graph
b) Directed Graph
c) Directed Acyclic Graph
d) Regular Graph
View Answer

10. 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
View Answer

11. Graph Structured Stack finds its application in _____________
a) Bogo Sort
b) Tomita’s Algorithm
c) Todd–Coxeter algorithm
d) Heap Sort
View Answer

12. 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
View Answer

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.