ANNA UNIV CS2201 - DATA STRUCTURES NOV/DEC 2010 QUESTION PAPER - REG 2008

CS2201 - DATA STRUCTURES

NOV/DEC 2010 QUESTION PAPER

3RD SEMESTER CSE - REG 2008

PART A — (10 × 2 = 20 Marks) 
1. What is an Abstract Data Type? What are all not concerned in an ADT?
2. Explain why binary search cannot be performed on a linked list.
3. Number the following binary tree (Fig. 1) to traverse it in.
(a) Preorder
(b) Inorder
4. What is a threaded binary tree?
5. Define a heap. How can it be used to represent a priority queue?
6. Give any two applications of binary heaps.
7. What is hashing?
8. Mention any four applications of a set.
9. What is breadth-first traversal?
10. Define spanning tree of a graph.

PART B — (5 × 16 = 80 Marks)
11. (a) Describe the data structures used to represent lists. (Marks 16)

Or

(b) Describe circular queue implementation in detail giving all the relevant features. (Marks 16) 

12. (a) Explain the tree traversals. Give all the essential aspects. (Marks 16)

Or

(b) Explain binary search tree ADT in detail. (Marks 16) 

13. (a) Discuss in detail the B-tree. What are its advantages? (Marks 16)

Or

(b) Explain binary heaps in detail. Give its merits. (Marks 16)

14. (a) Explain separate chaining and extendible hashing. (Marks 16)

Or

(b) Explain in detail the dynamic equivalence problem. (Marks 16)

15. (a) Consider the following graph
(i) Obtain minimum spanning tree by Kruskal's algorithm. (Marks 10)
(ii) Explain Topological sort with an example. (Marks 6)

Or

(b) (i) Find the shortest path from 'a' to 'd' using Dijkstra's algorithm in the graph in Figure 2 given in question 15(a). (Marks 10)
(ii) Explain Euler circuits with an example. (Marks 6)