CS-62 December, 2005 QUESTION PAPER

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 2005
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.

---

1. (a) Write a non recursive function to traverse a binary tree using inorder traversal. (Marks 10)

(b) What is sparse array ? Write an algorithm to represent a sparse array using a linked list. Using the data structure created above, write an algorithm for finding the transpose of the sparse array. (Mark10)

(c) Write an algorithm for the implementation of a 2-way merge sort. What is its time complexity ? Sort the following sequence of numbers using 2-way merge sort : (Mark10)
7, 4, 1, 3, 0, 2, 6, 5

2. (a) A 3-dimensional integer array X [4] [5] [3] is stored using the column major order. What will the address of X [2] [3] [1] be it the base address is 100 ? Also, calculate the address if the array is stored using row major order. (Mark5)

(b) Write an algorithm for creation of a doubly linked list. Also, write an algorithm for deletion of elements from a doubly linked list. (Mark5)

3. (a) Define the following :
(i) Syntax for a typedef statement
(ii) Digraphs
(iii) Adjacency Matrix
(ivl Garbage Collection
(v) Height balanced tree

(b) Write an algorithm to evaluate the postfix expression. Draw the expression tree for the following postfix expresslon : (Mark5)
a b + c* d e / f * - g h * +

4. (a) Consider the following graph :
-----DIAGRAM NOT AVAILABLE-----
Construct a minimum cost spanning tree. Also, give the minimum cost. (Mark5)

(b) Using Quick sort, sort the following sequence in descending order :
25, 12, 9, 30, 15, 50
What is the average run time complexity of Quick sort ? (Mark5)

5. (a) Write a function which accepts a stack as input and reverses the elements of the stack using one additional queue. (Mark5)

(b) Write an algorithm to list the nodes of a Binary tree in the following way :
List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. (Mark5)