CS-62: 'C' PROGRAMMING & DATA STRUCTURE PAPER

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
June, 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.l(a) What is the Time and Space complexity of an algorithm? For the binary search algorithm, derive the best, average and worst case time complexities for its execution.

(b) What are Row major and Column major representations of arrays? For a character array defined as AJ2O] [20], if A|0] |0| is located at memory address 100, where is element A[10J [1] located in Column major representation and in Row major representation.
(c) Write an algorithm that takes a pointer to the root of a binary tree T and another variable which indicates whether preorder, postorder or inorder traversal of the tree is required. Depending on this variable, the function should print the tree in either preorder, poster or inorder.

Q.2(a) What is a Circular Queue? Give an example of its application. Give an algorithm for the addition of a new element to the circular queue. Include necessary validation checks.

(b) Prove that a binary tree with N internal nodes has N+l external nodes. Preferably, use mathematical induction for this.

Q.3(a) The following are the inorder and preorder traversal of a Binary Tree.
Inorder: NTCGOISU
Preorder: IGNCTOUS
Construct the Binary Tree.

(b) Define the following:
(i) Tree

(ii) Strongly Connected Graph

(iii) Adjacency Matrix

(iv) Binary Tree

(v) Directed Graph

Q.4(a) Write an algorithm for creation of a Singly Linked List. Also write algorithms for insertion and deletion of elements from the Singly Linked List.

(b) Write an algorithm to list the nodes of a Binary Tree in the following way:
List the root, then nodes at depth 1, followed by m nodes at depth 2, and so on.
You algorithm should have linear time complexity.

Q.5(a) Consider the following graph:

Construct a minimum cost spanning tree. Give the cost.

(b) Write an algorithm to convert a decimal number to binary number using stacks(s).

Q.6(a) Using Heapsort, sort the following in Ascending order:
17,12,29,33,2,15,8
Show all the steps involved.

(b) Write an algorithm for 2-way merge sort. Give an application of it also.