## Data Structure & Algorithm Analysis - May 2016

### 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)** Explain with example

(i) Degree of tree

(ii) Height of tree

(iii) Depth of tree(3 marks)
**1(b)** What is linked list? Give its applications.(2 marks)
**1(c)** What is recursion? State its advantages and disadvantages.(3 marks)
**1(d)** Define Asymptotic Notation along with exmaple.(3 marks)
**1(e)** What is Expression Tree? Give Example.(3 marks)
**1(f)** What are linear and non-linear data structure?(3 marks)
**1(g)** What is time Complexity? Determine the Time complexity for the following code :

for (c = 0 {

for (d = 0(3 marks)
**2(a)** Write a program to implement queue using array.(10 marks)
**2(b)** Write an algorithm for merge sort and comment on its complexity.(10 marks)
**3(a)** Define binary search tree. Write algorithm to implement insertion and deletion operation.(10 marks)
**3(b)** Write a program to crete single link list and display the list.(10 marks)
**4(a)** What is priority? Give implementation of it.(10 marks)
**4(b)** Using Prim's and Kruskal's algorithm find minimum spanning tree for the following graph:

**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 marks)

**5(b)**Construct the binary tree for the inorder and post order traversal sequence given below.

In order: 'INFORMATION'

Post order: 'INOFMAINOTR'(10 marks)

### Write short note on any four of the following

**6(a)** Euclid's Algorithm(5 marks)
**6(b)** Red and Black Trees(5 marks)
**6(c)** DFS and BFS(5 marks)
**6(d)** B-Tree(5 marks)
**6(e)** Radix Sort(5 marks)