## Data Structure & Algorithm Analysis - Dec 2015

### 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.(3 marks)
**1 (c)** Define Graph. List the types Graph with example.(3 marks)
**1 (d)** What is Asymptotic Notations.(3 marks)
**1 (e)** Write down the properties of Red-Black trees.(3 marks)
**1 (f)** What are linear and non-linear data structures.(3 marks)
**1 (g)** Define minimum spanning tree. List the techniques to compute minimum spanking tree.(2 marks)
**2 (a)** Write a program to implement Queue ADT using array.(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 convert INFIX expression into POSTFIX expression.(10 marks)
**3 (b)** Define AVL tree? Construct AVL tree for following data [ Mention type of rotation for each case]

1, 2, 3, 4, 8, 7, 6, 5, 11, 10, 12.(10 marks)
**4 (a)** Using Prim's and Kruskal's algorithm find minimum spanning tree for the following Graph.
(10 marks)
**4 (b)** Write an algorithm to implement shell sort.(10 marks)
**5 (a)** Write a program to create singly linked list and display the list.(10 marks)
**5 (b)** Explain BFS and DFS algorithm with example.(10 marks)

### Write short note on any four.

**6 (a)** B-Tree(5 marks)
**6 (b)** Red Black Trees(5 marks)
**6 (c)** Searching Algorithms(5 marks)
**6 (d)** Sparse Matrix(5 marks)
**6 (e)** Euclid's algorithm(5 marks)
**6 (f)** Marge Sort(5 marks)