[考研类试卷]计算机专业基础综合数据结构（线性表）历年真题试卷汇编1及答案与解析.doc

《[考研类试卷]计算机专业基础综合数据结构（线性表）历年真题试卷汇编1及答案与解析.doc》由会员分享，可在线阅读，更多相关《[考研类试卷]计算机专业基础综合数据结构（线性表）历年真题试卷汇编1及答案与解析.doc（40页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 1 及答案与解析一、单项选择题1 线性表是具有 n 个_的有限序列(n0)。【清华大学 1998 年】（A）表元素（B）字符（C）数据元素（D）数据项2 一个顺序表所占用的存储空间大小与无关。【北京航空航天大学 2004 年】（A）表的长度（B）元素的存放顺序（C）元素的类型（D）元素中各字段的类型3 线性表的顺序存储结构是一种_。【北京理工大学 2006 年】（A）随机存取的存储结构（B）顺序存取的存储结构（C）索引存取的存储结构（D）Hash 存取的存储结构4 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。【青岛大学

2、2000 年】（A）0(n)0(n)（B） 0(n)0(1)（C） 0(1)0(n)（D）0(1)0(1)5 若长度为 n 的非空线性表采用顺序存储结构，删除表的第 i 个数据元素，首先需要移动表中个数据元素。【北京航空航天大学 2004 年】（A）n-i（B） n+i（C） n-i+1（D）n-i-16 对顺序存储的线性表，设其长度为 n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的_个元素。【华中科技大学 2007 年】（A）n2（B） (n+1)2（C） (n 一 1)2（D）n7 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时

3、间复杂度为_。(1in+1) 【北京航空航天大学 1999 年】（A）0(0)（B） 0(1)（C） 0(n)（D）0(n)8 线性表中各链接点之间的地址_。【北京航空航天大学 2002 年】（A）必须连续（B）部分地址必须连续（C）不一定连续（D）连续与否无所谓9 在 n 个结点的线性表的数组表示中，算法的时间复杂度是 0(1)的操作是_。【哈尔滨工业大学 2003 年】（A）访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in)（B）在第 i 个结点后插入一个新结点(1in)（C）删除第 i 个结点(1in)（D）以上都不对10 单链表中，增加一个头结点的目的是为了_。【江苏大

4、学 2005 年】（A）使单链表至少有一个结点（B）标识表结点中首结点的位置（C）方便运算的实现（D）说明单链表是线性表的链式存储11 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是_。【北京工商大学 2001 年】（A）head=NULL（B） head-next=NULL（C） head 一next=head（D）headl=NULL12 将长度为 n 的单链表链接在长度为 m 的单链表后面的算法的时间复杂度采用大0 形式表示应该是_。【北京航空航天大学 2007 年】（A）0(1)（B） 0(n)（C） 0(m)（D）0(n+m)13 静态链表中指针表示的是_。【

5、中南大学 2003 年】（A）下一元素的地址（B）内存储器的地址（C）下一元素在数组中的位置（D）左链或右链指向的元素的地址14 非空的循环单链表 head 的尾结点 p 满足_。 【武汉大学 2000 年】（A）p-link。head（B） p-link=NULL（C） p=NULL（D）p=head15 某线性表用带头结点的循环单链表存储，头指针为 head，当 head-next-next=head 成立时，线性表长度可能是 _。【华中科技大学 2007 年】（A）0（B） 1（C） 2（D）316 在什么情况下，应使用链式结构存储线性表 L?_。【北京交通大学 2006 年】（A）需经

6、常修改 L 中的结点值（B）需不断对 L 进行删除插入（C）需要经常查询 L 中结点值（D）L 中结点结构复杂17 与单链表相比较，双向链表的优点之一是_。【北京航空航天大学 2005 年】（A）可以省略头结点指针（B）可以进行随机访问（C）插入、删除操作更简单（D）顺序访问相邻结点更灵活18 某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素，采用_作为存储结构，能使其存储效率和时间效率最高。【华中科技大学 2007年】（A）单链表（B）仅用头指针的循环单链表（C）双向循环链表（D）仅用尾指针的循环单链表19 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个

