Data Structure and Algorithm Question Fall 2016

This is the question set along with answers of Data Structure and Algorithm Fall 2016, which was taken by the Pokhara University.

Pokhara University –Data Structure and Algorithm Fall 2016

1. 1.a) What is ADT? Explain stack and queue as ADT.
   b) How can we analyse an algorithm? Time complexity and space complexity.
2. a) Why Stack is called LIFO data structure? Write the algorithms for push and pop operation on stack.
   b) What is balanced tree? Create a AVL tree with following data:
   15,20,24,10,13,7,30,36,25,32,28,22,35,40
3. a) Explain splay trees with different types of rotation techniques.
   b) Define Hash function and load factor. For the input {21,26,39,16,25,34,0,61,14,9} show the resulting Hash table using quadratic probing.
4. a) Explain shell sort with its algorithm one suitable example.
   b) Construct a skew-Heap from the data [20,12,5,2,14,18,23,17,15,22} and show the deletion of one element from the heap.
5. a) What do you mean by adjacency matrix and adjacency list for a graph? Explain.
   b) Find the minimum spanning tree from the given graph using prim’s algorithm. 
6. a) Write the advantages of B*-trees over B-trees. Create the B* tree with following data assume the 4 elements in a node.
   (2,12,14,18,15,30,16,38,32,40,45,8,10,20,50,60)
   b) Write the collision detection techniques. And write about liner probing.
7. Write short note onany two:
   a) Recursion
   b) Dynamic programming
   c) Backtracking algorithms