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)
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)
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 bi-connected 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 pre order, in order and post order 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)
-----------------------------------------------------------------------------------------------------------------------
EE 2204 — DATA STRUCTURES AND ALGORITHMS PREVIOUS YEAR QUESTION PAPER
