Monday, March 7, 2016

CS 8302 – DATA STRUCTURE - April May 2014

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

Academic Year
April May 2014
Subject Code
CS 8302
Subject Name
Data Structure
Computer Science and Engineering
Third Semester

Computer Science and Engineering
Third Semester
(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. 2n2 2n + n log n = 6 (n2 2n)
b. 10n3 + 15n4 + 100n22n = O(100 n2 2n)
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)
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)
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)
b) Discuss in detail sorting with tapes. (16)

15. a) Describe about the cylinder surface indexing. (16)
b) Write in detail the B-Tree indexing. (16)


Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery