计算机专业基础综合(线性表)-试卷1

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.顺序表 b.双链表c.带头结点的双循环链表d.单循环链表解析

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

5、能实现顺序查找，其时间复杂度为 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) 解析：解析：对于a，删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。 对于b，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。 对于c，顺序输出前k个元素，单链表和顺序表的效率几乎相同。 对于d，交换第i个元素和第2n-i-1个元素的值(i

8、=0，1，n-1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。12.下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入( )。 voidreverse(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.hb.pc.q d.q一next解析：解析：h-next=q；表示将当前结点作为头结点后的第一元素结点插入。13.若长度为n的线性表采用顺序存储结构，在其第i个位置插入

9、一个新元素的算法的时间复杂度为( )(1in+1)。（分数：2.00）a.o(0)b.o(1)c.o(n) d.o(n )2解析：解析：此题考查的知识点是线性表基本操作的时间复杂度。顺序存储的线性表插入元素时需要从插入位置开始向后移动元素，腾出位置以便插入，平均移动次数为(n+1)2，所以复杂度为o(n)，选c。14.线性表(a ，a ，a )以链式存储方式存储时，访问第i位置元素的时间复杂度为( )。12n（分数：2.00）a.o(i)b.o(1)c.o(n) d.o(i一1)解析：解析：此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第i个位置的元素时需要从头开始向后查找

10、，平均查找次数为(n+1)2，所以时间复杂度为o(n)，选c。15.非空的循环单链表head的尾结点p满足( )。（分数：2.00）a.p一next=head b.p一next=nullc.p=nulld.p=head解析：解析：此题考查的知识点是循环单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点，所以选a。b、c、d均不能构成非空的循环单链表。16.双向链表中有两个指针域，即prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一个待插入结点，现要求在p前插入q，则正确的插入为( )。（分数：2.00）a.p一prior=q；q一next=p；p一prior一

11、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的prior指针、p的prior所指结点的next指针，所以选a。b、c、d都将使地址丢失，连接失败。 17.静态链表中指针表示的是( )。（分数：2.00）a.内存地址b.数组下标c.

12、下一元素数组下标 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一next=s一next；p一next=s；解析：解析：此题考查的知识点是单链表的插入操作。要先保存 p的后继结点，再连入s结点，所以选 b。a、c、d都将使地址丢失，连接失败。19.对于一个头指针为 head的带头结点的单链表，判定该表为空表的条件是( )

13、。（分数：2.00）a.head=nullb.head一next=null c.head一next=headd.head!=null解析：解析：此题考查的知识点是带头结点的单链表操作。带头结点的单链表空的时候表示只有一个结点存在，但没有存信息。所以选 b。a表示没有结点，c表示循环单链表，d表示有一个指针不为空，所以都不对。20.以下与数据的存储结构无关的术语是( )。（分数：2.00）a.循环队列b.链表c.哈希表d.栈 解析：解析：此题考查的知识点是对数据结构和存储结构的理解。a、b、c描述的均为物理结构即数据的存储结构，d是逻辑结构，所以选 d。21.以下数据结构中，( )是线性数据结构

14、。（分数：2.00）a.广义表b.二叉树c.稀疏矩阵d.串 解析：解析：此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导、一个后继，而 a、b、c有多个后继，均错，所以选 d。二、 综合应用题(总题数：15，分数：50.00)22.综合应用题 41-47小题。_解析：有两个集合 a和 b，利用带头结点链表表示，设头指针分别为 la和 lb。两集合的链表元素皆为递增有序。设计一个算法，将 a与 b合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 a和 b的原有结点空间上完成。要求：（分数：6.00）(1).给出算法的基本设计思想。（分数：

15、2.00） _正确答案：(正确答案：算法的基本设计思想：分别从 a、b的头结点开始，依次比较 a、b中元素的内容，如果 a中的元素值大于 b中的元素值，则将 b中的结点插入结果链表，反之将 a中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果 a、b中两个元素值相同，只将其中的一个加入结果链表。)解析：(2).根据设计思想，采用 c或 c+或 java语言描述算法，关键之处给出注释。（分数：2.00）_正确答案：(正确答案：算法的设计如下： typedef struct lnode int data： struct lnode：lcnext； *li

16、nkedlist； linkedlist union(ijnkedlist la，lb) pa=la一next； pb=lb一next； 设工作指针 pa和 pb pc=la； pc为结果链表当前结点的前驱指针 while(pa&pb) if(pa一datadata) pc一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)； i

17、f(pa)pc-next=pa； 若 la表未空，则链入结果表 else pc-next=pb； 若 lb表未空，则链入结果表 free(lb)； 释放 lb头结点 return(la)； )解析：(3).分别给出算法各部分的时间复杂度。（分数：2.00）_正确答案：(正确答案：本题中的主要操作是依次比较 a、b链表中的数据元素值的大小，因此时间复杂度为 o(n)。)解析：线性表(a ，a ，a ，a )中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时123间在表中查找数值为 x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素n插入表中并使表中元素仍递增有序

18、。（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_正确答案：(正确答案：顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为 x的元素”，这里应使用折半查找方法。)解析：(2).根据设计思想，采用 c或 c+或 java语言描述算法，关键之处给出注释。（分数：2.00）_正确答案：(正确答案：算法的设计如下：void search：exchangeinsert(elemtype a，elemtype x) intlow=0；inthigh=n-l；int mid； low和 high指向线性表下界和上界的下标while(lowhig

19、h；i一一) ai+1=ai；后移元素 alow=x； 插入 x 结束插入 )解析：(3).分别给出算法各部分的时间复杂度。（分数：2.00）_正确答案：(正确答案：在利用折半查找的方法查找 x的过程中时间复杂度为 o(nlog n)；交换元素位置2时的时间复杂度为 o(1)；当查找不成功时，插入元素时的时间复杂度为 o(n)。)解析：已知顺序表 a，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_正确答案：(正确答案：基本的设计思想：先将偶数号元素复制到一个辅助空间，

20、然后整理数组剩下的奇数号元素，最后将辅助空间中的元素复制到数组的后半部分，但这种思路的空间复杂度为 o(n)。 另一种思路： 在数组尾部从后往前找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成 了两个前后相连且相对顺序不变的奇数号元素“块”。暂存中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。暂存中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。如此继续，直到前一步的“块”前没有元素为止。)解析

21、：(2).根据设计思想，采用c或c+或java语言描述算法，关键之处给出注释。（分数：2.00）_正确答案：(正确答案：算法的设计如下： void swap(elemtype a，int n) int i=nv=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）_正确答案：(正确答案：一共

22、进行了n2次交换，每次交换的元素个数从1n2，因此时间复杂度为o(n)。虽然时间复杂度为o(n )，但因n 前的系数很小，实际达到的效率是很高的。算法的空间复杂度222为o(1)。)解析：23.已知单链表l是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。（分数：2.00）_正确答案：(正确答案：struet node datatype data； struct node*next； listnode； typedeflistnode*linklist： void deletelist(l

23、inklist l，datatype min，datatype max) listnode*p，*q，*h； p=l一next： 采用代表头结点的单链表 while(p&p一datanext： p=q： 保存这个元素位置 while(q&q一datanext；找比max小的最后一个元素位置 while(p-next!=q) h=p-next； p=p一next： free(h)； 释放空间 p一next=q； 把断点链上 )解析：线性表(a ，a ，a ，a )中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内31容：（分数：4.00）2n(1).用最少的时间在表中查找数值为x的元素

24、。若找到将其与后继元素位置相交换。（分数：2.00）_正确答案：(正确答案：顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。void searchexchangelnsert(elemtype a；elemtype x) a 是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的 元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序 low=0： high=n-1； low和high指向线性表下界和上界的下标 while(lowhigh；i一一) ai+1=ai； 后移元素 ai+1

25、=x； 插入 x 结束插入 结束本算法)解析：(2).若找不到将其插入表中并使表中元素仍递增有序。（分数：2.00）_正确答案：(正确答案：算法讨论 首先是线性表的描述。算法中使用一维数组a表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体，对元素的引用应使用aelemi。另外，元素类型就假定是elemtype，未指明具体类型。其次，c中一维数组下标从0开始，若说有n个元素的一 维数组，其最后一个元素的下标应是 n-1。最后，本算法可以写成三个函数，即查找函数、交换后继函数与插入函数，写成三个函数显得逻辑清晰、易读。)解析：24.设有一个双链表 l，每个结点中除有

26、prior、data和 next这 3个域外，还有一个访问频度域 freq，在链表被启用之前，其值均初始化为零。每当在链表进行一次 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

27、，elemtype x) l是带头结点的按访问频度递减的双向链表 dlist p=l一next，q； p为 l表的工作指针，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一

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

29、从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。)解析：(2).根据设计思想，采用 c或 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

30、) r=p一link； r是 p的后继 q=list； if(q一datap一data) 处理待排序结点 p比第一个元素结点小的情况 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）_正确答案：(正确答案：由集

31、合运算的规则知，集合的差 ab为包含所有属于 a而不属于 b的元素，因此，算法的思路在于对于所有属于集合 a中的元素 e，在集合 b中进行查找，若能找到，则说明它不属于 a一 b，应从 la中删除。若 la的长度为 o(n)，lb的长度为 o(m)，则该算法的时间复杂度为 o(mn)。 算法参考伪代码如下： 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； 遍

32、历 lb表，判断 la中元素是否在 lb中 node*while(q!=null&q一data!=-data)q=q一next if(q!=null)在 lb中找到相同结点元素，则应在 la中删除该结点 r=p： pre一next=r 一next： p=p一next； free(r)； else未能找到，说明该结点属于 ab。继续在 la中对下一个元素进行判断 pre=p； p=p一next： )解析：26.已知 3个带头结点的线性链表 a、b、c中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表 a进行如下操作：使操作后的链表 a中仅留下 3个表中均包含的数

33、据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 o(m+n+p)，其中 m、n和 p分别为 3个表的长度。（分数：2.00）_正确答案：(正确答案：typedef struct lnode int data；struct lnode*next：*linkedlist；linkedlistcommon(linkedlist a，b，c) 链表 a、链表 b和链表 c是三个带头结点且结点元素值非递减排列的有序表 本算法使链表 a仅留下三个表均包含的结点，且结点值不重复，释放所有结点 linkedlist*pa，*pb，*pc，*pre，*u； pa=a一next；pb

34、=b一next；pc=c一next； pa，pb，pc分别是链表 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当前结点

35、值不等，pa后移指针 if(pc一datapa一data)u=pa；pa=pa一next；free(u)； elsepc、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(p

36、a=null)pre-next=null； 原链表 a已到尾，置新链表 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).给出算法的基本设计思想。（分数

37、：2.00）_正确答案：(正确答案：算法的基本设计思想：首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下(不是删除并回收空间)，再插入到链表的最前面。)解析：(2).根据设计思想，采用 c或 c+或 java语言描述算法，关键之处给出注释。（分数：2.00）_正确答案：(正确答案：算法的实现如下： typedef struct lnode char data； structlnode*link； *linkedlist； linkedlist delinsert(linkedlist list)将链表中数据域值最小的那个结点移到链表的最前面 linkedlist*p，*p

38、re，*q；p=list-link;p是链表的工作指针 pre=list;pre指向链表中数据域最小值结点的前驱 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、左指针

39、域 llink、右指针域 rlink；设指针 p指向双向链表中的某个结点。写出一个算法，实现 p所指向的结点和它的前缀结点之间顺序的互换。要求：（分数：4.00）(1).给出算法的基本设计思想。（分数：2.00） _正确答案：(正确答案：算法的基本思想：已知双向循环链表中的一个结点 p，与前驱交换涉及 4个结点(p结点，前驱结点，前驱的前驱结点，后继结点)、6条链。)解析：(2).根据设计思想，采用 c或 c+或 java语言描述算法，关键之处给出注释。（分数：2.00）_正确答案：(正确答案：算法的设计如下： typedef struct dulnode int data； struct d

40、ulnode*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 ，a ，a ，a 和 b=b ，b ，b ，b 已经存入两个单链表中，212设计一个算法，判断序列 b是否是序列 a的子序列。3n13n（分数：2.00）_正确答案：(正确答案：typedef struct lnode int data； struct lnode*next； *linkedlist； intpattern(linkedlist a，b) a和 b分别是数据域为整数的单链表，本算法判断链表 b是否