ANNA UNIVERSITY
B.E/B.Tech. DEGREE EXAMINATION, MAY/JUNE-2010
CS 1151 DATASTRUCTURES
Third Semester
Electronics and Communication Engineering
Time : 3 hours Minimum: 100 Marks
PART – A (10 * 2 = 20 Marks)
Answer ALL questions
1. Define ADT.
2. How do you push and pop elements in a linked stack?
3. Prove that the number of odd degree vertices in a connected graph should be even.
4. Define NP hard and NP complete.
5. Define binary search tree.
6. List out and define the performance measures of an algorithm.
7. What is Recursion? Explain with an example.
8. List out the various techniques of hashing.
9. What is the worst case complexity of Quick sort?
10. State the algorithmic technique used in merge sort.
PART B (5 * 16 = 80 Marks)
11.(a) Derive the best, average, worst case time complexity of a linear search.
Or
(b) (i) Develop an algorithm for binary search. Validate the algorithm with a suitable data set. (10)
(ii) What is Top down approach? Explain. (6)
12. (a) Write ADT operations for array implementation of polynomial addition.
Or
(b) Write ADT operations for array implementation of a queue.
13. (a) Write insertion algorithm for AVL tree. Write suitable rotation algorithms.
Or
(b) (i) Explain the algorithm for separate chaining. ( 8 )
(ii) Explain implementation of priority queue ( 8 )
14. (a) Write ADT operations for heap sort. Using the above algorithm sort the following:
35 45 25 11 6 85 17 35
Or
(b) (i) Explain the quick sort algorithm. ( 8 )
(ii) Explain external sorting. Give relevant example. ( 8 )
15. (a) Explain Dijkstra's algorithm using the following graph. Find the shortest path between v1, v2, v3, v4, v6 and v7.
[Diagram not available]
Or
(b) (i) Write ADT operation for Prim's algorithm. ( 8 )
(ii) Explain the topological sort algorithm. ( 8 )
KEYWORDS:2010 ANNA UNIVERSITY CHENNAI B.E ELECTRONICS & COMMUNICATION ENGINEERING DATA STRUCTURE-CS 1151, ANNA UNIVRSITY,ELECTRONIC AND COMMUNICATION,ANNA UNIVERSITY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS
B.E/B.Tech. DEGREE EXAMINATION, MAY/JUNE-2010
CS 1151 DATASTRUCTURES
Third Semester
Electronics and Communication Engineering
Time : 3 hours Minimum: 100 Marks
PART – A (10 * 2 = 20 Marks)
Answer ALL questions
1. Define ADT.
2. How do you push and pop elements in a linked stack?
3. Prove that the number of odd degree vertices in a connected graph should be even.
4. Define NP hard and NP complete.
5. Define binary search tree.
6. List out and define the performance measures of an algorithm.
7. What is Recursion? Explain with an example.
8. List out the various techniques of hashing.
9. What is the worst case complexity of Quick sort?
10. State the algorithmic technique used in merge sort.
PART B (5 * 16 = 80 Marks)
11.(a) Derive the best, average, worst case time complexity of a linear search.
Or
(b) (i) Develop an algorithm for binary search. Validate the algorithm with a suitable data set. (10)
(ii) What is Top down approach? Explain. (6)
12. (a) Write ADT operations for array implementation of polynomial addition.
Or
(b) Write ADT operations for array implementation of a queue.
13. (a) Write insertion algorithm for AVL tree. Write suitable rotation algorithms.
Or
(b) (i) Explain the algorithm for separate chaining. ( 8 )
(ii) Explain implementation of priority queue ( 8 )
14. (a) Write ADT operations for heap sort. Using the above algorithm sort the following:
35 45 25 11 6 85 17 35
Or
(b) (i) Explain the quick sort algorithm. ( 8 )
(ii) Explain external sorting. Give relevant example. ( 8 )
15. (a) Explain Dijkstra's algorithm using the following graph. Find the shortest path between v1, v2, v3, v4, v6 and v7.
[Diagram not available]
Or
(b) (i) Write ADT operation for Prim's algorithm. ( 8 )
(ii) Explain the topological sort algorithm. ( 8 )
KEYWORDS:2010 ANNA UNIVERSITY CHENNAI B.E ELECTRONICS & COMMUNICATION ENGINEERING DATA STRUCTURE-CS 1151, ANNA UNIVRSITY,ELECTRONIC AND COMMUNICATION,ANNA UNIVERSITY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS