Test Papers / Previous Question Papers of IGNOU CS04 Data Structures through C and PASCAL

PGDCA / MCA (I Yr)
Term-End Examination

December, 2005

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

Time: 2 hours
Maximum Marks: 60

Note : There are five questions in this paper Question No. 1 is compulsory. Answer any three questions from the rest. All algorithms should be written nearer to 'C' or Pascal Language.

1. (a) Write an algorithm that accepts a Binary tree as input and reverses the left and right children of each node. (7)

(b) Write at least four advantages of implementing a stack using Linked Lists in comparison to implementation of stack using Arrays. (4)

Write an algorithm that accepts two lower triangularmatrices, M and N, each with P rows as input. The total number of elements in the lower triangles is P(P + 1). Now, the algorithm should output a single mairix Q of order P x (P + 1) which represents both the lower triangular matrices. It is not necessary for Q to be either a lower triangular or upper triangular matrix. (13)

2. (a) Write a recursive function to print Post-order traversal of a Binary Tree. (3)
(b) Wite an algorithm for the 2 way Merge Sort and illustrate each pass for the following data. (7)
7, 4, 1, 3, 0, 2, 6, 5.

3. (a) Write an algorithm for the addition of two sparse matrices. Use linked lists. (7)
(b) Explain Indexed sequential file organization (3)

4. (a) Write an algorithm to convert an infix expression to a postfix expression. The algorithm should evaluate the resultant postfix expression. (6)

(b) Write any four applications of a Queue. Justify your answer. (4)

5. (a) Sort the following Sequence of data using Heap Sort : (5)
7, 6, 3, 14, 5, 9, 11, 10, 8, 20.
(b) Find the minimum cost spanning tree for the following graph : (5)
----DIAGRAM----