1、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。 #define MAX 100 typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv) { TNODE *root; if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }
TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______;
for((2)_______ ; rpos ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } 2、假设K1，?，Kn是n个关键词，试解答： 试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，?，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。 3、约瑟夫环问题（Josephus问题）是指编号为1、2、?，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，?，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。 #include typedef listnode *linklist; void jose(linklist head,int s,int m) {linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1为报数的起点*/ while (count!=s) /*找初始报数起点*/ {pre=k1; k1=k1->next; count++; } while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/ { p=k1; /*从k1开始报数*/ count=1; while (count!=m) /*连续数m个结点*/ { pre=p; p=p->next; count++; } pre->next=p->next; /*输出该结点，并删除该结点*/ printf(\ free(p); k1=pre->next; /*新的报数起点*/ } printf(\输出最后一个结点*/ free(k1); } main() {linklist head,p,r; int n,s,m,i; printf(\ scanf(\ printf(\ scanf(\ printf(\ scanf(\ if (n<1) printf(\ else {/*建表*/ head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n; r=head; for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/ { p=(linklist)malloc(sizeof(listnode)); p->data=i; p->next=head; head=p; } r->next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ } } 4、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分） （1）A和D是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A中。 int Judge(char A[]) //判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。 j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j++; break; //入栈次数增1。 case‘O’: k++; if(k>j){printf(“序列非法\\n”)；exit(0);} } i++; //不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k) {printf(“序列非法\\n”)；return(false);} else {printf(“序列合法\\n”)；return(true);} }//算法结束。 5、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立，现证明当n=m时结论成立。 设中序序列为S1，S2，?，Sm,后序序列是P1,P2,?，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，?，Si-1是左子树的中序序列，而Si+1,Si+2,?,Sm是右子树的中序序列。 若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，?，Sm}和{P1，P2，?，Pm-1}可以唯一确定右子树，从而也确定了二叉树。 若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，?，Sm-1}和{P1，P2，?，Pm-1}唯一确定左子树，从而也确定了二叉树。 最后，当1 6、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7 7、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7 8、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。 void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2) //将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1) {post[h2]=pre[l1]; //根结点 half=(h1-l1)/2; //左或右子树的结点数 PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost 32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt) //中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树 if(bt->lchild==null && bt->rchild==null) //叶子结点 if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 } return(head); } //InOrder 时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n) 9、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。