Unit 4 Most Frequently Asked Questions of Data Structure
Q1: What are the
applications of graph ?
Q2: Write down
the applications of DFS.
Q3: Write down
the applications of BFS.
connected and strongly connected graph.
Q5: What are the
advantages of DFS over BFS?
Q6: How the
graph can be represented in memory ? Explain with suitable example.
List the different types of
representation of graphs.
Q7: Discuss the
disadvantages of Dijkstra’s algorithm.
Q8: How many
ways are there to implement Kruskal’s algorithm ?
Q9: How Prim’s
Algorithm is similar to Dijkstra’s algorithm ?
Q10: Prove that
the number of odd degree vertices in a connected graph should be even.
Q11: Number of
nodes in a complete tree is 10000. Find
Q12: What is a
graph ? Discuss various types of graphs. Briefly explain few applications of
What is graph ? Discuss various terminologies
used in graph.
Q13: Discuss the
various types of representation of graph.
Q14: Write a
short note on graph traversal.
*Q15: Write and
Explain DFS graph traversal algorithm.
algorithm to traverse a graph. Apply same algorithm for the graph given in Fig.
by considering node 1 as starting node.
BFS algorithm to find the shortest path form node A to J.
detail about the graph traversal techniques with suitable example.
the importance of various traversing techniques in graph along with its
connected component and strongly connected component. Write an algorithm to find strongly connected
Q8: What do you
mean by spanning tree and minimum spanning tree ?
Q9: Write down
Prim’s algorithm to find out minimal spanning tree.
minimum spanning tree. Find the minimal spanning tree for the following graph
using Prim’s algorithm.
Kruskal’s algorithm to find minimum spanning tree.
the following undirected graph.
a. Find the adjacency list
representation of the graph.
b. Find the minimum cost spanning tree
by Kruskal’s algorithm.
*Q13: Find the
minimum spanning tree for the following graph using
Prim’s and Kruskal’s algorithm.
Prim’s and Kruskal’s algorithm. Construct minimum spanning tree for the below given graph using Prim’s algorithm. (Source node =a)
Q16: Write down
Warshall’s algorithm for finding all pair shortest path.
*Q17: Write the
Floyd Warshall algorithm to compute the all pair shortest path. Apply the algorithm on following graph.
Q18: Write and
explain Dijkstra’s algorithm for finding shortest path.
Write and explain an algorithm for
finding shortest path between
any nodes of a given graph.
*Q19: Find out
the shortest path from node 1 to 4 in a given graph using Dijkstra shortest path algorithm.
Dijkstra’s algorithm for finding shortest path. Describe its working for the graph given below.
Describe Dijkstra algorithm with
*Q21: 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.