CS 8302 – DATA STRUCTURE - April May 2014

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ⁿ + n log n = 6 (n² 2ⁿ)

b. 10n³ + 15n⁴ + 100n²2ⁿ = O(100 n² 2ⁿ)

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)

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

Go back to Anna University B.E Computer Science and Engineering Questions April May 2014 Regulation 2012  page

Go back to Anna University B.E Computer Science and Engineering Questions April May 2014  page

Go back to Anna University B.E Computer Science and Engineering Questions page