Madras University (UnOM) 2005 M.Sc Computer Science Data Structures - Question Paper

PART A - (5 x two = 10 marks)

ans ALL ques.. All ques. carry equal marks. every ans 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 calculate time and space complexity for a provided algorithm?



PART B - (4 x five = 20 marks)

ans any 4 ques.. All ques. carry equal marks.

every ans should not exceed 250 words.



6. define 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 info 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)

ans ALL ques.. All ques. carry equal marks.Each ans should not exceed 500 words.



12. (a) How an array is reversed? discuss array reversal for various representation schemes.

Or

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



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

Or

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



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

Or

(b) define any 1 Graph representation method and how does the minimum cost spanning tree be found. Write algorithm.

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

Or

(b) discuss sorting with tapes and disks.



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

Or



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

Earning:   Approval pending.