Job Saarnee

# Unit 4 Long answer Important Questions of Data Structure

Q1: What is a
graph ? Discuss various types of graphs. Briefly explain few applications of
graph.

Q2: What is
graph ? Discuss various terminologies used in graph.

Q3: Discuss the
various types of representation of graph.

Q4: Explain

Q5: Write a
short note on graph traversal.

*Q6: Write and
Explain DFS graph traversal algorithm.

OR

Write DFS
algorithm to traverse a graph. Apply same algorithm for the graph given in Fig.
by considering node 1 as starting node.

*Q7: Implement
BFS algorithm to find the shortest path form node A to J.

OR

Explain in
detail about the graph traversal techniques with suitable example.

Q8: Illustrate
the importance of various traversing techniques in graph along with its
applications.

Q9: Define
connected component and strongly connected component. Write an  algorithm to find strongly connected components.

Q10: What do you
mean by spanning tree and minimum spanning tree ?

Q11: Write down
Prim’s algorithm to find out minimal spanning tree.

*Q12: Define
minimum spanning tree. Find the minimal spanning tree for the following graph
using Prim’s algorithm.

Q13: Write
Kruskal’s algorithm to find minimum spanning tree.

Q14: Considering
the following undirected graph.

a. Find the adjacency list
representation of the graph.

b. Find the minimum cost spanning tree
by Kruskal’s algorithm.

*Q14: Find the
minimum spanning tree for the following graph using
Prim’s and Kruskal’s algorithm.

*Q15: Discuss
Prim’s and Kruskal’s algorithm. Construct minimum spanning tree for the below given graph using Prim’s   algorithm. (Source node =a)

Q16: Explain
transitive closure.

Q17: Write down
Warshall’s algorithm for finding all pair shortest path.

*Q18: Write the
Floyd Warshall algorithm to compute the all pair   shortest path. Apply the algorithm on following graph.

Q19: Write and
explain Dijkstra’s algorithm for finding shortest path.

OR

Write and explain an algorithm for
finding shortest path between
any nodes of a given graph.

*Q20: Find out
the shortest path from node 1 to 4 in a given graph using Dijkstra shortest path algorithm.

Q21: Describe
Dijkstra’s algorithm for finding shortest path. Describe its working for the graph given below.

OR

Describe Dijkstra algorithm with
suitable example.

*Q22: By considering vertex ‘1’ as source vertex, find the shortest paths to all other vertices in the
following graph using
Dijkstra’s
algorithm. Show all the steps.

Shopping Cart

You cannot copy content of this page