ANNA UNIVERSITY COIMBATORE

B.E./B.Tech. DEGREE EXAMINATION:DECEMBER 2009

REGULATION-2008

THIRD SEMESTER

(COMMON TO EEE/EIE/ICE)

080300003-DATA STRUCTURES AND ALGORITHMS

Time : 3 hours Maximum : 100 marks

Answer ALL questions.

PART A — (20 * 2 = 40 marks)

1. What are the advantage of modularity?

2. What are the two basic operation on array?

3. Give any two example for linked list

4. What is circularly linked list?

5. Differentiate LIFO and FIFO and give typical examples of it.

6. What is a tree?why it is used.

7. What is the need for non-linear data structure?

8. What are the operation on the binary tree?

9. What is the majar drawback of sepsrste chaining hashing?

10.What is a balance factor for any node in AVL tree?

11.What is heap?

12.What is linear probing?

13.Define the following:

(i)Graph (ii)cycle

14.What is Biconnectivity?

15.Give any tow typical application of graphs.

16.where is Huffman coding is used?

17.What is principle of divide and conquer algorithms?

18.What do you mean by best fit in Bin packing?

19.What is the principle of randomized algorithms?

20.List out any two examples for NP complete problems.

PART B — (5 * 12 = 60 marks)

21.Explain the operation of a linked list.Also compara linked list and Array

22.Explain the various traversals in binary tree with example.

23.What is AVL tree? Also write suitable rotation algorithm.

24.Expain the shortest path algorithm with diagram.

25.Expain the kruskal's algorithm with diagram.

26.Expain the concept of stack and briefed on its two functions.

27.What is hashing?list out the various techniques of hashing.

28.Write short noteson folloeing:(i)B-tree(ii)Dynamic programming