Mumbai University Question Papers
III Sem CSE – Examination June 2005
Data Structures and Files
N.B. : (1) Question No.1 is compulsory.
(2) Attempt any four out of remaining six questions.
(3) Subquestions of individual questions should be answered one other.
(4) All questions carry equal marks.
a) Give different methods of carrying out ‘File Input/output’ using ‘e’ language. Also discuss the different library functions supported by ‘e’ language for e~h’ of the~<wovemej;hod.:t.
2. Given a list of numbers, wd te a pr.ogram to sort these numbers in ascending order using a binary search j:bree. Print the sorted list.
(a)’ Assume that a file ‘IN.OAT’ is existing. It stores students records in £he ascending order of ‘SEAT NO’ Each student record consists of the following fields-
SEAT NO 4 digit positive integer
PHY marks 3
digit +ve integer
CHEM marks 3 digit +ve integer
MATHS marks 3 digit +ve integer.
Using ‘Formatted File r/o’- method, write a program to update this file to include PCM tot~l (total ofPHY, CHEM, MATHS marks) in each record. Also calculate ‘percentagePCM total marks’ and include t~se in the student’s records. Clearly specify the method of updation used.
(b) Write a program to create a ‘STACK’ ADT (Abstract Data Type) using Array implementation. ADT should support the following operations
(a) (i) Write a n~on ‘cirG~ar queues’r
(ii) write a note on ‘priority queues’.
(b) Write functions to insert an element- and to delete an element from a doubly linked list. Clearly explain all cases of insertionanddeletion.Use pointer implementation.
4. (a) Write a’ program to create a ‘Linked List’ ADT. ADT should support the following operations
(i) Creation of the list.
(ii) Insertion of nodes into the list.
(iii) Deled:i.o:n. of nodes from the list.
(b) Explain giving examples how a linked list can be implemented using arrays. Compare Dynamic and Array respresentations of linked list.
5. (a) write a program to implement ‘QUEUE’using linked list representation.
(b) (i) Write a short note on ‘Recursion in C’.
(ii) Write a recursive program to evaluate given PREFIX expression.
6. (a) Explain the method of Huffman Encoding~ How is the ‘Huffman Tree’ constructed? How is the code of any symbol in the alphabet constructed using Huffman Tree? Explain giving example.
(b) Write a note on a~y one of the following:
(i) Expression Trees
(ii) -Game Tre~
(iii) Threaded Binary Tree
(iv) Representing Lists as Binary Trees.
7. (a) Write routines to traverse a nonempty binary tree in (i) preorder
(ii) Inorder (iii) Postorder.
(b) What are the different ways of representing a binary tree? How would you choose a representation?