# 2005 Madras University M Sc Computer Science Data Structures Question paper

** University Question Papers **

**
**2005 Madras University M Sc Computer Science Data Structures Question paper

PART A - (5 x 2 = 10 marks)

Answer ALL questions. All questions carry equal marks. Each answer should not exceed 50 words.

1. What is data abstraction? Why it is needed?

2. How do you insert an element in a priority queue?

3. What is BFS and DFS?

4. Compare internal and external sorting schemes.

5. How do you compute time and space complexity for a given algorithm?

PART B - (4 x 5 = 20 marks)

Answer any FOUR questions. All questions carry equal marks.

Each answer should not exceed 250 words.

6. Describe representation of arrays using row major and column major order.

7. What is a circular linked list? Compare with Doubly linked list.

8. How insertion and deletion of information take place in Stack? How stack over flow is indicated?

9.Explain searching of an element in BST.

10.Describe DFS along with an application.

11.Discuss the shortest path finding algorithm.

PART C - (5 x 10 = 50 marks)

Answer ALL questions. All questions carry equal marks.Each answer should not exceed 500 words.

12. (a) How an array is reversed? Explain array reversal for different representation schemes.

Or

(b) Describe polynomial addition and subtraction using ordered list.

13. (a) Explain the insertion of a list in a linked list if the position is specified. Obtain the length of the new list.

Or

(b) How insertion and deletion of nodes takes place in a queue? How two different queues are merged? Write algorithms.

14. (a) Explain binary tree representation and how tree traversals are used in the conversion of expressions

Or

(b) Describe any one Graph representation method and how does the minimum cost spanning tree be obtained. Write algorithm.

15. (a) Explain sorting large objects. Why it is dealt separately than conventional approaches?

Or

(b) Explain sorting with tapes and disks.

16. (a) Explain Hashing and A VL Trees.

Or

(b)Write short notes on : (i) Splay trees. (ii) Applications of B-Trees.