Page 92 - Data Structures Handout_Neat

8.9 Exercise

Essay Programming Questions
1. Define a graph and explain the difference between directed and undirected

graphs.

2. Compare adjacency matrix and adjacency list representations in terms of

memory and performance.
3. Implement BFS and DFS for a given graph and compare their traversal outputs.

4. Implement Dijkstra’s algorithm to find the shortest path from a source vertex to

all other vertices in a weighted graph.

5. Implement Prim’s and Kruskal’s algorithms to compute the Minimum Spanning
Tree (MST) and compare their performance.

6. Discuss real-world applications of graphs (e.g., social networks, computer

networks, transportation systems).

Multiple Choice Questions (MCQ)
Q1. What is the main difference between directed and undirected graphs?

a) Directed graphs have edges with direction, undirected graphs do not

b) Directed graphs cannot have cycles

c) Undirected graphs always use adjacent lists
d) Directed graphs use less memory

Q2. Which representation of graphs is more memory-efficient for sparse graphs?

a) Adjacency Matrix b) Adjacency List

c) Both are equally efficient d) None of the above
Q3. What is the time complexity of Breadth-First Search (BFS) in a graph with

vertices and edges?

a) ( ) b) ( ) c) ( + ) d) ( ⋅ )

Q4. Which of the following algorithms can detect negative weight cycles?
a) Dijkstra’s Algorithm

b) Bellman-Ford Algorithm

c) Floyd-Warshall Algorithm

d) Prim’s Algorithm

92