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.
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Programming Books
- Practice Programming MCQs
- Practice Design & Analysis of Algorithms MCQ
