问答题
设计求解下列问题的算法，并分析其最坏情况的时间复杂度。
问答题
在数组A[1，…，n]中查找值为K的元素，若找到则输出其位置i；否则输出0作为标志。
【正确答案】算法如下：
int locate(datatype A[],datatype k)
//datatype为C语言标准数据类型
{
int i=n;
while(i＞=1 && A[i]!=k)
--i;
return i;
}
当查找不成功时，总是比较n+1次，所以最坏的时间复杂度为O(n)。
【答案解析】
问答题
找出数组A[1，…，n]中元素的最大值和次最大值。
【正确答案】算法如下：
void max(datatype A[],datatype m,datatype sm)
//datatype为C语言标准数据类型
{
int i;
m=sm=A[1];//m存放最大值，sm存放次最大值
for(i=2;i＜=n;++i)
if(A[i]＞m)
{
sm=m;m=A[i];
}
else if(A[i]＞sm) sm=A[i];
}
为了得到最大值和次最大值，必须经过n-1次循环，所以最坏的时间复杂度为n-1，即O(n)。
【答案解析】
问答题
以下算法是在一个有n个数据元素的数组A中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求平均删除一个数组元素需要移动的元素个数是多少?其中，数组下标从0至n-1。
int delete(int A[],int n,int i)
{
int j;
if(i＜0||i＞n)
return 0;
for(j=i+1;j＜n;++j)
A[j-1]=A[j];
--n;
return 1;
}
【正确答案】当删除最后一个元素时，移动的元素个数为0；当删除倒数第二个元素时，移动的元素个数为1；…；当删除第一个元素时，移动的元素个数为n-1。也就是说，当删除第i个元素时，移动的元素个数为n-i，设P为删除第i个位置上数据元素的概率，则有Pi=1/n，平均删除一个数组元素需要移动的元素个数是
[*]
[*]
【答案解析】
问答题
说明在线性表的链式存储结构中，头指针与头结点之间的根本区别以及头结点与开始结点的关系。
【正确答案】用链表存储结构来表示线性表时，链表的头指针一般指向其第一个结点，它有标识链表的作用。头结点的作用在于统一相关操作，如对链表中第一数据元素结点前插入结点和删除第一结点，这些操作就和其他结点统一了。头结点的数据域一般没有意义，某些情况下可以存放链表长度。如果链表含有头结点，无论链表是否为空，头指针均不为空。开始结点也就是链表中存储数据的第一个结点，它是头结点后边的第一个结点。
【答案解析】
问答题
请简要比较顺序表和链表各自的特点。
【正确答案】(1)基于空间的比较。
1)存储分配的方式：
顺序表的存储空间是静态分配的。
链表的存储空间是动态分配的。
2)存储密度(存储密度=结点值域所占的存储量/结点结构所占的存储总量)：
顺序表的存储密度=1。
链表的存储密度＜1(因为结点中有指针域)。
(2)基于时间的比较。
1)存取方式：
顺序表可以随机存取，也可以顺序存取(对于顺序表一般只答随机存取即可)
链表是顺序存取的。
2)插入/删除时移动元素的个数：
顺序表平均需要移动近一半元素。
链表不需要移动元素，只需要修改指针。
【答案解析】
问答题
编写一个算法实现两个有序(从小到大)顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储(假设这两个有序顺序表中没有相同的元素)。
【正确答案】可以按照如下策略实现顺序表A和B的合并过程：从A和B的最后一个元素逐个向前进行比较，将较大的元素先定位在A中。
代码如下：
int comb(int A[],int na,int B[],int nb)
{
int n=na,m=nb;
if(na+nb＞MaxLen) return 0; //顺序表上溢，假设MaxLen已定义
while(nb＞0)
if((na==0)||(A[na-1]＜B[nb-1]))
{
A[na+nb-1]=B[nb-1]; //说明B[nb-1]是第na+nb大的元素
--nb;
}
else
{
A[na+nb-1]=A[na-1]; //说明A[na-1]是第na+nb大的元素
--na;
}
na=n+m;
return na;
}
【答案解析】
问答题
设A=(a1，a2，…，am)和B=(b1，b2，…，bn)均为顺序表。若n=m且ai=bi(i=1，…，n)，则称A=B；若ai=bi(i=1，…，j)且aj+1＜bj+1(j＜n≤m)，则称A＜B；在其他情况下均称A＞B。试编写一个比较A和B的算法，当A＜B、A=B或A＞B时分别输出-1、0或1。
【正确答案】本题算法思想：先找出A和B中前面对应位置相同的结点，用指针i和j分别指示A和B中不同元素的下标，根据指针i和j提供的信息即可得到A和B的比较结果。
代码如下：
int comp(int A[],int na,int B[],int nb)
{
int i=0,j=0;
while(i＜na && j＜nb && A[i++]==B[j++]); //比较相同的部分
--i;
--j;
if(i==na && j==nb)
return 0;
if(i==na && j!=nb)
return -1;
if(i!=ma && j==nb)
return 1;
if(A[i]＞B[j])
return 1;
else
return -1;
}
【答案解析】
问答题
编写一个算法，将m(m≥2)个有序(从小到大)顺序表合并成一个有序顺序表，合并过程中不另设新的顺序表存储。
【正确答案】将线性表A和B合并的过程如下：从A的最后一个元素和B的第一个元素开始分别向前、向后进行比较，将较大的元素先定位在A中。
代码如下：
int Comb1(int A[],int na,int B[],int nb)
{
int n=na,m=0;
while(m＜nb)
if(n==0||A[n-1]＜B[m])
{
A[n+nb-m-1]=B[m]; //说明B[m]是第n+nb-m大的元素
++m;
}
else
{
A[n+nb-m-1]=A[n-1]; //说明A[n-1]是第n+nb-m大的元素
--n;
}
return na+nb;
}
【答案解析】
问答题
设A和B是两个顺序表，其元素按从小到大的顺序排列。编写一个将A和B中相同元素组成一个新的从大到小的有序顺序表C的算法，并分析算法的时间复杂度。
【正确答案】本算法是从A和B的最后两个元素开始比较，若相等，将其值放入C的第一个元素中，如此直到A和B中的所有元素比较完毕。实现本题功能的程序代码如下：
int intersect(int A[],int na,int B[],int nb,int C[])
{
int i=na,j=nb,k=0;
while(i＞=0 && j＞=0)
if(A[i-1]＞B[j-1])
--i;
else if(A[i-1]＜B[j-1])
--j;
else //A[i-1]=B[j-1]
{
C[k++]=A[i-1];
--i;
--j;
}
return k-1;
}
本算法intersect(A，na，B，nb，C)的时间复杂度为O(na+nb)，其中na和nb分别为A和B的长度。
【答案解析】
问答题
设A和B是两个顺序表，其元素按非递减的顺序排列。编写一个将A和B中所有元素组成一个新的从小到大的有序顺序表C的算法，要求删除重复的元素，并返回C表的长度。
【正确答案】此题简单，程序代码如下：
int unions(int A[],int na,int B[],int nb,int C[])
{
int i=0,j=0,k=0;
while(i＜na && j＜nb){
if(A[i]＜=B[j]){
if(k＞0){
if(C[k-1]!=A[i])
C[k++]=A[i++];
else
++i;
}
else
C[k++]=A[i++];
}
else
{
if(k＞0){
//此处注意k为0时的处理，因为A或B有可能是空表。没有
//k等于0的判断，C[k-1]出现溢出
if(C[k-1]!=B[j])//这个判断起到过滤相同元素的作用
C[k++]=B[j++];
else
++j;
}
else
C[k++]=B[j++];
}
}
while(i＜na)
{
if(k＞0){
if(C[k-1]!=A[i])
C[k++]=A[i++];
else
++i;
}
else
C[k++]=A[i++];
}
while(j＜nb)
{
if(k＞0){
if(C[k-1]!=B[j])
C[k++]=B[j++];
else
++j;
}
else
C[k++]=B[j++];
}
return k;
}
【答案解析】[说明] 本题容易忽略对A或者B内部相同元素的处理，题目用非递减这个信息提示了考生，细心观察即可避免错误的发生。
问答题
设有一个表头指针为h的单链表，试设计一个算法，通过遍历一趟链表，将链表中所有结点的链方向逆转，如图所示。
【正确答案】void Reverse(LNode *&h)
{
//设单链表没有表头结点，h直接指示链表首元结点。链表全部逆转后，h
//指向原链尾结点，它成为新的首元结点
if(h==NULL) return;
LNode *p=h→next,*pr=NULL;
while(p!=NULL)
{
h→nexr=pr; //逆转h指针
pr=h;h=p;p=p→next; //指针前移
}
h→next=pr;
}
【答案解析】
问答题
以下是两个n阶方阵的乘积C=A×B，给出该算法的时间复杂度。
void matmult(int n,float A[][maxSize],float B[][maxSize],float C[maxSize][maxSize])
{
int i,j,k;
float x;
for(i=1;i＜=n;++i) //①
for(j=1;j＜=n;++j) //②
{
x=0; //③
for(k=1;k＜=n;++k) //④
x+=A[i][k]*B[k][j]; //⑤
C[i][j]=x; //⑥
}
}
【正确答案】在算法中，语句①的循环控制变量i要增加到n+1，测试i＞n成立才会终止，所以它的频度是n+1，但是它的循环体却只能执行n次。语句②作为语句①的循环体内的语句应执行n次，但语句②本身要执行n+1次，所以语句②的频度是n(n+1)。同理得到语句③、④、⑤、⑥的频度分别为n2、n2(n+1)、n3、n2。本算法的时间复杂度T(n)为
T(n)=n+1+n(n+1)+n2+n2(n+1)+n3+n2=2n3+3n2+2n+1=O(n3)
实际上，只需考虑基本语句的时间复杂度即可，在上述算法中，语句③、⑤、⑥是基本语句，它们的时间复杂度为O(n3)。
T(n)=n+1+n(n+1)+n2+n2(n+1)+n3+n2=2n3+3n2+2n+1=O(n3)
实际上，只需考虑基本语句的时间复杂度即可，在上述算法中，语句③、⑤、⑥是基本语句，它们的时间复杂度为O(n3)。
【答案解析】
问答题
假设有n(n＞1)个线性表顺序地存放在顺序表S[1，…，m]中，令F[i]和R[i]指示第i个(1≤i≤n)表的第1个元素和最后1个元素在S中的位置，并设定R[i]＜F[i+1]，F[n+1]=m+1，如图所示。试写出实现下列要求的算法。
【正确答案】本题实质上是将n个线性表(长度可能不相同)放于一个连续空间(长度为m)，来解决这些线性表的插入和删除问题。
(1)的算法程序代码如下：
void ins(i,j,x)
{
int p,k;
if(R[n]==m)
cout＜＜"上溢"＜＜endl;
else
{
for(p=n;p＞=i+1; --p) //将i+1到n的线性表后移一个元素
{
for(k=R[p];k＞=F[p]; --k)
//将第p个线性表后移一个元素
S[k+1]=S[k];
++R[p];++F[p]; //第p个线性表的首尾元素位置均增1
}
for(p=R[i];p＞=j+1;--p)
//将第i个线性表中的第j个位置起的元素均后移
S[p+1]=S[p];
S[p]=x; //在第i个线性表的第j个位置处存放x
++R[p]; //第p个线性表的R[p]增1
}
}
(2)的算法程序代码如下：
void del(i,j)
{
for(p=F[i]+j;p＜=m; ++p) //元素前移覆盖要删除的元素
S[p]=S[p+1];
for(p=i;p＜=n; ++p) //第i个及以后的线性表的R[i]值减1
--R[p];
for(p=i+1;p＜=n; ++p) //第i+1个及以后的线性表的F[i]值减1
--F[p];
}
【答案解析】
问答题
设某机器表示的整数不超过5位十进制数字。试设计一种表示任意长的整数的数据结构，并利用设计的数据结构，写出计算任意给定的两个整数之和的算法。
【正确答案】将用户输入的正整数按各位数字存放在一个顺序表中，这样就变成了两个顺序表中的数字相加。实现本题功能的程序代码如下：
int input(int A[])
{
int i;
for(i=0;i＜MaxLen; ++i)
A[i]=0;
cout＜＜”输入一个正整数的各位(以-1结束)"＜＜endl;
i=0;
while(true)
{
cin＞＞A[i];
if(A[i]＜0) break;
++i;
}
return i;
}
void output(int A[],int low,int high)
//输出顺序表A中的A[low]到A[high]
{
int i;
for(i=low;i＜high; ++i)
cout＜＜A[i];
cout＜＜endl;
}
void move(int A[],int na) //将A中存放的数字移到后面
{
int i;
for(i=0;i＜na; ++i)
A[MaxLen-i-1]=A[na-i-1];
}
int add(int A[],int na,int B[],int nb)
//实现A和B相加，结果放在A中
{
int nc,i,j,length;
if(na＞nb) nc=na;
else nc=nb;
move(A,na);
move(B,nb);
for(i=MaxLen-1;i＞=MaxLen-nc; --i)
{
j=A[i]+B[i];
if(j＞9)
{
A[i-1]=A[i-1]+1;
A[i]=j-10;
}
else A[i]=j;
if(i==MaxLen-nc)
{
if(j＞9)
{
A[i-1]=1;
length=nc+1;
}
else length=nc;
}
}
return length;
}
【答案解析】
问答题
已知在一维数组A[0，…，m+n-1]中依次存放着两个顺序表(a1，a2，…，am)和(b1，b2，…，bn)。试编写程序，将数组中两个顺序表的位置互换，即将(b1，b2，…，bn)放在(a1，a2，…，am)的前面。
【正确答案】分析：只需将顺序表整体逆转，然后再对子表分别逆转，即可满足题目要求。
由此可以写出如下程序代码：
void Reverse(int A[],int left,int right,int arraySize)
(//假设A是int型数组，此函数逆转(aleft,aleft+1,...,aright)为(aright,aright-1,...,aleft)
if(left＞=right||right＞=arraySize)
return;
int i=left,j=right;
while(i＜j)
{
int temp=A[i];
A[i]=A[j];
A[j]=temp;
++i;
--j;
}
}
void Exchange(int A[],int m,int n,int arraySize)
{
//在数组A[m+n]中，从0到m-1存放顺序表(a1，a2,...,am)，从m到m+n-1存
//在顺序表(b1,b2,...,bn)，算法把这两个表的位置互换
Reverse(A,0,m+n-1,arraySize);
//逆转为(bn,bn-1,...,bi,am,am-1,...,a1)
Reverse(A,0,n-1,arraySize);
//逆转为(b1,b2,...,bn,am,am-1,...,a1)
Reverse(A,n,m+n-1,arraySize);
//逆转为(b1,b2,...,bn,a1,a2,...,am)
}
由此可以写出如下程序代码：
void Reverse(int A[],int left,int right,int arraySize)
(//假设A是int型数组，此函数逆转(aleft,aleft+1,...,aright)为(aright,aright-1,...,aleft)
if(left＞=right||right＞=arraySize)
return;
int i=left,j=right;
while(i＜j)
{
int temp=A[i];
A[i]=A[j];
A[j]=temp;
++i;
--j;
}
}
void Exchange(int A[],int m,int n,int arraySize)
{
//在数组A[m+n]中，从0到m-1存放顺序表(a1，a2,...,am)，从m到m+n-1存
//在顺序表(b1,b2,...,bn)，算法把这两个表的位置互换
Reverse(A,0,m+n-1,arraySize);
//逆转为(bn,bn-1,...,bi,am,am-1,...,a1)
Reverse(A,0,n-1,arraySize);
//逆转为(b1,b2,...,bn,am,am-1,...,a1)
Reverse(A,n,m+n-1,arraySize);
//逆转为(b1,b2,...,bn,a1,a2,...,am)
}
【答案解析】[说明] 此题不难，但可以反映考研中数据结构科目的一个特点，即问题常常可以抽象成一个最简单情况，通过这个最简单情况来反映问题的一般特征，进而达到节省思维量的目的。对于本题，最简单情况下A可以取为(a1，a2，b1，b2)，两个子表为(a1，a2)和(b1，b2)，之所以这样取，是因为这能反映表自身顺序的最小情况。将A整体逆转得到(b2，b1，a2，a1)，将(b2，b1)和(a2，a1)分别逆转，得到(b1，b2，a1，a2)，达到了将A中两个子表位置互换的目的。
问答题
假定数组A[0，…，n-1]中有多个零元素，试写出一个函数，将A中所有的非零元素依次移到数组A的前端。
【正确答案】因为数组是一种直接存取的数据结构，在一维数组中元素不是像顺序表那样集中存放于表的前端，而是根据元素下标直接存放于数组某个位置，所以将非零元素前移时必须检测整个数组空间，并将后面变成零元素的空间清零。函数中设置一个辅助指针free，指示当前可存放的位置，初值为0。算法的程序代码如下：
void compact(int A[],int n)
{
int free=0;
for(int i=0;i＜n;++i) //检测整个数组
if(A[i] !=0) //发现非零元素
{
if(i !=free) //前移非零元素
{
A[free]=A[i];
A[i]=0;
}
++free;
}
}
【答案解析】
问答题
已知L为不带表头结点的单链表的表头指针(L非空)，链表中存储的都是整型数据，试写出实现下列运算的递归算法。
(1)求链表中的最大整数。
(2)求链表的结点个数。
(3)求所有整数的平均值。
【正确答案】(1)求链表中的最大整数的程序代码如下：
int Max(LNode *L) //递归算法：求链表中的最大值
{
if(L→next==NULL) //链表仅一个结点，其值即所求
return L→data;
int temp=Max(L→next); //否则递归求后继链表中的最大值
if(L→data＞temp) //再与首元的值比较，取大值
return L→data;
else
return temp;
}
(2)求链表的结点个数的程序代码如下：
int Num(LNode *L) //递归算法：求链表中结点个数
{
if(L==NULL) //空链表结点个数为0
return 0;
return 1+Num(L→next); //否则求后继链表结点数再加1
}
(3)求所有整数的平均值的程序代码如下：
float Avg(LNode *L,int& n) //递归算法：求链表中所有元素的平均值
{
if(L→next==NULL) //链表仅一个结点
{ //其值即所求
n=1;
return(float)(L→data);
}
else //否则
{
float Sum=Avg(L→next,n) *n; //先递归求后继链表的平均值
++n; //再计算总和
return(L→data+Sum)/n; //然后加上首元的值再求平均值
}
}
【答案解析】[说明] 对诸如此类递归算法不是很清楚的同学，可以参考《数据结构高分笔记》一书中的特别章——考研中某些算法的分治法解释。
问答题
从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将链接方向逆转，如图所示。图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。
【正确答案】(1)假设输入的p和pr都是指向待处理链表的合法位置的指针，指针p右移k个结点并逆转pr之前(包括pr)的所有结点的链接指针。程序代码如下：
void siftToRight(LNode *p,LNode *pr,int k)
{
//因为此操作在链表中只改变局部顺序，所以不修改表头和表尾指针。如果能够右移
//的结点数不够k个，则处理到链尾为止，并报告右移结点个数
LNode *q;int count=0;
while(p!=NULL && count＜k) //右移k个结点
{
q=p→next;p→next=pr; //链指针p→next逆转指向pr
pr=p;p=q; //指针pr和p右移
++count;
}
}
(2)此题和上一小题类似，指针p左移k个结点。程序代码如下：
void siftToLeft(LNode *&p,LNode *&pr,int k)
{
LNode *q;int count=0;
while(pr !=NULL && count＜k) //左移k个结点
{
q=pr→next;pr→next=p; //链指针p→next逆转指向pr
p=pr;pr=q; //指针pr和p左移
++count;
}
}
【答案解析】
问答题
根据一个结点数据类型为整型的单链表生成两个单链表，第一个单链表中包含原单链表中所有数据值为奇数的结点，第二个单链表中包含原单链表中所有数据值为偶数的结点，原有单链表保持不变。
【正确答案】void Separate(LNode *&HL,LNode *&L1,LNode *&L2)
{
//将一个单链表HL按各个结点中数据的奇偶性拆分成两个单链表L1和L2
LNode *r1,*r2,*p,*s;
r1=L1=(LNode*)malloc(sizeof(LNode));
r2=L2=(LNode*)malloc(sizeof(LNode));
p=HL→next; //链表HL的扫描指针
while(p!=NULL) //对原链表的结点逐个进行检测
{
s=(LNode*)malloc(sizeof(LNode)); //创建新结点
s→data=p→data;
if(p→data % 2==1) //奇数
{
r1→next=s;
r1=s;
}
else //偶数
{
r2→next=s;
r2=s;
}
p=p→next;
}
r1→next=NULL;r2→next=NULL;
}
【答案解析】
问答题
已知一个带表头结点的单链表中含有3类字符(数字字符、字母字符和其他字符)。试编写一个函数，构造3个新的单链表，使每个单链表中只包含同一类字符。要求使用原表的空间，表头结点可以另辟空间。
【正确答案】void Separate1(LNode *&LA,LNode *&LB,LNode *&LC)
{
//原来的单链表是LA，新的3个单链表是LA(数字)、LB(字母)和LC(其他)
LNode *pa,*pb,*pc,*p=LA→next; //原链表检测指针
pa=LA;pb=LB=(LNode*)malloc(sizeof(LNode));
pc=LC=(LNode*)malloc(sizeof(LNode));
//指针pa、pb、pc分别是3个结果链表的链尾指针，初始时指向各表头结点
while(p !=NULL)
{
//假设ctype.h文件已经包含
if(isdigit(p→data)) //数字字符，链入数字链
{
pa→next=p;
pa=p;
}
else if(isalpha(p→data)) //字母字符，链入字母链
{
pb→next=p;
pb=p;
}
else //其他字符，链入其他字符链
{
pc→next=p;
pc=p;
}
p=p→next;
}
pa→next=NULL;pb→next=NULL;pc→next=NULL;
}
【答案解析】[说明] 以上代码中isdigit()和isalpha()两个函数分别用于识别数字字符和字母字符。对于isdigit()参数传入的是数字字符，则返回真，否则返回假；isalpha()类似。这两个函数是ctype.h文件中已经定义好的，并且本题考查的重点不在实现以上两个函数，因此可以直接调用。如果对于这两个函数功能不熟悉，以上代码中相应的if语句可以做如下替换同样能达到目的。
将
if(isdigit(p→data))
替换为
if(p→data＞='0' && p→data＜='9')
将
if(isalpha(p→data))
替换为
if((p→data＞='a'&&p→data＜='z')||(p→data＞='A'&&p→data＜='z'))
这是用判别相应字符的ASCII区间来实现的。
问答题
试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate(x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
【正确答案】算法用到4个双向循环链表的主要操作：①正向搜索寻找满足要求的结点；②把该结点从链中摘下；③反向根据访问计数寻找插入位置；④把该结点重新插入到链中。程序代码如下：
DLNode *Locate(DLNode *&DL,int x)
{
DLNode *p=DL→next,*q;
while(p !=NULL && p→data !=x)p=p→next;
if(p !=NULL) //链表中存在包含x的结点
{
++(p→freq);q=p; //该结点的访问频度加l
q→prior→next=q→next; //从链表中摘下这个结点
q→next→prior=q→prior;
p=q→prior; //寻找重新插入的位置
while(p !=DL && q→freq＞p→freq) p=p→prior;
q→next=p→next;q→prior=p; //插入在p之后
p→next→prior=q;p→next=q;
return q;
}
else
return NULL; //没找到
}
【答案解析】
问答题
若采用数组来存储一元多项式的系数，则用数组的第i个元素存放多项式的i次幂项的系数。如对于一元多项式f(x)=6x6+7x4-10x2+5x+3，可用数组表示，如图所示。
【正确答案】如果用如题意所述的数组来存放多项式，则多项式的结构定义的程序代码如下：
typedef struct node
{
float coef[maxSize];
//多项式系数数组，maxSize为已经定义的大于多项式最大项数的常数
int order; //多项式最高阶数
}Polynomial;
(1)求两个一元多项式的和。
设两个一元多项式A(x)和B(x)分别为
A(x)=a0+a1x+a2x2+…+anxn，B(x)=b0+b1x+b2x2+…+bmxm
当n≤m时，两个一元多项式的和为
A(x)+B(x)=(a0+b0)+(a1+b1)x+(a2+b2)x2+…+(an+bn)xn+bn+1xn+1+…+bmxm
当n＞m时，两个一元多项式的和为
A(x)+B(x)=(a0+b0)+(a1+b1)x+(a2+b2)x2+…+(am+bm)xm+am+1xm+1+…+anxn
相应算法的程序代码如下：
void Add(Polynomial &A,Polynomial &B,Polynomial &C)
{
//两个按升幂排列的多项式A和B相加，结果多项式放在C中。假设C已经
//存在，且其存储空间C.coef已经成功分配。多项式次数从0开始，因此
//本题数组从0下标开始存储多项式
int m=A.order,n=B.order,i;
for(i=0;i＜=m && i＜=n;++i) //指数相同，系数相加
C.coef[i]=A.coef [i]+B.coef[i];
while(i＜=m) //两个while循环只执行一个，直接复制剩余项
{
C.coef[i]=A.coef[i];
++i;
}
while(i＜=n)
{
C.coef[i]=A.coef[i];
++i;
}
C.order=(m＞n) ? m:n; //计算结果多项式的阶数
}
(2)求两个一元多项式的乘积
[*]
将xi移入第二个求和符号里边，以方便翻译成相应的代码。由此，原式写为
[*]
由此，可以清楚地看到，通过一个二重循环即可实现多项式乘法。算法程序代码如下：
void Mul(Polynomial &A,Polynomial &B,Polynomial &C,float x)
{
//两个按升幂排列的多项式A和B相乘，结果多项式放在C中。假设C已经存在，且
//其存储空间c.coef已经成功分配。pow(x,y)是求x的y次幂的函数，其原型在
//math.h文件中，并假设此文件已经包含
int m=A.order,n=B.order,i,j;
if(m+n+1＞=C.maxSize)
{
cout＜＜"memory limit"＜＜endl;
//这里打印出错信息正规的写法应该是用cerr，对于考研要求，可以用熟悉的cout代替。
return;
}
for(i=0;i＜=m*n+1;++i)
C.coef [i]=0.0;
for(i=0;i＜=m;++i)
for(j=0;j＜=n;++j)
C.coef[i+j]
=C.coef[i+j]+A.coef[i]*B.coef[j]*pow(x,i+j);
C.order=m+n;
}
typedef struct node
{
float coef[maxSize];
//多项式系数数组，maxSize为已经定义的大于多项式最大项数的常数
int order; //多项式最高阶数
}Polynomial;
(1)求两个一元多项式的和。
设两个一元多项式A(x)和B(x)分别为
A(x)=a0+a1x+a2x2+…+anxn，B(x)=b0+b1x+b2x2+…+bmxm
当n≤m时，两个一元多项式的和为
A(x)+B(x)=(a0+b0)+(a1+b1)x+(a2+b2)x2+…+(an+bn)xn+bn+1xn+1+…+bmxm
当n＞m时，两个一元多项式的和为
A(x)+B(x)=(a0+b0)+(a1+b1)x+(a2+b2)x2+…+(am+bm)xm+am+1xm+1+…+anxn
相应算法的程序代码如下：
void Add(Polynomial &A,Polynomial &B,Polynomial &C)
{
//两个按升幂排列的多项式A和B相加，结果多项式放在C中。假设C已经
//存在，且其存储空间C.coef已经成功分配。多项式次数从0开始，因此
//本题数组从0下标开始存储多项式
int m=A.order,n=B.order,i;
for(i=0;i＜=m && i＜=n;++i) //指数相同，系数相加
C.coef[i]=A.coef [i]+B.coef[i];
while(i＜=m) //两个while循环只执行一个，直接复制剩余项
{
C.coef[i]=A.coef[i];
++i;
}
while(i＜=n)
{
C.coef[i]=A.coef[i];
++i;
}
C.order=(m＞n) ? m:n; //计算结果多项式的阶数
}
(2)求两个一元多项式的乘积
[*]
将xi移入第二个求和符号里边，以方便翻译成相应的代码。由此，原式写为
[*]
由此，可以清楚地看到，通过一个二重循环即可实现多项式乘法。算法程序代码如下：
void Mul(Polynomial &A,Polynomial &B,Polynomial &C,float x)
{
//两个按升幂排列的多项式A和B相乘，结果多项式放在C中。假设C已经存在，且
//其存储空间c.coef已经成功分配。pow(x,y)是求x的y次幂的函数，其原型在
//math.h文件中，并假设此文件已经包含
int m=A.order,n=B.order,i,j;
if(m+n+1＞=C.maxSize)
{
cout＜＜"memory limit"＜＜endl;
//这里打印出错信息正规的写法应该是用cerr，对于考研要求，可以用熟悉的cout代替。
return;
}
for(i=0;i＜=m*n+1;++i)
C.coef [i]=0.0;
for(i=0;i＜=m;++i)
for(j=0;j＜=n;++j)
C.coef[i+j]
=C.coef[i+j]+A.coef[i]*B.coef[j]*pow(x,i+j);
C.order=m+n;
}
【答案解析】