CS04 : DATA STRUCTURE THROUGH “C” & “PASCAL”
June 2003
1(a) Write an algorithm for the creation of Queue using two stacks together
with function/procedures for the Enqueue and Dequeue operations.
(b) Write an algorithm which translates a postfix expression to a prefix
expression. What is the time complexity of the algorithm?
(c) A full node in a Binary Tree is a node with two nonempty subtrees.
Let ‘I’ be the number of leaf nodes in a Binaray Tree. Show that the number
of full nodes is I  1.
2(a) Write an algorithm that visits the nodes of a tree in the reverse
order of their levels in the tree. Trace the algorithm with sample data
set.
(b) The order of nodes of a Binary Tree in Preorder and Inorder Traversal
are as under:
Inorder Traversal : B C E D F A G H
Preorder Traversal : A B C D E F G H
Draw the corresponding Binary Tree.
3 (a) Write an algorithm to compute the height of a givenBinary Tree.
(b) Write an alogrithm to count the number of nodes in a Binary Tree.
4 (a) Consider the graph of the following figure:
Perform a BreadthFirst Search beginning at vertex V2. List the vertices
in the order in which they are visited.
(b) Prove that an undirected graph with ‘n’ vertices contains at most
edges.
5 Consider an arbitrary sequence {S1, S2, .... Sn}. To sort the sequence,
we determine the permutation [P1, P2, P3, .... Pn] such that Prove that
Bubble sort requires atleast ‘P’ passes where
P = max (i  Pi).1 i n
6 Write short notes on the following :
 Hash Table
 Garbage Collection and Compaction
