CS-62 December 2001 QUESTION PAPER

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 2001
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.I (a) A general polynomial A(x) can be written as
ax’ + a .x"-1 +…..+ a,x + a.
where an*0 and we say that the degree of A is ‘n Each ax1 is a term of the polynomial. If a. - 0, then it is a zero term, otherwise, it is a nonzero term. Now, write an algorithm which evaluates a polynomial at a value ‘x0′

(b) Let (P’ be a pointer to a circularly linked list Show how this list may be used as a queue by writing algorithms to add and delete elements. Specify the value for *P’ when the queue is empty.

(c) Write a non-recursive procedure for traversing a Binary Tree in “Preorder".

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

(b) Write an algorithm to construct the binary tree with a given preorder and inorder sequence.

Q.3(a) Write the postfix form of the following expressions
(i) -A + B - C + D
(ii) A**B**C

(b) Write an algorithm for generating the transpose of a given sparse matrix.

Q.4(a) Prove that the number of edges in an n-vertex complete graph is n(n-l)/2.

(b) Write Kruskal’s Algorithm.

Q.5(a) Consider the following graph :

Find the minimum cost spanning tree for the above graph using Prim’s Algorithm.

(b) Write a program to determine whether a directed graph of ‘n’ vertices has a cycle.

Q.6(a) Write an algorithm to implement insertion sort.

(b) The input sequence to a Quick Sort Algorithm which sorts in decreasing order is : 4,5,25,23, 11, 15, 16, 18
Show the sorting process stepwise.