Uttar Pradesh Technical University (UPTU) 2007 M.C.A Data & File Structure Using 'C' - Question Paper
Printed Pages : 3 MCA - 202
(Following Paper ID and Roll No. to be filled in your Answer Book)
Roll No. | | | | | | | | | 1 | M. C. A.
PAPER ID : 1467
(SEM. II) EXAMINATION, 2006-07 DATA & FILE STRUCTURE USING C
Time : 3 Hours] [Total Marks : 100
Note : Attempt all questions. All question carry equal marks
1 Attempt any two parts of the following : 10x2=20
(a) A magic square is square array of integers such that the sum of every row, the sum of every column, and the sum of each of the two diagonals are all equal.
Write a program that reads a square array of integers and determines whether or not it is a magic square.
(b) Consider the following arithmetic expression P written in postfix notation.
P : 12, 7, 3, /, 2, 1, 5, +, , +
(i) Translate P, by inspection and hand, into its equivalent infix expression.
(ii) Evaluate the infix expression.
(iii) Evaluate the post fix expression P using stack.
(c) Write down both iterative and recursive version of Binary search algorithm. What is the time-complexity in both cases?
2 Attempt any two parts of the following : 10x2=20
(a) Write C function to implement queues in a linear array with two indices front and rear, such that when rear reaches the end of the array, all the items are moved to the front of the array.
(b) Write a procedure SORT, which sorts a linked list without changing any values in information field of the nodes.
(c) Write a function that splits a list into two other lists, so that the entries that were in odd-numbered positions are now in one list (in the same relative order as before) and those from even numbered positions are in the other new list.
3 Attempt any two parts of the following : 10x2=20
(a) Write functions in C that will
(i) find height of a linked binary tree
(ii) copy a linked binary tree.
(b) Suppose that LI and L2 are lists containing nl and n2 integers, respectively, and both lists are already sorted into numeric order.
Use the idea of binary search to describe how to find the median of the nl+n2 integers in the combined lists.
(c) Write a C function to retrieve an item from a hash table with open addressing and linear probing.
(a) Write a program in C which sorts a list of n items using insertion sort method.
Illustrate your algorithm with an example.
(b) (i) Write an algorithm to insert an item into
a binary search tree.
(ii) Illustrate the execution of HEAP SORT on the array
A = <6,14,3,25,2,10,20,7,6>
(c) Write procedures of Operations:
(i) B-Tree search
(ii) B-Tree Insert.
Attempt any two parts of the following : 10x2=20
(a) (i) Explain depth first search traversal
algorithm of a graph (ii) Write a procedure which determines whether or not a graph G is a graph. The graph is maintained in memory by linked representation.
(b) Explain prims algorithm to find the minimum cost spanning tree of a weighted graph. Illustrate your algorithm with an example.
(c) Write short notes on:
(i) B+Tree index files
(ii) Hash Task Implementation
(iii) Recursion
(iv) Threaded Binary Tree.
V-1467] 3 [ 6550 ]
|
Attachment: |
| Earning: Approval pending. |
