# Mumbai University Previous year question papers

## III Sem IT Examination June 2010

## Data Structure and Algorithms

N.B.

1) Question No. ! is compulsory

2) Attempt any FOURquestionsf,romremaining~ questions.

1.

a) -Write a program to implement a STACKADTusing Linked list.

b) ExplainHuffmanCodingand constructHuffmancodefor the following

“JAVA DATA STRUCTURES”

2.

a) Construct the binary tree for the inorder and post order traversal sequence given below

In order: “INFORMATION” 10

Post order: “INOFMAINOTR

b) Write and explain Radixsort algorithm with suitable example. 10

3. a) Writean algorithmfor mergesort and commenton its complexity. 10

b) Calculateand drawthe minimumcost spanningtree usingKruskal’salgorithmfor the followinggraph.

4. a) ExplainhowInterfacesand Packagesare created and accessedwiththeir syntax.

b) WriteanyPattern MatchingAlgorithmand explainit withsuitable example.

5.

a) Writea programto implementqueue usingarray.

b) Writea programto search an element inan arrayusingbinarysearch technique.

6.

a) Write algorithm for heap sort and explain Ascending heap with suitable example.

b) Hashthe following in a table of size 11. Use allYtwo collision resolution technique

99 67 41 0 17 2 98 20 94 27

7. Writeshort note on anyfour of the following:-

i) AVLTrees

ii) Red and BlackTrees

iii) Asymptotic Notation

Iv) Recursion

v) Graph traversal technique

vi) Abstract data type.