7、结点。则采用_存储方式最节省运算时间。【北京理工大学 2000 年】（A）单链表（B）双链表（C）单循环链表（D）带头结点的双循环链表20 对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够反映数据之间的逻辑关系，则应用_。【浙江大学 2004 年】【哈尔滨工业大学 2005年】（A）顺序方式存储（B）散列方式存储（C）链接方式存储（D）以上方式均可21 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。【哈尔滨工业大学 2001 年】（A）顺序表（B）双链表（C）带头结点的双循环链表（D）单循环链表22 若线性表最常用的操作是存

8、取第 i 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式为_。【北京理工大学 2004 年】（A）单链表（B）双向链表（C）单循环链表（D）顺序表23 下面哪一条是顺序存储结构的优点?_。【江苏大学 2006 年】（A）插入运算方便（B）可方便地用于各种逻辑结构的存储表示（C）存储密度大（D）删除运算方便24 下面关于线性表的叙述中，错误的是_。【北方交通大学 2001 年】（A）线性表采用顺序存储，必须占用一批连续的存储单元。（B）线性表采用顺序存储，便于进行插入和删除操作。（C）线性表采用链接存储，不必占用一片连续的存储单元。（D）线性表采用链接存储，便于插入和删除操作。25 在

9、非空线性链表中由 p 所指的链接点后面插入一个由 q 所指的链接点的过程是依次执行动作。【北京航空航天大学 2002 年】（A）q-link=p ；p-link=q：（B） q-link=p-link：p。 link=q;（C） q-link=p-link；p=q；（D）p 一link=q;q-link=p26 在非空双向循环链表中由 q 所指的链接点前面插入一个由 p 指的链接点的过程是依次执行语句 prlink=q：p-llink=q llinkq-llink=p ；_。【北京航空航天大学 2007 年】（A）q-rlink-llink=p；（B） q-llink-rlink=p（C） p

10、-rlink-llink=p；（D）p-Uink-rlink=p；27 在非空双向循环链表中由 q 所指的链接点后面插入一个由 p 指的链接点的动作依次为_。【北京航空航天大学 2005 年】（A）p-llink=q ；p-rlink=q-rlink ；q-rlink=p；q-rlink-llink=p：（B） p-rlink=q-rlink;p-Uink=q；q-rlink=p ；q-rlink-llink=p（C） p-llink=q；p-rlink=q-rlink；q-rlink=p ； p-llink-rlink=p（D）p-llink=q ；p-rlink=q-rlink ；q-rl

11、ink=p;p-rlink-llink=p；28 在双向链表存储结构中，删除 p 所指的结点时须修改指针_。【西安电子科技大学 1998 年】（A）p-llink-rlink=p-rlink;p-rlink-llink=p-llink;（B） p-llink=p-llink 一 llink;p-llink-dink=p;（C） p-rlink-llink=pp-rlink=p-rlink-rlinkt（D）p-rlink=p-llink-llink;p-llink=p-rlink-rlink；二、综合题29 利用顺序表的操作，实现以下函数：1)从顺序表中删除具有最小值的元素并由函数返回被删除元

12、素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2)从顺序表中删除第 i 个元素并由函数返回被删除元素的值。如果 j 不合理或顺序表为空则显示出错信息并退出运行。 3)向顺序表中第 i 个位置插入一个新的元素 x。如果 i 不合理则显示出错信息并退出运行。 4)从顺序表中删除具有给定值 x 的所有元素。5)从顺序表删除其值在给定值 s 与 t 之间(要求 s 小于t)的所有元素。如果 s 或 t 不合理或者顺序表为空，则显示错误信息并退出。 6)从有序顺序表中删除其值在给定值 s 与 t 之间(要求 s 小于 t)的所有元素。如果 s 或 t不合理或顺序表为空，则显

13、示错误信息并退出。7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。8)从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。30 请设计算法将不带头结点的单链表就地逆置。【北京交通大学 2001 年】31 有一个单链表 L(至少有 1 个结点)，其头结点指针为 head，编写一个过程将 L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。【燕山大学 2001 年】32 设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：1)找出最小值结点，且打印该数值。2)若该数值是奇数，则将其与直接后继结点的数值交换。3) 若该数值是

