Anna University - Data Structure and Algorithm (DSA) - May / June 2007 Question Paper

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.