## Search This Blog

### DATA STRUCTURES AND ALGORITHMS EE2204 NOV/DEC 2011 ANNA UNIVERSITY QUESTION PAPER | EE2204 DSA ANNA UNIVERSITY QUESTION PAPER

Tuesday, January 24, 2012 ·

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Third Semester
Electrical and Electronics Engineering
EE 2204 — DATA STRUCTURES AND ALGORITHMS
(Common to Electronics & Instrumentation Engineering and Instrumentation &
Control Engineering)
(Regulation 2008)
Time : Three hours Maximum : 100 marks
PART A — (10 × 2 = 20 marks)
1. What is Abstract data type?
2. List any two applications of queue.
3. Define non linear data structure.
4. Define complete binary tree.
5. Define AVL trees.
6. Define load factor of a hash table.
7. What is a forest?
8. Define Biconnectivity.
9. List any two applications that use greedy algorithm.
10. Define Skip Lists.

PART B — (5 × 16 = 80 marks)
11. (a) (i) Explain in detail the linked stack and linked queue.
(ii) Given two sorted lists, L1 and L2, write procedure to compute L1 U L2 and L1 using only the basic list operations.
Or
(b) What is a doubly linked list? Write an algorithm for inserting and deleting an element from Doubly linked list.
12. (a) How do you represent binary tree in a list? Write an algorithm for finding Kth element and deleting an element.
Or
(b) Construct an expression tree for the following expression (a + b*c)+(d*e + f)*g.
13. (a) Write the functions to insert and delete elements from the AVL tree.
Or
(b) What is meant by open addressing? Explain the collusion resolution strategies in detail.
14. (a) Compare Prim’s algorithm with Kruskal’s algorithm.
Or
(b) List any two applications of DFS. Explain in detail.
15. (a) State the running time equation theorem of divide and conquer algorithms and prove it.
Or
(b) Prove that the travelling salesman problem is NP complete.