Subject: Data Structures and Algorithms
Time: 3 Hours
Instructions
- Answer any 5 questions out of 8
- Each question carries equal marks
1. a. Explain the concept of a linked list and its advantages over an array.
b. Write an algorithm to delete a node from the middle of a singly linked list.
c. Write a program to implement the above algorithm to delete the node with data 10 from a linked list with the following nodes: 10 -> 20 -> 30 -> 40 -> 50.
2. a. Explain the concept of a stack and its real-life applications.
b. Write an algorithm to implement a stack using an array.
c. Write a program to implement a stack using an array and use it to evaluate a postfix expression.
3. a. Explain the concept of a queue and its real-life applications.
b. Write an algorithm to implement a queue using an array.
c. Write a program to implement a queue using an array and use it to simulate a single-server queuing system.
4. a. Explain the concept of a binary search tree and its advantages over a sorted array.
b. Write an algorithm to insert a node into a binary search tree.
c. Write a program to implement the above algorithm to insert the following nodes into a binary search tree: 10, 20, 30, 40, 50.
5. a. Explain the concept of hashing and its advantages over sequential search.
b. Write an algorithm to implement a hash table using an array.
c. Write a program to implement the above algorithm to insert the following key-value pairs into a hash table: (10, "Apple"), (20, "Banana"), (30, "Cherry"), (40, "Date"), (50, "Elderberry").
6. a. Explain the concept of a heap and its applications in priority queues and sorting.
b. Write an algorithm to implement a heap data structure using an array.
c. Write a program to implement the above algorithm to build a heap from the following list of numbers: 10, 20, 30, 40, 50.
7. a. Explain the concept of a graph and its different representations (adjacency matrix, adjacency list, edge list).
b. Write an algorithm to implement a breadth-first search (BFS) on a graph.
c. Write a program to implement the above algorithm to find the shortest path from a source node to all other nodes in the following graph:
```
A -> B -> C
| |
V V
D -> E
```
8. a. Explain the concept of a minimum spanning tree (MST) and its applications.
b. Write an algorithm to implement Kruskal's algorithm for finding an MST.
c. Write a program to implement the above algorithm to find an MST for the following weighted undirected graph:
```
A -> B: 10
A -> C: 20
B -> C: 30
B -> D: 40
C -> D: 50
C -> E: 60
D -> E: 70
```