CS-62 DEC 2006 QUESTION PAPER

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 2006
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) Show how the arraywould appear in memory when stored in
(i) Row major order
(ii) Column major order
(iii) Logical representation (10)

(b) What is a Binary Search Tree (BST) ? Write algorithms for inserting and deleting nodes in a
BST. Explain them with the help of an example each. (10)

(c) Assume A is a N x N square matrix . Write the algorithm for the following operations in the matrix A. (10)
(i) Find the product of the diagonal elements of A.
(ii) Find the sum of the elements above the diagonal elements.

2- (a) Construct a Height Balanced Tree for the following list of elements : (5)
2, 6, 13, g, 4, 3, 18 7 , 1, 8, 11
(b) Write an algorithm to convert an infix expression to a postfix expression. Also, explain the logic with the help of an example. (Use stack implementation) (5)

3 (a) Write and explain the hash function method, “Division - Remainder Hashing”. Also explain
where this can be used.(5)

(b) For the digraph shown below find (5)
(i) the indegree and outdegree of each vertex
(ii) its adjacency matrix representation
(iii) its adjacency list representation
(iv) its strongly connected component
4. (a) Write an algorithm to construct a doubly linked List and search for a data. (5)
(b) Write an algorithm for addition and deletion of an element into a queue. (5)

5. Define the following and give an example for each : (10)
(i) UNION in C language
(ii) Circular linked list
(iii) Post order traversal of a binary tree
(iv) Insertion sort
(v) K-way merging