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

Code No: R059211201Set No. 1II 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) What do you mean by Data abstraction.
(b) Di.erence between “C structure" and “C++ structure"..
(c) Di.rence between a “assignment operator" and a “copy constructor".
(d) What is the di.erence between overloading and “overridding". [4+4+4+4]
2. (a) What is multilevel inheritance. Write a program to illustrate the concept ofMultilevel Inheritance.
(b) What is Hybrid inheritance. Write a program to illustrate the concept ofHybrid Inheritance.[8+8]
3. What is an Error and Exception. Explain the exception handling mechanism inC++ .[16]
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. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. (a) Write a method to delete the pair with the largest key from a Binary SearchTree.(b) Write a method to find the height of a Binary Search Tree.[8+8]
7. Write and explain an algorithm to determine if the AND/OR tree T is solvable.[16]8. (a) Write a linear time algorithm that generates the OBST from the root table.(b) Prove that the greedy method always obtains an optimal solution to the job-sequencing problem.[8+8]