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

算法与数据结构C语言
习题参考答案章
集团标准化工作小组#Q8QGGQT-GQ8-GNQGJ8-MHHGN#
*
a片
L结论

1.将下列好杂度由小到大重新排序：

A.TB.C.n5D.10000
E.7Z*10g2(//)

【答】10000<n*log2(n)<n5<

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

A.n*log2(/i)B.n+n2+n3C.24D.

【答】24<</?*log(；7)<n+n2+
2

3.用大“O”表示法描述下列复杂度：
：(/?)
A.5n5f2+n1/5B.6*log
+9〃
C.3〃'+〃*log2(〃)
D.5n2+-
【答】A:OQ产)B:O(n)
D:0(2
4•按照增长率从低到高的顺序排列以下表达式：4112,log3n,3n,20n,2000,log2n,n2/3o又n!
应排在第几位

【答】按照增长率从低到高依次为：，，产，20〃，4n2。
〃！的增长率比它们中的每一个都要大，应排在最后一位。

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

inti-l;

while(i<-n)
(

i-i+1;

)

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

中第一句pdntf执行n次，第二句i从1循环到n,共执行n次。所以该程序段总的时间代价为：
T(n)=1+/?+2n=3〃+1=0(n)

6.计算下列程序片断的时间代价：

inti-l;

while(i<-n)
(

rntj-1;

while(j<-n)
{

mtk-1;

while(k<-n)
}

J-j十1;

i-i十1;

)

【答】循环控制变量i从1增加到n,最外层循环体执行n次，循环控制变量j从1增加到n,中间层循环体执行

n次，编环控制变量k从1增加到n,最内层循环体执行n次，所以该程序段总的时间代价为：
T(n)=1十〃十〃{1十〃十;?[1十〃+2n+1]+1+1}+1
=3〃3+3//+4/7+2

=。(〃3)
2.线性表

1.试写一个插入算法mtuiseitPost_seq(palist,p,x),在palist所指顺序表中，下标为p的元素之后，
插入一个值为x的元素，返回插入成功与否的标志。
【答】
数据结构
采用2.1.2节中顺序表定义。

mtmseitPost_seq(PseqListpalist.mtp,DataTypex){

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

if(pahst->n>-palist-〉MAXNUM){/*溢出率/

pnntf「；return0;)

if(p<0||p>palist->n-l){/*不存在下标为p的元素*/

piintff'Notexist!加')；return0;
)

for(q-palist->n-1;q>-p-rl:q--)/*插入位置及之后的元素均后移一个位置.♦/

palist->element[q+1]-palist->element[q];

palist->element[p-M]-x;/*插入元素x

palist->n-palist->n+1;元素个数加1*/

return1;)

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

mtdeleteV_seq(PseqListpalist,p、DataTypex){片在pahst所指顺序表中删除值为x的元素*/mtp,q:fo1(p-0:p<n:pH)/*

查找值为x的元素的下标号

if<x-palist->element[p]){

fbr(q-p:q<palist->n-l;q-H-)/*被删除元素之后的元素均前移一个位置*/palist->element[q]-palist->element[q+l];

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

renirn1;

)return0;)
3.设有一线性表e=(e,ei,e,--,e),其逆线性表定义为e=(e，…，e?,q，⑹。请设计一个算
02nini
法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的空间。
【答】
数据结构
采用2.1.2节中顺序表的定义。
思路

考虑对数组element□进行置逆，即把第一个元素和最后一个元素换位置，把第二个元素和倒数第二个元素换
位气……。

注意

这种调换的工作只需对数组的前一半元素进行，所以设置整数变量count用于存放数组长度的一半的值。大家可以考虑
一下：为什