2007 Rajiv Gandhi Proudyogiki Vishwavidyalaya(Technical University) Computer M.C.A M.C.A.(Second Semester) EXAMINATION,Nov.-Dec.,2007 Question paper
M.C.A.(Second Semester) EXAMINATION,Nov.-Dec.,2007
Time : Three Hours
Maximum Marks : 100
Minimum Pass Marks : 40
Note : Attempt one question from each Unit. All questions carry equal marks.
Unit - I
1.(a) Enlist different operations which are normally performed on any linear array. Which are
normally performed on any linear array. Write the algorithm for any two such operations.
(b) Explain briefly an array, structure and array of structures. If an array B is
stored as columnwise and B is stored at 1024 and B at 1084, find the
addresses of B and B.
2.(a) Write an algorithm to find the value of Arithmetic expression P into postfix notation :
P= 2 ? 3 + 5 * 2 ? 2 - 12 / 6
(B) What si Priority Queue ? Write an algorithm to delete the first element in a Priority
Unit - II
3.(a) Discuss 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) Explain the memory representation of a doubly linked list.
4.(a) Explain the following :
(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 nine nodes, the inorder and preorder traversal of T yields
the following 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) What are the differences between 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 Average Case Time Complexity
is O(n log n).
8.(a) Explain Hashing procedure. Give four advantages of a chained hash table over open addressing.
(b) Construct a Max Heap for the following elements and their sort :
58, 92, 102, 60, 50, 70, 190, 130, 30
Unit - V
9.(a) Write the algorithm for Breadth First Graph Traversal. Also prove the time complexity is
(b) Give five differences between B-tree and B+ -tree.
10.(a) Construct an AVL-search tree from the given set of item values :
H, I, J, B, A, E, C, F.
(B)Represent the linked adjacency list for the Graph G given below :
Return to question paper search