# ADVANCED DATA STRUCTURES AND ALGORITHMS JNTU previous years question papers

2011

Common to Information Technology, Computer Science And Systems
Engineering

Time: 3 hours Max Marks: 80

All Questions carry equal marks

1. Develop a class for hash table using linear probing and neverUsed concept to handle an erase operation. Write complete C++ code for all the methods. Include a method to reorganize the table when (say) 60% of the empty buckets have never used equal to false. The reorganization should move pairs around as necessary and leave a properly con gured hash table in which neverUsed is true for every empty bucket. [16]

2. (a) Prove to yourself that all exception objects (the ones that are thrown) areproperly destroyed.
(b) Prove to yourself that if you create an exception object on the heap and throw the pointer to that object, it will not be cleaned up. [8+8]

3. (a) De ne inheritance? Explain about the access control mechanism in Inheritance in C++?
(b) Write a program to illustrate the concept of hierarchical Inheritance? [8+8]

4. (a) Derive the time complexity of Quick sort in average case.
(b) Write a non recursive algorithm for pre order traversal of a tree. [8+8]

5. Using algorithm OBST compute W(i, j), R(i, j) and C(i, j) for the identifier set (a1; a2; a3; a4)=(end, goto, print, stop, continue) with p1 = p2 = 0:125; p3 = p4 = 00625; p5 = 0:1875 q0 = 0; q1 = 0:1875; q2 = q3 = q4 = q5 = 0:0625 using R(I, j) and construct the optimal binary search tree. [16]

6. (a) Explain about the dynamic memory allocation and de-allocation in C++.
(b) Explain about static inner classes with a program. [8+8]

7. (a) Solve the following recurrence relation using substitution method
T(n) = 1 where n  4 = T(pn) + c where n > 4
(b) Explain Big Oh notation with an example. [8+8]

8. Start with an empty AVL search tree and insert the following keys in the given order:15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
Draw the gures depicting the tree immediately after each insertion and following the rebalancing rotation (if any). Label all nodes with their balance factors and identify their rotation types. [16]