CS-04 : 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 non-empty 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 Breadth-First 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

Next Paper

UNIVERSAL TEACHER PUBLICATIONS
Web: www.universalteacherpublications.com, www.universalteacher.com