R09 - December, 2011 - Regular Examinations - Set - 3.

II B.Tech I Semester Examinations,December 2011
DATASTRUCTURES THROUGH 'C '
Common to Information Technology, Computer Science And Engineering,
Electronics And Communication Engineering, Electrical And Electronics
Engineering
Time: 3 hours Max Marks: 75
Answer any FIVE Questions
All Questions carry equal marks
*****
1. (a) How is the deletion of a node that has both left and right subtrees, undertaken
in a binary search tree? Explain.
(b) What is the need for an AVL tree? How is the rotation free deletion of a node
having both the subtrees done in an AVL search tree? Explain. [15]
2. (a) Trace the steps of the following balanced 3 way merge on the following \sam-
ple" list of keys available on a disk, with the internal memory capable of
holding 6 keys:
12, 1, 65, 7, 34, 15, 90, 22, 63, 56, 18, 3, 9, 22, 12, 88, 41
(b) Explain the principle behind the distribution of runs in a multiway merge sort.
[15]
3. (a) Give the advantages and disadvantages of inheritance.
(b) What is abstraction? Explain with an example.
(c) Discuss the usage of delegation. [6 5 4]
4. De ne algorithm. What are the desirable properties of the best algorithm. [15]
5. Write brie
y about collisions and its resolving techniques. [15]
6. Show all insertion of the following sequence of letters/numbers in a B - tree of order
6.
All 26 letters A through Z, starting from A as the rst insertion. [15]
7. Write a 'C ' program to print all occurrences of Pattern in Text using brute force
substring search algorithm. [15]
8. (a) De ne destructors and list its properties. Explain destructor with examples?
(b) Write a 'C ' program to demonstrate the constructors and destructor. [7 8]
****