Anna University - Data Structure and Algorithm (DSA) - Nov / Dec 2006 - Question Paper

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2006.

Third Semester

Electrical and Electronics Engineering

DATA STRUCTURES AND ALGORITHMS

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

(Regulation 2004)

Time : Three hours

Maximum: 100 marks
Answer ALL questions.

PART A — (10 x 2 = 20 marks)

1. What is the purpose of the do-while statement? How does it differ from the
while statement.

2. What is recursion? What advantages is there in its use?

3. State the different application of stack.

4. What is the significance of priority queue?

5. What are the disadvantages of sequential representation of tree over the linked representation?

6. What is the use of threaded binary tree?

7. When is the need of external sort? Give example.

8. Define address calculation sort.

9. What are strongly connected graph? Give example.

10. State any two application of depth first traversal.

PARTB—(5 x 16=80 marks)

11. (a) (i) Name the four storage class specifications are included in C. Explain them with suitable example. (8)

(ii) Write a for ioop that will read the charter type array called text and write the characters backwards into another charter type array called back_text. Assume that the text contains 80 characters. (8)

Or

(b) (i) Write a C program that reads several different names and addresses into the computer, rearrange the names into alphabetic order, and then write out the alphabetize list. Make use of structure variable within the program. (10)

(ii) State the difference between call-by-value and call-by-reference? Give a suitable example. (6)

12. (a) Compare the following with suitable example. (2 x 8 = 16)
(j) Linked list and array
(ii) Singly linked list and Doubly linked list.

Or

(b) i) What are the advantages of circular linked list? Write down the various primitive operations performed on circular linked list. Write the algorithm for insertion of element in the circular linked list. (8)

(ii) Write a C program to perform the following operation on a queue
(1) Insert
(2) Delete and

(3) Display. (8)

13. (a) (i) Write a note on expression tree with suitable example. (6)

(ii) Write a C program to perform following operations in a binary tree.
(1) To search for particular information
(2) To compute number of nodes in a tree. (10)

Or

(b) (i) Write a C pseudo code to create, insert and delete a node recursively in Binary search tree. (10)

(ii) Draw the complete undirected graphs with five vertices. Prove that the number of edges in an n vertices complete graph is n (n -1)/2. (6)

14. (a) (i) Devise an algorithm for an insertion sort. (6)
(ii) What are different types of sorting techniques? Write an algorithm for shell sort and explain it with example. (10)

Or

(b) (i) Write notes on interpolation search with suitable example. (9)

(ii) Why do we say quick sort is an unstable sorting method? Write an algorithm to prove the same. (7)

15. (a) (i) Devise a round robin algorithm. Explain it in detail with a suitable example. (8)

(ii) State the array and the linked representation of graphs with example. (8)

Or

(b) (i) What are the different graph traversal methods? Explain them with example. (8)

(ii) Give an algorithm to find a shortest path in a graph. Explain it with a suitable example. (8)