EE2204 DATA STRUCTURES AND ALGORITHMS ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER NOV/DEC 2009, IMPORTANT QUESTIONS, 2 MARKS AND 16 MARKS QUESTIONS FOR EEE DEPARTMENT

EE2204 DATA STRUCTURES AND ALGORITHMS ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER NOV/DEC 2009, IMPORTANT QUESTIONS, 2 MARKS AND 16 MARKS QUESTIONS FOR EEE DEPARTMENT

ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER EE2204 DATA STRUCTURES AND ALGORITHMS  NOV/DEC 2009, IMPORTANT QUESTIONS, 2 MARKS AND 16 MARKS QUESTIONS FOR EEE DEPARTMENT

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2009

Third Semester

Electrical and Electronics Engineering

EE 2204 — DATA STRUCTURES AND ALGORITHMS

(Regulation 2008)

(Common to Instrumentation and Control Engineering and Electronics and

Instrumentation Engineering)

Time : Three hours Maximum : 100 Marks

Answer ALL Questions

PART A — (10 × 2 = 20 Marks)

1. Define Abstract Data Type.
2. Convert the infix expression F) (D/E B/C) (A − ∗ − into a postfix.
3. What are the steps to convert a general tree into a binary tree?
4. List the applications of trees.
5. What do you mean by a heap?
6. Define hashing.
7. What is topological sort?
8. Define biconnected graph.
9. State the greedy algorithm.
10. Mention any two decision problems which are NP-Complete.

PART B — (5 × 16 = 80 Marks)

11. (a) Explain the following operations in a doubly linked list.
(i) Insert an element (6)
(ii) Delete an element (5)
(iii) Reverse the list. (5)
Or
(b) (i) Discuss the algorithms for push and pop operations on a stack. (8)
(ii) Write an algorithm to insert and delete a key in a circular queue. (8)
12. (a) (i) Construct all possible tree structure with 4 nodes. (8)
(ii) Perform preorder, inorder and postorder traversals of the given
tree. (8)
Or
(b) Explain the following operations on a binary search tree with suitable
algorithms.
(i) Find a node (5)
(ii) Insert a node (5)
(iii) Delete a node. (6)
13. (a) (i) Discuss how to insert an element in an AVL tree. Explain with
algorithm. (10)
(ii) What is B-Tree? Explain its properties. (6)
Or
(b) (i) Describe the different hashing functions with an example. (8)
(ii) Explain the common collision resolution strategies in open
addressing hashing. (8)
14. (a) (i) Explain the breadth first search algorithm. (8)
(ii) Write and explain the Prim’s algorithm with an example. (8)
Or
(b) (i) What is a strongly connected graph? Give an example. (4)
(ii) Write the algorithm to compute lengths of shortest path. (4)
(iii) Explain the depth first search algorithm. (8)
15. (a) Find the optimal tour in the following traveling salesperson problem
using dynamic programming. (16)
Or
(b) (i) Explain the method of solving N queens problem by back tracking.
(10)
(ii) Discuss briefly the various asymptotic notations used in algorithm
analysis. (6)