3II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS

Code No: R059211201Set No. 3II B.Tech I Semester Regular Examinations, November 2006ADVANCED 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) What do you mean by Stack unwinding.
(b) What is the di.erence between const char *myPointer and char *const
(c) Define precondition and post-condition to a member function.
(d) What are the conditions that have to be met for a condition to be an invariantof the class.[4+4+4+4]
2. (a) Explain the need for “Virtual Destructor".
(b) Can we have “Virtual Constructors".[8+8]
3. (a) What are some ways try / catch / throw can improve software quality.
(b) How can we handle a constructor that fails.
(c) How can we handle a destructor that fails.[5+5+6]
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. What is Hashing. Explain the di.erent Hash table representations in detail. [16]6. Define a class called binarySearchTree to represent a Binary search tree. Extendthis class by adding a public method outputInRange (Low,High) that outputs,in ascending order of key, all elements in a binary search tree whose key lies betweenLow and High. Use recursion and avoid entering sub trees that cannot possiblycontain any elements with keys in desired range.[16]
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) Explain the Job sequencing with deadlines with an example using the greedyapproach.
(b) Describe the dynamic programming approach for the construction of OBSTfor a set of n keys, if all keys are equally likely to be searched for. [8+8]