a knowledge trading engine...

Rajiv Gandhi Proudyogiki Vishwavidyalaya 2007-2nd Sem M.C.A Computer Aplications .(ester) , e, - exam paper

Monday, 28 January 2013 11:00Web

Page 1 of 3

MCA-203
M.C.A.(Second Semester) EXAMINATION, June,2007
DATA STRUCTURE
(MCA-203)
Time : 3 Hours
Maximum Marks : 100
Minimum Pass Marks : 40

Note : Attempt 1 ques. from every Unit. All ques. carryequal marks.

Unit - I
1.(a) What is recursion ? Solve Tower of Hanoi issue by using recursion.
(b) What is the procedure for calculating the address of any two-dimensional array ? discuss with
the help of an example.

2.(a) discuss briefly an array, structure and array of structures. If an array B[11][8] is stored
as columwise and B[2][2] is stored at 1024 and B[3][3] at 1084, obtain the addresses of
B[5][3] and B[1][1].
(b) Write an algorithm to obtain the VALUE of an Arithmetic expression P into postfix notations :
P = (3 ? two * 5)/(3 * two -3) + 5.

Unit - II
3.(a) Draw the picture representation of a polynomial function P(x) using linked list :
P(x) = 2x8 -5x7 - 3s2 + 4
(b) Write an algorithm to delete the 1st Node N from a linked list which contain the provided
ITEM of info.
4.(a) discuss the memory representation of a doubly linked list.
(b) discuss the subsequent :
(i) To represent linked list using array
(ii) Sparse matrices.

Unit - III
5.(a) discuss the memory representation of a binary tree with suitable example.
(b) elaborate basic differences ranging from complete binary tree and almost complete binary tree ?
Construct the binary tree with general tree.
6.(a) Show that maximum number of nodes in a binary tree of height 'h' is 2h+1 -1 ,h>=0.
(b) Construct a Binary Tree T with 9 Nodes and the Inorder and Preorder Traversal of T
yields the subsequent sequence of nodes :
INORDER : E,A,C,K,F,H,D,B,G
PREORDER : F,A,E,K,C,D,H,G,B

Unit - IV
7.(a) Write the procedure for shell sort. discuss with suitable example.
(b) Write the algorithm for Merge Sort and also prove that the worst case complexity is
O(n logn).

8.(a) discuss Hasing Procedure. provide 4 advantages of a chained hash table over open
addressing.
(b) elaborate the differences ranging from Sequential Search and Binary Search ? Write an algorithm
for binary search on linear array.

Unit -V
9.(a) What is minimum Cost Spanning Tree ? An undirected graph G is provided beneath. Convert into the
Minimum Cost Spanning Tree by using Kruskal's Algorithm.
(b) Write an Algorithm to insert the element into the B-tree.

10.(a) Write the Algorithm for Breadth 1st Graph Traversals. Also prove the time complexity
is :
T(n,e) = T(n2)
(b) Construct the AVL search-tree from the provided set of item values :
H,I,J,B,A,E,C,F