MORE IN Data Structure & Algorithm Analysis
MU Information Technology (Semester 3)
Data Structure & Algorithm Analysis
May 2016
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1(a) Explain with example
(i) Degree of tree
(ii) Height of tree
(iii) Depth of tree
3 M
1(b) What is linked list? Give its applications.
2 M
3 M
1(d) Define Asymptotic Notation along with exmaple.
3 M
1(e) What is Expression Tree? Give Example.
3 M
1(f) What are linear and non-linear data structure?
3 M
1(g) What is time Complexity? Determine the Time complexity for the following code :
for (c = 0 {
for (d = 0
3 M

2(a) Write a program to implement queue using array.
10 M
2(b) Write an algorithm for merge sort and comment on its complexity.
10 M

3(a) Define binary search tree. Write algorithm to implement insertion and deletion operation.
10 M
3(b) Write a program to crete single link list and display the list.
10 M

4(a) What is priority? Give implementation of it.
10 M
4(b) Using Prim's and Kruskal's algorithm find minimum spanning tree for the following graph: 10 M

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 M
5(b) Construct the binary tree for the inorder and post order traversal sequence given below.
In order: 'INFORMATION'
Post order: 'INOFMAINOTR'
10 M

Write short note on any four of the following
6(a) Euclid's Algorithm
5 M
6(b) Red and Black Trees
5 M
6(c) DFS and BFS
5 M
6(d) B-Tree
5 M