B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2010
Third Semester
Electrical and Electronics Engineering
EE 2204 — DATA STRUCTURES AND ALGORITHMS
(Common to Electronics and Instrumentation Engineering and Instrumentation and
Control Engineering)
(Regulation 2008)
Time : Three hours Maximum : 100 Marks
Answer ALL questions
PART A — (10 × 2 = 20 Marks)
1. Distinguish between linear and non-linear data structures.
2. Write down the steps to modify a node in linked lists.
3. Define a path in a tree.
4. What is a binary search tree?
5. Define hashing.
6. What is meant by open addressing?
7. What is minimum spanning tree?
8. Define depth-first traversal in a tree.
9. Differentiate ‘‘divide and conquer’’ technique from ‘‘branch and bound’’
technique.
10. Explain dynamic programming.
PART B — (5 × 16 = 80 Marks)
11. (a) Write down and explain the algorithms for basic operations on stack ADT.
Or
(b)Explain polynomial manipulation using linked lists with an example.
12. (a) With suitable examples, explain binary tree traversal algorithms.
Or
(b) Explain the following operations in binary search trees :
(i) Insertion of a node (6)
(ii) Searching a node (5)
(iii) Modification of a node. (5)
13. (a) With suitable examples, explain the basic operations on AVL trees.
Or
(b) Explain the following in hashing :
(i) Folding method (6)
(ii) Division method (5)
(iii) Linear probing. (5)
14. (a) Explain in detail the Dijkstra’s algorithm to solve the shortest path problem.
Or
(b) Discuss in detail the applications of graphs.
15. (a) (i) With an example, explain backtracking. (8)
(ii) Discuss the asymptotic notations. (8)
Or
(b) Write detailed notes on NP-complete problems.