2010香港特别行政区java版本高级

1、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。2、将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。intBPGraph(AdjMatrixg)//判断以邻接矩阵表示的图g是否是二部图。{ints[];//顶点向量，元素值表示其属于那个集合〔值1和2表示两个集合〕intQ[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。intf=0,r,visited[];//f和r分别是队列的头尾指针,visited[]是访问数组for(i=1;i<=n;i++){visited[i]=0;s[i]=0;}//初始化，各顶点未确定属于那个集合Q[1]=1;r=1;s[1]=1;//顶点1放入集合S1while(f<r){v=Q[++f];if(s[v]==1)jh=2;elsejh=1;//准备v的邻接点的集合号if(!visited[v]){visited[v]=1;//确保对每一个顶点，都要检查与其邻接点不应在一个集合中for(j=1,j<=n;j++)if(g[v][j]==1){if(!s[j]){s[j]=jh;Q[++r]=j;}//邻接点入队列elseif(s[j]==s[v])return(0);}//非二部图}//if(!visited[v])}//whilereturn(1);}//是二部图[算法讨论]题目给的是连通无向图，假设非连通，则算法要修改。3、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;if(argc<3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE*restore(char*ppos,char*ipos,intn){TNODE*ptr；char*rpos;intk;if(n<=0)returnNULL;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);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}4、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。5、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，则将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。voidSpnTree(AdjListg)//用“破圈法”求解带权连通无向图的一棵最小代价生成树。{typedefstruct{inti,j,w}node;//设顶点信息就是顶点编号，权是整型数nodeedge[];scanf("%d%d",&e,&n);//输入边数和顶点数。for(i=1;i<=e;i++)//输入e条边：顶点，权值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按边上的权值大小，对边进行逆序排序。{edge[0]=edge[i];j=i-1;while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;eg=e;while(eg>=n)//破圈，直到边数e=n-1.{if(connect(k))//删除第k条边假设仍连通。{edge[k].w=0;eg--;}//测试下一条边edge[k]，权值置0表示该边被删除k++;//下条边}//while}//算法结束。connect()是测试图是否连通的函数，可用图的遍历实现，6、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，则将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。voidSpnTree(AdjListg)//用“破圈法”求解带权连通无向图的一棵最小代价生成树。{typedefstruct{inti,j,w}node;//设顶点信息就是顶点编号，权是整型数nodeedge[];scanf("%d%d",&e,&n);//输入边数和顶点数。for(i=1;i<=e;i++)//输入e条边：顶点，权值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按边上的权值大小，对边进行逆序排序。{edge[0]=edge[i];j=i-1;while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;eg=e;while(eg>=n)//破圈，直到边数e=n-1.{if(connect(k))//删除第k条边假设仍连通。{edge[k].w=0;eg--;}//测试下一条边edge[k]，权值置0表示该边被删除k++;//下条边}//while}//算法结束。connect()是测试图是否连通的函数，可用图的遍历实现，7、设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况〔入栈满等〕给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择假设干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在以下算法的下划线处填空，使其正确求解背包问题。Knap(S，n)假设S=0则Knap←true否则假设〔S<0〕或(S>0且n<1)则Knap←false否则假设Knap(1),_=true则print(W[n])；Knap←true否则Knap←Knap(2)_,_设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如：设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效〔时间、空间〕的算法，将R中保存的序列循环左移p〔0<p<n〕个位置，即将R中的数据〔x0,x1,x2,…,xn-1〕，变换为(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。8、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时假设有元素移动，则与之相应的行中各元素也必须做相应变动。voidTranslation〔float*matrix，intn〕//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。{inti,j,k,l；floatsum，min；//sum暂存各行元素之和float*p,*pi,*pk;for(i=0;i<n;i++){sum=0.0;pk=matrix+i*n;//pk指向矩阵各行第1个元素.for(j=0;j<n;j++){sum+=*(pk);pk++;}//求一行元素之和.*(p+i)=sum;//将一行元素之和存入一维数组.}//forifor(i=0;i<n-1;i++)//用选择法对数组p进行排序{min=*(p+i);k=i;//初始设第i行元素之和最小.for(j=i+1;j<n;j++)if(p[j]<min){k=j;min=p[j];}//记新的最小值及行号.if(i!=k)//假设最小行不是当前行,要进行交换(行元素及行元素之和){pk=matrix+n*k;//pk指向第k行第1个元素.pi=matrix+n*i;//pi指向第i行第1个元素.for(j=0;j<n;j++)//交换两行中对应元素.{sum=*(pk+j);*(pk+j)=*(pi+j);*(pi+j)=sum;}sum=p[i];p[i]=p[k];p[k]=sum;//交换一维数组中元素之和.}//if}//forifree(p);//释放p数组.}//Translation[算法分析]算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.假设用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).9、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。假设查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。10、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。此题要找p和q的最近共同祖先结点r,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配〔即相等〕的元素就是结点p和q的最近公共祖先。typedefstruct{BiTreet;inttag;//tag=0表示结点的左子女已被访问，tag=1表示结点的右子女已被访问}stack;stacks[],s1[];//栈，容量够大BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。{top=0;bt=ROOT;while(bt!=null||top>0){while(bt!=null&&bt!=p&&bt!=q)//结点入栈{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下if(bt==p)//不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点{for(i=1;i<=top;i++)s1[i]=s[i];top1=top;}//将栈s的元素转入辅助栈s1保存if(bt==q)//找到q结点。for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配{pp=s[i].t;for(j=top1;j>0;j--)if(s1[j].t==pp){printf(“p和q的最近共同的祖先已找到”)；return(pp);}｝while(top!=0&&s[top].tag==1)top--;//退栈if(top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝//沿右分枝向下遍历}//结束while(bt!=null||top>0)return(null);//ｑ、p无公共祖先｝//结束Ancestor11、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。〔15分〕〔1〕下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO〔2〕通过对〔1〕的分析，写出一个算法，判定所给的操作序列是否合法。假设合法，返回true，否则返回false〔假定被判定的操作序列已存入一维数组中〕。12、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;if(argc<3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE*restore(char*ppos,char*ipos,intn){TNODE*ptr；char*rpos;intk;if(n<=0)returnNULL;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);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}13、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列〔即任一遍历序列均可确定一棵二叉树〕。voidPreToPost(ElemTypepre[],post[],intl1,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)//将右子树先序序列转为后序序列}}//PreToPost32..叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedListhead,pre=null;//全局变量LinkedListInOrder(BiTreebt)//中序遍历二叉树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)14、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。voidLongestPath(BiTreebt)//求二叉树中的第一条最长路径长度{BiTreep=bt,l[],s[];//l,s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点inti，top=0,tag[],longest=0;while(p||top>0){while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if(tag[top]==1)//当前结点的右分枝已遍历{if(!s[top]->Lc&&!s[top]->Rc)//只有到叶子结点时，才查看路径长度if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;