Test Papers / Previous Question Papers of IGNOU CS62 'C' Programming and Data Structure December 2005

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination

December, 2005

CS60 : 'C' PROGRAMMING AND DATA STRUCTURE

Time: 2 hours
Maximum Marks: 60

1. (a) Write a non recursive function to traverse a binary tree using inorder traversal. (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. (10)

(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 : (10)
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. (5)

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

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 : (5)
a b + c* d e / f * - g h * +

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

(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 ? (5)

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

(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. (5)