Data Structures and Algorithms 2080

Section A
Long Answer Questions
Attempt any TWO questions. [2 × 10 = 20]

1. What is a stack? Explain different stack operations. Explain algorithm to evaluate postfix expression. [1+4+5]

2. Explain almost complete binary tree with example. How do you insert, search, and delete nodes in a binary search tree? Explain with suitable example. [3+7]

3. Discuss the limitation of choosing the first element as pivot in quick sort. Using merge sort algorithm, sort the numbers 40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30. [4+6]

Section B
Short Answer Questions
Attempt any EIGHT questions. [8 × 5 = 40]

4. Define data type and ADT. What are the benefits of using ADT? Explain. [2+3]

5. What is space complexity? Explain omega notation with example. [1.5+3.5]

6. Define recursion. Explain Tower of Hanoi (TOH) with example. [1.5+3.5]

7. How can we use linked list to implement queue? Explain. [5]

8. What are different applications of binary tree? Explain. [5]

9. Why do we need hashing? Explain quadratic probing. [2+3]

10. Define spanning tree. Explain minimum spanning tree with example. [1.5+3.5]

11. Write short notes on: [2 × 2.5 = 5]
(a) Doubly circular linked list
(b) Breadth first search