14、偶数，则将其直接后继结点删除。【东北大学 2000 年】33 给定(已生成) 一个带表头结点的单链表，设 head 为头指针，结点的结构为(data， next)，data 为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求：不允许使用数组作辅助空间)。 【华中科技大学 2000 年】34 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学 1998 年】35 在一个递增有序的线性表中，有数值相同的元

15、素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(7，10 ，10，21，30，42，42，42，51，70)将变为(7，10，21，30，42，51，70)。【北京工业大学 1996 年】36 试编写在带头结点的单链表中删除一个最小值结点的高效算法：voiddelete(LinklistNODE*dlf ference(NOI)E*A，N0 L)E*B)42 设一单向链表的头指针为 head，链表的记录中包含着整数类型的 key 域，试设计算法，将此链表的记录按照 key 递增的次序进行就地排序。【中科院计算所1999 年】43 设计算法将一个带头结点的

16、单链表 A 分解为两个具有相同结构的链表 B、C，其中 B 表的结点为 A 表中值小于零的结点，而 C 表的结点为 A 表中值大于等于零的结点(链表 A 的元素类型为整型，要求 B、C 表利用 A 表的结点)。【北京理工大学 2000 年】44 将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中含有原表中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。1)写出其类型定义。2)写出算法。【山东工业大学 2000 年】45 两个整数序列 A=a1,a2，a 3，a n 和 B=b1，b 2,b3，b n 已经存入两个单链表中，设计一个

17、算法，判断序列 B 是否是序列 A 的子序列。 【东北大学 1999 年】46 已知线性表(a 1，a 2，a 3，a n)按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值(假设 0 为正数)元素前边的算法。例如：(x ，一 x，一 x，x，x，一 x，x)变为(一 x，一 x，一 x，x，x，x)。【东北大学 1998 年】47 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域 coef，指数域 exp 和指针域 next。现对链表求一阶导数，链表的头指针为 ha，头结点的 exp域为一 1。【南京理工大学 2000 年】48 设用带头结点的双向

18、循环链表表示的线性表为 L=(a1，a 2，a n)。写出算法将L 改造成：L=(a 1，a 3， ，a n，a 4，a 2)。【华中科技大学 2007 年】结点和结点指针类型定义如下：typedefstrUCtnodeElemTypedata；strLICtnode*prior，next；*DLinkList；49 设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data( 数据 )和 next(后继指针)域外，还有一个访问频度域 freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次 Loga,te(L，x)运算时，令元素值为 x 的结点

19、中 freq 域的值增 1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学 1997 年】计算机专业基础综合数据结构（线性表）历年真题试卷汇编 1 答案与解析一、单项选择题1 【正确答案】 C【试题解析】 考查线性表的概念。线性表是由 n 个数据元素组成的有序序列。【知识模块】 线性表2 【正确答案】 B【试题解析】 考查顺序表的相关概念。顺序表是线性表的数组存储表示，一占用的存储空间大小与元

20、素存放顺序无关。【知识模块】 线性表3 【正确答案】 A【试题解析】 考查顺序表的存储结构。应该注意到顺序存储和顺序存取的不同。顺序表既可以随机存取，也可以顺序存取，但顺序表的特点只能是随机存取。随机存取是指可以通过数组下标存取任意位置的元素。【知识模块】 线性表4 【正确答案】 C【试题解析】 考查顺序表的基本操作。顺序存储可以随机访问结点，但是增加、删除结点的效率较低。【知识模块】 线性表5 【正确答案】 A【试题解析】 考查顺序表的删除操作。删除第 i 个元素，需将其后的 ni 个元素顺序前移。【知识模块】 线性表6 【正确答案】 C【试题解析】 考查顺序表的删除操作。对顺序表进行删除操

21、作时要将删除位置后的所有元素前移。对此题来说，删除每个元素的概率均为 ln ，从第一个元素开始，删除时所要移动的元素个数分别为 n 一 1，n 一 2，n 一 3，1，0 所以删除一个元素时平均要移动表中的(0 十 1+2+n 一 1)n=(n1)2 个元素。【知识模块】 线性表7 【正确答案】 C【试题解析】 考查线性表的插入操作。【知识模块】 线性表8 【正确答案】 C【试题解析】 考查线性表两种存储结构的比较。线性表的顺序存储要求存储在地址连续的存储单元中。链式存储结构的结点地址可以不用连续。所以 c 正确。D 不正确是因为不能说连续与否无所谓，因为顺序存储必须是连续的。【知识模块】 线

