CS-62 JUNE 2003 QUESTION PAPER

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
June, 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 a function to multiply two polynomials, using a linked list implementation. You must make sure that the output polynomial is sorted by exponent and has almost one term corresponding to any power. Assume appropriate representation for input polynomials.

(b) Given two Sorted Lists, L, and L2, write an algorithm to compute Lj u L2. Lj and L2 are to be implemented as Arrays.

(c) Write a function that takes only a pointer to the root of a binary tree T and computes the number of nodes in T.

Q.2(a) Draw the Internal memory representation of the following Binary Tree using Sequential Representation. Assume that nodes appear in the following physical sequence:
A, B, C, D, E, F, G, H
Image is not available

(b) Consider the tree in the following figure:

(c) List atleast 4 differences between Arrays and Pointers in *C Ianguage.

Q.3(a) Write the Postfix form of the following expression:
(i) (C x D) + (a - b)
(ii) C x D + a - b

(b) Write an algorithm for the addition of two matrices. The second matrix will be a sparse matrix. The first matrix is not a sparse matrix.

(c) What is an AVL Tree? How does it differ from a Binary Tree?

Q.4(a) Write an algorithm to solve the Single-Source Shortest-Path problem.

(b) Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights? Justify your answer.

Q.5(a) Consider the following figure:

Find the Minimum Cost Spanning Tree for the above graph using Prim’s Algorithm.

(b) Write Prim’s Algorithm.

Q.6(a) Write a recursive algorithm to implement Quick Sort.

(b) The input sequence to a Quick Sort’ algorithm which sorts in increasing order is
75, 73, 65, 82, 55, 90
Show the Sorting Process step-wise.