Bsc CSIT Semester 3 – Data Structure and Algorithms – Unit 8: Trees and Graphs (8 Hrs.)

Question 1

Explain AVL tree with example. Also, explain balancing algorithm for this tree.

Marks: 10

Year: 2080 Final TU

AVL Tree (Definition & Concept) Definition An AVL Tree is a self-balancing Binary Search Tree (BST) in which the difference between the heights of the left and right subtrees of any node is at most 1

Question 2

Write Dijkstra’s algorithm to find shortest path between any two vertices of a graph.

Marks: 5

Year: 2080 Final TU

Definition Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. --- Key Ide

Question 3

What is AVL tree? How heap differ from tree? Construct an AVL tree for data 24,12,8,15,35,30,57,40,45 and 78.

Marks: 10

Year: 2081 Final TU

1. AVL Tree Definition An AVL Tree is a self-balancing binary search tree (BST) in which the height difference between the left and right subtrees of any node is at most 1. - Named after Adelson-Ve

Question 4

What is the application of spanning tree? Draw a MST of a graph containing any 8 vertices and 11 edges with arbitrary edge costs.

Marks: 5

Year: 2081 Final TU

1. Definition of Spanning Tree A Spanning Tree of a connected, undirected graph is a subgraph that: - Includes all vertices of the graph - Contains no cycles - Has exactly (V − 1) edges, where V i

Question 5

Why do we need to balance the binary search tree? Justify with an example. Create an AVL tree from the data 24, 12, 8, 15, 35, 30, 57, 40, 45, 78.

Marks: 10

Year: 2079 Final TU

Definition A Binary Search Tree (BST) is a binary tree in which: - The left child of a node contains a value less than the node's value. - The right child of a node contains a value greater than the n

Question 6

Find the MST of following graph using Prim’s algorithm.

Marks: 5

Year: 2079 Final TU

Question 7

What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree.

Marks: 10

Year: 2078 Final TU

1. Definition of Binary Search Tree (BST) A Binary Search Tree (BST) is a binary tree in which each node satisfies the following properties: - The left subtree of a node contains only nodes with val

Question 8

What is graph traversal? Explain.

Marks: 5

Year: 2078 Final TU

Definition Graph Traversal is the process of visiting all the vertices (nodes) and edges of a graph in a systematic way. - Traversal helps in searching, analyzing, and processing graphs. - Every n

Question 9

What is shortest path? Explain Dijkstra algorithm for finding shortest path using suitable example.

Marks: 10

Year: 2077 Final TU

1. Shortest Path (Definition) The shortest path between two vertices in a graph is the path with the minimum total weight (or distance) among all possible paths connecting them. - Graph types: Wei

Question 10

What is minimum spanning tree? Explain

Marks: 5

Year: 2077 Final TU

Definition A Minimum Spanning Tree (MST) is a spanning tree of a connected, weighted, undirected graph such that: - It includes all the vertices of the graph. - It has no cycles. - The total weight of