2007 Rajiv Gandhi Proudyogiki Vishwavidyalaya(Technical University) Computer M.C.A M.C.A.(Second Semester) EXAMINATION, June,2007 Question paper
MCA203 M.C.A.(Second Semester) EXAMINATION, June,2007 DATA STRUCTURE (MCA203) Time : Three Hours Maximum Marks : 100 Minimum Pass Marks : 40
Note : Attempt one question from each Unit. All questions carryequal marks.
Unit  I 1.(a) What is recursion ? Solve Tower of Hanoi problem by using recursion. (b) What is the procedure for calculating the address of any twodimensional array ? Explain with the help of an example.
2.(a) Explain 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, find the addresses of B[5][3] and B[1][1]. (b) Write an algorithm to find the VALUE of an Arithmetic expression P into postfix notations : P = (3 ? 2 * 5)/(3 * 2 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 First Node N from a linked list which contain the given ITEM of information. 4.(a) Explain the memory representation of a doubly linked list. (b) Explain the following : (i) To represent linked list using array (ii) Sparse matrices.
Unit  III 5.(a) Explain the memory representation of a binary tree with suitable example. (b) What are basic differences between 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 Nine Nodes and the Inorder and Preorder Traversal of T yields the following 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. Explain with suitable example. (b) Write the algorithm for Merge Sort and also prove that the worst case complexity is O(n logn).
8.(a) Explain Hasing Procedure. Give four advantages of a chained hash table over open addressing. (b) What are the differences between 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 given below. Convert into the Minimum Cost Spanning Tree by using Kruskal's Algorithm. (b) Write an Algorithm to insert the element into the Btree.
10.(a) Write the Algorithm for Breadth First Graph Traversals. Also prove the time complexity is : T(n,e) = T(n2) (b) Construct the AVL searchtree from the given set of item values : H,I,J,B,A,E,C,F
Attachments:
Return to question paper search
