CS-62 December, 2003 QUESTION PAPER

IGNOU BCA CS-62: 'C' PROGRAMMING & DATA STRUCTURE - DECEMBER 2003 QUESTION PAPER

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 2003
CS-62: 'C' PROGRAMMING & DATA STRUCTURE

Time : 2 Hours

Max. Marks : 60

---

Note : Question number 1 is compulsory. Answer any three questions from the rest. All algorithms should be written nearer to 'C' language.

---

Q.1(a) Write an algorithm to add two polynomials. Use the array implementation. If the polynomials have M and N terms respectively, what is the time complexity of your algorithm?

(b) Write an algorithm to convert an Infix Expression which includes the operators (,), +, -, * and / to Postfix Expression.

(c) Write a function that takes a pointer to the root of a binary tree T and computes the number of full nodes in T. What is the running time of your function?

Q.2(a) Draw the internal memory representation of the following Binary Tree using Sequential Representation.

(b) What is the minimum number of external nodes for a Binary Tree with height ‘h’? Justify your answer.

Q.3(a) Write the postfix form of the following expression:
(i) a + b - c * d
(ii) (a -b) * (c + d)

(b) Write an algorithm for the multiplication of two Sparse matrices (Use proper representation for the Sparse matrices).

Q.4(a) Draw the transitive closure of the directed graph shown in the following figure:

(b) Write Dijkstra’s Algorithm.

Q.5(a) Consider the following figure:
image is not available
Find Minimum Cost Spanning Tree for the above graph using Prim’s Algorithm.

(b) Is the Minimum Cost Spanning Tree found by using Prim’s Algorithm unique? Justify your answer.

Q.6(a) Write an algorithm to implement Bubble Sort technique of sorting.

(b) The input sequence to a Bubble Sort algorithm which sorts in increasing order is
35, 5, 38, 41, 39, 37
Show the sorting process stepwise.