【考研类试卷】计算机学科专业基础综合数据结构-线性表(二)及答案解析.doc

《【考研类试卷】计算机学科专业基础综合数据结构-线性表(二)及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机学科专业基础综合数据结构-线性表(二)及答案解析.doc（19页珍藏版）》请在麦多课文档分享上搜索。

1、计算机学科专业基础综合数据结构-线性表(二)及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：20，分数：40.00)1.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是_。 A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表（分数：2.00）A.B.C.D.2.已知两个长度分别为 l 和 s 的降序链表，若将它们合并为一个长度为 l+s 的升序链表，则最坏情况下的时间复杂度是_。 A.O(l) B.O(ls) C.O(min(l，s) D.O(max(l，s)（分数：2.0

2、0）A.B.C.D.3.线性表中存放的主要是_。 A.整型常量 B.字符 C.数据元素 D.信息元素（分数：2.00）A.B.C.D.4.下面的叙述中正确的是_。线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比 A.仅 B.仅 C.仅 D.、（分数：2.00）A.B.C.D.5.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择_存储方式最节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表（分数：2

3、.00）A.B.C.D.6.若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式中最节省时间的是_。 A.单链表 B.双链表 C.单循环链表 D.顺序表（分数：2.00）A.B.C.D.7.如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表（分数：2.00）A.B.C.D.8.算法的时间复杂度取决于_。 A.问题的规模 B.待处理数据的初态 C.A 和 B D.以上都不正确（分数：2.00）A.B.C.D.9.关于链表的特点，下面的叙述中不正确

4、的是_。 A.插入、删除运算方便 B.可实现随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比（分数：2.00）A.B.C.D.10.设线性表中有 2n 个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是_。 A.删除指定元素 B.在最后一个元素的后面插入一个新元素 C.顺序输出前 k 个元素 D.交换第 i 个元素和第 2n-i-1 个元素的值(i=0，1，n-1)（分数：2.00）A.B.C.D.11.下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入_。void reverse(pointer h) /h 为附加头结点指针point

5、er p,q;p=h-next; h-next=NULL;while(p !=null)q=p;p=p-next;q-next=h-next;h-next=(_); A.h B.p C.q D.q-next（分数：2.00）A.B.C.D.12.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为_(1in+1)。 A.O(0) B.O(1) C.O(n) D.O(n2)（分数：2.00）A.B.C.D.13.线性表(a 1，a 2，a n)以链式存储方式存储时，访问第 i 位置元素的时间复杂度为_。 A.O(i) B.O(1) C.O(n) D.O(i

6、-1)（分数：2.00）A.B.C.D.14.非空的循环单链表 head 的尾结点 p 满足_。 A.p-next=head B.p-next=NULL C.p=NULL D.p=head（分数：2.00）A.B.C.D.15.双向链表中有两个指针域，即 prior 和 next，分别指向前驱及后继，设 p 指向链表中的一个结点，q指向一个待插入结点，现要求在 p 前插入 q，则正确的插入为_。 A.p-prior=q;q-next=p;p-prior-next=q;q-prior=p-prior; B.q-prior=p-prior;p-prior-next=q;q-next=p;p-pri

7、or=q; C.q-next=p;p-next=q;p-prior-next=q;q-next=p; D.p-prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;（分数：2.00）A.B.C.D.16.静态链表中指针表示的是_。 A.内存地址 B.数组下标 C.下一元素数组下标 D.左、右孩子地址（分数：2.00）A.B.C.D.17.在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是_。 A.p-next=s;s-next=p-next; B.s-next=p-next;p-next=s： C.p-next=s;p-next=s-n

8、ext; D.p-next=s-next;p-next=s;（分数：2.00）A.B.C.D.18.对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是_。 A.head=NULL B.head-next=NULL C.head-next=head D.head!=NULL（分数：2.00）A.B.C.D.19.以下与数据的存储结构无关的术语是_。 A.循环队列 B.链表 C.哈希表 D.栈（分数：2.00）A.B.C.D.20.以下数据结构中，_是线性数据结构。 A.广义表 B.二叉树 C.稀疏矩阵 D.串（分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：14

9、，分数：60.00)21.有两个集合 A 和 B，利用带头结点链表表示，设头指针分别为 la 和 lb。两集合的链表元素皆为递增有序。设计一个算法，将 A 与 B 合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 A 和 B 的原有结点空间上完成。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。（分数：5.00）_22.线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为 x 的元素，并

10、将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。(3)分别给出算法各部分的时间复杂度。（分数：5.00）_23.已知顺序表 A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。（分数：5.00）_24.已知单链表 L

11、是一个递增有序表，试写一高效算法，删除表中值大于 min 且小于 max 的结点(若表中有这样的结点)，同时释放被删结点的空间，这里 min 和 max 是两个给定的参数。（分数：5.00）_25.线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：(1)用最少的时间在表中查找数值为 x 的元素。(2)若找到将其与后继元素位置相交换。(3)若找不到将其插入表中并使表中元素仍递增有序。（分数：4.00）_26.设有一个双链表 L，每个结点中除有 prior、data 和 next 这 3 个域外，还有一个访问频度域 freq，在链表被启用之前，

12、其值均初始化为零。每当在链表进行一次 LocateNode(L，x)运算时，令元素值为 x 的结点中 freq 域的值加 1，并调整表中结点的次序，使其按访问频度的递减排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 LcateNode 运算的算法。（分数：4.00）_27.有一个不带头结点的单链表 list，链表中结点都有两个域：数据域 data 和指针域 link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C

13、或 C+或 Java 语言描述算法，关键之处给出注释。（分数：4.00）_28.如果以单链表表示集合，设集合 A 用单链表 LA 表示，集合 B 用单链表 LB 表示，设计算法求两个集合的差，即 A-B。（分数：4.00）_29.已知 3 个带头结点的线性链表 A、B、C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表 A 进行如下操作：使操作后的链表 A 中仅留下 3 个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p)，其中 m、n 和p 分别为 3 个表的长度。（分数：4.00）_30.已知非

