IGNOU ASSIGNMENT MCS021
IGNOU SOLVED ASSIGNMENT MCS021
IGNOU SOLVED QUESTION PAPER MCS021
IGNOU SOLVED ASSIGNMENT MCS021
IGNOU SOLVED QUESTION PAPER MCS021
IGNOU ASSIGNMENT MCS021
IGNOU SOLVED ASSIGNMENT MCS021
IGNOU SOLVED QUESTION PAPER MCS021
SOLVED QUESTION PAPER
MCA (Revised) / BCA
(Revised)
Term-End Examination
December, 2015
MCS-021: DATA AND FILE
STRUCTURES
IGNOU 1.(a) Write an algorithm that accepts
two polynomials as input and prints the resultant polynomial due to the
addition of input polynomials. [10 Marks]
# include<stdio.h>
void main()
{
int poly1[6][2],poly2[6][2],term1,term2,match,proceed,i,j;
printf("Enter
the number of terms in the first polynomial. They should be less than
6:\n");
scanf("%d",&term1);
printf("Enter
the number of terms in the second polynomial. They should be less than
6:\n");
scanf("%d",&term2);
printf("Enter
the coefficient and exponent of each term of the first polynomial:\n");
for(i=0;i<term1;i++)
{
scanf("%d %d",&poly1[i][0],&poly1[i][1]);
}
printf("Enter
the coefficient and exponent of each term of the second polynomial:\n");
for(i=0;i<term2;i++)
{
scanf("%d
%d",&poly2[i][0],&poly2[i][1]);
}
printf(“The resultant polynomial due to the
addition of the input two polynomials:\n”);
for(i=0;i<term1;i++)
{
match=0;
for(j=0;j<term2;j++)
{
if (match==0)
if(poly1[i][1]==poly2[j][1])
{
printf("%d %d\n", (poly1[i][0]+poly2[j][0]), poly1[i][1]);
match=1;
}
}
}
for(i=0;i<term1;i++)
{
proceed=1;
for(j=0;j<term2;j++)
{
if(proceed==1)
if(poly1[i][1]!=poly2[j][1])
proceed=1;
else
proceed=0; }
if (proceed==1)
printf("%d
%d\n", poly1[i][0], poly1[i][1]);
}
for(i=0;i<term2;i++)
{
proceed=1;
for(j=0;j<term1;j++)
{
if(proceed==1)
if(poly2[i][1]!=poly1[j][1])
proceed=1;
else
proceed=0; }
if (proceed==1)
printf("%d
%d", poly2[i][0], poly2[i][1]);
}
}
(b) What is a stack ? Explain the
various operations of stack with an example for each operation. [10 Marks]
A stack is a linear structure in which items
may be inserted or removed only at one end called the top of the stack.
Generally,
two operations are associated with the stacks named Push & Pop.
• Push is an operation used to insert an element at the top.
• Pop is an operation used to delete an element from the top.
• Push is an operation used to insert an element at the top.
• Pop is an operation used to delete an element from the top.
(c) Write an
algorithm for each of the following: (i)
Depth first search (ii) Breadth first search
(i) Algorithm for DFS
Step 1: Select a vertex in the graph and make
it the source vertex and mark it visited.
Step 2: Find a vertex that is adjacent to the
souce vertex and start a new search if it is not already visited.
Step 3: Repeat step 2 using a new source
vertex. When all adjacent vertices are
visited, return to previous source vertex and continue search from
there.
If n is the
number of vertices in the graph and the graph is represented by an adjacency
matrix, then the total time taken to perform DFS is O(n2). If G is represented
by an adjacency list and the number of edges of G are e, then the time taken to
perform DFS is O(e).
(ii)Breadth First Search
Step 1:
Select a vertex in the graph and make it the source vertex and mark it visited
(mark it 1)
Step 2: Find
a vertex which is adjacent to the visited vertex from left to order
Step 3:
Repeat step 2 using a new source vertex. In this way, all the vertices of the
graph are searched.
(d) What is a Splay Tree ? How does
it differ from a Tree ? [10 Marks]
Splay Trees
are self-adjusting binary search trees in which every access for insertion or
retrieval of a node, lifts that node all the way up to become the root, pushing
the other nodes out of the way to make room for this new root of the modified
tree.
Addition of
new records in a Binary tree structure always occurs as leaf nodes, which are
further away from the root node making their access slower. If this new record is to be accessed very
frequently, then we cannot afford to spend much time in reaching it but would
require it to be positioned close to the root node. This would call for
readjustment or rebuilding of the tree to attain the desired shape. But, this process of rebuilding the tree
every time as the preferences for the records change is tedious and time
consuming. There must be some measure so
that the tree adjusts itself automatically as the frequency of accessing the
records changes. Such a self-adjusting tree is the Splay tree.
A tree
doesn’t adjust by itself. A Splay tree is self-adjusting. In a splay tree,
, the frequently accessed nodes
will frequently be lifted up and remain
around the root position; while the most infrequently accessed nodes would move
farther and farther away from the root.
This process
of readjusting may at times create a highly imbalanced splay tree, wherein a
single access may be extremely expensive. But over a long sequence of accesses,
these expensive cases may be averaged out by the less expensive ones to produce
excellent results over a long sequence of operations.
2. (a) Write an algorithm for the
implementation of a doubly linked list.
[10 Marks]
Step 1 Begin
Step 2 Define a structure ELEMENT with fields
Data
Left pointer
Right pointer
Step 3 Declare a pointer by name head and by using (malloc()) memory allocation function allocate space for one element and store the address in head pointer
Head = (ELEMENT *) malloc(sizeof(ELEMENT))
Step 4 Read the value for head->data
Step 2 Define a structure ELEMENT with fields
Data
Left pointer
Right pointer
Step 3 Declare a pointer by name head and by using (malloc()) memory allocation function allocate space for one element and store the address in head pointer
Head = (ELEMENT *) malloc(sizeof(ELEMENT))
Step 4 Read the value for head->data
head->left = NULL
head->right = (ELEMENT *) malloc(size of (ELEMENT))
head->right = (ELEMENT *) malloc(size of (ELEMENT))
Step 5
Repeat step3 to create required number of element
Step 6 End
Step 6 End
(b) Write an algorithm
for the implementation of a stack.
[10 Marks]
Algorithm to push an item onto the
stack
Step 1: [Check for stack overflow] if tos >=MAXSTACK print “Stack overflow” and exit
Step 2: [Increment the pointer value by one] tos=tos+1
Step 3: [Insert the item] arr[tos]=value
Step 4: Exit
Step 2: [Increment the pointer value by one] tos=tos+1
Step 3: [Insert the item] arr[tos]=value
Step 4: Exit
Algorithm to pop an element from the
stack
Step 1: [Check whether the stack is
empty] if tos = 0 print “Stack underflow” and exit
Step 2:
[Remove the top most item]
value=arr[tos] tos=tos-1
Step 3: [Return the item of the stack] return(value)
3. (a) Write
a non-recursive algorithm for in order traversal of a binary tree.
In Order Traversal, we perform the following three
operations:
1. Traverse the left subtree in in order
2. Visit the root
3. Traverse the right subtree in in order
2. Visit the root
3. Traverse the right subtree in in order
(b) Define B-tree. Give
an example of a B-tree [10
Marks]
B-trees are special m–ary balanced trees used in databases
because their structure allows records to be inserted, deleted and retrieved
with guaranteed worst case performance.
A B-Tree is a specialised multiway tree. In a B-Tree each node may contain a large
number of keys. The number of subtrees
of each node may also be large. A B-Tree is designed to branch out in this
large number of directions and to contain a lot of keys in each node so that
height of the tree is relatively small.
E.g.
Step 1: Search first node for key nearest to 33. Key 30 was
found.
Step 2: Node pointed by key 30, is searched for inserting 33.
Node is split and 36 is shifted upwards.
Step 3: Key 33 is inserted between 32 and 35.
Deletion of a key from B-tree is possible, but care must be
taken to ensure that the properties of b-tree are maintained if the deletion
reduces the number of keys in a node below the minimum degree of tree, this
violation must be connected by combining several nodes and possibly reducing
the height if the tree. If the key has
children, the children must be rearranged.
4. (a) Explain Kruskal's
algorithm with an example.
[10 Marks]
Krushkal’s algorithm uses the concept of forest of trees.
Initially the forest consists of n single node trees (and no edges). At each
step, we add one (the cheapest one) edge so that it links two trees together.
If it forms a cycle, it would simply mean that it links two nodes that were
already connected. So, we reject it.
The steps in Kruskal’s
Algorithm are as follows:
1. The forest is constructed from the graph G - with each
node as a separate tree in the forest.
2. The edges are placed in a priority queue.
3. Do until we have added n-1 edges to the graph,
1. Extract the cheapest edge from the queue.
2. If it forms a cycle, then a link already exists between the concerned nodes. Hence reject it.
3. Else add it to the forest. Adding it to the forest will join two trees together.
1. Extract the cheapest edge from the queue.
2. If it forms a cycle, then a link already exists between the concerned nodes. Hence reject it.
3. Else add it to the forest. Adding it to the forest will join two trees together.
(b) What are red-black
trees ? Explain the properties of a red-black tree. [10 Marks]
A Red-Black Tree (RBT) is a type of Binary Search tree with
one extra bit of storage per node, i.e. its color which can either be red or
black. Now the nodes can have any of the
color (red, black) from root to a leaf node.
These trees are such that they guarantee O(log n) time in the worst case
for searching.
Each node of a red black tree contains the field color, key,
left, right and p (parent). If a child
or a parent node does not exist, then the pointer field of that node contains
NULL value.
Properties of a
Red-Black Tree
Any binary search
tree should contain following properties to be called as a red-black tree.
1. Each node of a tree should be either red or black.
2. The root node is always black.
3. If a node is red, then its children should be black.
4. For every node, all the paths from a node to its leaves
contain the same number of black nodes.
5. (a) Explain
QuickSort algorithm. Trace the algorithm for the following set of data : 25, 0,
8, 78, 6, 34, 56, 90, 100
[10 Marks]
The basis of quick sort is the divide and conquer strategy
i.e. Divide the problem [list to be sorted] into sub-problems [sub-lists],
until solved sub problems [sorted sub-lists] are found.
Rearrange the list so that this item is in the proper
position, i.e., all preceding items have a lesser value and all succeeding
items have a greater value than this item.
1. Place A[0], A[1] .. A[I-1] in sublist 1
2. A[I]
3. Place A[I + 1], A[I + 2] ... A[N] in sublist 2
Repeat steps 1 & 2 for sublist1 & sublist2 till A[ ]
is a sorted list.
As can be seen, this algorithm has a recursive structure.
The divide' procedure is of utmost importance in this
algorithm. This is usually implemented as follows:
1. Choose A[I] as the
dividing element.
2. From the left end of the list (A[O] onwards) scan till an
item A[R] is found whose value is greater than A[I].
3. From the right end of list [A[N] backwards] scan till an
item A[L] is found whose value is less than A[1].
4. Swap A[R] & A[L].
5. Continue steps 2, 3 & 4 till the scan pointers cross.
Stop at this stage.
6. At this point, sublist1 & sublist are ready.
7. Now do the same for each of sublist1 & sublist2.
(b) Explain the merits
and demerits of various file organisations.
Sequential File Organisation finds use in application areas
where batch processing is more common. Sequential files are simple to use and
can be stored on inexpensive media. They are suitable for applications that
require direct access to only particular records of the collection. They do not
provide adequate support for interactive applications.
In Direct file organisation, there exists a predictable
relationship between the key used and to identify a particular record on
secondary storage. A direct file must be stored on a direct access device.
Direct files are used extensively in application areas where interactive
processing is used.
An Indexed Sequential file supports both sequential access by
key value and direct access to a particular record, given its key value. It is
implemented by building an index on top of a sequential data file that resides
on a direct access storage device.
IGNOU SOLVED QUESTION PAPER MCS021
IGNOU ASSIGNMENT MCS021
