# RGPV Exams Questions Papers Data structure 3rd SEM June 2009

**B.E. (Third semester) EXAMINATION, JUNE.2009**

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

**(DATA STRUCTURE AND ALGORITHMS)**

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

Note. Attempt all question . Each question carries equal marks.

1. (A) What do you understand by complexity of an algorithm? Explain space and time complexity. What

is big-oh notation?

(b) Write a program in C/C ++ which does multiplication of two matrices.

2. (a) How is physical memory allocated for a two-dimensional array? If each element of an array D [20]

[50] requires 4 bytes of storage, base address of data is 2000, determine the location of D [10]

[10], when the array is stored as:

(I) Row major

(ii) Column major

(b) Write short notes on the following:

(I) Sparse matrices

(ii) Recursion

3. Write the algorithm for the following operation which is performed as doubly linked list:

(I) Creation

(ii) Traversing

(iii) Insertion

(iv) Deletion

(v) Concatenation

OR

4. (a) Write insert and delete function in C/C++ language simulating insertion and deletion in queue

which is implemented by array of character.

(b) Convert the following infix expression to prefix expression and give various steps in evaluating

using stacks. How much time and space does your algorithm takes?

(5*3?2)/(3+ (7+3)/10)

5. What is B^{+} tree? Compare it with B-tree .Insert the following entries into an initially empty B-tree of

order 5 –

a,g,f,b,k,c,n,j,d,r,I,s,x,e,l,m,t,u,v.

6. (A) Construct a binary tree whose in order and post order traversals are as follow:

In order – D, B, A, E, C, G, F, H.

Post order – D, B, E, G, H, F, C, A.

(b) What is height balancing in a tree? Explain it by taking an example bad also write the algorithm for

inserting an element.

7. (A) enumerate various sorting algorithms and mention their time complexities.

(b) Sort the following integers using:

(I) Bubble sort

(ii) Selection sort

(iii) Merge sort

5 7 3 6 2 8 4 1

OR

8. (A) Explain the following:

(I) Insertion sort

(ii) Shell sort

(iii) Radix sort

(b) Write a sort note on binary search algorithm and its time complex city.

9. (A) Differentiate between DFS and BFS. Give spanning tree and BFS spanning tree of the given graph.

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

OR

10. (A) for the following graph construct minimum spanning tree using:

(I) Prim’s algorithm

(ii) Kruskal algorithm

(b)Write short notes on the following:

(I) Random access files

(ii) Internal sorting

(iii) B tree indexing