Question Paper: Data Structure & Algorithm Analysis : Question Paper Dec 2013 - Information Technology (Semester 3) | Mumbai University (MU)
0

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