CS 1151 DATASTRUCTURES : Anna University ECE Question Papers

Started by Kalyan, Jul 17, 2008, 11:31 am

previous topic - next topic
Go Down

Kalyan

CS 1151 DATASTRUCTURES

B.E/B.Tech. DEGREE EXAMINATION, MAY/JUNE 2007

Third Semester

Electronics and Communication Engineering

Time : Three hours Minimum: 100 Marks

PART - A (10 * 2 = 20 Marks)

Answer ALL questions

1.   List out and define the performance 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, 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 )

Go Up
 

Quick Reply

With Quick-Reply you can write a post when viewing a topic without loading a new page. You can still use bulletin board code and smileys as you would in a normal post.

Warning: this topic has not been posted in for at least 120 days.
Unless you're sure you want to reply, please consider starting a new topic.

Note: this post will not display until it's been approved by a moderator.
Name:
Email:
Verification:
Please leave this box empty:

Type the letters shown in the picture
Listen to the letters / Request another image

Type the letters shown in the picture:

shortcuts: alt+s submit/post or alt+p preview