A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

81. 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. None of the mentioned statements
View Answer Report Discuss Too Difficult!
Answer: (b).Number of edges*number of vertices

82. 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 Report Discuss Too Difficult!
Answer: (a).0

83. 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 Report Discuss Too Difficult!
Answer: (d).O(E)

84. 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
c. May be
d. Can't say
View Answer Report Discuss Too Difficult!
Answer: (a).True

85. 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 Report Discuss Too Difficult!
Answer: (a).n-1

86. A Graph Structured Stack is a _____________
a. Undirected Graph
b. Directed Graph
c. Directed Acyclic Graph
d. Regular Graph
View Answer Report Discuss Too Difficult!
Answer: (c).Directed Acyclic Graph

87. 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. None of the Mentioned
View Answer Report Discuss Too Difficult!
Answer: (c).Source – 1, 8 Sink – 4

88. Graph Structured Stack finds its application in _____________
a. Bogo Sort
b. Tomita’s Algorithm
c. Todd–Coxeter algorithm
d. All of the mentioned
View Answer Report Discuss Too Difficult!
Answer: (b).Tomita’s Algorithm

89. 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
c. May be
d. Can't say
View Answer Report Discuss Too Difficult!
Answer: (b).False

90. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________
a. O(E)
b. O(V*V)
c. O(E+V)
d. O(V)
View Answer Report Discuss Too Difficult!
Answer: (c).O(E+V)