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

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

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)

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

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)

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

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

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.

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

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

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

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

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