**B.E./B.Tech. DEGREE EXAMINATION, MAY/JUNE 2007.**

**Third Semester**

**Electrical and Electronics Engineering**

**DATA STRUCTURES AND ALGORITHMS**

**(Common to Electronics and Instrumentation Engineering / Instrumentation and Control Engineering)**

**(Regulations 2004)**

Time: Three hours

Maximum: 100 marks

Answer ALL
questions.

**PARTA—(10x2 =20 marks)**

1. Write code for
generating fibonacci sequence recursively.

2. How do you access
the address where the element of a
matrix, whose index is given, is stored?

3. Justify queue as
ADT.

4. Write simple code
to traverse through DLL.

5. Construct a
binary tree for the following Infix expression: A + B * C/D.

6. Perform post
order traversal for the following binary tree:

7. Give examples of
sorting techniques that is not based on Divide and Conquer algorithmic
technique.

8. What is the best case and worst case complexity of merge sort?9. What are spanning forests? Discuss.

10. What is an adjacency matrix used for? Discuss.

**PARTB—(5x 16=80 marks)**

11. (a) How do you implement union, structures and arrays in C? Explain with suitable examples. (6 + 4 + 6)

Or

(b) (i) Write algorithm for reversing the elements of an array (one dimensional). (6)

(ii) Write a C program to find the product of a matrix A and its transpose. (10)

12. (a) (i) Write algorithms for insertion and deletion of nodes in a

(1) Stack (5)

(2) Circular List (5)

(ii) What is a priority queue? State the advantages with reference to implementation. (6)

Or

(b) Define a header node in Doubly Linked List. How do you merge two Doubly Linked Lists into a sing1e one? Compare with Circular Linked List. Write suitable algorithms.

13. (a) What is threaded binary tree? How do you represent binary tree using list? Write algorithms for finding the Kth element.

Or

(b) (i) Develop a ‘C’ program to implement a binary tree. Discuss how evaluation of expressions are handled using a binary tree structure. (10)

(ii) What are the applications of binary tree data structure? Explain. (6)

14. (a) Explain algorithms for bubble sort and selection sort. Which one of these outperforms? Why? Discuss.

Or

(b) Describe with suitable algorithms for indexed sequential search, binary search and interpolation search schemes.

15. (a) Describe BFS and DFS methods for graphs with suitable algorithms. How efficiencies are computed?

Or

(b) Write algorithm for finding minimum spanning tree and explain applications. Illustrate the algorithm with typical data of your own.