CS1211-Data structures and Algorithm question papers Anna university question papers Download

2007 Anna University Chennai B.E Electrical and Electronics Engineering CS1211-Data structures and Algorithm Question paper
B.E/B.TECT. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2007
Third semester
(Regulation 2004)
Electrical and Electronics engineering
CS1211-Data structures and Algorithm

Time:three hours Maximum:100 Marks\

Answer all questions
PART-A(10*2=20 MARKS)
1.Differentiate Recursion and iteration.
2.Give the general syntax for nested-if-structure
3. state any two application of queue
4. what is the importance of header nodes?
5.Give the array representation binary tree.
6. What is the significant of threaded binary array?
7.What are the different notations used for time complexity in sorting techniques?
8.Define address calculation sort..
9. what do you mean by transitive closure?.
10. Define Minimum spanning tree.

PART-B(5*16=80 marks)
11.a). I)Give the memory representation and the equation for calculating the address of required element of required element in the following arrays:
1. one dimensional array of size ‘n’
2. two dimensional ‘m x n’ array(for both row-major order and column major order) (8)
ii). Explain ‘call by value and call by reference’ with simple c program. (8)
(or)
b) Differentiate structures and unions in ‘c’.illustrate the nested structure with an example c program. (16)

12.a).(i). write an algorithm for transforming infix expression into postfix expression. (6)
ii).using the above algorithm transform the folowing arithmetic infix expression ‘Q’ into its equivalent postfix expression ‘P’
Q:A+(B*C-(D/E ?E)*G)*H
Show the status of the stack and the string. (10)
(or)
b) I)explain basic operations of circular queue with an example and also compare the advantages and disadvantages of linear queue and circular queue. (8)
ii).write an algorithm to insert and delete an element in the doubly linked list. (8)

13. a).i) give the three cases involved in deleting a node from a binary search tree. (6)
ii). Consider the following binary search terr and do the following deletion operations cited below. (10)
60

25 75

15 50 66

33

44

1)node 44 is deleted
2) node 75 is deleted
3) node 25 is deleted
give the resultant tree and also indicate the case in each deletion.

(or)
b) i) write an insertion algorithm for AVL tree (4)
ii)Do the following insertions with the explanation of rotation involved in each insertion in AVL tree (12)
insert K ,insert M ,insert U,insert T,insert V, insert P



14.a).explain the algorithm of depth first search and breadth first with the following graph.
5
3
1
6
7
4 9

8 (16)
(or)
b).Explain the kruskal’s algorithm with relevant example in detail. (16)

15. a). I)Explain the two phases of heap sort in detail . (8)
ii).sort the following elements using heap sort. (8)
25 55 46 35 10 90 84 31
(or)



b).i)Explain the following searching techniques with their alsorithms and example for each
1.linear search
2.binary serach
state the time complexity of each above searching technique. (8+8)

FEEL USEFUL PLEASE GIVE +1