数据结构与算法课后习题解答.docx

数据结构与算法课后习题解答

数据结构与算法课后习题解答

第一章绪论（参考答案）

1.3(1)O(n)

(2)(2)O(n)

(3)(3)O(n)

(4)(4)O(n1/2)

(5)(5)执行程序段的过程中，x,y值变化如下：

循环次数xy

0（初始）91100

192100

293100

。。

9100100

10101100

1191

12

。

2099

219198

。。

3010198

319197

到y=0时，要执行10*100次，可记为O（10*y）=O（n）

数据结构与算法课后习题解答

1.52100,(2/3)n,log2n,n1/2,n3/2,(3/2)n,nlog2n,2n,n!,nn

第二章线性表(参考答案)

在以下习题解答中，假定使用如下类型定义：

（1）顺序存储结构：

#define*****1024

typedefintElemType;//实际上，ElemType

typedefstruct

{ElemTypedata[*****];

intlast;//last

}sequenlist;

（2

*next；

}linklist;

（3）链式存储结构（双链表）

typedefstructnode

{ElemTypedata;

structnode*prior,*next；

数据结构与算法课后习题解答

}dlinklist;

（4）静态链表

typedefstruct

{ElemTypedata;

intnext;

}node;

nodesa[*****];

2.1la，往往简称为“链表la”。

是副产品）

2.223

void

elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的

{inti=0,j;

while(ielenumA[i]=x)i++;//查找插入位置

for(j=elenum-1;jj--)A[j+1]=A[j];//向后移动元素

A[i]=x;//插入元素

数据结构与算法课后习题解答

}//算法结束24

voidrightrotate(ElemTypeA[],intn,k)

//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

{intnum=0;//计数，最终应等于n

intstart=0;//记录开始位置（下标）

while(numn)

{temp=A[start];//暂存起点元素值，temp

empty=start;//保存空位置下标

next=(start-K+n)%n;//

while(next!=start)

{A[empty]=A[next];//

num++;1

//计算新右移元素的下标

//把一轮右移中最后一个元素放到合适位置

num++;

start++;//起点增1，若numn则开始下一轮右移。}

}//算法结束

数据结构与算法课后习题解答

算法二

算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。

voidrightrotate(ElemTypeA[],intn,k)

//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

{ElemTypetemp;

for(i=0;i(n-k)/2;i++)//左面n-k个元素逆置

{temp=A[i];A[i]=A[n-k-1-i];A[n-k-1-i]=temp;}

for(i=1;ii++)//右面k个元素逆置

{temp=A[n-k-i];A[n-k-i]=A[n-i];A[n-i]=temp;}

for(i=0;ii++)//全部n个元素逆置

{t