**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-1**

** **

1. (a) What should be placed inside a try block? Give the syntax.

(b) Write a program to implement the use of try block.

2. (a) Distinguish between early binding and late binding.

(b) Write a program to show how we achieve late binding.

3. (a) Calculate the time complexity of Bubble sort.

(b) Distinguish between Big ‘O’ and Omega() notations.

4. (a) What is a Dictionary?

(b) Give the ADT for dictionary.

(c) What are the operations performed on dictionary? Explain them in detail.

5. What is priority queue? What are the applications of priority queue? How do you

implement a priority queue using Heap?

6. (a) How do you represent an AVL tree.

(b) What is the height of an AVL tree.

(c) Write an algorithm for searching an AVL tree.

7. (a) When do you use recursive approach as part of Divide and Conquer. Explain

it with example.

(b) When do you stop splitting a problem into sub problems. Explain.

8. Prove that kruskals algorithm generates a minimum cost spanning tree for every

connected undirected graph.