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

PGDCA / MCA (I Yr)
Term-End Examination

June, 2005

CS04 : Data Structures through "C" and "PASCAL"

Time: 2 hours
Maximum Marks: 60

1. (a) Write an algorithm to convert an lnfix expression into Postfix expression. Also convert the following Prefix expression into a Postfix expression:
(i) // * + ABCDE
(ii) - + A * B/CDE (10)

(b) Write an algorithm to implement bubble sort, and sort the following list in ascending order by using the algorithm. (10)
14, 11, 3, 15, 18, 9

(c) Give three applications of Trees. (3)

(d) Define the following terms with a suitable example of each: (7)
(i) Tree
(ii) Depth of a Tree
(iii) Height of a Tree
(iv) length of a Tree
(v) Forest
(vi) Leaf node
(vii) Degree of a Tree

2. (a) Design an algorithm to implement a Deque using Arrays. (5)

(b) Find a minimum cost spanning tree of the following graph using PRIM'S algorithm. (5)
-----DIAGRAM-----

3. (a) L1 and L2 are two singly linked lists which are already sorted. Now, write an algorithm to concatenate L1 and L2. Ensure that the concatenated list is sorted. (5)

(b) Write a function that returns the height of an AVL tree. (5)

4. (a) Construct a Binary tree from the given Preorder as well as lnorder traversals:
Preorder * - + E AB + CD
Inorder E + A - B * C + D (5)

(b) Write an algorithm that accepts two singly linked lists L1 and L2. lt should print L3, where L3 is a singly linked list and L3 = L1 ∩ L2. (5)

5. (a) What is a 'heap' ? Write an algorithm for the insert as well as delete heap operations. (7)

(b) List at least 3 differences between Arrays and Pointers. (3)

6. (a) Explain the following types of file organization techniques: (6)
(i) Sequential File organization
(ii) Indexed Sequential File organization
(iii) Direct File organization

(b) Write a recursive algorithm to generate a fibonacci sequence upto the n^th term, where n is any integer. (4)