Mahatma Gandhi University (MGU) 2006 M.C.A Computer Aplications DATA STRUCTURES - Question Paper

M.C.A (AFFILIATED COLLEGES)DEGREE EXAMINATION, SEPTEMBER 2006
Second Semester
DATA STRUCTURES

Time: 3 Hours Maximum :75 Marks
ans any 5 ques..
All ques. carry equal marks.

1. (a) Explain the need for dynamic data structures, and compare their access time and storage requirements with those of static data structures such as array.(8 marks)
(b) Write a program that accepts the Reg.No, Name, marks secured in 5 subjects by N students in a class and prepare the rank list.. (7 marks)

2. The pixel data of a color image is represented as a 3 dimensional array (height, width,3), where the 1st layer provide the value of red component and the 2nd and 3rd layer provide the value of green and blue respectively (for example the RGB components 1st pixel are D[1,1,1], D[1,1,2] and D[1,1,3]). Let the starting address of the array is 500 and the value of height and width are 100 and 150 respectively. obtain the address of the cell that refers the value of green component of tenth pixel in third row. (15 marks)

3. What are the possible methods to implement the data structure STACK? discuss how it is possible to implement 2 stacks using 1 array. Your stack should not generate an overflow condition unless the sum of the number of elements held in th e stack exceeds the size of the array. (15 marks)

4. (a) elaborate the demerits of a static QUEUE? Write an algorithm for implementing a self adjusting QUEUE that will decrease the length of the QUEUE by ½ if the number of elements is less than ½ of QUEUE size and the size become Size +3 while the number of elements is equal to the QUEUE size. (10 marks)
(b) Write the importance of Circular Queue with an example.
(5 marks)

5. (a) Write the procedure for interchanging 2 adjacent nodes in a doubly linked list without using a temporary node. (5 marks)
(b) Write an algorithm to split a singly linked list into 2 in such a way that the odd nodes are in 1 list and the even nodes in a different one. Write a different procedure for joining the 2 lists found to get the original list(first node from the 1st list and 2nd node from 2nd list and so on). (10 marks)

6. (a) If you wanted to traverse a tree and write all the elements to a file, and later ( the next time you ran the program) rebuild the tree by studying and inserting, would an in-order traversal be appropriate? Why or why not? Comment with suitable example.
(10 marks)
(b) What is an AVL tree? Write the characteristics of an AVL tree. (5 marks)

7. Write the algorithms for any 2 sorting algorithms you learned and discuss with a suitable example. Finally compare the algorithms and suggest the best method from that.
(15 marks)

8. (a) What do you mean by hashing? discuss any 2 hashing functions.(8 marks)
(b) What is recursion? discuss with an example. How does a stack help in recursion? (7 marks)

Earning:   Approval pending.