# RTU Previous Exam Papers BE EC 3rd Semester

# 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