1
Code No: R7211203 II B.Tech I Semester(R07) Supplementary Examinations, May 2009 ADVANCED DATA STRUCTURES AND 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. Write a class to represent a vector. Include the following functions to the above class (a) to create the vector (b) to modify the value of a given element (c) to multiply by a scalar value Write a program to implement above.
[4+6+6]
2. Write a program to implement Infix and Prefix increment operator for counting the user define object.
[16]
3. Write a non-recursive function to compute factorial of n. Compare the space requirements of your non-recursive function and these of the recursive functions.
[16]
4. What is Rehashing? Explain in detail about the Rehashing with an example.
[16]
5. Define maxHeap. Write algorithms for different operations of maxHeap.
[16]
6. Explain in detail about Splay trees.
[16]
7. Divide and Conquer involves splitting the problems in to sub problems, solving the sub problems, and then combining the solutions. Explain this with the help of an example. 8. Solve any problem that comes under subset paradigm using Greedy method.
?????
[16] [16]
2
Code No: R7211203 II B.Tech I Semester(R07) Supplementary Examinations, May 2009 ADVANCED DATA STRUCTURES AND 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 rethrowing? (b) When do we need rethrowing? (c) Write a program to demonstrate the concept of rethrowing an exception. [4+4+8] 2. (a) Distinguish between overloaded functions and function templates. (b) Distinguish between class templates and templates class.
[8+8]
3. (a) Explain how linked lists can be used to implement polynomial operations. (b) Write a method to multiply two polynomials.
[16]
4. Write the routines f ind and remove for Separate Chaining hash table and explain them in detail.
[16]
5. Explain in detail how Heap sort algorithm works with the help of an example.
[16]
6. (a) Create a Binary search tree using the following data entered in a sequence: 14, 25, 7, 10, 33, 56, 80 66, 70 (b) Display the output of preorder, inorder, and postorder traversal of the above tree. [6+10] 7. Write Quick Sort algorithm which uses random partitioning element. Trace it with sample data.
[16]
8. What are constraints? What is feasible solution? What is objective function? What is optimal solution? Explain all of them by solving any problem with Greedy method.
?????
[16]
3
Code No: R7211203 II B.Tech I Semester(R07) Supplementary Examinations, May 2009 ADVANCED DATA STRUCTURES AND 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) How does the objects are passed as arguments to the member function? Explain with an example. (b) Write a program to send an array object as an argument to the function? Write a program to implement the above.
[8+8]
2. Create a class matrics MAT of size m × n. Define matric addition, substraction & multiplication operations for MAT type objects.
[16]
3. Obtain the asymptotic time complexity of the following : (a) Factorial of N (b) Selection sort.
[8+8]
4. (a) What is Separate Chaining? (b) Discuss in detail about Separate Chaining. (c) What are the problems associated with Separate Chaining?
[3+8+5]
5. Define maxHeap. Give examples of max Heap. Define max Heap as Abstract Data type. Explain the different operations on maxHeap.
[16]
6. Write an algorithm for creation of an AVL tree. Explain it with an example.
[16]
7. Explain in detail the applications of Divide and Conquer strategy.
[16]
8. (a) How do you determine whether a give job sequence has a feasible solution or not. (b) Prove that the Greedy method always obtains an optimal solution to the job sequencing problem.
[6+10]
?????
4
Code No: R7211203 II B.Tech I Semester(R07) Supplementary Examinations, May 2009 ADVANCED DATA STRUCTURES AND 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) When a catch (.....) handler is used? What should be placed inside a catch block? (b) When do we use multiple catch handlers? Give an example.
[8+8]
2. Write a program using templates to implement for finding the minimum and maximum value contained in an array.
[16]
3. (a) Explain in detail about the Linked lists. (b) Give the class interface using template to construct Linked List.
[8+8]
4. (a) Describe a procedure that avoids initializing a hash table. (b) What are the advantages and disadvantages of the various collision resolutions strategies? [8+8] 5. How Heap is used to implement sorting algorithm called Heap sort.
[16]
6. (a) Construct a Binary search tree with the following values: 2, 5, 10, 8, 7, 3, 4, 20, 30, 15, 25. (b) Write algorithms to find the maximum and minimum value in Binary search tree. [6+10] 7. What is tree traversal? Write recursive versions of all tree traversal algorithms. How do you make them non-recursive versions?
[16]
8. Solve job sequencing with deadlines problem using Greedy method.
?????
[16]