Baba Ghulam Shah Badshah University 2007 B.E CS 1151 DATASTRUCTURES - Question Paper
Saturday, 02 February 2013 10:05Web
CS 1151 DATASTRUCTURES
B.E/B.Tech. DEGREE EXAMINATION, MAY/JUNE 2007
Third Semester
Electronics and Communication Engineering
Time : 3 hours Minimum: 100 Marks
PART - A (10 * two = 20 Marks)
ans ALL ques.
1. List out and describe the performance measures of an algorithm.
2. What is Recursion? discuss with an example.
3. describe ADT.
4. How do you push and pop elements in a linked stack?
5. describe binary search tree.
6. List out the different 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. describe 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? discuss. (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) discuss the algorithm for separate chaining. ( eight )
(ii) discuss implementation of priority queue ( eight )
14. (a) Write ADT operations for heap sort. Using the above algorithm sort the following:
35 45 25 11 six 85 17 35
Or
(b) (i) discuss the quick sort algorithm. ( eight )
(ii) discuss external sorting. provide relevant example. ( eight )
15. (a) discuss Dijkstra’s algorithm using the subsequent graph. obtain the shortest path ranging from v1, v2, v3, v4, v6 and v7.
[Diagram not available]
Or
(b) (i) Write ADT operation for Prim’s algorithm. ( eight )
(ii) discuss the topological sort algorithm. ( eight
Earning: Approval pending. |