Gujarat University
MCA Semester II
Data & File Structures
Date: 27th July, 2000
Marks:50
Instructions:
1. Write answers of each section in separate answer books.
2. Figures to the right of each question indicate marks allocated to
that question.
3. You may make assumptions wherever necessary. Indicate clearly such
assumptions you have made.
Section I
Q-1 State whether the following statements are TRUE of FALSE:
[8]
1. Array is a non-linear data structure.
2. Fortran maps a two dimensional array in row-major order.
3. A sparse array will have high density of non-zero elements.
4. It is impossible to implement recursion without using stack-like data
structure.
5. Stack data structure is used not only for converting the infix
expression to postfix but also for evaluating the postfix expression.
6. A deque is a double-ended queue in which items can be inserted in the
middle and removed from either end.
7. Josephus problem is normally implemented using circular queue.
8. A connected graph is a graph that can be partitioned without removing
any edge.
9. Breadth-first traversal of a graph proceeds level-by-level, whereas
depth-first traversal follows first a path from starting node to an ending
node, then another path form the start to an end and so forth.
10. AVL trees are weight-balanced trees, whereas BB trees are height-
balanced trees.
11. Although quicksort is fastest sorting procedure of all, it performs
worst for a list which is completely unsorted.
12. Mid-square hashing gives better performance than Division-Reminder
hashing.
13. Each node in a trie stores only 10 pointers either null r pointing to
respective key digits.
14. A completely inverted file has an inversion index for every data
field.
15. Red-Black Tree is an m-way search tree where m is always grater than
4.
16. Records can be directly accessed by mapping RECORD KEY in relative
file.
Q-2 a) Develop an addressing function for a two-dimensional array with
lower and upper bounds AX (L1: U1,
L2:U2) mapped in row-major order. Name at least three languages which
implement such arrays in
row-major order.
Given a two dimensional array Z1(3:10, 10:20) stored in row-major
order with base address of 200 and size of each element of 4 bytes,
find address of element Z1(5, 15). [5]
b) Describe Triangular and Sparse arrays. How such arrays get
generated? What are the options for
mapping of these arrays?
OR
Q-2 a) What is the advantage of converting an arithmetic expression from
infix notation to postfix notation?
Write the algorithm for conversion of given infix expression using
stack. [5]
b) Convert the following infix expression to prefix and postfix
notations: [4]
1. (A + B)* D+ E/(F +A*D) +C
2. A/B^C+D E-AC
(The symbol ^ stands for exponential)
Q-3 a) Taking the following set of elements, show step by step hoe
Heapsort procedure will sort the elements
in required order:
[4]
20, 52,49,41,17,90,85,32
b) Name different methods to external sorting. Using Polyphase
sorting, show step by step how the
following list will be sorted. Assume four tapes/files are available
for sorting: [4]
18,30,5,19,8,39,32,26,45,16,11,37,24,3,21,43
OR
Q-3 a) Give diagrammatic representation of GETNODE and FREENODE algorithms
used for management of
available pool of space.
[4]
b) Write and explain diagrammatically the algorithm for insertion
of a node in a doubly linked list. [4]
Section II
Q-4 a) Write algorithms for pre-order, in-order and post-order traversal
method of a binary tree. [4]
b) Sketch a simple binary tree from following data:
[4]
Parent Left Child Right Child
A(root) B C
B D -
C E F
D - G
F H I
State the result of pre-order, in-order and post-order traversal of
the tree. [4]
OR
Q-4 a) Define threaded binary tree. Describe its node structure and
advantages over unthreaded binary tree.
[4]
b) Construct a binary search tree for following elements:
[4]
52,77,62,26,45,97,33,16,49,35,88.
Reconstruct this tree after following operations:
1. Node 90 is added
2. Node 26 is deleted.
