Data structure and Algorithms (DSA) S.E (I.T.) SEM III (December 2013)

Data structure and Algorithms (DSA) S.E (I.T.) SEM III 4/12/2013     (3 Hours)
GX-12128 [Total Marks:80]
N.B	(1) Question No. 1 is compulsory.
	(2) Solve any three questions from remaining questions.
	(3) Assume suitable data wherever necessary.
	(4) Figures indicate marks.
1.	(a)  What is Data structure and Abstract Data Type.	2
	(b) What is AVL tree? Give example.	3
	(c) What is recursion? State its advantages and disadvantages.	3
	(d) What is Expression tree? Give example.	3
	(e) What is Link List? State the different types of Link List.	3
	(f) List out the properties of a symptotic notations	3
	(g) What is Data structure for Graphs ? Explain.	3
2.	(a) What is Doubly Linked List? Write an algorithm to implement following operations:-     (i) Insertion (All cases) (ii) Traversal (Forward and Backward)	10
	(b) Define Binary search tree. Write an algorithm to implement Insertion and Deletion operation	10
3.	(a) Write a program to implement queue using array.	10
	(b) Explain in brief insetion sort and shell sort.	10
4.	(a) Explain in brief:-                                             (i) Directed Graph (ii) Weighted Graph (iii) Minimum spanning tree (iv) Adjacency Matrix representation (v) Adjacency List representation	10
	(b) Find Minimum spanning tree for following graph using prim's and krusal algorithm show various steps.

10

 
5. (a) Write a program to convert INFIX expression into POSTFIX expression.   10

     (b) Write a program to create singly linked List and display the List   10

6. (a) Write a program to implement a stack ADT using linked List. 10

      (b) What is an AVL tree? Construct the AVL tree for follwing set of data. [Mention the type of
            rotation for each case].
           1,2,3,4,5,6,7,8,9,10,11,12. 10

Also see Data structure & algorithms question papers for May/June 2011