## Anna University CS 8302 – DATA STRUCTURE, April May 2014, Computer Science and Engineering, Third Semester, Regulation 2012

Exam |
B.E/B.Tech. (Full
Time) DEGREE END SEMESTER EXAMINATIONS |

Academic Year |
April May 2014 |

Subject Code |
CS 8302 |

Subject Name |
Data Structure |

Branch |
Computer Science and Engineering |

Semester |
Third Semester |

Regulation |
2012 |

**B.E/B.Tech (Full Time) DEGREE END SEMESTER EXAMINATIONS, APRIL / MAY 2014**

Computer Science
and Engineering

Third Semester

**CS 8302 – DATA STRUCTURE**

(Regulation 2012)

Time : 3 Hours Answer A L L Questions Max. Marks 100

**PART-A (10 x 2 = 20 Marks)**

1. Show that the following equalities
are correct:

a. 2n

^{2}2^{n}+ n log n = 6 (n^{2}2^{n})
b. 10n

^{3}+ 15n^{4}+ 100n^{2}2^{n}= O(100 n^{2}2^{n})
2. List the applications of stack.

3. Give the advantages and
disadvantages of threaded binary trees.

4. Write the inorder traversal
algorithm of a binary tree

5. What are the properties of red
black tree?

6. Define leftist heap property.

7. Compare and contrast internal and
external sorting.

8. Illustrate the algorithm for
insertion sort

9. What are the techniques used for
overflow handling?

10. Write the linear search algorithm
and its order of complexity.

**Part-B (5* 16 = 80 Marks)**

11. a. A double ended queue (Deque) is
a linear list in which additions and deletions may be made at either end.
Implement the Deque using an array representation. Write algorithms to add and
delete elements from either end of the Deque. (8)

b. Implement an algorithm to
polynomials represented as single linked list. (8)

12. a. (i) Develop the algorithm to
perform the inorder traversal and insertion in a threaded binary tree. (10)

(ii) Show the result of inserting 3,
1,4, 6, 9, 2, 5, 7 into an initially empty binary search tree. Delete the root
and show the tree. (6)

**(OR)**

b.(i) Illustrate the algorithms for
Breadth First Search and Depth First Search, (8)

(ii) Find the minimum spanning tree
for the given graph. (8)

13. a) (i) Illustrate in the given red
black tree with algorithm to insert the following values: 20,16,17,6.Delete the
values: 4,20 (8)

Note: shaded boxes are red and others black nodes.

(ii) Show the result of inserting 2,
1,4, 5, 9, 3, 6, 7 into an initially empty AVL tree. (8)

**(OR)**

b) (i) Given a list of elements with
priorities: 21, 13,17,10,7,11 do the following:

* Build the binary heap (draw the tree
at each step) and show the corresponding array

* Delete the element with the highest
priority, drawing the tree at each step of the deleting procedure

* Insert a new element with priority
15 and draw the tree at each step of the insertion procedure. (16)

14. a) Show how the heap sort
processes the following input 31, 41, 59, 26, 53, 58, 97 with the algorithm.
(16)

**(OR)**

b) Discuss in detail sorting with
tapes. (16)

15. a) Describe about the cylinder
surface indexing. (16)

**(OR)**

b) Write in detail the B-Tree
indexing. (16)

****************************