22、性表9 【正确答案】 A【试题解析】 考查顺序表的各种操作。线性表用数组表示，即顺序存储。顺序存储可以方便地访问第 i 个结点。【知识模块】 线性表10 【正确答案】 C【试题解析】 考查单链表的头结点。如果没有头结点，对于插入、删除等操作需要使用不同的代码。增加头结点之后，可以用相同的操作方法实现插入和删除。【知识模块】 线性表11 【正确答案】 B【试题解析】 考查单链表的特点。注意 C 为循环链表为空的条件。【知识模块】 线性表12 【正确答案】 C【试题解析】 考查单链表的链接。两个单链表的链接，需要将第一个单链表的尾结点指向第二个单链表的第一个结点。找到第一个链表的尾结点的时间与第一

23、个链表的长度 m 成正比，所以算法时间复杂度为 0(m)。【知识模块】 线性表13 【正确答案】 C【试题解析】 考查静态链表的概念。静态链表中的指针所存储的不再是链表中的指针域，而是其下一结点在一维数组中的位置其实就是数组下标。【知识模块】 线性表14 【正确答案】 A【试题解析】 考查循环单链表的特点。尾结点指针应该指向链表头。【知识模块】 线性表15 【正确答案】 B【试题解析】 考查循环单链表的特点。通过画图可以很清晰地看到，head-next指向头指针后一个结点，head-next-next 指向 head，所以总共有两个结点。头结点不存储线性表元素，所以线性表长度为 1。【知识模块

24、】 线性表16 【正确答案】 B【试题解析】 考查链式结构的特点。链式结构与顺序结构相比可以方便地对线性表进行插入、删除操作。【知识模块】 线性表17 【正确答案】 D【试题解析】 考查双向链表的特点。A 不对，双向链表也可以有头指针。 B 是顺序存储的特点。C 与单链表相比，双向链表增加了指针数量，使得插入、删除操作更麻烦。D 正确，因为双向链表即可以访问前驱结点，也可以访问后继结点。【知识模块】 线性表18 【正确答案】 D【试题解析】 考查链式存储的各种实现。首先看题意，要方便删除第一个数据元素，必须要能方便获取指向头结点的指针；要在最后一个元素后添加新元素，则要有一个指向尾结点的指针。

25、单链表显然不行，最后结点后添加新结点需要遍历线性表，效率太低。仅用头指针的循环单链表在获取尾指针时也需要遍历。双向循环链表的存储效率太低。仅用尾指针的循环单链表，可以很方便地获得头指针，满足两个条件。【知识模块】 线性表19 【正确答案】 D【试题解析】 考查链式存储的各种实现。A、B、 C 都需要遍历才能得到尾结点的指针。D 可以通过头结点方便地得到尾结点。【知识模块】 线性表20 【正确答案】 C【试题解析】 考查链式存储的各种实现。要想能够反映数据之间的逻辑关系，必须是线性表，而又要求能够进行较快地插入和删除，则应该选择链接方式存储。【知识模块】 线性表21 【正确答案】 A【试题解析】

26、 考查线性表两种存储的特点。本题较易出错，存取任一指定序号的元素，很显然应该是顺序表。顺序表不方便进行插入和删除操作，不过本题只要求在最后进行插入和删除，顺序表完全满足要求。所以应选择顺序表。【知识模块】 线性表22 【正确答案】 D【试题解析】 考查线性表各种存储方式的特点。随机存取第 i 个元素最快捷的方式是采用顺序存储，而且，顺序表中元素存储地址相邻，可以方便地存取其前驱和后继元素。【知识模块】 线性表23 【正确答案】 C【试题解析】 考查两种存储结构的特点。A 和 D 属于链式结构的优点，B 属于线性表的优点。【知识模块】 线性表24 【正确答案】 B【试题解析】 考查线性表两种存储

