CS-62 'C' PROGRAMMING & DATA STRUCTURE PAPER

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

---

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
June, 2001
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) Write a program EXPR in C language which evaluates a Reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,

EXPR 2 3 4 + *
evaluates 2 x (3 + 4).
For example:

(b) Give the node structure for implementing a linked list containing two information fields viz. info 1, info 2. Let p be the pointer to the first node of the linked list. Traverse the linked list to go to the node containing the information info 1 = u and>Hen print the info 1 and info 2 fields.

(c) Define binary search tree. Write a function in *C* to create a binary search tree.

Q.2(a) The order of nodes of a Binary Tree in Preorder and Inorder Traversal are as follows :
Preorder ; A B C D F H J M K E G I L N
Inorder : A D J M H K F C I N L G E B
Draw the corresponding Binary Tree.

(b) List the differences between a Singly Linked Circular List and Doubly Linked Circular List. List the advantages of each list.

Q.3(a) Draw the tree representation for the following prefix expression :
+*/A**BCDE

(b) Write a non-recursive program in ‘C language to traverse a binary tree in preorder.

Q.4(a) Consider the following diagraph :

Write an algorithm which accepts an adjacency matrix as input and prints the corresponding graph as output.

(b) Write the advantages of arrays over linked list and advantages of linked list over arrays.

Q5. Discuss the differences between the following file organization techniques :
1. Sequential File Organization
2. Index Sequential File Organization
3. Direct File Organization

To what type of applications are each of the above techniques suited?

Q.6(a) Write an Algorithm to implement Two Way Merge Sort. Discuss its efficiency.

(b) The input sequence to a Quick Sort Algorithm which sorts in increasing order is: 11, 2, 23, 14, 15, 66, 22
Show the sorting process stepwise.