Question Paper -Data Structures through "C" and "PASCAL"

1. (a) Write an algorithm to multiply two polynomials using linked list.

(b) Let T be a binary tree with height h and n nodes. Show that log(n + 1)- 1 < = h < = (n - 1)/2. For which values of n and h can the above lowest upper bounds of h be attained equality.

(c) Write an algorithm to implement the bubble sort and sort the following list in ascending order using bubble sort :
13, 24, 5, 19, 2, 17, 4

(d) List any three disadvantages of sequential file organization.

(e) Write an algorithm to insert a node before a given node in a linked list.

2. (a) Write an algorithm to convert the following infix expression to the postfix expression and illustrate the position of stack after each step :
z + (y*x-(w/v ? u)*t)*s

(b) Write a recursive algorithm for two way merge sort.



3.Write an algorithm for insertion and deletion of elements in a Queue.

4. (a) Write an algorithm for the breadth first traversal of a graph.

(b) Write an algorithm to insert a node into a Binary Search Tree.

5. (a) What is Direct File organization ? Explain any two advantages of Direct File organization over Sequential File organization.

(b) Write an algorithm for performing Binary Search. What is the condition to perform Binary Search ?