Indira Gandhi National Open University Test Papers - CS62 'C' Programming and Data Structure - June 2007

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination

CS60: 'C' PROGRAMMING AND DATA STRUCTURE

Time: 2 hours
Maximum Marks: 60

Note : Question number 1 is compulsory. Answer any three questions from the rest. All algorithms should be written nearer to 'C' language.

June, 2007

1. (a) Write a 'C' function to compute the total number of nodes in a binary tree. (6)

(b) Write an algorithm to sort 'N' numbers using Bubble sort. Also, show that bubble sort algorithm, on average, makes O(N²) comparisons while sorting a list of N elements. (7)

(c) What is indexed sequential file organisation? Name the data structure which is most appropriate for this file organisation. Justify the answer. (6)

(d) Write a program in 'C' language that counts total number of characters, words, white-spaces and lines in a given text file. (8)

(e) Construct a binary tree from the following preorder and inorder traversal sequence :

Preorder: ABCDEF

Inorder: CBAEDF

2. Write a 'C' language that sorts a given linked list of integers. Also, write a function that splits this linked list into a linked list of even integers and a linked list of odd integers. 10

3. (a) What is a height-balanced tree ? Construct an AVL tree for the following elements : 5, 9, 12, 10, 6, 1, 20, 8, 4, 15 (6)

(b) Write a recursive function to calculate the 'gcd' of a number. (4)

4. (a) Consider the following graph :

=== DIAGRAM ===

Make the adjacency matrix for the given graph. Also, write an algorithm to compute the transpose of the matrix.

(b) What is the difference between Sequential and Direct file organisations ? Under what conditions, if any, is it advantageous to have the file or ganized as a direct file rather than sequential file ?

5. Explain the following with example :

(a) Column-major order

(b) Structures vs Unions

(d) m-way merging

(e) Spanning tree

Test Papers / Previous Question Papers of Indira Gandhi National Open University CS62 'C' Programming and Data Structure June 2007

CS60: 'C' PROGRAMMING AND DATA STRUCTURE