资源描述：
《数据结构与算法 作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、作业参考答案一、（带头结点）多项式乘法C=A×B：voidPolyAdd(list&C,listR)//R为单个结点{p=C;while((！p->next)&&(p->next->exp>R->exp))p=p->next;if((p->next)
2、
3、(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
4、(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
5、)+2i–1若n=i,则M(n-n)=0,故：M(n)=2nM(n-n)+2n–1=2n–115所以，梵塔的移动次数为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]);}}四、判断括号是否配对：intCo
6、rrect(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;}五、堆栈可能的输出：151234124313241342142314322134214323
7、14234124132431312431423214324134123421412341324213423143124321六、用两个堆栈实现一个队列：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))P
8、ush(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
9、=0;for(i=1;i<=Len(S);i++){15ch=Sub(S,i,1);if(!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
10、=1;j<=m;j++)if(p->str[j]==ch)i=j;if(!i)p=p->next;}if(!i)for(j
