Test Papers / Previous Question Papers of IGNOU CS04 (S) Data Structures through C and PASCAL June 2007

PGDCA / MCA (I Yr)
Term-End Examination

June, 2007

CS04 (S): Data Structures through "C" and "PASCAL"

Time: 2 hours
Maximum Marks: 60

1.(a) Write an algorithm to implement quick sort technique. Also, show the steps of quick sort on the following given numbers : (10)
"14, 7 , 11, 35, 9, 41, 18"

(b) A traditional tridiagonal matrix A is a square matrix in which all elements other than those on the major-diagonal and on the diagonals immediately above and below this diagonal formed by non-zero elements in the diagonals are stored row-wise in a linear array B - the element A[1, 1] being stored at B[1]. Obtain an access formula to determine the position of element A[i, j] in the array B. Asterisks in the 4 x 4 tridiagonal array shown below mark the position of non-zero elements. (10)
________(matrix)_________

(c) Write a program to count the nodes of a Binary tree. (10)

2. It is intended to insert the following data item in a B-tree of order 5 a g f b k d h m j e s i r x c l n t u p Show how the tree would appear on deletion of each of the following items in sequence : h, r, P, d. (10)

3. (a) Find minimal spanning tree for the following graph. Also show the steps involved in it. (6)
_________(diagram)________
(Weights have been shown along with the edges)

(b) Differentiate between Depth first search and Breadth first search techniques. (4)

4.(a) Write an algorithm which translates an infix expression to a postfix expression.What is the time complexity of this algorifhm ? (6)

(b) Write a function in C language to insert the element in Circular Queue. (4)

5. Write short notes on the following (with their advantages and disadvantages) :

(a) Direct File Organization (5)

(b) Dynamic Memory Allocation (5)