Download Model question papers & previous years question papers
|
Posted By: jegadesh Member Level: Gold Posted Date: 08 Dec 2007
|
2007 Anna University B.E Electrical and Electronics CS1151 – DATA STRUCTURES Question paper
|
|
|
B.E./B/Tech. DEGREE EXAMINATION, MAY/JUNE 2007
Third Semester
Computer Science and Engineering
CS1151 – DATA STRUCTURES
(Common to B.E. (Part – Time) Second Semester Regulation 2005)
(Regulation 2004)
Time: Three hours Maximum: 100 Marks
Answer ALL questions
PART A – (10 ´ 2 = 20 marks)
1. List out and define the performances measures of an algorithm.
2. What is Recursion? Explain with an example.
3. Define ADT.
4. How do you push and pop elements in a linked stack?
5. Define binary search tree.
6. List out the various techniques of hashing.
7. What is the worst case complexity of Quick sort?
8. State the algorithmic technique used in merge sort.
9. Prove that the number of odd degree vertices in a connected graph should be
even.
10. Define NP hard and NP Complete.
PART B – (5 ´ 16 = 80 marks)
11. (a) (i) Develop an algorithm for binary search. Validate the algorithm with a
suitable data set. (10)
(ii) What is Top down approach? Explain. (6)
Or
(b) Derive the best average, worst case time complexity of a linear search.
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 to v2, v3, v4, v6, v7
(b) (i) Write ADT operation for Prim’s algorithm.
(ii) Explain the topological sort algorithm. (8)
******
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and
make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.