7-1 File Transfer We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other? Input Specification: Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format: ...

7-1 Complete Binary Search Tree A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than or equal to the node’s key. Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST. ...

6-1 Percolate Up and Down Write the routines to do a “percolate up” and a “percolate down” in a binary min-heap. Format of functions: void PercolateUp( int p, PriorityQueue H ); void PercolateDown( int p, PriorityQueue H ); where int p is the position of the element, and PriorityQueue is defined as the following: typedef struct HeapStruct *PriorityQueue; struct HeapStruct { ElementType *Elements; int Capacity; int Size; }; Sample program of judge: #include <stdio.h> #include <stdlib.h> typedef int ElementType; #define MinData -1 typedef struct HeapStruct *PriorityQueue; struct HeapStruct { ElementType *Elements; int Capacity; int Size; }; PriorityQueue Initialize( int MaxElements ); /* details omitted */ void PercolateUp( int p, PriorityQueue H ); void PercolateDown( int p, PriorityQueue H ); void Insert( ElementType X, PriorityQueue H ) { int p = ++H->Size; H->Elements[p] = X; PercolateUp( p, H ); } ElementType DeleteMin( PriorityQueue H ) { ElementType MinElement; MinElement = H->Elements[1]; H->Elements[1] = H->Elements[H->Size--]; PercolateDown( 1, H ); return MinElement; } int main() { int n, i, op, X; PriorityQueue H; scanf("%d", &n); H = Initialize(n); for ( i=0; i<n; i++ ) { scanf("%d", &op); switch( op ) { case 1: scanf("%d", &X); Insert(X, H); break; case 0: printf("%d ", DeleteMin(H)); break; } } printf("\nInside H:"); for ( i=1; i<=H->Size; i++ ) printf(" %d", H->Elements[i]); return 0; } /* Your function will be put here */ Sample Input: 9 1 10 1 5 1 2 0 1 9 1 1 1 4 0 0 Sample Output: 2 1 4 Inside H: 5 10 9 Code #include <stdio.h> #include <stdlib.h> typedef int ElementType; #define MinData -1 typedef struct HeapStruct *PriorityQueue; struct HeapStruct { ElementType *Elements; int Capacity; int Size; }; PriorityQueue Initialize( int MaxElements ); /* details omitted */ void PercolateUp( int p, PriorityQueue H ); void PercolateDown( int p, PriorityQueue H ); void Insert( ElementType X, PriorityQueue H ) { int p = ++H->Size; H->Elements[p] = X; PercolateUp( p, H ); } ElementType DeleteMin( PriorityQueue H ) { ElementType MinElement; MinElement = H->Elements[1]; H->Elements[1] = H->Elements[H->Size--]; PercolateDown( 1, H ); return MinElement; } int main() { int n, i, op, X; PriorityQueue H; scanf("%d", &n); H = Initialize(n); for ( i=0; i<n; i++ ) { scanf("%d", &op); switch( op ) { case 1: scanf("%d", &X); Insert(X, H); break; case 0: printf("%d ", DeleteMin(H)); break; } } printf("\nInside H:"); for ( i=1; i<=H->Size; i++ ) printf(" %d", H->Elements[i]); return 0; } /* Your function will be put here */ void swap(int pos1, int pos2, PriorityQueue H){ ElementType tmp = H->Elements[pos1]; H->Elements[pos1] = H->Elements[pos2]; H->Elements[pos2] = tmp; } int min_idx(int idx1, int idx2, PriorityQueue H){ if(H->Elements[idx1] < H->Elements[idx2]) return idx1; return idx2; } void PercolateUp( int p, PriorityQueue H ){ int pos = p; while(pos>1){ int parent_idx = 1; int val = H->Elements[pos]; if(pos%2==0) parent_idx = pos/2; else parent_idx = (pos-1)/2; if(H->Elements[parent_idx]>val) swap(pos, parent_idx, H); else break; pos = parent_idx; } } void PercolateDown( int p, PriorityQueue H ){ int pos = p; while(pos*2 <= H->Size){ int val = H->Elements[pos]; int child_idx = H->Size; if(pos*2+1 <= H->Size) child_idx = min_idx(pos*2, pos*2+1, H); else child_idx = pos*2; if(H->Elements[child_idx] < val) swap(pos, child_idx, H); else break; pos = child_idx; } }

7-1 ZigZagging on a Tree Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15. ...

6-1 Isomorphic Two trees, T1 and T2, are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1. For instance, the two trees in Figure 1 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped. Give a polynomial time algorithm to decide if two trees are isomorphic. ...

7-1 Pop Sequence Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4. ...