14、空链表 A，其指针是 list，链表中的结点由两部分组成：数据域 data 和指针域 link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：4.00）_31.已知一个双向链表，其结点结构为数据域 data、左指针域 llink、右指针域 rlink；设指针 P 指向双向链表中的某个结点。写出一个算法，实现 P 所指向的结点和它的前缀结点之间顺序的互换。要求： (1)给出算法

15、的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：4.00）_32.两个整数序列 A=a1，a 2，a 3，a n和 B=b1，b 2，b 3，b n已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。（分数：4.00）_33.已知一个带有头结点的单链表 L，其结点结构由两部分组成：数据域 data，指针域 link。设计一个算法，以最高效的方法实现在单链表中删除数据域最小值结点。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：

16、4.00）_34.设有集合 A 和集合 B，要求设计生成集合 C=AB 的算法，其中集合 A、集合 B 和集合 C 用链式存储结构表示。（分数：4.00）_计算机学科专业基础综合数据结构-线性表(二)答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：20，分数：40.00)1.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是_。 A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表（分数：2.00）A.B.C.D. 解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址

17、，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是 O(1)，所以答案是 D。2.已知两个长度分别为 l 和 s 的降序链表，若将它们合并为一个长度为 l+s 的升序链表，则最坏情况下的时间复杂度是_。 A.O(l) B.O(ls) C.O(min(l，s) D.O(max(l，s)（分数：2.00）A.B.C.D. 解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最大值。3.线性表中存放的主要是_。 A.整型常量 B.字符 C.数据元素 D.信息元素（分数：2.00）A.B.C.

18、D.解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。4.下面的叙述中正确的是_。线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比 A.仅 B.仅 C.仅 D.、（分数：2.00）A. B.C.D.解析：在线性表链式存储结构中，查找第 i 个元素的时间与 i 的位置成正比。而在顺序存储结构中查找第i 个元素的时间与 i 的位置无关。5.对于某线性表来说，主要的操作是存取任一指定序号的元素

19、和在最后进行插入运算，那么应该选择_存储方式最节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表（分数：2.00）A. B.C.D.解析：线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。6.若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式中最节省时间的是_。 A.单链表 B.双链表 C.单循环链表 D.顺序表（分数：2.00）A.B.C.D. 解析：本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链

20、表两种，其特点如下： (1)顺序表可以实现随机存取，其时间复杂度为 O(1)。但在顺序表中，进行插入和删除操作需要移动大量的元素，其时间复杂度为 O(n)； (2)链表中只能实现顺序查找，其时间复杂度为 O(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为 O(1)。 本题中，线性表中常用的操作是取第 i 个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第 i 个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第 i 个元素的前驱也不方便；双链表虽然能快速查找第 i 个元素的前驱，但不能实现随机存取。7.如果线性表中最常用的操作是在最后一

21、个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表（分数：2.00）A.B.C.D. 解析：最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。8.算法的时间复杂度取决于_。 A.问题的规模 B.待处理数据的初态 C.A 和 B D.以上都不正确（分数：2.00）A.B.C. D.解析：此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态，所以选 C。A 和 B 都不全面。9.关于链表的特点，下面的叙述中不正确的是_。

22、 A.插入、删除运算方便 B.可实现随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比（分数：2.00）A.B. C.D.解析：链表的特点包括：事先不需要申请存储空间，插入和删除运算方便，但不能实现随机存取。10.设线性表中有 2n 个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是_。 A.删除指定元素 B.在最后一个元素的后面插入一个新元素 C.顺序输出前 k 个元素 D.交换第 i 个元素和第 2n-i-1 个元素的值(i=0，1，n-1)（分数：2.00）A. B.C.D.解析：对于 A，删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样

23、的操作不需要移动元素，因此单链表的效率要高一些。 对于 B，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。 对于 C，顺序输出前 k 个元素，单链表和顺序表的效率几乎相同。 对于D，交换第 i 个元素和第 2n-i-1 个元素的值(i=0，1，n-1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。11.下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入_。void reverse(pointer h) /h 为附加头结点指针pointer p,q;p=h-next; h-next=NULL;while(p !=null)q=p;p=

24、p-next;q-next=h-next;h-next=(_); A.h B.p C.q D.q-next（分数：2.00）A.B.C. D.解析：h-next=q;表示将当前结点作为头结点后的第一元素结点插入。12.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为_(1in+1)。 A.O(0) B.O(1) C.O(n) D.O(n2)（分数：2.00）A.B.C. D.解析：此题考查的知识点是线性表基本操作的时间复杂度。顺序存储的线性表插入元素时需要从插入位置开始向后移动元素，腾出位置以便插入，平均移动次数为(n+1)/2，所以复杂度为 O(n

25、)，选 C。13.线性表(a 1，a 2，a n)以链式存储方式存储时，访问第 i 位置元素的时间复杂度为_。 A.O(i) B.O(1) C.O(n) D.O(i-1)（分数：2.00）A.B.C. D.解析：此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第 i 个位置的元素时需要从头开始向后查找，平均查找次数为(n+1)/2，所以时间复杂度为 O(n)，选 C。14.非空的循环单链表 head 的尾结点 p 满足_。 A.p-next=head B.p-next=NULL C.p=NULL D.p=head（分数：2.00）A. B.C.D.解析：此题考查的知识点是循环

26、单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点，所以选 A。B、C、D 均不能构成非空的循环单链表。15.双向链表中有两个指针域，即 prior 和 next，分别指向前驱及后继，设 p 指向链表中的一个结点，q指向一个待插入结点，现要求在 p 前插入 q，则正确的插入为_。 A.p-prior=q;q-next=p;p-prior-next=q;q-prior=p-prior; B.q-prior=p-prior;p-prior-next=q;q-next=p;p-prior=q; C.q-next=p;p-next=q;p-prior-next=q;q-next=p; D.p-

27、prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;（分数：2.00）A. B.C.D.解析：此题考查的知识点是双向链表的插入操作。在 p 前插入，要修改 p 的 prior 指针、p 的 prior 所指结点的 next 指针，所以选 A。B、C、D 都将使地址丢失，连接失败。16.静态链表中指针表示的是_。 A.内存地址 B.数组下标 C.下一元素数组下标 D.左、右孩子地址（分数：2.00）A.B.C. D.解析：静态链表中指针表示的是下一元素的数组下标。17.在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是_。 A.p-ne

28、xt=s;s-next=p-next; B.s-next=p-next;p-next=s： C.p-next=s;p-next=s-next; D.p-next=s-next;p-next=s;（分数：2.00）A.B. C.D.解析：此题考查的知识点是单链表的插入操作。要先保存 p 的后继结点，再连入 s 结点，所以选B。A、C、D 都将使地址丢失，连接失败。18.对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是_。 A.head=NULL B.head-next=NULL C.head-next=head D.head!=NULL（分数：2.00）A.B. C.D.解

29、析：此题考查的知识点是带头结点的单链表操作。带头结点的单链表空的时候表示只有一个结点存在，但没有存信息。所以选 B。A 表示没有结点，C 表示循环单链表，D 表示有一个指针不为空，所以都不对。19.以下与数据的存储结构无关的术语是_。 A.循环队列 B.链表 C.哈希表 D.栈（分数：2.00）A.B.C.D. 解析：此题考查的知识点是对数据结构和存储结构的理解。A、B、C 描述的均为物理结构即数据的存储结构，D 是逻辑结构，所以选 D。20.以下数据结构中，_是线性数据结构。 A.广义表 B.二叉树 C.稀疏矩阵 D.串（分数：2.00）A.B.C.D. 解析：此题考查的知识点是线性结构的定

30、义。线性结构的定义可简单地理解为元素只有一个前导、一个后继，而 A、B、C 有多个后继，均错，所以选 D。二、B综合应用题/B(总题数：14，分数：60.00)21.有两个集合 A 和 B，利用带头结点链表表示，设头指针分别为 la 和 lb。两集合的链表元素皆为递增有序。设计一个算法，将 A 与 B 合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 A 和 B 的原有结点空间上完成。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。（分数：5.00）_

31、正确答案：(1)算法的基本设计思想：分别从 A、B 的头结点开始，依次比较 A、B 中元素的内容，如果 A中的元素值大于 B 中的元素值，则将 B 中的结点插入结果链表，反之将 A 中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果 A、B 中两个元素值相同，只将其中的一个加入结果链表。 (2)算法的设计如下： typedef struet LNode int data; struct LNode *next; *Linkedlist; LinkedList Union(LinkedList la,lb) pa=la-next; pb=lb-next

32、; /设工作指针 pa 和 pb pc=la; /pc 为结果链表当前结点的前驱指针 while(pa pc=pa; pa=pa-next; elseif(pa-datapb-data) pc-next=pb; pc=pb; pb=pb-next; else /处理 pa-data=pb-data. pc-next=pa; pc=pa; pa=pa-next; u=pb; pb=pb-next; free(u); if(pa)pc-next=pa; /若 la 表未空，则链入结果表 else pc-next=pb; /若 lb 表未空，则链入结果表 free(lb); /释放 lb 头结点 r

33、eturn(la); (3)本题中的主要操作是依次比较 A、B 链表中的数据元素值的大小，因此时间复杂度为 O(n)。)解析：22.线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为 x 的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。(3)分别给出算法各部分的时间复杂度。（分数：5.00）_正确答案：(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找

34、。题目要求“用最少的时间在表中查找数值为 x 的元素”，这里应使用折半查找方法。(2)算法的设计如下：void SearchExchangeInsert(ElemType a,ElemType x)int low=0; int high=n-1; int mid; /low 和 high 指向线性表下界和上界的下标while(Low= high)mid = (low+high)/2; /找中间位置if(amid =x) break; /找到 x，退出 while 循环else if (amidx) low = mid+1; /到中点 mid 的右部去查else high = mid - 1;

35、/到中点 mid 的左部去查if(amid = x amid = amid+1;amid+1= t; /数值 x 与其后继元素位置交换if(low high) /查找失败，插入数据元素 xint i;for(i-n-1;ihigh;i-) ai+1=ai; /后移元素alow = x; /插入 x /结束插入(3)在利用折半查找的方法查找 x 的过程中时间复杂度为 O(nlog2n)；交换元素位置时的时间复杂度为 O(1)；当查找不成功时，插入元素时的时间复杂度为 O(n)。)解析：23.已知顺序表 A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有

36、偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。（分数：5.00）_正确答案：(1)基本的设计思想：先将偶数号元素复制到一个辅助空间，然后整理数组剩下的奇数号元素，最后将辅助空间中的元素复制到数组的后半部分，但这种思路的空间复杂度为 O(n)。另一种思路：在数组尾部从后往前找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元素“块”。暂存中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号

37、结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。暂存中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。如此继续，直到前一步的“块”前没有元素为止。(2)算法的设计如下：void Swap(ElemType A, int n)int i=n, v=1; /i 为工作指针，初始假设 n 为奇数，v 为“块”的大小ElemType temp; /辅助变量if(n%2=0) i=n-1; /若 n 为偶数，则令 i 为 n-1while(i1) /假设数组从 1 开始存放。当 i=1 时，气泡浮

38、出水面temp=Ai-1; /将“块”前的偶数号元素暂存for(int j=0; jv; j+) /将大小为 v 的“块”整体向前平移Ai-1+j=Ai+j /从前往后依次向前平移Ai+v-1=temp; /暂存的奇数号元素复制到平移后空出的位置i-; v+; /指针向前，块大小增 1/while(3)一共进行了 n/2 次交换，每次交换的元素个数从 1n/2，因此时间复杂度为 O(n2)。虽然时间复杂度为 O(n2)，但因 n2前的系数很小，实际达到的效率是很高的。算法的空间复杂度为 O(1)。)解析：24.已知单链表 L 是一个递增有序表，试写一高效算法，删除表中值大于 min 且小于 m

39、ax 的结点(若表中有这样的结点)，同时释放被删结点的空间，这里 min 和 max 是两个给定的参数。（分数：5.00）_正确答案：(struct node Datatype data; struct node * next; ListNode; typedef ListNode * LinkList; void DeleteList(LinkList L,DataType min,DataType max) ListNode *p, *q, *h; p=L-next; /采用代表头结点的单链表 while(p p=p-next; p=q; /保存这个元素位置 while(q /找比 max

40、小的最后一个元素位置 while(p-next!=q) h=p-next; p=p-next; free(h); /释放空间 p-next = q; /把断点链上 )解析：25.线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：(1)用最少的时间在表中查找数值为 x 的元素。(2)若找到将其与后继元素位置相交换。(3)若找不到将其插入表中并使表中元素仍递增有序。（分数：4.00）_正确答案：(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为 x 的元素”，这里应使用折半查找方法。 void S

41、earchExchangelnsert(ElemType a;ElemType x) /a 是具有 n 个元素的递增有序线性表，顺序存储。本算法在表中查找数值为 x 的 /元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序 low=0; high=n-1; /low 和high 指向线性表下界和上界的下标 while(low=high) mid=(low+high)/2; /找中间位置 if(amid = =x) break; /找到 x，退出 while 循环 else if(amid x) low=mid+1; /到中点 mid 的右半去查 else high=mid-1; /到中点 mid 的左半去查 if(amid = =x amid=amid+1; amid+1=t; /数值 x 与其后继元素位置交换 if(low