作业参考答案一、（带头结点）多项式乘法C=A×B：voidPolyAdd(list&C,listR)//R为单个结点{p=C;while((！p->next)&&(p->next->exp>R->exp))p=p->next;if((p->next)||(p->next->expexp)){R->next=p->next;p->next=R;}else{p->next->inf+=R->inf;deleteR;if(!p->next->inf){R=p->next;p->next=R->next;deleteR;}}}voidPolyMul(listA,listB,list&C){C=newstructnode;C->next=NULL;q=B->next;While(q){p=A->next;while(p){r=newstructnode;r->exp=p->exp+q->exp;r->inf=p->inf*q->inf;PolyAdd(C,r);p=p->next;}q=q->next;}}二、梵塔的移动次数：已知移动次数迭代公式为：M(n)=2M(n-1)+1初值为：M(0)=0则：M(n)=2(2M(n-2)+1)+1=4M(n-2)+3=8M(n-3)+7=2iM(n-i)+2i–1若n=i,则M(n-n)=0,故：M(n)=2nM(n-n)+2n–11=2n–1所以，梵塔的移动次数为2n–1次。三、简化的背包问题：voidPack(intm,inti,intt)//初始值为:11t{for(k=i;k<=n;k++){solution[m]=weight[k];if(t==weight[k]){for(j=1;j<=m;j++)cout<weight[k])Pack(m+1,k+1,t-weight[k]);}}四、判断括号是否配对：intCorrect(strings){Inistack(Q);for(i=0;s[i]==‘=’;i++)//表达式以‘=’结束{switch(s[i]){case‘(’:case‘[’:case‘{’:Push(Q,s[i]);break;case‘)’:case‘]’:case‘}’:if(Empty(Q))return0;t=Pop(Q);if(!Matching(t,s[i]))return0;}}if(!Empty(Q))return0;return1;}五、堆栈可能的输出：2123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321六、用两个堆栈实现一个队列：intFullQ(){if(Full(S1)&&!Empty(S2))return1;return0;}intEmptyQ(){if(Empty(S1)&&Empty(S2))return1;return0;}voidEnqueue(elemtypex){if(Full(S1))if(Empty(S2))while(!Empty(S1))Push(S2,Pop(S1));if(!Full(S1))Push(S1,x);}elemtypeDequeue(){if(Empty(S2))while(!Empty(S1))Push(S2,Pop(S1));if(!Empty(S2))returnPop(S2);}七、生成新串及字符第一次出现位置：intIndex(stringS,stringT){for(i=1;i+Len(T)-1<=Len(S);i++)ifEqual(Sub(S,I,Len(T)),T)returni;return0;}voidCreatNewStr(stringS,stringT,stringR,arrantP){R=“”;j=0;for(i=1;i<=Len(S);i++){ch=Sub(S,i,1);3if(!Index(T,ch)&&!Index(R,ch)){R=Concat(R,ch);P[j++]=i;}}}八、块链字符串插入：{为避免字符串内部块间大量的数据移动，最好的方法是定义两种字符串中不出现的字符作为空标记和串结束标记，如‘#’和‘$’；也可只使用空标记，串结束以块尾指针为空表示，其算法如下：voidInsert(stringS,stringT,charch)//设块大小为m{i=0;p=T;while((p->next)&&(!i)){for(j=1;j<=m;j++)if(p->str[j]==ch)i=j;if(!i)p=p->next;}if(!i)for(j=1;j<=m;j++)if(p->str[j]==ch)i=j;if(!i)p->next=S;else//S插在T后{//ch所在结点分裂，S插在T中分裂的两结点间q=newstructnode;q->str=p->str;q->next=p->next;for(j=i;j<=m;j++)p->str[j]=‘#’;p->next=S;for(j=1;jstr[j]=‘#’;p=S;while(p->next)p=p->next;p->next=q;}}九、上三角矩阵的存储：k=(i-1)*n+j-i*(i-1)/2=(2n-i+1)*i/2+j-nf1=(2n-i+1)*i/2f2=jc=-n十、循环右移k位：12345678（n=8,k=3）6781234587654321voidExch(arrtypeA,intst,inted){4for(i=st;i<=(st+ed)/2;i++)A[i]←→A[ed-i+1];}voidShift(arrtypeA,intk,intn){Exch(A,1,n);Exch(A,1,k);Exch(A,k+1,n)}十一、广义表运算结果：1、(a,b)2、((c,d))3、(c,d)4、(b)5、b6、(d)十二、利用广义表运算取出c原子：1、Head(Tail(Tail(L1)))2、Head(Head(Tail(L2)))3、Head(Head(Tail(Tail(Head(L3)))))4、Head(Head(Head(Tail(Tail(L4)))))5、Head(Head(Tail(Tail(L5))))6、Head(Tail(Head(L6)))7、Head(Head(Tail(Head(Tail(L7)))))8、Head(Head(Tail(Head(Tail(L8)))))十三、满k叉树问题：1、kn-12、n=1无父结点，否则为3、(n-1)k+1+i4、(n-1)Modk≠0十四、叶子结点数目：n0=∑(i-1)ni+1十五、找最近共同祖先：bitptrForefather(bitptrroot,bitptrp,bitptrq)5n-2+kki=1m{f...
