Data Structures and Algorithms 2079

Section A

Attempt ant Two questions:

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

2. How recursive algorithm use stack to store intermediate results? Illustrate with an example. Convert the infix expression A+B-(C*D/E+F)-G*H into postfix expression using stack.

3. How do you insert and delete a node at k^th position of the doubly linked list? Describe the process of implementing stack and queue using linked list.

Section B

Attempt any Eight questions:

4. Sort the numbers 82, 73, 12, 39, 26, 88, 2, 9, 60 and 41 using shell sort.

5. Why do we need asymptotic notation? Describe about Big oh notation with its curve.

6. Define  a queue. Explain about enqueue and dequeue operation in circular queue.

7. Write a program to implement binary search.

8. Find the MST of following graph using Prim's algorithm.