文档介绍：数据结构与算法分析课后习题答案
数据结构与算法分析课后习题答案
1 / 17
数据结构与算法分析课后习题答案
数据结构与算法分析课后习题答案
【篇一：《数据结构与算法》课后习题答案】
> 判断题
2．顺序存储的线性表可以按序号随机存取。（ √）
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素
具有相同的特性，因此属于同一数据对象。（ √）
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（ √）
8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（ √）
9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（ √）
算法设计题
1．设线性表存放在向量 a[arrsize] 的前 elenum 个分量中，且递增有序。试写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插
入 x ，最后修改表示表长的变量。
int insert (datatype a[],int *elenum,datatype x) /* 的最大下标 */ {if (*elenum==arrsize-1) return 0; /*
设 elenum 为表
表已满，无法插
数据结构与算法分析课后习题答案
数据结构与算法分析课后习题答案
17 / 17
数据结构与算法分析课后习题答案
入*/
数据结构与算法分析课后习题答案
数据结构与算法分析课后习题答案
17 / 17
数据结构与算法分析课后习题答案
else {i=*elenum;
while (i=0 a[i]x)/* 边找位置边移动 */
{a[i+1]=a[i];
i--;
a[i+1]=x;/* 找到的位置是插入位的下一位
return 1;/* 插入成功 */
}
*/ (*elenum)++;
数据结构与算法分析课后习题答案
数据结构与算法分析课后习题答案
17 / 17
数据结构与算法分析课后习题答案
}
时间复杂度为 o(n) 。
2．已知一顺序表 a，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。
【提示】对顺序表 a，从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。
void delete(seqlist *a)
{i=0;
while(ia-last)/* 将第 i 个元素以后与其值相同的元素删除 */ {k=i+1;
while(k=a-lasta-data[i]==a-data[k])
k++;/* 使 k 指向第一个与 a[i] 不同的元素 */ n=k-i-1;/*n 表示要删除
元素的个数 */
for(j=k;j=a-last;j++)
a-data[j-n]=a-data[j]; /* 删除多余元素 */
a-last= a-last -n;
i++;
}
}
3．写一个算法，从一个给定的顺序表 a 中删除值在 x~y(x=y) 之间
的所有元素，要求以较高的效率来实现。
【提示】对顺序表 a，从前向后依次判断当前元素 a-data[i] 是否介
于 x 和 y 之间，若是，并不立即删除，而是用 n 记录删除时应前移
元素的位移量；若不是，则将 a-data[i] 向前移动 n 位。 n 用来记录
当前已删除元素的个数。
void delete(seqlist *a,int x,int y)
{i=0;
n=0;
while (ia-last)
数据结构与算法分析课后习题答案
数据结构与算法分析课后习题答案
5 / 17
数据结构与算法分析课后习题答案
{if (a-data[i]=x a-data[i]=y)n++; /* 自增 */ else a-data[i-