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

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

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

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 * (^{1}⁄_{2} * number of vertices)

View Answer

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

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

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

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

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

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

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

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

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

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

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

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

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

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!