RGPV Exams Questions Papers 3rd SEM Dec 2010 Data Structure
RGTU B.E. (Third semester) EXAMINATION, DEC.2010
(Common for CS/IT Engg.)
(DATA STRUCTURE AND ALGORITHMS – CS/IT-305(N)]
Note. Attempt any five questions. Each question carries equal marks.
1 (a) What are Asymptotic notations? Explain each notation with example and diagram.
(b)Solve the following recurrence relation T(n)=T(n-1)+1, with T(0) as initial condition./ Also find big oh
2. (a) What is recursion ? How does it differ from iteration? Write an algorithm to generate first ten
Fibonacci numbers recursively.
(b) Consider a 2d array declared in “c” A  . Element type is integer. If the base address is 1076,
what will be the address of A  ? Memory is byte oriented.
3. (a) Explain the inserting and deleting nodes from linked list implementing stack and queue.
(b) What are D-queue and priority queue?
4. (a) Write an algorithm to convert infix to postfix expression . Explain with example.
(b) Write function for:
(i) Finding size
(ii) Checking empty
(iii) Checking full
For the implementation of a queue in circular array with index value to indicate emptiness.
5. (a) Following nodes are insert into empty tree in order :
5 16 22 45 2 10 18 30 50 12 1
(i) Binary search tree
(ii) AVL tree
(b) Draw the order-5 B- tree resulting from inserting the following keys (in this order) in to initially
4 40 23 050 11 34 62 78 66 22 90 59 25 72 64 77 39 12
6. (a) Explain the operation of AVL tree.
(b) Write an algorithm to delete operation in any binary search tree (taking all classes).
7. (a) Compare the worst case performance of heap sort with the worst case performance and average
case of quick sort.
(b) Explain insertion sort and selection sort briefly.
8. (a) What is the difference between an index function and a hash function? Explain three techniques
to build the hash function.
(b) Explain how balance is restored when an insertion into height-balance tree puts a code out of
9. (a) Apply Prim’s algorithm to find the minimum tree of the given graph.
Display the tree at each stage.
(b) Compare graph traversal techniques.
10 (a) Explain Dijkstra’s algorithm with suitable example.
(b) Write short notes on the following:
(i) Strongly connected graph
(ii) Sparse matrix