University of Mumbai 2006 M.C.A Computer Aplications ADVANCED DATA AND FILE STRUCTURES - Question Paper
C6n. 1691-06. BB-6918
(3 Hours) [ Total Marks : 100
N.B. (1) Question No. 1 is compulsory.
(2) Attempt any four from question Nos. 2 to 7.
(3) Assume suitable data wherever required.
(4) State your assumptions clearly.
(5) Answers to sub questions of any individual questions should be written together.
(6) Use of pencil should be done only to draw diagrams and graphs.
(7) Figures to the right indicate marks.
1 yCe. efine binary search tree. Write a pseudo code for inserting an element in binary search tree. iq Jtiy Find the Huffmans code for each of the following characters. 10
A B C D E F
45 13 12 16 9 5 Write the pseudo code for, the same.
2-V\|Q Wat is hashing ? Explain the terms synonyms, collision and home address. Using modulo-division 10 \>&nd linear probing method, store the keys given below in an array of 13 elements. How many collision occured ? **
28 7 846
786 431 870
612 675 876
546 34 12 V
Exofein the need for balancing binary search tree. Explain with suitable example the concept and 10 Vgnstruction of balanced AVL trees.
3. (a) Describe in detail Indexed Sequential Access Method. 10 (b) Write an algorithm for sorting the elements using shell sort. An array contains the elements shown 10
below. Show the contents of the array after it has gone through a one-increment pass of the shell sort. The increment factor is k = 3.
23 3 7 13 89 7 66 2 6 44 18 90 98 57 *
4. (a) (i). Define m-way trees. How are B and B+ trees used to maintain indexes ? 5
(ii) Build a B-tree of ordr 4 by inserting the following data in the sequence given below : 5
92 24 6 7 11 8 22 4 5 16 19 20 78 (b) With a suitable example explain with steps to find JJne path matrix using Warshall's Algorithm. 10
5. J) ./Create a binary search 1ree oi tolkmng data entered as a sequential set 10
, 14 23 7 10 33 56 80 66 70 (b) tymte an algorithm for depth first traversal of a graph. Traverse the following graph using breath 10
t
. 1691-B'B-6918-06.
Explain preorder, inorder and post order traversal of a tree. Give the preorder, inorder and post order listing of the nodes of the following :
s/L
ib/M/Vrite a short notes on any two of the following : <8 v<!) Multilist File Organization A ' & Quick Sort
10
(iii) Relative File Organization.
What is a spanning tree ? What is a minimum spanning tree ? Write an algorithm to find the minimum spanning tree.
n/
10
An array contains the elements shown below. Using the binary search algorithm, trace the steps followed to find 88. At each loop iteration including the last, show the contents of the first, last and mid.
10
|
Attachment: |
| Earning: Approval pending. |
