What is space complexity? Explain omega notation with example. [5]
Background and Concept of Data Structures
1.
Define data type and ADT. What are the benefits of using ADT? Explain [5]
Graph
1.
Define spanning tree. Explain minimum spanning tree with example. [5]
List
1.
How can we use linked list to implement queue? Explain. [5]
2.
Write short notes on a.) Doubly circular linked list Write short notes on b.) Breadth first Search [2.5+2.5]
Queue
1.
What is circular queue? How can you implement circular queue? [5]
Recursion
1.
Define recursion. Explain Tower of Hanoi (TOH) with example. [5]
Searching
1.
Why do we need hashing? Explain quadratic probing. [5]
Sorting
1.
Discuss the limitation of choosing 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. [10]
Stack
1.
What is stack? Explain different stack operations. Explain algorithm to evaluate postfix expression. [10]
Tree
1.
Explain almost complete binary tree with example. How do you insert, search, and delete nodes in a binary search tree? Explain with suitable example? [10]
2.
What are different applications of binary tree? Explain. [5]