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

Code No: R059211201Set No. 4II 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 di.erence between global static functions and static functions,class members.
(b) What is common and what is the di.erence between implementations of thecopy constructors, initialization and overloaded assignment operators.
(c) What is the di.erence between modifiers register, const and volatile. [5+5+6]
2. (a) Write a program to illustrate the concept of virtual base class with exampleprogram.
(b) How to implement run time polymorphism using virtual functions. [8+8]
3. (a) Explain about console I/O and formatted I/O streams in C++.
(b) Write a program to count the no of lines in given text file.[8+8]
4. Write and explain UNION and find algorithms with weighting and collapsing rule.[16]
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. Define a Binary Search Tree. Write the procedures to perform insertion, deletionand searching in a binary search tree.[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) 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]