## Data Structure & Algorithm Analysis - May 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 Asymptotic Notations. (3 marks)

** 1 (b) ** What is linked list? State the advantages of linked list. (3 marks)

** 1 (c) ** Define Double Ended queue. List the variants of Double ended queue. (3 marks)

** 1 (d) ** Define Graph. List its types with example. (3 marks)

** 1 (e) ** State the properties of Red Black Tree. (3 marks)

** 1 (f) ** Explain with example.

i) Degree of tree

ii) Height of tree (3 marks)

** 1 (g) ** Distinguish between linear data structure and non linear data structure. (2 marks)

** 2 (a) ** Write a program to implement STACK ADT using array. (10 marks)

** 2 (b) ** Write an algorithm to implement Quick sort. Explain with an example. (10 marks)

** 3 (a) ** Define binary search tree. Write algorithm to implement insertion ad deletion operation. (10 marks)

** 3 (b) ** Give an INFIX expression and write a program to convert in POSTFIX expression. (10 marks)

** 4 (a) ** Write a program to sort an array using insertion sort algorithm. (10 marks)

** 4 (b) ** What is AVL tree? Construct AVL tree using following sequence of data:

16, 27, 9, 11, 36, 54, 81, 63, 72 (10 marks)

** 5 (a) ** Find the minimum spanning tree for the given graph using Kruksal's algorithm. Also find its cost with all intermediate steps..

:IMAGE- (10 marks)

** 5 (b) ** Write functions to implement insert () and traverse () of singly linked list. (10 marks)

** 6 (a) ** Write algorithm to traverse a graph using:

i) Breadth First Search

ii) Depth First Search. (10 marks)

** 6 (b) ** What is priority queue? Give implementation of it. (10 marks)