## 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)