TWO MARKS QUESTIONS AND ANSWERS

DATA STRUCTURES

Previous Next

91. Explain about Adjacency Matrix
Adjacency matrix consists of a n*n matrix where n is the no. of vertices
present In the graph,which consists of values either 0 or 1.

92. Explain about Adjacency linked list.
It consists of a table with the no. of entries for each vertex for each entry a
linked List is inititated for the vertices adjacent to the corresponding table entry.

93. What is a single souce shortest path problem?
Given as an input,a weighted graph,G= and a distinguished vertex ‘S’
as the source vertex.Single source shortest path problem finds the shortest
weighted path from s to every other vertex in G.

94. Explain about Unweighted shortest path.
Single source shortest path finds the shortest path from the source to each
and every vertex present in a unweighted graph.Here no cost is associated
with the edges connecting the vertices.Always unit cost is associated with
each edge.

95. Explain about Weighted shortest path

Single source shortest path finds the shortest path from the source to each
and
Every vertex present In a weighted graph.In a weighted graph some cost is
always
Associated with the edges connecting the vertices.

96. What are the methods to solve minimum spanning tree?

a) Prim’s algorithm
b) Kruskal’s algorithm

97. Explain briefly about Prim’s algorithm

Prim’s algorithm creates the spanning tree in various stages.At each stage,a
node is picked as the root and an edge is added and thus the associated
vertex along with it.

98. Define a depth first spanning tree.

The tree that is formulated by depth first search on a graph is called as depth
first spanning tree.The depth first spanning tree consists of tree edges and
back edges.

99. What is a tree edge?

Traversal from one vertex to the next vertex in a graph is called as a tree
edge.

100. What is a back edge?

The possibility of reaching an already marked vertex is indicated by a dashed
line,in a graph is called as back edge.