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
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.
(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)
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)
