Advanced Data Structures Algorithms Jan2007 R059211201

Set No. 1

Code No: R059211201

II B.Tech I Semester Supplementary Examinations, February 2007 ADVANCED DATA STRUCTURES & ALGORITHMS ( Common to Information Technology and Computer Science & Systems Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆ 1. (a) What do you mean by Data abstraction? (b) Difference between “C structure” and “C++ structure”. (c) Diffrence between a “assignment operator” and a “copy constructor”. (d) What is the difference between overloading and “overridding”?

[4+4+4+4]

2. (a) What is multilevel inheritance? Write a program to illustrate the concept of Multilevel Inheritance. (b) What is Hybrid inheritance? Write a program to illustrate the concept of Hybrid Inheritance. [8+8] 3. What is an Error and Exception? Explain the exception handling mechanism in C++ ? [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 increasing difficulty? [5+5+6] 5. Develop a class for hash table using linear probing and neverUsed concept to handle an erase operation. Write complete C++ code for all the methods. Include a method to reorganize the table when (say) 60% of the empty buckets have never used equal to false. The reorganization should move pairs around as necessary and leave a properly configured hash table in which neverUsed is true for every empty bucket. [16] 6. (a) Write a method to delete the pair with the largest key from a Binary Search Tree. (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 jobsequencing problem. [8+8] ⋆⋆⋆⋆⋆ 1 of 1

Set No. 2

Code No: R059211201

II B.Tech I Semester Supplementary Examinations, February 2007 ADVANCED DATA STRUCTURES & ALGORITHMS ( Common to Information Technology and Computer Science & Systems Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆ 1. (a) Explain about the friend function with a suitable example. (b) Why is it best to use inline functions instead of plain old # define macros? (c) How to tell the compiler to make a non-member function inline? (d) How to tell the compiler to make a member function inline?

[4+4+4+4]

2. What do you mean by run time polymorphism and how to implement run time polymorphism using virtual functions in C++? [16] 3. (a) How do I use exceptions? (b) Can I throw an exception from a constructor? From a destructor? (c) Why doesn’t C++ provide a “finally” construct? (d) What is an auto ptr and why isn’t there an auto array? (e) Why can’t I resume after catching an exception?

[3+3+3+3+4]

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 increasing difficulty? [5+5+6] 5. (a) Explain the linear probing method in Hashing? Explain its performance analysis? (b) What is hashing with Chains? Explain? Compare this with Linear Probing? [8+8] 6. (a) Prove that the insertion of a new node in a red-black tree with n nodes in θ (logn) time in the worst case. (b) Derive the amortized complexity of a find, insert or delete operation performed on a splay tree with n elements. [8+8] 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 difference between Greedy method and Divide and conquer. [6+6+4]

1 of 2

Set No. 2

Code No: R059211201

8. (a) What are the general characteristics of greedy algorithms and the problems solved by these algorithms. (b) What is 0/1 Knapsack problem? Explain how principle of optimality applies to it. Also derive its dynamic recurrence relation. [8+8] ⋆⋆⋆⋆⋆

2 of 2

Set No. 3

Code No: R059211201

II B.Tech I Semester Supplementary Examinations, February 2007 ADVANCED DATA STRUCTURES & ALGORITHMS ( Common to Information Technology and Computer Science & Systems Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All 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 with suitable 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 increasing difficulty? [5+5+6] 5. Develop a class for hash table using linear probing and neverUsed concept to handle an erase operation. Write complete C++ code for all the methods. Include a method to reorganize the table when (say) 60% of the empty buckets have never used equal to false. The reorganization should move pairs around as necessary and leave a properly configured hash table in which neverUsed is true for every empty bucket. [16] 6. (a) Write a method to delete the pair with the largest key from a Binary Search Tree. (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 jobsequencing problem. [8+8] ⋆⋆⋆⋆⋆

1 of 1

Set No. 4

Code No: R059211201

II B.Tech I Semester Supplementary Examinations, February 2007 ADVANCED DATA STRUCTURES & ALGORITHMS ( Common to Information Technology and Computer Science & Systems Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆ 1. (a) What is diff between malloc()/free() and new/delete? (b) What are the access privileges in C++? What is the default access level? (c) What is destructor? (d) What is passing by reference?

[4+4+4+4]

2. (a) What’s the deal with operator overloading? (b) What are the benefits of operator overloading? (c) What are some examples of operator overloading? (d) What operators can/cannot be overloaded?

[4+4+4+4]

3. (a) How can we provide printing for an entire hierarchy of classes? (b) How can we open a stream in binary mode? (c) How can we “reopen” std::cin and std::cout in binary mode?

[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 increasing difficulty? [5+5+6] 5. (a) What is a dictionary? Define the abstract data type for it? Write the abstract class for the dictionary? (b) Give the applications of dictionary or dictionary with duplicates in which sequential access is desired. [8+8] 6. What is a Binary search tree? Provide a specification for the abstract data type BSTree(binary search tree with duplicates). Define a C++ abstract class that corresponds to this ADT. Write a program to insert a pair into a binary search tree. [16] 7. Write and explain a non recursive algorithm for post order traversal of a Binary tree with an example. [16] 8. (a) Explain the Job sequencing with deadlines with an example using the greedy approach.

1 of 2

Set No. 4

Code No: R059211201

(b) Describe the dynamic programming approach for the construction of OBST for a set of n keys, if all keys are equally likely to be searched for. [8+8] ⋆⋆⋆⋆⋆

2 of 2