27、结构的特点。顺序存储占用连续单元，插入和删除需要移动大量数据，所以不利于插入和删除操作。【知识模块】 线性表25 【正确答案】 B【试题解析】 考查单链表的插入操作。【知识模块】 线性表26 【正确答案】 D【试题解析】 考查双向链表的插入操作。执行完以上三步之后，只需要再将原线性表前面结点的 rlink 指向 p 即可。所以题目答案为 p-llink-rlink=p。【知识模块】 线性表27 【正确答案】 D【试题解析】 考查双向链表的插入操作。解答过程与上一题基本一致，读者可以自己画图解决此类问题。【知识模块】 线性表28 【正确答案】 A【试题解析】 考查双向链表的删除操作。【知识模块】

28、 线性表二、综合题29 【正确答案】 考查顺序表各种操作的实现。线性表这一章出综合题的概率很大，且出题灵活。但是不论出什么样的题目，同学们应扎实掌握线性表的基础操作，以不变应万变。1)实现删除具有最小值元素的函数。算法的基本设计思想：从前向后遍历线性表，用个变量记录最小值，同时用另一个变量记录最小值位置。遍历之后将最小值删除。算法的代码：DataType deleteMin(SeqL 5st 假定 0 号元素的值最小int i，pos=0；for(i=1；iLn)return false; 表空或者 i 不合理，终止操作value=Ldatai ；for(int j=i+1；jLn)retur

29、n false; 表空或者 i 不合理，终止操作value=Ldatai ；for(int j=i+1；jLn)return falSe; 表满或者参数不合理，终止操作for(int J=Ln; Ji ；J 一一)LdataJ=LdataJ 一 1jLdatai=value， 从第 i 个位置插入Ln+ ；retUrn true ;insertnoi4)从顺序表中删除具有给定值 X 的所有元素。算法的基本设计思想：从后向前遍历，一直找到具有 x 值的元素，然后依次将此后的元素前移。算法的代码：void deleteValue(SeqLiStL，DataType value)int i，J ；f

