2022年2022年计算机专业基础综合-试卷 3.pdf

《2022年2022年计算机专业基础综合-试卷 3.pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机专业基础综合-试卷 3.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机专业基础综合（线性表）-试卷 1(总分：92.00，做题时间：90 分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_ 解析：2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是()。（分数：2.00）A.单链表B.带有头指针的单循环链表C.双链表D.带有尾指针的单循环链表解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环

2、链表中删除第一个结点，其时间性能是O(1)，所以答案是D。3.已知两个长度分别为l 和 s 的降序链表，若将它们合并为一个长度为l+s 的升序链表，则最坏情况下的时间复杂度是()。（分数：2.00）A.O(l)B.O(ls)C.O(min(l，s)D.O(max(l，s)解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和 n 中的最大值。4.线性表中存放的主要是()。（分数：2.00）A.整型常量B.字符C.数据元素D.信息元素解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。

3、5.下面的叙述中正确的是()。线性表在链式存储时，查找第i 个元素的时间同i 的值成正比线性表在链式存储时，查找第i 个元素的时间同i 的值无关 线性表在顺序存储时，查找第i 个元素的时间同 i 的值成正比（分数：2.00）A.仅B.仅C.仅D.、解析：解析：在线性表链式存储结构中，查找第i 个元素的时间与i 的位置成正比。而在顺序存储结构中查找第 i 个元素的时间与i 的位置无关。6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择()存储方式最节省时间。（分数：2.00）A.顺序表名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页

4、-B.双链表C.带头结点的双循环链表D.单循环链表解析：解析：线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。7.若线性表最常用的运算是查找第i 个元素及其前驱的值，则下列存储方式中最节省时间的是()。（分数：2.00）A.单链表B.双链表C.单循环链表D.顺序表解析：解析：本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，其特点如下：(1)顺序表可以实现随机存取，其时间复杂度为O(1)。但在顺序表中，进行插入和删除操作需要移动大量的元

5、素，其时间复杂度为O(n)；(2)链表中只能实现顺序查找，其时间复杂度为O(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为O(1)。本题中，线性表中常用的操作是取第i 个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第i 个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第i 个元素的前驱也不方便；双链表虽然能快速查找第 i 个元素的前驱，但不能实现随机存取。8.如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。（分数：2.00）A.单链表B.仅有头指针的单循环链表C.双链表D.

6、仅有尾指针的单循环链表解析：解析：最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。9.算法的时间复杂度取决于()。（分数：2.00）A.问题的规模B.待处理数据的初态C.A 和 B D.以上都不正确解析：解析：此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态，所以选C。A和 B都不全面。10.关于链表的特点，下面的叙述中不正确的是()。（分数：2.00）A.插入、删除运算方便B.可实现随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比解析：解析：链表的特点包括：事先不需要申请存储空间，插入和删

7、除运算方便，但不能实现随机存取。11.设线性表中有2n 个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是()。（分数：2.00）A.删除指定元素B.在最后一个元素的后面插入一个新元素C.顺序输出前 k 个元素D.交换第 i 个元素和第 2n-i-1个元素的值(i=0，1，n-1)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -解析：解析：对于A，删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。对于 B，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。对于 C，顺序

8、输出前k 个元素，单链表和顺序表的效率几乎相同。对于 D，交换第 i 个元素和第2n-i-1个元素的值(i=0，1，n-1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。12.下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入()。void reverse(pointer h)h 为附加头结点指针 pointer p，q；P=h 一next：h 一next=NULL；while(P!=null)q=P：P=P 一next：q-next=h一next；h-next=(_)；（分数：2.00）A.h B.P C.q D.q 一next 解析：解析：h-next=q；

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

10、解析：解析：此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第i 个位置的元素时需要从头开始向后查找，平均查找次数为(n+1)2，所以时间复杂度为O(n)，选 C。15.非空的循环单链表head 的尾结点 P满足()。（分数：2.00）A.P 一next=head B.p 一next=NULL C.P=NULL D.P=head 解析：解析：此题考查的知识点是循环单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点，所以选 A。B、C、D 均不能构成非空的循环单链表。16.双向链表中有两个指针域，即prior和 next，分别指向前驱及后继，设P指向链表中的一个结点，q

11、 指向一个待插入结点，现要求在P 前插入 q，则正确的插入为()。（分数：2.00）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 一prior一next=q；q 一next=p；q 一prior=p一prior；p 一prior=q；解析：解析：此题考查的知识点是双向链表的插入操作。在p 前插入，要修改p 的 prio

12、r指针、p 的 prior所指结点的 next 指针，所以选A。B、C、D都将使地址丢失，连接失败。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -17.静态链表中指针表示的是()。（分数：2.00）A.内存地址B.数组下标C.下一元素数组下标D.左、右孩子地址解析：解析：静态链表中指针表示的是下一元素的数组下标。18.在单链表指针为P的结点之后插入指针为s 的结点，正确的操作是()。（分数：2.00）A.p-next=s；s-next=p 一next；B.s 一next=p 一next；p 一next=s；C.p-next=s：p-next=s 一next；D.p

13、一next=s 一next；p 一next=s；解析：解析：此题考查的知识点是单链表的插入操作。要先保存 p 的后继结点，再连入s 结点，所以选 B。A、C、D都将使地址丢失，连接失败。19.对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是()。（分数：2.00）A.head=NULL B.head 一next=NULL C.head 一next=head D.head!=NULL 解析：解析：此题考查的知识点是带头结点的单链表操作。带头结点的单链表空的时候表示只有一个结点存在，但没有存信息。所以选B。A表示没有结点，C 表示循环单链表，D表示有一个指针不为空，所以都不对。

14、20.以下与数据的存储结构无关的术语是()。（分数：2.00）A.循环队列B.链表C.哈希表D.栈解析：解析：此题考查的知识点是对数据结构和存储结构的理解。A、B、C描述的均为物理结构即数据的存储结构，D是逻辑结构，所以选D。21.以下数据结构中，()是线性数据结构。（分数：2.00）A.广义表B.二叉树C.稀疏矩阵D.串解析：解析：此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导、一个后继，而A、B、C 有多个后继，均错，所以选D。二、综合应用题(总题数：15，分数：50.00)22.综合应用题41-47 小题。_ 解析：有两个集合 A 和 B，利用带头结点链表

15、表示，设头指针分别为la 和 lb。两集合的链表元素皆为递增有序。设计一个算法，将A与 B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 A 和 B 的原有结点空间上完成。要求：（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -_ 正确答案：(正确答案：算法的基本设计思想：分别从A、B的头结点开始，依次比较A、B 中元素的内容，如果 A中的元素值大于B中的元素值，则将B 中的结点插入结果链表，反之将A中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递

16、增地排列。因此，如果 A、B中两个元素值相同，只将其中的一个加入结果链表。)解析：(2).根据设计思想，采用C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法的设计如下：typedef struct LNode int data：struct LNode：lc next；*Linkedlist；LinkedList Union(IJnkedList la，lb)pa=la一next；pb=lb一next；设工作指针pa 和 pb pc=la；pc 为结果链表当前结点的前驱指针 while(pa&pb)if(pa一datadata )pc

17、一next=pa；pc=pa；pa=pa一next；else if(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 头结点 return(la)；)解析：(3).分别给出算法各部分的时间复杂度。（分数：2.00）_ 正确答案：(正确答案：本题

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

19、言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法的设计如下：void Search：ExchangeInsert(ElemType a，ElemType x)int low=0；int high=n-l；int mid；low 和 high 指向线性表下界和上界的下标while(lowhigh；i 一一)ai+1=ai；后移元素 alow=x；插入 x 结束插入 )解析：(3).分别给出算法各部分的时间复杂度。（分数：2.00）_ 正确答案：(正确答案：在利用折半查找的方法查找x 的过程中时间复杂度为O(nlog 2 n)；交换元素位置时的时间复杂度为O(1)；当

20、查找不成功时，插入元素时的时间复杂度为O(n)。)解析：已知顺序表 A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_ 正确答案：(正确答案：基本的设计思想：先将偶数号元素复制到一个辅助空间，然后整理数组剩下的奇数号元素，最后将辅助空间中的元素复制到数组的后半部分，但这种思路的空间复杂度为O(n)。另一种思路：在数组尾部从后往前找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -

21、了两个前后相连且相对顺序不变的奇数号元素“块”。暂存中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。暂存中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。如此继续，直到前一步的“块”前没有元素为止。)解析：(2).根据设计思想，采用C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法的设计如下：void Swap(ElemType A，int n)int i=n

22、v=1：i 为工作指针，初始假设n 为奇数，v 为“块”的大小ElemType temp：辅助变量if(n2=0)i=n-1；若 n 为偶数，则令 i 为 n-1 while(i1)假设数组从1开始存放。当 i=1 时，气泡浮出水面temp=Ai-1；将“块”前的偶数号元素暂存 for(int j=0；j 解析：(3).说明你所设计算法的时间复杂度和空间复杂度。（分数：2.00）_ 正确答案：(正确答案：一共进行了n2 次交换，每次交换的元素个数从1n2，因此时间复杂度为O(n 2)。虽然时间复杂度为O(n 2)，但因 n 2前的系数很小，实际达到的效率是很高的。算法的空间复杂度为 O(1)。

23、)解析：23.已知单链表L 是一个递增有序表，试写一高效算法，删除表中值大于min 且小于 max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。（分数：2.00）_ 正确答案：(正确答案：struet 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一da

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

25、应使用折半查找方法。void SearchExchangelnsert(ElemType a ；ElemType x)a是具有 n 个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x 的 元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序 low=0：high=n-1；low和 high 指向线性表下界和上界的下标 while(lowhigh；i 一一)ai+1=ai；后移元素 ai+1=x；插入 x 结束插入 结束本算法)解析：(2).若找不到将其插入表中并使表中元素仍递增有序。（分数：2.00）_ 正确答案：(正确答案：算法讨论首先是线性表的描述。算法中使用一维

26、数组a 表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体，对元素的引用应使用aelemi。另外，元素类型就假定是ElemType，未指明具体类型。其次，C中一维数组下标从0 开始，若说有n 个元素的一名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -维数组，其最后一个元素的下标应是n-1。最后，本算法可以写成三个函数，即查找函数、交换后继函数与插入函数，写成三个函数显得逻辑清晰、易读。)解析：24.设有一个双链表L，每个结点中除有prior、data 和 next 这 3 个域外，还有一个访问频度域freq，在链表被启用之前，其值均初始化为

27、零。每当在链表进行一次LocateNode(L，x)运算时，令元素值为x 的结点中 freq域的值加 1，并调整表中结点的次序，使其按访问频度的递减排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode 运算的算法。（分数：2.00）_ 正确答案：(正确答案：typedef struct DuLNode ElemType data；int freq；struct DuLNode*pred，*next；*DList；DList locate(DList L，ElemType x)L 是带头结点的按访问频度递减的双向链表 DList p=L一next，q；p 为 L 表的

28、工作指针，q 为 P 的前驱，用于查找插入位置 whileP&p一data!=x)p-p-next；查找值为x 的结点if(!p)pfintf(”不存在所查结点 n”)；exit(0)；else p一freq+；令元素值为x 的结点的 freq 域加 1 p 一next 一pred=p 一pred；将 P结点从链表上摘下 p-pred一next=p 一next；q=P 一pred；以下查找P结点的插入位置while(q!=L&q-freqfreq)q=q一pred；p 一next=q 一next；q 一next-pred-p；将 P结点插入p-pred=q；q 一next=P；return(p

29、)；返回值为x 的结点的指针 )解析：有一个不带头结点的单链表list，链表中结点都有两个域：数据域data 和指针域 link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求：（分数：4.00）(1).给出算法的基本设计思想。（分数：2.00）_ 正确答案：(正确答案：算法的基本设计思想：本题实质上是一个排序问题。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。)解析：(2).根据设计思想，采用C 或

30、C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法设计如下：typedef struct LNode int data；struct LNode*link；*linkedlist；LinkedList LinkListSort(LinkedList list)Lnode*P，*q；p=list一link；p 是工作指针，指向待排序的当前元素 list一link=null：假定第一个元素有序，即链表中现只有一个结点while(P!=null)r=p一link；r 是 P的后继 q=list；if(q一datap 一data)处理待排序结点 P比第一

31、个元素结点小的情况 p-link=list；list=P：链表指针指向最小元素 else 查找元素值最小的结点while(q一link=null&q-link-datadata)q=q一link；p 一link=q一link；将当前排序结点链入有序链表中 q-link=p；p=r；p 指向下个待排序结点 )解析：25.如果以单链表表示集合，设集合 A用单链表 LA表示，集合 B 用单链表 LB表示，设计算法求两个集合的差，即 A-B。（分数：2.00）_ 正确答案：(正确答案：由集合运算的规则知，集合的差 AB为包含所有属于A 而不属于 B的元素，因此，算法的思路在于对于所有属于集合A 中的元

32、素 e，在集合 B中进行查找，若能找到，则说明它不属于A 一 B，应从 LA中删除。若LA的长度为 O(n)，LB 的长度为 O(m)，则该算法的时间复杂度为O(m n)。算法参考伪代码如下：void Difference(LinkList*LA，LinkList*LB)设 LA，LB均具有头结点 Node*pre，*P，*r；pre=LA：p=LA-next；p指向 LA表中的某一结点，而 pre 指向 P的前面一个结点while(P!=NULL)q=LB-next；遍历 LB表，判断 LA中元素是否在LB中 Node*while(q!=NULL&q一data!=-data)q=q 一nex

33、t if(q!=NULL)在 LB中找到相同结点元素，则应在LA 中删除该结点r=P：pre 一next=r名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -一next：P=P一next；free(r)；else未能找到，说明该结点属于AB。继续在 LA 中对下一个元素进行判断 pre=P；P=P 一next：)解析：26.已知 3 个带头结点的线性链表A、B、C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表A进行如下操作：使操作后的链表A中仅留下 3 个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法

34、的时间复杂度为O(m+n+p)，其中 m、n 和 p分别为 3 个表的长度。（分数：2.00）_ 正确答案：(正确答案：typedef struct LNode int data；struct LNode*next：*Linkedlist；LinkedList Common(LinkedList A，B，C)链表 A、链表 B和链表 C是三个带头结点且结点元素值非递减排列的有序表 本算法使链表A仅留下三个表均包含的结点，且结点值不重复，释放所有结点Linkedlist*pa，*pb，*pc，*pre，*u；pa=A 一next；pb=B一next；pc=C一next；pa，pb，pc 分别是链

35、表 A，B，C的工作指针 pre=A；pre 是链表 A 中当前结点的前驱结点的指针 while(pa&pb&pc)当链表A，B和 C均不空时，查找三链表共同元素while(pa&pb)if(pa一datadata)u=pa；pa=pa-next；free(u)；结点元素值小时，后移指针 else if(pa-datapb-data)pb=pb-next；else if(pa&pb)处理链表 A 和 B 元素值相等的结点 while(pc&pc 一datadata)pc=pc一next；if(pc)pc 当前结点值与 pa当前结点值不等，pa后移指针 if(pc一datapa 一data)u=

36、pa；pa=pa一next；free(u)；else pc、pa 和 pb 对应结点元素值相等 if(pre=A)pre一next=pa；pre=pa；pa=pa-next；结果表中第一个结点else if(pre一data=pa 一data)(处理)重复结点不链入链表A u=pa；pa=pa-next；free(u)；elsepre一next=pa；pre=pa；pa=pa-next；将新结点链入链表A pb=pb 一next：pc=pc一next；链表的工作指针后移 else pc，pa 和 pb 对应结点元素值相等 if(pa=null)pre-next=null；原链表A已到尾，置新链

37、表A表尾 else 处理原链表A 未到尾而链表 B 或链表 C 到尾的情况pre 一next=null：置链表A表尾标记 while(pa!=null)u=pa；pa=pa一next；free(u)；删除原链表A剩余元素 )解析：已知非空链表A，其指针是list，链表中的结点由两部分组成：数据域data 和指针域 link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求：（分数：4.00）(1).给出算法的基本设计思想。（分数：2.00）_ 正确答案：(正确答案：算法的基本设计思想：首先要查找最小值结

38、点。将其移到链表最前面，实质上是将该结点从链表上摘下(不是删除并回收空间)，再插入到链表的最前面。)解析：(2).根据设计思想，采用C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法的实现如下：typedef struct LNode char data；struct LNode*link；*Linkedlist；LinkedList delinsert(LinkedList list)将链表中数据域值最小的那个结点移到链表的最前面Linkedlist*P，*pre，*q；P=list-link;p 是链表的工作指针pre=list;pr

39、e 指向链表中数据域最小值结点的前驱 q=P;q 指向数据域最小值结点，初始假定是第一结点while(p-link!=null)if(p一link一datadata)pre=P；q=p-link；找到新的最小值结点P=p-link；if(q!=list一link)若最小值是第一元素结点，则不需再操作pre 一link=q一link；将最小值结点从链表上摘下 q 一link=list一link；将 q 结点插到链表最前面 list一link=q；算法结束)解析：已知一个双向链表，其结点结构为数据域data、左指针域llink、右指针域rlink；设指针 P指向双向链表中的某个结点。写出一个算法，

40、实现P 所指向的结点和它的前缀结点之间顺序的互换。要求：（分数：4.00）(1).给出算法的基本设计思想。（分数：2.00）名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -_ 正确答案：(正确答案：算法的基本思想：已知双向循环链表中的一个结点P，与前驱交换涉及4 个结点(P结点，前驱结点，前驱的前驱结点，后继结点)、6 条链。)解析：(2).根据设计思想，采用C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法的设计如下：typedef struct DuLNode int data；struct DuLNode*

41、llink，*rlink：DuLNode*Linkedlist；void Exchange(LinkedList P)将 P所指结点与其前驱结点交换Linkedlist*q；q=p-llink；q 一llink一rlink=P；p 的前驱的前驱之后继为P p 一llink=q一llink；p 的前驱指向其前驱的前驱 q 一rlink=p一rlink；p 的前驱的后继为P的后继 q一llink=P；p 与其前驱交换 P 一rlink一llink=q；p 的后继的前驱指向原P的前驱 p一rlink=q；p 的后继指向其原来的前驱)解析：27.两个整数序列A=a 1，a 2，a 3，a n和 B=b

42、 1，b 2，b 3，b n已经存入两个单链表中，设计一个算法，判断序列B 是否是序列 A 的子序列。（分数：2.00）_ 正确答案：(正确答案：typedef struct LNode int data；struct LNode*next；*Linkedlist；int Pattern(LinkedList A，B)A和 B分别是数据域为整数的单链表，本算法判断链表B是否是链表 A 的子序列。如是，返回1；否则，返回0，表示失败。Linkedlist*P，*pre，*q：p=A；p 为链表 A 的工作指针，本题假定链表A和链表 B均无头结点 pre=p；pre 记住每趟比较中链表A的开始结点

43、 q=B；q 是链表 B的工作指针 while(p&q)if(p一data=q 一data)P=p-next；q=q-next；else pre=pre-next；P=pre；链表A新的开始比较结点 q=B；q 从链表 B 第一结点开始if(q=null)return(1)；链表 B是链表 A的子序列 else return(0)；链表 B不是链表 A的子序列 算法结束)解析：已知一个带有头结点的单链表L，其结点结构由两部分组成：数据域data，指针域 link。设计一个算法，以最高效的方法实现在单链表中删除数据域最小值结点。要求：（分数：4.00）(1).给出算法的基本设计思想。（分数：2.

44、00）_ 正确答案：(正确答案：算法的基本思想：单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。)解析：(2).根据设计思想，采用C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法的设计如下：typedef struct LNode int data；struct LNode*next；LNode*Linkedlist；LinkedList Delete(LinkedList L)L 是带头结点的单链

45、表，本算法删除其最小值结点 Linkedlist木 P，*q，*pre；P=L 一next;p 为工作指针，指向待处理的结点。假定链表非空 pre=L;pre 指向最小值结点的前驱 q=P;q 指向最小值结点，初始假定第一元素结点是最小值结点 while(p一next!=null)if(P一next 一datadata)f pre=P;q=P-next；查最小值结点 P=P 一next;指针后移 pre一next-q一next；从链表上删除最小值结点free(q)；释放最小值结点空间 结束算法delete)解析：28.设有集合 A 和集合 B，要求设计生成集合C=A B 的算法，其中集合 A、

46、集合 B和集合 C用链式存储结构表示。（分数：2.00）_ 正确答案：(正确答案：typedef struct node int data；struct node*next；lklist；void 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -intersection(1klist*ha，lklist*hb，lklist*&hc)lklist*P，*q;*t；for(P=ha，hc=NULL；P!=NULL；P=p一next)for(q=hb；q!=NULL；q=q 一next)if(q-data=p-data)break；if(q!=NULL)t=(1klist*)malloc(sizeof(lklist)；t-data=p-data；t 一next=hc；hc=t；)解析：名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -