Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Incidence Matrix and Graph Structured Stack

1 - Question

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.




2 - Question

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 - Question

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.




4 - Question

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 - Question

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.




6 - Question

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.




7 - Question

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.




8 - Question

 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 - Question

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 - Question

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 - Question

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 - Question

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.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners