Test Papers / Previous Question Papers of Indira Gandhi National Open University CS62 'C' Programming and Data Structure December 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.

December, 2007

1. (a) Define an AVL tree. Construct a height balanced tree for the following list of elements : 4, 6, 12, 8 , 4, 2 , 15 , 7 , 3 (8)

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

(i) Delete a node in the list, given 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 defined then calculate the product.

Note : Show proper error handling also. (7)

(d) Calculate the time complexity of the following 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 different string-size. Arrange 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' starts 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 following given number: "5, 12, 38, 7, 3, 18, 68, 115" (4)

3. (a) Construct the binary tree using the following 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 following 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 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 a sparse matrix ? Which method represent its non-zero elements ? Also, write the algorithm corresponding to this method, explaining its steps.

5. Explain the following with an example of each : (10)

(a) Direct file organisation

(b) Depth first search

(d) Column major order

Testpapers of related examinations conducted by Indira Gandhi National Open University

The following is a partial list of Testpapers of similar / related courses to 'C' Programming and Data Structure offered by Indira Gandhi National Open University