a knowledge trading engine...

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

Monday, 28 January 2013 10:15Web

Page 1 of 2

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

Note : Attempt 1 ques. from every Unit. All ques. carry equal marks.

Unit - I
1.(a) Enlist various operations which are normally performed on any linear array. Which are
normally performed on any linear array. Write the algorithm for any 2 such operations.
(b) discuss briefly an array, structure and array of structures. If an array B[11][8] is
stored as columnwise 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].

2.(a) Write an algorithm to obtain the value of Arithmetic expression P into postfix notation :
P= two ? three + five * two ? two - 12 / 6
(B) What si Priority Queue ? Write an algorithm to delete the 1st element in a Priority
Queue.

Unit - II
3.(a) explain the advantages, if any, of a two-way linked-list over a one-way linked list.
Write an algorithm which counts the number of nodes in a linked list.
(b) discuss the memory representation of a doubly linked list.

4.(a) discuss the subsequent :
(i) Linked list using array
(ii) Sparse matrices
(b) Write program to insert an element on a sorted list using pointer.

Unit - III
5.(a) Show that maximum number of nodes in a binary tree of height 'h' is 2^(h+1) -1, by using
induction hypothesis method.
(b) Write an algorithm for inserting a node in a threaded binary tree.

6.(a) Construct a Binary Tree T with 9 nodes, the inorder and preorder traversal of T yields
the subsequent sequences of node :
INORDER : E, A, C, K, F, H, D, B, G
PREORDER : F, A, E, K, C, D, H, G, B

Unit - IV
7.(a) elaborate the differences ranging from sequential search and binary search ? Write an algorithm
for binary search on linear array.
(b) Write the algorithm for insertion sort. Also prove that the avg. Case Time Complexity
is O(n log n).

8.(a) discuss Hashing procedure. provide 4 advantages of a chained hash table over open addressing.
(b) Construct a Max Heap for the subsequent elements and their sort :
58, 92, 102, 60, 50, 70, 190, 130, 30

Unit - V
9.(a) Write the algorithm for Breadth 1st Graph Traversal. Also prove the time complexity is
T(n^2).
(b) provide 5 differences ranging from B-tree and B+ -tree.

10.(a) Construct an AVL-search tree from the provided set of item values :
H, I, J, B, A, E, C, F.
(B)Represent the linked adjacency list for the Graph G provided beneath :

V6

V3 V9

VI