**B.E. (Third semester) EXAMINATION, DEC.2008 **

**(Common of CS/IT Engg.)**

**(DATA STRUCTURE AND ALGORITHMS)**

**[CS/IT-305(N)]**

Note. Attempt any five questions. All question carry equal marks. Make suitable assumption

Necessary.

1. (a) Consider a sorted array of ‘N’ element . Element are sorted in ascending order. A new element in

To be inserted in this array such that array remains sorted, algorithm for this operation.

(b) Write a program to find largest and smallest in any array.

2. (a) Write a recursive algorithms to calculate the factorial of a given number. What is the importance?

Of stack is recursion?

(b) Consider a 2-D 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. How stacks and queue can be represented by circular list? Write algorithm for primitive operation of

Stacks and queue represented circular list

OR

4. (a) Convert the following infix notation into prefix and postfix notation :

(i)-b+

(ii) a+b+c+d

(iii) (a+b ?c)*(e+f/d*g)

(iv) –a *(*b++)c^{– – }

^{ }(b) Explain the implementation of list linked using array and dynamic memory allocation.

5. (a) The following nodes are inserted into empty tree in order :

5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1

Construct the following:

(i) Binary search tree

(ii) AVL tree

(iii) Heap tree

(b) Write a sort note on m –way search tree.

6. (a) A binary tree T has 9 nodes. The in order and pre order traversal of T yield of the following

sequence of nodes:

Inorder: E A C K F H D B G

Preorder F A E K C D H G B

Draw the tree.

(b) Insert the following key into B-tree of order 5 step by step

1, 7, 6, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24, 3, 12, 14, 20, 21, 16

7. (a) Here are eight integers :

1, 7, 3, 2, 0, 5, 0, 8

Sort them using:

(i) Bubble sort (ii) insertion sort (iii) selection sort

In terms of best, average and worst case.

8. (a) For the following list :

(i) Construct max heap

(ii) 7,3,9,5,1,13,11,15

(b) Write short note on complexity of radio sort.

9. (a) For graph given below, find its :

(i) Adjacency matrix

(ii) Path matrix

(iii) Path matrix using Warshall’s algorithm

s

(b) Explain Dijkstra’s algorithm with suitable example.

10. (a) Diffrencaite between DFS and BFS . Give DFS spanning tree and BFS spanning tree of the given

graph.

(b) Write short notes on the following:

(i) Indexed sequential files

(ii) internal and External sorting