2012云南省JAVA版本入门

if（pre==null）pre=t；// 中序遍历的第一个结点不必判断 else if（pre->data<t->data）pre=t；//前驱指针指向当前结点 else{flag=flase；} //不是完全二叉树 Judgebst （t->rldgeBST 算法结束
1、 设 t 是给定的一棵二叉树， 下面的递归程序 count(t)用于求得:二叉树 t 中具有非空的左, 右两个儿子的结点个数 N2;只有非空左儿子的个数 NL;只有非空右儿子的结点个数 NR 和叶子 结点个数 N0。N2、NL、NR、N0 都是全局量，且在调用 count(t)之前都置为 0. typedef struct node {int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t) {if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ; if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; } 26.树的先序非递归算法。 void example(b) btree *b; { btree *stack[20], *p； int top; if (b!=null) { top=1; stack[top]=b; while (top>0) { p=stack[top]; top--; printf(“%d”,p->data); if (p->rchild!=null) {(1)___; (2)___; } if (p->lchild!=null) (3)___; (4)__; }}}} 2、矩阵中元素按行和按列都已排序，要求查找时间复杂度为 O（m+n） ，因此不能采用常规的 二层循环的查找。 可以先从右上角 （i=a,j=d） 元素与 x 比较， 只有三种情况： 一是 A[i,j]>x， 这情况下向 j 小的方向继续查找； 二是 A[i,j]<x， 下步应向 i 大的方向查找； 三是 A[i,j]=x， 查找成功。否则，若下标已超出范围，则查找失败。 void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m 矩阵 A,行下标从 a 到 b,列下标从 c 到 d,本算法查找 x 是否在矩阵 A 中. {i=a; j=d; flag=0; //flag 是成功查到 x 的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} else if (A[i][j]>x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定 x 为整型. else printf(“矩阵 A 中无%d 元素” ，x)； }算法 search 结束。 [算法讨论]算法中查找 x 的路线从右上角开始， 向下 （当 x>A[i,j]） 或向左 （当 x<A[i,j]） 。 向下最多是 m， 向左最多是 n。 最佳情况是在右上角比较一次成功， 最差是在左下角 （A[b,c]） ， 比较 m+n 次，故算法最差时间复杂度是 O(m+n） 。
7、 我们可用 “破圈法” 求解带权连通无向图的一棵最小代价生成树。 所谓 “破圈法” 就是 “任 取一圈，去掉圈上权最大的边” ，反复执行这一步骤，直到没有圈为止。请给出用“破圈法” 求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算 法。注：圈就是回路。 8、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用 llink-rlink 法存储。 9、约瑟夫环问题（Josephus 问题）是指编号为 1、2、„，n 的 n（n>0）个人按顺时针方向 围坐成一圈，现从第 s 个人开始按顺时针方向报数，数到第 m 个人出列，然后从出列的下一 个人重新开始报数，数到第 m 的人又出列，„，如此重复直到所有的人全部出列为止。现要 求采用循环链表结构设计一个算法，模拟此过程。 #include<stdlib.h> typedef int datatype; typedef struct node {datatype data; struct node *next; }listnode; 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("%4d",p->data); free(p);
3、#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top 为栈顶指针，定义 top=0 时为栈空。 for(i=1; i<=n; i++) //n 个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1 时入栈。 if(top==maxsize-1){printf(“栈满\n”);exit(0);} else s[++top]=x; //x 入栈。 else //读入的整数等于-1 时退栈。 {if(top==0){printf(“栈空\n”);exit(0);} else printf(“出栈元素是%d\n”,s[top--])；} } }//算法结 4、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用 递归算法。 int Similar(BiTree p,q) //判断二叉树 p 和 q 是否相似 {if(p==null && q==null) return (1); else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束 Similar 5 、 (1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild) 25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild) 26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild 27. (1)*ppos // 根结点 （2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1 6、 根据二叉排序树中序遍历所得结点值为增序的性质， 在遍历中将当前遍历结点与其前驱结 点值比较，即可得出结论，为此设全局指针变量 pre（初值为 null）和全局变量 flag，初值 为 true。若非二叉排序树，则置 flag 为 false。 #define true 1 #define false 0 typedef struct node {datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag） // 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由 flag 得出结论。 { if（t!=null && flag） { Judgebst（t->llink,flag） ；// 中序遍历左子树
} 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<ipos+n;rpos++) if(*rpos==*ppos) break; k=(3)_______; 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); } 11、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表， 表头指针为 head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链 表指针。分析你的算法的时、空复杂度。