# 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 the remaining six questions.

(3) All programs are to be written in Java.

1. (a) Define 0 notation. Compute space and time completely of Binary Search technique. 10

(b) Construct suffix trie for string “communication”. .6

(c) Distinguishbetween datatype and data s.tructure. 4

2. (a) Specify an Abstract Data Type for binary tree.

(b) Write a program to implement Radix sort.

(c) Write the algorithm for linear search.

3.(a) Cpnstructthe binarytree for the in order and post order traversalsequencesgiven bellow- 10

Inorder:

“INFORMATION”

Post order: “INOFMAINOTR”

(b) Write a program to implement stacks using arrays. 10

4. (a) Write a program to implement queues using Linked Lists.

(b) For the following graph compute minimum spanning tree?

5. (a) Hash the following in a table of size 11. US’eany two collision resolution techniques.

23, 0, 52, 61, 78, 33, 100,’ 8, 90, 10, 14.

(b) Define ADT for priority queue and explain its working.

6. (a) Write an algorithm for merge sort and comment on its complexity. 9

(b) Construct a sorted heap for the’ following:

(20, X), (14, V), (50, C) (3,8), (5, D), (7, Q), (11, S), (8, V), (12, H) and (15,P).

7- Write short notes on anyfour the following :-

(a) Complexity of recursive functions

(b) Use of Arraylists

(c) Expression and realization of ADT’s in Java

(d) Comparison of searching Algorithms

(e) Pattern matching.

(f) B trees.