APPLICATIONS
Term-End Examination
June, 2OO6
CS-62 (s) : C PROGRAMMING AND DATA STRUCTURE
Time : 2 hours Maximum Marks : 60
Note ; Question no. 1 is compulsory. Answer any three questions From the rest.
All algorithms should be
written nearer to 'C' language.
l. (a) Write a non-recursive function to traverse a tree in postorder. Apply the function on the following tree. (10)
(b) How is a graph represented by an adjacency (5)
matrix ? Write any two drawbacks of such a
representation.
(c) Give any two differences between binary search and linear search. Also, write
a function to implement the binary search algorithm. Show the output of the
algorithm using an example. (10)
(d) Write five differences between Sequential file organisation and Direct file organisation. (5)
2. (a) Write an algorithm to evaluate a Postfix expression by using a stack. (7)
Illustrate the working of this algorithm with a suitable example.
(b) Compare the Best and Worst case complexities of Merge Sort, Quick Sort and
the Bubble Sort algorithms. (3)
3. (a) Write a program in C to sort a single linked list. Also convert the (7)
sorted.linked list into a circular linked list.
(b) Define the following terms : (3)
(i) Spanning tree
(ii) Weakly connected graph
(iii) B-Tree
4. (a) Define a circular queue. Write an algorithm to implement the insertion and
deletion operations in a circular queue. (7)
(b)Give any two differences between 'Call by value' and 'Call by reference'
methods. Also, give an example for each method. (3)
5. Explain the following, with an example of each . (10)
(i) L value
(ii) Heap
(iii) Height-balanced-tree
(iv) Garbage collection
(v) Row major order