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

本文档如对你有帮助，请帮忙下载支持！

1.绪

论

1．将下列复杂度由小到大重新排序：

A．2nB．n!C．n5D．10000E．n*log2

10000<n*log(n)<n5<2n<n!(n)
【答】2

2．将下列复杂度由小到大重新排序：

A．n*log(n)B．n+n2+n3
2C．240.5
D．n
【答】24<n0.5<n*log2(n)<n+n2+n3

3.用大“0”表示法描述下列复杂度：

A．5n5/2+n2/5B．6*log2(n)+9n

C．3n4+n*log2(n)D．5n2+n3/2

【答】A：0(n5/2)B：0(n)C：0(n4)D：0(n2)

44n2,log3n,3n,2000,
．按照增长率从低到高的顺序排列以下表达式：
n2/3。又n!应排在第几位？20n,log2n,

【答】按照增长率从低到高依次为：2000,log3n,log2n,n2/3,20n,4n2,3n。

n的增长率比它们中的每一个都要大，应排在最后一位。

5.
计算下列程序片断的时间代价：
inti=1;

while(i<=n)

{

“”
Printf(i=%d

,i);

i=i+1;

}
【答】循环控制变量i从1增加到n,循环体执行n次，第一句i的初始化执行次数为句执行1，第二

次，循环体中第一句执行次，第二句从1循环到，共执行次。序段总的时间所以该程
nPrintfninn
代价为：

T(n)=1+n+2n=3n+1=
O(n)
6.计算下列程序片断的时间代价：

int
i=1;
while(i<=n)

{

intj=1;

while(j<=n)

{

intk=1;

本文档如对你有帮助，请帮忙下载支持！

while(k<=n)

{
printf(“i=%d,j=%d,k=%d
”,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的元素，返回插入成功与否的标志。

【答
】
数据结构

采用

intinsertPost_seq(PseqListpalist,intp,DataTypex)
{

/*在palist所指顺序表中下标为p的元素之后插入元素x*/
intq;

/*溢出*/
if(palist->n>=palist->
MAXNUM){
printf(n)
“；
return0;

}
if(pv0IIp>palist->n-1){/*不存在下标为P的元素*/

printf(n”)；return
“N
0;
}
for(q=palist->n-1;q>=p+1;q--)/*插入位置及之后的元素均后移一个位置*
/
palist->element[q+1]=p

alist->element[q];palist->element[p+1]=/*插入元素x*/
x;
Palist->n=Palist->n/元素个数加1*/
+1;*
return
1;

2试写一个删除算法deleteV_seq(palist,在Palist所指顺序表中,删除一个值为x的
x)，元素，返回删除成功与否的标志。

【答

】

数据结构

采用

intdeleteV_seq(PseqListpalist,p,DataType

x){/*在palist所指顺序表中删除值为x的元素*/

intp,q;

for(p=0;pvn;P++)/*查找值为x的元素的下标*/
if(x==p

alist->element[p]){for(q=p;被删除元素之后的元素均前移一个位置*

qvpalist->n-1;q++)/*/
palist->element[q]=palist->element[q+1];

palist->n=palist->n-1;/*元素个数减1*/

return
1;

本文档如对你有帮助，请帮忙下载支持！

return0;

}

3.设有一线性表e=(eo,ei,e2,…，eni),其逆线性表定义为e=

(eni,