Job Saarnee

# 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.

Q4: Define
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.

OR

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
it’s depth.

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

OR

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.

OR

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

*Q16: 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.

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

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

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

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

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

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

Q12: 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.

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

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

Q15: Explain
transitive closure.

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.

OR

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.

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

OR

Describe Dijkstra algorithm with
suitable example.

*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.

Shopping Cart

You cannot copy content of this page