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