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

PGDCA / MCA (I Yr)
Term-End Examination

December, 2005

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

Time: 2 hours
Maximum Marks: 60

1. (a) Write an algorithm to multiply two polynomials using linked list. (8)

(b) Let T be a binary tree with height h and n nodes. Show that log(n + 1)- 1 < = h < = (n - 1)/2. For which values of n and h can the above lowest upper bounds of h be attained equality. (7)

(c) Write an algorithm to implement the bubble sort and sort the following list in ascending order using bubble sort : (7)
13, 24, 5, 19, 2, 17, 4

(d) List any three disadvantages of sequential file organization. (3)

(e) Write an algorithm to insert a node before a given node in a linked list. (5)

2. (a) Write an algorithm to convert the following infix expression to the postfix expression and illustrate the position of stack after each step : (7)
z + (y*x-(w/v ↑ u)*t)*s

(b) Write a recursive algorithm for two way merge sort. (3)

3. (a) Find the postorder traversal of the tree given below : (3)
-----DIAGRAM-----

(b) Write an algorithm for insertion and deletion of elements in a Queue. (7)

4. (a) Write an algorithm for the breadth first traversal of a graph. (4)

(b) Write an algorithm to insert a node into a Binary Search Tree. (6)

5. (a) What is Drect File organization ? Explain any two advantages of Drect File organization over Sequential File organization. (4)

(b) Write an algorithm for performing Binary Search. What is the condition to perform Binary Search ? (6)