# Data Structure and Algorithms January 2013

UNIT – I

1.  (a) What is complexity of algorithm ? Explain the time-complexity in detail, also give the significance of Big-oh notation in brief.

OR

(a) Give the difference between Array and linked – list. How we represent the linear Array in memory ?

(b) What is difference between singly and Doubly linked list ? Explain it with example.

UNIT – II

2 (a) Explain the concept of mapping with suitable example.

(b) Write an algorithm to insert an item in 2D-Array.

OR

2. (a) Explain the various types of special matrices.

(b) What do you mean by sparse matrices ? Explain this in detail.

UNIT – III

3.Write an algorithm to transform infix expressions into postfix expressions, with an example.

OR

3. (a) Explain the Queue representation in Array and its applications.

(b) Explain the application of stack in case of tower of Hanai problem.

UNIT – IV

4    Find the Pre-order, In-order and Post-order traversal of given Binary Tree.

OR

4.(a)  Write an algorithm to insert an item into Binary search tree.

(b) What do you understand by Height of Binary tree.

UNIT – V

5. (a)  What is difference between BFS and DFS.

(b) Explain the steps to sort the following list of numbers using insection sort. 77, 33, 44. 11, 88, 22, 66, 55

OR

Write short notes : (any two)

(i)  Minimum Spanning Tree

(ii)  Heap sort

(iii)  Unweighted Graph