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

Answer: b
Explanation: For a graph having V vertices and E edges, Adjacency matrix have V*V elements while Incidence matrix have V*E elements.
advertisement

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

Answer: c
Explanation: For every edge only the vertices with which it is connected would have the value 1 in the matrix, as an edge connects two vertices sum will always be 2.

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 * (12 * number of vertices)
View Answer

Answer: b
Explanation: Columns may represent edges and vertices may be represented by the rows.
advertisement
advertisement

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

Answer: a
Explanation: Under every edge column there would be either all 0 values or a pair of -1 and +1 value exists.

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

Answer: d
Explanation: We have to check for all edges, in the worst case the vertices will have no common edge.
advertisement

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

Answer: a
Explanation: Two graphs are isomorphic if their Incidence Matrices differ only by permutation of columns and rows.
advertisement

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

Answer: a
Explanation: Every column of the incidence matrix may contain only +1 and -1 as non zero entries rank would be less than n.
advertisement

8. In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.
data-structure-questions-answers-incidence-matrix-graph-structured-stack-q8
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: c
Explanation: Path ADE, BDE and BCE are possible.

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

Answer: c
Explanation: A Graph Structured Stack is a Directed Acyclic Graph with each path representing a stack.

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

Answer: c
Explanation: Every Stack of the Graph Structured Stack represents a path, each path starts with the source vertex and ends with the sink vertex.

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

Answer: b
Explanation: Tomita’s is a parsing algorithm which uses Graph Structured Stack in its implementation.

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

Answer: b
Explanation: The answer would depend on the intermediate vertices also.

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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter