# Mumbai University Previous year question papers

## III Sem IT Examination June 2009

## Data Structure and Algorithms

N.S. :- (1) Question NO.1 is compulsory.

(2) Answer any four out of remaining six questions.

(3) All Programs are to be written in.JAVA only.

1. (a). What is Recursion? Give disadvantagesof recursion. Write a programto implement Towerof HanoL

(b) ExplainAsympoticNotations(0, 0,.8) and write the propertiesof asympoticnotations. 5

(c) Explain packages and how do we hide classes using packages. 5

2.(a) Write a program to implement Quick 50rt and comment on its complexity.

(b) Write an algorithm for binary search method with example.

(c) Explain vectors with at least five methods.

3. (a) Write a program to implement Circular queue using array. 10

(b) Explain Huffman Algorithm. Construct Huffman tree for “MALAYALAM” with its optimal code.

4. (a)’ Write an algorithm to traverse a graph using – (with example)-

(i) Breadth First Search

(ii) Depth First Search.

(b) Implement the function to delete a node from Binary Search Tree.

(consider all possible cases)

5. (a) Draw the minimum cost spanning tree using Kruskal’s algorithm. Also find its cost with all intermediate steps.

b) Write a program to implement STACK using Linked List. 10

6. (a) Explain in brief-

(i) Ascending heap

(ii) Desending heap.

Write a program to implement heap sort.

(b) What is hashing? Explain Ha:;hing methods and collision avoiding techniques.

7. Write short notes on any **four **of the following with example –

(a) AVL Trees

(b) B-Tress

(c) Shortest Path Algorithm.

(d) Pattern matching.

(e) Comparision of sorting Algorithms.

(f) ~xpression and realization of ADT’s in JAVA.