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
UNIVERSAL TEACHER PUBLICATIONS
Web: universalteacherpublications.com,
universalteacher.com,
universalteacher4u.com