**JNTU II B.Tech I Semester Regular Examinations, November 2008**

**ADVANCED DATA STRUCTURES AND ALGORITHMS**

**( Common to Information Technology and Computer Science & Systems**

**Engineering)**

**SET-2**

** **

1. (a) Distinguish between errors and exceptions.

(b) Explain the mechanism provided in C++ for handling synchronous exceptions.

2. (a) What do you mean by overloading of a function? When de we use it?

(b) Write a program to implement function overloading to perform the operations addition, substraction and multiplication both for integer and float data types.

3. (a) Write the insertion routine for linked list and explain.

(b) Write the deletion routine for linked list and explain.

4. (a) What is hashing? Why de we need hashing?

(b) Explain the importance of hashing with an example.

5. Explain in detail how Heap sort algorithm works with the help of an example.

6. Insert the following in to AVL tree in the sequence: march, may , nov, august,

april, january, december, july, february, june, october, september.

7. (a) Consider the recurrence relation

T(n) = T(1) if n=1

aT(n/b) = f(n) if n >1

where a and b are constants. Assume n = bk

(b) Solve the recurrence relation for the following choices of a,b, and f(n):

i. a = 5, b=2 and f(n) = cn

ii. a= 5, b=4, and f(n) = cn2.

(c) Solve the recurrence relation T(n) = 1 if n<=4

= T(sqrt(n)) + c if n>4

using substitution method.

8. (a) How do you measure the performance of an algorithm for constructing Optimal

Binary search tree.

(b) Write an algorithm to construct Optimal Binary search tree given the

root r(i,j), 0 <= j <= n.