Data Structure & Algorithm Analysis - Dec 2013

Information Technology (Semester 3)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks. 1 (a) What is Data structures and Abstract Data Type?(2 marks) 1 (b) What is AVL tree? Give example.(3 marks) 1 (c) What is recursion? State its advantages and disadvantages.(3 marks) 1 (d) What is Expression tree? Give example.(3 marks) 1 (e) What is Link List? State the different types of Link List.(3 marks) 1 (f) List out the properties of a symptotic notations.(3 marks) 1 (g) What is Data structures for Graph? Explain.(3 marks) 2 (a) What Doubly Linked List? Write an algorithm to implement following operations :-
(i) Insertion (All cases)
(ii) traversal (Forward and Backward)(10 marks) 2 (b) Define Binary search tree. Write an algorithm to implement Insertion and Deletion operation.(10 marks) 3 (a) Write a program to implement queue using array.(10 marks) 3 (b) Explain in brief insertion sort and shell sort.(10 marks) 4 (a) Explain in brief :-
(i) Directed Graph
(ii) Weighted Graph
(iii) Minimum spanning tree
(iv) Adjacency Matrix representation
(v) Adjaceny List representation(10 marks) 4 (b) Find Minimum spanning tree for following graph using Prim's and krusal algorithm show various steps. (10 marks) 5 (a) Write a program to convert INFIX expression into POSTFIX expression.(10 marks) 5 (b) Write a program to create singly Linked List and display the List.(10 marks) 6 (a) Write a program to implement a stack ADT using linked list.(10 marks) 6 (b) What is an AVL tree? Construct the AVL tree for following set of data. [Mention the type of rotation for each case].
1, 2, 3, 4, 8, 7, 6, 5, 11, 10, 12.(10 marks)