II B.Tech I Semester Regular Examinations, November 2006

Code No: R059211201Set No. 1 II 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 is the default data hiding type for a class. Why are data membershidden. How would you access them.
(b) In a printf statement, what are the codes for integer. .oat. string. How canyou choose how many numbers occur before and after the decimal point fora .oat. How can you pad zeroes to the beginning of an integer to make it aspecific length.[8+8]
2. What do you mean by run time polymorphism and how to implement run timepolymorphism using virtual functions in C++.[16]
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. 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. What is an AVL Tree. Write the algorithm to search for an element of an AVLSearch Tree. What is its time complexity.[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