GUJARAT UNIVERSITY
MCA. Semester II
Data & File Structure
Date: 30th July, 2001
Marks:50
INSTRUCTIONS:
1. Attempt both the Sections in separate answer books.
2. Right side indicates the marks.
3. Assume suitable data wherever required.
SECTION I
Q-1 Answer the following Questions:
[9]
(A) What is Primitive & Non Primitive data Structures? Explain with
suitable example.
(B) Write an algorithm to check whether a string is palindrome or not
using stack.
(C) What is recursion & Explain the problem of Towers of Hanoi with
algorithm?
Q.2.Answer the following questions:
[8]
(A) Write an algorithm for converting an Infix Expression into Postfix
Expression with brackets & convert
following expression into postfix:
A*B+(C*D/E)*F-G
(B) Write an algorithm that inserts a node in doubly linked list in
ascending order.
OR
Q.2.Answer the following questions:
[8]
(A) Write an algorithm to insert a node in an ordered threaded binary tree
(B) Explain the Circular queue with an example & explain the inserting &
deleting algorithm for that.
Q.3 Answer the following questions:
[8]
(A) Write an algorithm to find all the leaf nodes & nodes which have only
one child from an ordered Unary
tree.
(B) Write an algorithm to delete a root node from an ordered binary tree.
OR
(B) Define different methods for traversal of tree with suitable
example.
OR
Q.3 Answer the following questions:
[8]
(A) Write an algorithm for conversion of general tree into binary
tree & trace with the following example.
(C) Explain how threaded binary tree is more efficient than ordered binary
tree Give node representation in
threaded binary tree.
SECTION II
Q.4 Answer the following questions (Any six)
[9]
1. Prove that the complete binary tree with n nodes exactly n+l null
branches.
2. Explain the Hierarchical approach of the data base system.
3. Write note on collision-resolution technique.
4. Explain multiplicative hashing method.
5. Explain Cellular Partitioned structure.
6. Write notes on Spanning Trees.
7. Write notes on three external storage devices in brief.
8. What do you understand by sequential files explain the.structure
of sequential files. '
9. Explain the structure of direct files?
Q.5 Answer the following questions:
[8]
(A) Write an algorithm for quick sort & sort the following data using
quick sort.
10, 23,64,21, 74, 9S, 2, 59,44,87, 55
(B) Explain the method for inserting & deleting a node in weight
balance tree with suitable example.
OR
Q.5 Answer the following questions:
[8]
(A) Write algorithms for creation of heap & sorting of heap. Sort
the following data using heap sort.
20,65,43,53,78,10,78,40,39,29
(B) Explain in detail index sequential file organization.
Q.6 Write short note on following (any two)
[8]
(A) Write an algorithm for linear search & binary search.
(B) Write notes on BFS using suitable example.
(C) Write an algorithm for radix sort & sort the following data
using radix sort.
50, 31, 66, 309, 408, 201,49,53,576,11
(D) Define the following terms:
1. Null Graph 2. Weight Graph 3.
Isolated node
4. Graph . 5. Complete binary tree 6.
Forest
7. Converse Inorder 8. Converse Preorder
