  Preparing for Exams BCA & MCA (CS-17 & CS-76) FINAL YEAR PROJECTS TMA & PROJECTS Preparing A Synopsis

## 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 Learn Visual Basic Interactive Educational CDs TMA & PROJECTS Preparing A Synopsis

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