CS2201 - DATA STRUCTURES 141301 - DATA STRUCTURES ANNA UNIVERSITY QUESTION PAPER APRIL/MAY 2010

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2010.

Third Semester

Computer Science and Engineering

CS2201 — DATA STRUCTURES

141301 - DATA STRUCTURES

(Regulation 2008)

Time: Three hours Maximum: 100 Marks

Answer ALL Questions

PART A — (10 × 2 = 20 Marks)

1. Define List Abstract Data Type with example.

2. Mention the Applications of stack.

3. Write an algorithm to declare nodes of a tree structure.

4. Give an example for Expression Trees.

5. Define Splaying. Give example.

6. List out the structural properties of B-Trees.

7. Mention the difference between Hashing & Extendible Hashing with example.

8. Define Path Compression.

9. What is topological sort? Give algorithm.

10. What is biconnected graph? Give example.

PART B — (5 × 16 = 80 Marks)

11. (a) Describe the Cursor-based linked list with its implementation in detail.

Or

(b) Define Queue ADT. How is circular queue implemented? Give example.

12. (a) Define Tree. Explain the tree traversals with algorithms and examples.

Or

(b) Write an algorithm for binary search tree. Give example.

13. (a) Define AVL Trees. Explain its rotation operations with example.

Or

(b) Explain heap structures. How are binary heaps implemented? Give its

algorithm with example.

14. (a) Describe Equivalence Relations. Write down the algorithm for dynamic

equivalence problem.

Or

(b) Explain open addressing with its probing in detail.

15.(a)Explain any one of the shortest path algorithms with suitable example.

Or

(b)Describe the Prim’s algorithm for minimum spanning tree. Give an

example.