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

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 Object Oriented Programming principles.
(b) Comapare C++ with C.[8+8]
2. Define Inheritance. How many types of inheritances are there. Explain each withsuitable examples.[16]
3. (a) How does that funky while (std :: cin >> foo) syntax work.
(b) Why does input seem to process past the end of file.
(c) Should we end output lines with std::endl or ‘\n'.[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. 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]