IGNOU ‘C’ & 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. AII algorithms should be written nearer to ‘C’ Ianguage.

1. (a) Write a C function to convert the adjacency matrix of a graph to its
adjacency list. Illustrate this C function, using an example. (7)

(b) Explain the concept of representation of a graph. Write an algorithm for
graph traversal using Breadth First Search, with a suitable example.
Also, determine its space and time complexity. (10)

(c) Write an algorithm for the implementation of insertion sort. Compute the
time complexity of insertion sort in accordance to worst; best and average
case. Sort the following sequence of numbers by applying insertion sort(10)
7 , 4 , 7 ,g , 0 , 2 , 8 , 5

(d) How is a circular queue better than a linear queue? Explain this with an
example. (3)

2(a) Define an AVL Tree. Construct a Height Balanced Tree for the following
list of elements (7)
3 , 5 , 11 , 9 , 4 , 2 , 15 , 7 , 2 , 6 , 10

(b) Write a recursive function to generate the fibonacci series. (3)

3. (a) Explain any three advantages of a singly linked list over arrays. (3)

(b) Consider the graph:

Construct a minimum cost spanning tree for the graph above. Also give the
cost of this tree. (7)

4. Suppose there is a singly linked list of integers. The linked list is
implemented by pointers in ,’C’. Write ‘C’ functions for the following: (10)
(i) Delete a node in the list, given a pointer to that node.
(ii) Reverse the list.

5. Explain the following with an example each (10)
(i) Dynamic Memory Allocation
(ii) Sparse Array
(iii) Pre-order Traversal
(iv) Indexed Sequential File Organization
(v) Macros