Mumbai University question papers
III Sem CSE – Examination DEC 2006
Data Structures and Files
N.B. (1) Question NO.1 is compulsory.
(2) Answer any four questions out of remaining six questions.
(3) Assumptions made should be clearly stated.
(4) Figures to the right indicate full marks.
(5) Assume suitable data wherever required but justify the same.
1. (a) Suppose singly linear list is in memory. Write a function in ‘c’ to reverse. a given linked list without using additional memory allocations.
(b) Write a function in ‘c’ to delete a node from binary search tree, explain with examples, consider all cases.
2.(a) Write a program to implement ‘type’ command to type the contents of a file on the screen using ‘Low Level File I/O’,method. Program should make use of command line arguments.
(b) Develop an algorithm to convert given fully parenthesized expression (INFIX) to POSTFIX expression and evaluate POSTFIX expression.
3.(a) Convert the following Infix expression to Postfix and Prefix expression :-
(i) (a + b) * cld (iv) a * blc – d * e
(ii) a + ( b* c)/d – e (v) a * b + C* dIe
(iii) a* blc + die .
.(b) What is Recursion? Differentiate between Recursion and Iteration? Write a Recursive and Non Recursive function to calculate GCD of two numbers.
4. (a) Write a program to create DOUBLY LINKED List and performing following operations on it :-
(i) Insert into the list
(ii) Deleter from the list.
(iii) Search for data item in the list.
The list stores data about employees. Employee records are arranged in ASCENDING order of Employee Number. Each employee record consists of the following fileds-
-Joining Date –
(b) What are the different file 110in C language? What different library functions are supported by’C’ language to do this?
5.(a) Write a non~Recursive function to traverse Binary Tree in
(i) Inorder ‘(ii) Preorder.
(b) Construct a Binary Tree, using INORDER and POSTORDER traversal sequence given below:
Give justification for each step.
6.(a) Write a program in C to perform addition of two polynomials in one variable. Consider the polynomials represented in two linked list.
(b) Writea function CQINSERTand CQDELETEto insert and delete elementfrom circularQueue implemented by static memory allocations.
7.(a) Explain the method of Huffman Encoding. Apply Huffman Encoding method to following sentence ‘UNIVERSITY’. Give Huffman Code of each symbol.
(b) Write a note on any two of the following :-
(i) Threaded Binary Tree
(ii) Macro in ‘c’
(iii) Dynamic memory and pointers in ‘C’ language.