文档介绍：2。3 课后习题解答
2。 判断题
１．线性表的逻辑顺序与存储顺序总是一致的。（×）
。(√）
，因为每次操作平均只有近一半的元素需要移动。（×）
4。线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象.（√）
5。在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻.（×）
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）
7．线性表的链式存储结构优于顺序存储结构。(×）
8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关.（√)
９。线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）
10．在单链表中，要取得某个元素,只要知道该元素的指针即可,因此，单链表是随机存取的存储结构.(×)
11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。(×）
12。线性表的特点是每个元素都有一个前驱和一个后继。(×）
2。3。3 算法设计题
[aｒｒsｉze］的前elenum个分量中,且递增有序。试写一算法,将ｘ 插入到线性表的适当位置上，以保持线性表的有序性,并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储,分配的存储空间是固定大小的,所以首先确定是否还有存储空间,若有，则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位）然后插入
x ，最后修改表示表长的变量。
int inｓeｒt （dａｔａtype A［]，iｎｔ *ｅｌenum，ｄatａtype ｘ）ﻩ ﻩ /＊设elenum为表的最大下标*/
{if （＊eｌeｎum=＝aｒｒｓizｅ-1) ｒeｔurn ０；ﻩ ﻩ ／＊表已满，无法插入*/
ｅlsｅ {i=＊elenｕｍ;
whilｅ (i＞=0 ＆& A［i]〉x） ﻩ /＊边找位置边移动*/
{A[i+１］=A［i]；
i-－;
}
Ａ[i+1］＝x；ﻩﻩ ﻩﻩ ﻩ/＊找到的位置是插入位的下一位＊／
（*elｅnuｍ）++；
return 1; ﻩ ﻩﻩ ﻩ ／＊插入成功*／
｝
｝
时间复杂度为Ｏ（n）。
２．已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素.
【提示】对顺序表A,从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。
voｉd dｅleｔe（Seｑｌist ＊A)
{i=０；
ｗｈile(i<A-〉lasｔ）ﻩ ﻩ /＊将第i个元素以后与其值相同的元素删除＊／
ﻩ {k＝ｉ＋１;
ﻩ ﻩｗhile(k<=A—＞last&＆A-〉ｄatａ[i］==Ａ—>ｄata[k］）
ﻩﻩﻩ ｋ+＋；ﻩ ﻩ／＊使ｋ指向第一个与A［i]不同的元素＊/
ﻩﻩﻩ n=k-i-1；ﻩ ﻩﻩ ﻩ/＊ｎ表示要删除元素的个数*/
ﻩ ﻩｆｏr(ｊ＝k;j＜＝A—>lasｔ；ｊ++)
ﻩﻩＡ-〉data[j－n］=Ａ－〉data[ｊ]； /＊删除多余元素*／
ﻩﻩA—>last= A-〉lａｓt －n；
ｉ++;
｝
｝
3．写一个算法，从一个给定的顺序表A中删除值在x～ｙ（x〈＝y）之间的所有元素，要求以较高的效率来实现。
【提示】对顺序表A，从前向后依次判断当前元素A-＞daｔa［ｉ］是否介于x和y之间,若是，并不立即删除,而是用n记录删除时应前移元素的位移量；若不是,则将A－〉data［i］向前移动n位。n用来记录当前已删除元素的个数。
ｖoid deｌeｔe（Seｑlｉst ＊Ａ,ｉｎt x，ｉnｔ y) ﻩ
｛i＝0;
n=０;
while (i<Ａ－＞lａsｔ）
ﻩ{if (A—＞ｄata［i]>=ｘ &＆ Ａ－>dａta[i］〈=y) n++;ﻩ/＊若A-＞dａtａ[i] 介于x和y之间，n自增*/
ﻩelse A—>ｄaｔa[ｉ—ｎ]=A—〉dａta［i］; ﻩ /＊否则向前移动A－＞data[i］＊/
ﻩi++;
ﻩ ﻩ｝
Ａ－＞ｌast－=n;
｝