APPLICATIONS
Term-End Examination
June, 2006
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' Language.
----------------------------------------------------------------------------------------------------------------------
1. (a) Write a C function to convert the adjacency matrix (7)
of a graph to its adjacency list. Illustrate this C function, using an example.
(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 (10)
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 :
7 , 4 , 7 , g , 0 , 2 , 8 , 5
(d) How is a circular queue better than a linear queue ? (3)
Explain this with an example.
2. (a) Define an AVL Tree. Construct a Height Balanced (7)
Tree for the following list of elements :
3 , 5 , 1 1 , 9 , 4 , 2 , 7 5 , 7 , 2 , 6 , 10
(b) Write a recursive function to generate the Fibonacci (3)
series.
3. (a) Explain any three advantages of a singly linked list (3)
over arrays.
(b) Consider the graph :
Construct a minimum cost spanning tree for the graph above. Also give the cost of this tree.
4. Suppose there is a singly linked list of integers. The linked (10)
list is implemented by pointers in 'C'. Write 'C' functions
for the following :
(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