IGNOU ‘C’ Programming and Data Structure Question Paper

CS-62 ‘C’ Programming and Data Structure
Time : 2 hours Maximum Marks : 60
Note: Question no.1 is compulsory. Answer any three questions from the rest.
All algorithms should be written nearer to ‘C’ Ianguage.
1. (a) Write an algorithm to subtract two polynomials using array
implementation. Assume polynomials have M and N terms. (8)

(b) What is garbage collection? Explain Fragmentation, Compaction
and Relocation w.r.t. garbage collection. (6)

(c) Write an algorithm to store the sparse array using linked list. (6)

(d) Write the functions in C language for insertion and deletion of a
node in a Heap. (8)

(e) Find the number of nodes in a balanced binary tree of height “h”.
2. (a) A two dimensional matrix is represented using a row major
order. Write the formula and calculate the address of element A
[10] [10]. Assume the dimensions A [10] [10] (3)

2(b) Write an algorithm for converting an Adjacency list to an
adjacency matrix in ‘C’ language. (7)

3. (a) Consider the graph :

Construct a minimum cost spanning tree using Prim’s algorithm and calculate the cost of this tree. (7)

(b) How are command line arguments passed on to ‘C’ programs?
Writ e a program to count the number of command line
arguments. (3)

4. (a) The following input sequence is sorted in increasing order using
quicksort algorithm:
75, 72, 64, 91, 56, 92, 62

Show the sorting process step-wise. (5)
(b) Write a non-recursive program in ‘C’ to traverse a binary tree in
preorder. (5)

5. Explain the following with an example each: (10)
(a) Union in ‘C’
(b) AVL Tree
(c) Hash function
(d) Weakly connected graph
(e) Indexing w.r.t files