CS-62 June 2002 Question Paper

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
June, 2002
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) If A = (3j, a2,……, an) and B = (bp b2,…., bm) are ordered lists and are represented by Arrays, then write an algorithm for the concatenation of the above ordered lists.

(b) Write an algorithm to transform an infix expression to a postfix expression.

(c) Write an algorithm to count the number of leaves in a tree.

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

(b) Write an algorithm to evaluate a prefix arithmetic expression.

Q.3(a) Write the postfix form of the following expressions :

(i)(c*d)x(a + b)
(ii) a + b x c -5- d

(b) Write an algorithm for the addition of two sparse matrices (use proper representation for sparse matrices).

Q.4(a) What is the relationship between the sum of the degrees of the vertices of a graph and the number of edges in the graph?

(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) Prove that if the edge weights on an undirected graph are distinct, there is only one minimum-cost spanning tree.

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

(b) The input sequence to a Bubble Sort algorithm which sorts in increasing order is : 6, 5, 39, 32, 11, 41
Show the sorting process stepwise.