30、or(i=Ln 一 1;i=0ji 一一) 循环，寻找具有 X 值的元素并删除if(Ldatai=value) 删除具有 x 值的元素for(J=i+1；J=t)return false；int i，j，for(i=Ln 一 1；i=0；i 一一) 循环，寻找在给定范围内的元素并删除它if(Ldatai=s L datai=t)return false；int i，J ，k，u；for(i=0j i=Ln)return false；for(J=i；JLn)return false，for(k=j，u=i；knextj p 为工作指针。本文中所有未定义指针都假设为全局定义L-next=NULL；

31、 第一个结点成为尾结点while(P!=NULL)r=P 一next；p 一next=L； 将 P 结点插到 L 结点前面。L=pj L 指向新的链表“第一”元素结点。p=r；return L; invert【知识模块】 线性表31 【正确答案】 算法的基本设计思想：将头结点摘下，然后从第一个结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。算法的代码：LinkList invert(LinkList la)la 是带头结点的单链表p=la 一next， p 为工作指针1a 一next=NULL ；while(p!=NULL)r=p 一next; 暂存 P 的后继p

32、一next=la 一next; 将 P 结点前插入头结点后la-next=p;p=r;return 1a； invert【知识模块】 线性表32 【正确答案】 算法的基本设计思想：通过遍历的方式查找最小值结点，当找到最小值结点之后，判断是奇数还是偶数。若是奇数，通过赋值语句交换数值：若是偶数，删除后继结点。算法的代码：VOid MiniValue(LinkLiSt 1a)la 是数据域为正整数且无序的单链表，本算法查找最小值结点且打印若最小值结点的数值是奇数，则与后继结点值交换；否则，删除其直接后继结点p=la 一next; 设 la 为头指针，P 为：p 作指针pre=p； pre 指向最小

33、值结点，初始假定首元结点值最小while(p 一next!=NULL) p-next 是待比较的当前结点【知识模块】 线性表33 【正确答案】 算法的基本设计思想：对链表进行遍历，在每趟遍历中查找出整个链表的最小值元素，输出并释放结点所占空间；再查次小值元素，输出并释放空间，如此下去，直至链表为空：最后释放头结点所占存储空间。算法的代码：VOid MiniDelete(LinkLiSt head)head 为带头结点的单链表的头指针，本算法按递增顺序输出单链表中各结点的数据元素，并释放结点所占的存储空间while(head 一next!=NULL) 循环到仅剩头结点pre=head； pre

34、为元素最小值结点的前驱结点的指针p=pre-next； p 为工作指针while(P 一next!=NULL)if(p 一next 一datanext 一data)pre=p； 记住当前最小值结点的前驱P=P 一next；printf(pre 一 next 一data)；输出元素最小值结点的数据u=pre 一next， 删除元素值最小的结点，释放结点空间pre 一next=u 一next；free(u)； while(head-next!=NULL)free(head)； 释放头结点 MiniDelete【知识模块】 线性表34 【正确答案】 算法的基本设计思想：因为两链表已按元素值递增次序排

35、列，将其合并时，均从第一个结点起进行比较，将较小的结点链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列，故在合并的同时，将链表结点逆置。算法的代码：LinkList Union(LinkList la，LinkList ib)本算法将两链表合并成一个按元素值递减次序排列的单链表pa=la 一next；pb=ib 一next； pa，pb 分别为链表 la 和 ib 的工作指针la 一next=NULL ； la 作结果链表的头指针，先将结果链表初始化为空while(pa!=NULLpb!=NULL) 当两链表均不为空时if(pa-datadata、r=pa 一next；

36、 将 pa 的后继结点暂存于 rpa-next=la-next； 将 pa 结点链入结果表中，同时逆置1a 一next=pa；pa=r; 恢复 pa 为当前待比较结点elser=pb-next； 将 pb 的后继结点暂存于 rpb 一next=la 一next ； 将 pb 结点链入结果表中，同时逆置la 一next=pb ;pb=r； 恢复 pb 为当前待比较结点while(pa!=NULL) 将 la 表的剩余部分链入结果表中，并逆置r=pa 一next；pa 一next=la 一next ;la 一next=pa，Pa=r；while(pb!=NULL)r=pb 一next ;pb 一n

37、ext=la 一next ；la 一next=pb ；pb=r；retUrn a； Union上面两链表均不为空的表达式也可简写为 while(paq=p 一next； q 为工作指针，初始指向 A 链表第一个被删除结点k=0；while(q!=NULLknext ;free(U)；if(knext=q； A 链表删除了 len 个元素if(heada 一next!=NULL) heada 一next=NULL 说明链表中结点均删除，无需往 B 表插入while(P 一next!=NULL)p=p-next; 找 A 的尾结点q=headb； q 为链表 B 的工作指针k=0； 计数while

38、(q!=NULLknext ;if(q=NULL)printf(”给的 d 太大n”，J);return NULL；p-next=q-next， 将 A 链表链入q 一next=heada 一next ;A 的第一元素结点链在 B 的第 J 一 1 个结点之后 iffree(heada); 释放 A 表头结点return headb；DelInsert【知识模块】 线性表38 【正确答案】 算法的基本设计思想：首先耍查找最小值结点，然后将该结点从链表上摘下，再插入到链表的最前面。算法的代码：LinkList Delinsert(LinkList 1ist)本算法将链表中数据域值最小的那个结点移

39、到链表的最前面p=list 一next； p 为链表的工作指针pre=list； pre 指向链表中数据域最小值结点的前驱q=p； q 指向数据域最小值结点，初始假定是第一结点while(P 一next!=NULL)if(p 一next 一datadata)找到新的最小值结点Pre=p；q=P 一next；P=P 一next；if(q!=list 一next) 若最小值是第一元素结点-则不需再操作pre 一next=q-next； 将最小值结点从链表上摘下q 一next=list 一next； 将 q 结点插到链表最前面list 一next=q ；return 1ist；Delinsert本算

40、法中假定 list 带有头结点，否则，插入操作变为 q-next=list；list=q。【知识模块】 线性表39 【正确答案】 算法的基本设计思想：将两个链表归并，同时注意如果有元素值相等的元素，则应删掉一个。算法的代码：LinkList Union(LinkList ha，LinkList hb)线性表 A 和 B 代表两个集合，元素递增有序。 ha 和 hb 分别为其链表的头指针本算法求 A 和 B 的并集 Au B，仍用线性表表示，结果链表元素也是递增有序pa=ha 一next； 设工作指针 pa 和 pbpb=hb 一next；pc=ha； pc 为结果链表当前结点的前驱指针while(pa pb)if(pa 一datadata)pc 一next=pa；