Data Structure & Algorithms Information Technology (May/June 2011)

1.	(a) What is Data Structure and Abstract Data type?	05
	(b) Explain the Asymptotic notations to measure the time complexity of Algorithm.	05
	(c) What is Recursion? State its advantages and disadvantages.	05
	(d) What is vector? Explain any four functions.	05
2.	(a) Write an ADT for Stack. And implement it using array. The ADT should support the following operations.        i) Create ii) push iii) Pop iv) Display	10
	(b) Write an algorithm to implement Quick sort? Derive its Best case and Worst case Time complexity.	10
3.	(a) What is a Priority Queue? Explain the Insertion and Deletion operation on Priority Queue if it is implemented using Array.	10
	(b) Explain the working of Merge sort. And sort the following elements             70, 20, 30, 40, 10, 50, 60	10
4.	(a) Define Binary Tree. Write an algorithm to implement different tree traversal techniques.	10
	(b) What is Doubly Linked List? Write a program to implement the following operations on it.              i) Insert ii) Delete iii   Traverse	10
5	(a) What is an AVL tree? Construct the AVL tree for the following set of data.              14, 10, 1, 20, 17, 24, 18, 12, 15, 11, 4, 6	10
	(b) Explain the Huffman's Algorithm for encoding the characters. And construct the Huffman's              code for following characters. Alphabets C E F D A B Frequencies 12 9 5 16 45 13	10
6.	(a) Using Prim's and kruskal's algorithm find Minimum Spanning tree for the following graph.	10
	(b) What do you mean by Hashing and Collision. how do you resolve the Hash clashes.	10
7.	Write short note on (Any four)     i) MAP abstract Data Type.    ii) Splay Tree.   iii) Pattern Matching.   iv) Graph Traversal.  v) Expression Tree.	20

Also see Data structure & algorithms question papers for June 2010