算法与数据结构C语言习题参考答案章.docx

绪论
1．将下列复杂度由小到大重新排序：
A．2n B．n! C．n5 D．10000 E．n*log2(n)
【答】10000<n*log2(n)<n5<2n<n!
2．将下列复杂度由小到大重新排序：
A．n*log2(n) B．n+n2+n3 C．24 D．n0.5
【答】24<n0.5<n*log2(n)<n+n2+n3
3．用大“O”表示法描述下列复杂度：
A．5n5/2+n2/5 B．6*log2(n)+9n
C．3n4+n*log2(n) D．5n2+n3/2
【答】A：O(n5/2) B：O(n) C：O(n4) D：O(n2)
4．按照增长率从低到高的顺序排列以下表达式：4n2,log3n,3n,20n,2000,log2n,n2/3。又n！应排在第几位？
【答】按照增长率从低到高依次为：2000,log3n,log2n,n2/3,20n,4n2,3n。
n！的增长率比它们中的每一个都要大，应排在最后一位。
5.计算下列程序片断的时间代价：
inti=1;
while(i<=n)
{
printf(“i=%d\n”,i);
i=i+1;
}
【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。所以该程序段总的时间代价为：
T(n)=1+n+2n=3n+1=O(n)
6.计算下列程序片断的时间代价：
inti=1;
while(i<=n)
{
intj=1;
while(j<=n)
{
intk=1;
while(k<=n)
{
printf(“i=%d,j=%d,k=%d\n”,I,j,k);
k=k+1;
}
j=j+1;
}
i=i+1;
}
【答】循环控制变量i从1增加到n，最外层循环体执行n次，循环控制变量j从1增加到n，中间层循环体执行n次，循环控制变量k从1增加到n，最内层循环体执行n次，所以该程序段总的时间代价为：
T(n)=1+n+n｛1+n+n[1+n+2n+1]+1+1｝+1
=3n3+3n2+4n+2
=O(n3)
2.线性表
1.试写一个插入算法intinsertPost_seq(palist,p,x)，在palist所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。
【答】
数据结构
采用2.1.2节中顺序表定义。

intinsertPost_seq(PseqListpalist,intp,DataTypex){
/*在palist所指顺序表中下标为p的元素之后插入元素x*/
intq;
if(palist->n>=palist->MAXNUM){ /*溢出*/
printf(“Overflow!\n”);
return0;
}
if(p<0||p>palist->n-1) { /*不存在下标为p的元素*/
printf(“Notexist!\n”);return0;
}
for(q=palist->n-1;q>=p+1;q--)/*插入位置及之后的元素均后移一个位置*/
palist->element[q+1]=palist->element[q];
palist->element[p+1]=x; /*插入元素x*/
palist->n=palist->n+1; /*元素个数加1*/
return1;
}

2试写一个删除算法deleteV_seq(palist,x)，在palist所指顺序表中，删除一个值为x的元素，返回删除成功与否的标志。
【答】
数据结构
采用2.1.2节中顺序表定义。

intdeleteV_seq(PseqListpalist,p,DataTypex){
/*在palist所指顺序表中删除值为x的元素*/
intp,q;
for(p=0;p<n;p++)/*查找值为x的元素的下标*/
if(x==palist->element[p]){
for(q=p;q<palist->n-1;q++)/*被删除元素之后的元素均前移一个位置*/
palist->element[q]=palist->element[q+1];
palist->n=palist->n-1; /*元素个数减1*/
return1;
}
return0;
}

3.设有一线性表e=(e0,e1,e2,…,en1)，其逆线性表定义为e=(en1,…,e2,e1,e0)。请设计一个算法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的空间。
【答】
数据结构
采用节中顺序表的定义。
思路
考虑对数组element[]进行置逆，即把第一个元素和最后一个元素换位置，