Pokhara University

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

Pokhara University – Data Structure And Algorithm Spring 2016

Level:  Bachelor	Semester –Spring	Year: 2016
Program: BCIS		Full Marks: 100
Course: Data Structure And Algorithm		Pass Marks: 45
		Time:  3hrs.

 

1. a) Why sorting is needed in data structure?
b) How can you sort an unsorted array of data using merge sort algorithm? Sort the following data using merge sort method.
15, 30, 75, 56, 78, 85, 0, 10, 12, 60
2. a) Define best case, worst case and average case analysis of algorithm.
b) Explain about postfix, prefix and infix expression. Write the algorithm to convert an expression from infix to postfix. Convert ((A-(B+C/M))*D)$(E+F) to prefix.
3. a) Define ADT. Explain stack as ADT.
b) Explain in detail about algorithm of PUSH and POP of stack.
4. a) What is binary tree? Create BST of following data and also transverse it using postorder, preorder and inorder way.
3, 12, 75, 25, 16, 14, 90, 66, 55, 35
b) Create a max heap of following data
12, 86, 25, 92, 54, 70, 8, 20, 100, 75

5. a)  Define graph. Explain strongly connected and weakly connected graph. Define MST and find MST of following graph using Krushal method.

b) Differentiate between Queue and priority queue. Describe the method of inserting and deleting element from priority queue.

6. Define hashing and hash function. Mention the criteria for good hash table. Insert the following data in hash table using linear probing and quadratic probing method.
234, 456, 344, 5343, 4356, 789, 342, 456, 234, 7865
7. Write short notes on any two:
a) Divide and conquer.
b) Minimum spanning tree.
c) Double hashing and rehashing.
d) Randomized algorithm.