CS-62 Dec 2002 Question Paper

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 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) Ackermann’s function A (m, n) is defined as follows:

n + 1 ,ifm = 0
A (m,n)= A (m-1, 1) ,ifn = 0
A (m-1, A (m,n-1)) , otherwise.

Write a recursive algorithm for computing this function.

(b) Let *P* be a pointer to a doubly 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 “Postorder".

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

(b) Devise a scheme using a stack to convert an infix expression to a postfix expression.

Q.3(a) Write the postfix form of the following expressions:
(i) a + b x (C -j- d)

(b) Write an algorithm for multiplication of two matrices.

Q.4(a) Devise an algorithm to count the number of connected components in a directed graph.

(b) Write Prim’s Algorithm.

Q.5(a) Consider the following graph;

(b) Write Kruskal’s Algorithm.