CS-62 DEC 2004 QUESTION PAPER

IGNOU BCA CS-62: 'C' PROGRAMMING & DATA STRUCTURE - DECEMBER 2004 QUESTION PAPER

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 2004
CS-62: 'C' PROGRAMMING & DATA STRUCTURE

Time : 2 Hours

Max. Marks : 60

---

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

---

Q.1(a) Represent a polynomial using a circularly inked list. Write an algorithm to subtract two polynomials using the representation above. What is the time complexity of your algorithm to subtract two polynomials using the representation above. What is the time complexity of your algorithm ?

(b) A file stores a series of numbers. Write an algorithm using binary search tree that counts the occurrence of different numbers in the file. For example, file containing data 1, 50, 20, 1, 25 would produce output as
Number Occurrence
1 2
20 1
25 1
50 1

(c) Write an algorithm to sort a sequence of number of numbers in increasing order using bubble sort. What is the time complexity of this algorithm ?

(d) What are the various applications of stacks and queues ? Give at least two applications of each.

Q.2(a) What is a graph ? How can it be represented in a C program? Describe two important applications of graphs.

(b) Write an algorithm to delete a node from a doubly linked list. Show the process with the help of a diagram.

Q.3(a) How can a queue by represented using an array and a linked list ? Compare the two represented in terms of time and space complexities.

(b) Write an algorithm construct a binary tree from the given in order as well as preorder traversal.

Q.4(a) Differentiate between the following with an example
(i) Arrays vs Pointers
(ii) Sequential file organization vs Direct file organization

(b) Write an algorithm to implement a Queue that allows insertion and deletion at both ends.

Q.5 (a) Consider the graph :

(b) Write an algorithm for sorting a sequence of numbers using any merge sort technique.

Q.6(a) Write ab algorithm to find the first occurrence of the substring of the form ‘aab’ in an input string.

(b) Define the following terms :
(i) Height balanced tree
(ii) Post-order traversal
(iii) Column major order