Bharathidasan University 2006 B.Sc Computer Science 'C' PROGRAMMING - Question Paper

'C' PROGRAMMING
Time: two hours
Maximum Marks: 60

Note : ques. number one is compulsory. ans any 3 ques. from the rest. All algorithms should be written nearer to 'C' language.
December, 2007

1. (a) describe an AVL tree. Construct a height balanced tree for the subsequent list of elements : 4, 6, 12, eight , 4, two , 15 , seven , three (8)

(b) Write an algorithm to implement linked list using pointers and perform the subsequent tasks : (10)

(i) Delete a node in the list, provided a pointer to that node

(ii) Write a function to reverse the linked list.

(c) Write an algorithm that reads m x n matrix "A" and p x q matrix "B", checks whether these matrices are multipliable in either order or not. (e.g. whether A x B or BxA is defined). Further, if A x B or B x A is described then compute the product.

Note : Show proper fault handling also. (7)

(d) compute the time complexity of the subsequent code by using Big 'O' notation : (5)

1. Scanf ("%d," &n);
2. Scanf("%d", &m);
3. for (i=0; i<=m+n;i+=2)
4 . Printf("%d\ n", i-1);
5. for (j=m*n /I00; j<=mxn; j++)
6. Printf("%d\ n ", j);

2. (a) Write an algorithm, that accepts 12 words of various string-size. organize the words in descending order based on the sum of ASCII values of the characters in the string

e.g. : If string is "ABFD", its ASCII mapping is 65, 66, 70, 68 respectively and sum is 65 + 66 + 70 + 68 = 269

Hint: ASCII value of 'A' begins with 65, and 'a' startsw ith 97 . (6)

(b) Write an algorithm to implement bubble sort technique. Also, show the steps of bubble sort on the subsequent provided number: "5, 12, 38, 7, 3, 18, 68, 115" (4)

3. (a) Construct the binary tree using the subsequent preorder and inorder sequences:

Preorder: A B C E I F J D G H K L

Inorder: E I C F J B G D K H L A

Also, write the postorder sequence of it.

(b) Write algorithms to perform the subsequent operations in circular queue :

(i) Create a circular queue

(ii) Check whether a queue is empty

(iii) Insert an element in a queue

Consider the subsequent graph :

===DIAGRAM===

Make the adjacency matrix for the provided graph. Also, write an algorithm to calculate the transpose of the matrix

(b) What is a sparse matrix ? Which method represent its non-zero elements ? Also, write the algorithm corresponding to this method, explaining its steps.

5. discuss the subsequent with an example of every : (10)

(a) Direct file organisation

(b) Depth 1st search

(c) B-tree

(d) Column major order

Earning:   Approval pending.