CS-62: June, 2008 QUESTION PAPER

IGNOU BCA CS-62: 'C' PROGRAMMING & DATA STRUCTURE - JUNE 2008 QUESTION PAPER

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
June, 2008
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.

---

1. (a) What is sparse matrix ? Discuss methods of representation of sparse matrix in memory. Explain row-major and column-major order with example. (9)
(b) What is a binary search tree? Write an algorithm to find an element in a binary search tree. (5)
(c) Define a circular queue. What is the- condition that a circular queue is full (if queue is implemented using array)? Write an algorithm for inserting a node at given location in a circular queue. (8)
(d) Differentiate between internal and external sorting. Which sorting algorithm is preferred for external sorting? Write an algorithm for K-way merge sort. (2+7+5=8)

2. (a) Write a program in C for binary search tree. (5)
(b) Apply Binary search for elements in array P to find the element 40, 11, 22, 30, 33, 40, 44, 55, 60, 66, 77,808, 8, 99. (3)
(c) What are the various disadvantages of sequential file organisation? (2)

3. (a) Convert the following postfix expression into infix using stack: (3)
A B C * D E F ↑ / G * - H * +
(b) What is AVL tree? Construct an AVL search tree by inserting the following elements in order of their occurrence. (Show each of the rotations). (2+5=7)
64, l, 44, 26, 13, 110, 98, 85

4. Write short notes on the following: (5x2=1O)
(i) Directed graph
(ii) Compaction
(iii) Complete binary tree
(iv) Hash function
(v) Height balanced tree

5. (a) Write a program in C for bubble sort. (5)
(b) Explain indexed-sequential file organisation. Under what conditions is it advantageous to have file organised as indexed-sequential rather than direct file. (5)