# Mumbai University Question Papers

## III Sem CSE – Examination DEC 2009

## Data Structures and Files

N. B.: (1) Question NO.1 is compulsory. 2″3 £I J.o ~ C30

(2) Attemptany four questions out of remaining six questions.

(3) Assume any suitable data whenever required but justify the same.

1. (a) Explain linear and nonlinear data structure with example.

(b) Explain different method of graph representation.

(c) Write a program in Java to implement Binary Search.

2. (a) Discuss Threaded binary tree in detail.

(b) Write a program in Java to sort given n integer number using heap sort.

3. (a) A Binary tree has 7 nodes. The pre-order and post-order traversal of the tree are given below. Draw the tree.

Pre-order: GFDABEC

Post-order: ABDCEFG

(b) Write short note on B- Trees and B+- Trees.

4. (a) What is Recursion? Write a program in Java to implement “Tower of Hanoi Problem.

(b) Write a program in Java to sort given n integer numbers using Quicksort.

Show the steps to sort the following numbers.

44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66

5. (a) Write a Java program to implement circular queue using linked list.

(b) Explain the method of Huffman Encoding. Apply Huffman Encoding method for the sentence “MALAYALAM”. Give Huffman code for each symbol.

6. (a) Using the modulo-division method and linear probing. Store the keys shown below in an array with 19 elements. How many collisions occurred? What is the density of the list after all keys have been inserted?

224562, 137456, 214562

140145, 214576, 162145

144467, 199645, 234534

(b) “Explain BFS algorithm, explain it by example.

7. (a) Discuss practical application of trees.

(b) Compare Iteration and Recursion.

(c) Write short notes on :-

(i) AVL Tree

(ii) Infix, Prefix and Postfix expression.