2II B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS

Code No: R059211201Set No. 2II B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) Explain about the friend function with a suitable example.
(b) Why is it best to use inline functions instead of plain old # define macros.
(c) How to tell the compiler to make a non-member function inline.
(d) How to tell the compiler to make a member function inline. [4+4+4+4]
2. What do you mean by run time polymorphism and how to implement run timepolymorphism using virtual functions in C++.[16]
3. (a) How do I use exceptions.
(b) Can I throw an exception from a constructor. From a destructor.
(c) Why doesn’t C++ provide a “finally" construct.
(d) What is an autoptr and why isn’t there an autoarray.
(e) Why can’t I resume after catching an exception.[3+3+3+3+4]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. (a) Explain the linear probing method in Hashing. Explain its performance analy-sis.
(b) What is hashing with Chains. Explain. Compare this with Linear Probing.[8+8]
6. (a) Prove that the insertion of a new node in a red-black tree with n nodes in .(logn) time in the worst case.
(b) Derive the amortized complexity of a find, insert or delete operation performedon a splay tree with n elements.[8+8]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]