Term-End Examination
June, 2OO7
CS-62 :'C' PROGRAMMING AND DATA STRUCTURE
Time : 2 hours Maximum Marks : 60
---------------------------------------------------------------
Note : Question no. 1 questions from written nearer is compulsory. Answer any three the rest. All algorithms should be to 'C' language.
----------------------------------------------------------------
l. (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(power 2)) 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 : (6)
5, 9, 12, 10, 6, 1, 20, 8, 4, 15
(b) Write a recursive function to calculate the 'gcd' of a number. (4)
4. (a) Consider the following graph :
Make the adjacency matrix for the given graph. Also, write an algorithm to compute the transpose of the matrix. (5)
(b) What is the difference between Sequential and Direct file organizations ? Under what conditions, if any, is it advantageous to have the file organized as a direct file rather than sequential file ? (5)
5. Explain the following with example : (10)
(a) Column-major order
(b) Structures vs Unions
(c) Complete binary tree
(d) m-way merging
(e) Spanning tree