**B.E. (fourth semester) EXAMINATION, June 2008 **

**(Common for cs & it Engg.)**

** (DATA STRUCTURE ALGORITHMS)**

**(CS/IT-401)**

Note. Question paper is divided into five units. Attempt one question from each unit. All questions

Carry equal marks.

1. (a) Discuss the representation of 3-dimensinol array using sequential mapping. Derive an expression

For addressing an arbitrary element.

(b) How dynamic memory management is possible through pointers? Write a program to store n

Element in an array using pointer.

2. (a) Write a program in C to match given strings without using any string manipulation functions :

(b) Explain the following terms:

(i) Structured programming (ii) Triangular arrays

3. (a) Company singly linked list and doubly list . Write an algorithm to insert an element into a doubly

Linked list.

(b) What is recursion? What do you mean by base criteria? Write a recursive procedure to find X^{y}.

OR

4. (a) What is sparse matrix ? How sparse matrix can be represented in memory using linked list?

Explain.

(b) What do you understand by multitask? Write insertion and deletion algorithms for *n *stack stored in

a one –dimensional array of one size *mn *where *m* is integer.

5. (a) Explain the following terms :

(i) Complete binary tree (ii) Full binary tree

(iii) Strictly binary tree

(b) What is a binary expression tree? Create a binary expression tree for the following expression and

write its pre and post order traversals:

(A** B/C) * D + E + F/G

(c ) What are threaded binary trees ?

6. (a) Explain the following terms with example :

(i) Height balance tree

(ii) Digital search tree

(b) Write detailed note on hashing and collision resolution techniques.

7. (a) Sort the following sequence using bubble sort and insertion sort algorithm . Write the position of

List after each step:

(b) Write an algorithm for merge sort. Give example.

8. (a) What t is quick sort ? Why is it called partition exchange sort? Write quick sort algorithms…

(b)What is complexity of an algorithm? How do you determine the complexity of an algorithm?

9. (a) Compare graph traversal techniques

(b) Using prim’s algorithm finds the minimum spanning tree of the following graph:

10. (a) Using dijkstra’s algorithm find the shortest path between a to e

(b) What are the various representation of graph? Explain