Anna University Chennai 2012-3rd Sem B.E Computer Science and Engineering ./B.Tech , /E (ester, )-DATA STRUCTURES - Question Paper

B.E./B.Tech. DEGREE EXAMINATION, MAY/JUNE 2012.
Third semester
Computer Science and Engineering
CS 2201/141301/CS 33/10144 CS 302/080230007- DATA STRUCTURES
(Regulation 2008)
Time : 3 hours
Maximum : 100 marks
ans all ques..
PART A-(10*2 = 20 marks)
1. elaborate the operations can be done with set ADT?
2. provide any 3 applications of linked list.
3. Draw the expression tree for ((b+c)*a)+((d+e*f)+g).
4. elaborate the advantages of threaded binary tree?
5. elaborate the differences ranging from binary search tree and AVL tree?
6. What is the purpose of splay tree?
7. What is meant by open addressing?
8. What is the purpose of dynamic hashing?
9. describe critical path.
10. What is weakly connected graph?
PART B-(5*16 = 80 marks)
11. (a) (i) discuss the operations of queue with cC function. (8)
(ii) discuss the array implementation of stacks. (8)
Or
(b) discuss the cursor implimentation of linked list. (16)
12. (a) discuss the traversals of binary tree with examples. (16)
Or
(b) define the operations of binary search tree with functions. (16)
13. (a) Briefly discuss the single rotation and double rotation of AVL tree with examples. (16)
Or
(b) discuss the binary heap operations with examples. (16)
14. (a) For the provided input (4371,1323,6173,4199,4344,9679,1989) and a hash function n(X) = X mod 10. Show the resulting:
(i) Seperate chaining hash table.
(ii) Open addressing hash table using linear probing.
(iii) Open addressing hash table using quadratic probing.
(iv) Open addressing hash table with 2nd hash function.
h2(X)=7-(X mod 7). (16)
Or
(b) discuss the smart union algorithm with example. (16)
15. (a) (i) discuss the prims algorithm with example. (8)
(ii) discuss topological sort with an example. (8)
Or
(b) (i) discuss the kruskals algorithm with example. (8)
(ii) discuss the Dijikstras algorithm with an example. (8)

Earning:   Approval pending.