Full Marks: 60
Pass Marks: 24
Time: 3 hours

Attempt any two questions: (2 x 10 = 20)

1. Define stack as ADT. Describe its primitive operations on Array implementation and linked list implementation.
2. Describe properties of Binary Search Tree. Write recursive algorithms for constructing BST and its traversals. Illustrate them with an example.
3. What are external and internal sorting? Explain partition strategies of Merge sort and Quick sort. Trace these sort algorithms for following data:
   11 45 61 33 55 9 83 25

Construct the Binary tree T showing each step. Explain, how you can arrive at solution in brief?

Attempt any eight questions: (8 x 5 = 40)

4. Write recursive algorithm to get Fibonacci term. Illustrate it drawing recursion tree.
5. Construct an expression tree from the following postfix:
   AB + C*DC – -FG + $
6. Differentiate between Singly linked list, DLL, CLL and DCLL.
7. Describe circular Queue operations in array implementation.
8. Compare and Contrast between Binary searching and Binary tree searching.
9. State collision resolution techniques in hashing. Explain double hashing and quadratic probing techniques.
10. State MST (Minimum Cost Spanning Tree) problem and shortest path (single source and all other destination) problem. Name the algorithms for solving these problems.
11. Justify the statement: “To write an efficient program, we should know about data structures and algorithms”.
12. Discuss the merits and demerits of contiguous list and linked list.
13. What is priority queue? How it is best implemented?