# 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

notation.

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 [20] [30]. Element type is integer. If the base address is 1076,

what will be the address of A [17] [29]? 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?

OR

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

Construct:

(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

empty tree:

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

balance?

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