(总分：98.00，做题时间：90分钟)
一、 单项选择题(总题数：28，分数：56.00)
1.线性表是具有n个____的有限序列(n>0)。【清华大学1998年】 A.表元素 B.字符
C.数据元素 √ D.数据项
考查线性表的概念。线性表是由n个数据元素组成的有序序列。
2.一个顺序表所占用的存储空间大小与无关。【北京航空航天大学2004年】 A.表的长度
B.元素的存放顺序 √ C.元素的类型
D.元素中各字段的类型
考查顺序表的相关概念。顺序表是线性表的数组存储表示，一占用的存储空间大小与元素存放顺序无关。 3.线性表的顺序存储结构是一种____。【北京理工大学2006年】 A.随机存取的存储结构 √ B.顺序存取的存储结构 C.索引存取的存储结构 D.Hash存取的存储结构
考查顺序表的存储结构。应该注意到顺序存储和顺序存取的不同。顺序表既可以随机存取，也可以顺序存取，但顺序表的特点只能是随机存取。随机存取是指可以通过数组下标存取任意位置的元素。 4.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为____。【青岛大学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-1
考查顺序表的删除操作。删除第i个元素，需将其后的n—i个元素顺序前移。
6.对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____个元素。【华中科技大学2007年】 A.n／2 B.(n+1)／2 C.(n一1)／2 √ D.n
考查顺序表的删除操作。对顺序表进行删除操作时要将删除位置后的所有元素前移。对此题来说，删除每个元素的概率均为l／n，从第一个元素开始，删除时所要移动的元素个数分别为n一1，n一2，n一3，…，1，0所以删除一个元素时平均要移动表中的(0十1+2+…+n一1)／n=(n—1)／2个元素。
7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为____。(1≤i≤n+1)【北京航空航天大学1999年】 A.0(0)
B.0(1) C.0(n) √ D.0(n)
考查线性表的插入操作。
8.线性表中各链接点之间的地址____。【北京航空航天大学2002年】 A.必须连续 B.部分地址必须连续 C.不一定连续 √ D.连续与否无所谓
考查线性表两种存储结构的比较。线性表的顺序存储要求存储在地址连续的存储单元中。链式存储结构的结点地址可以不用连续。所以c正确。D不正确是因为不能说连续与否无所谓，因为顺序存储必须是连续的。
9.在n个结点的线性表的数组表示中，算法的时间复杂度是0(1)的操作是____。【哈尔滨工业大学2003年】
A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) √ B.在第i个结点后插入一个新结点(1≤i≤n) C.删除第i个结点(1≤i≤n) D.以上都不对
考查顺序表的各种操作。线性表用数组表示，即顺序存储。顺序存储可以方便地访问第i个结点。 10.单链表中，增加一个头结点的目的是为了____。【江苏大学2005年】 A.使单链表至少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 √
D.说明单链表是线性表的链式存储
考查单链表的头结点。如果没有头结点，对于插入、删除等操作需要使用不同的代码。增加头结点之后，可以用相同的操作方法实现插入和删除。
11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是____。【北京工商大学2001年】 A.head=NULL
B.head->next=NULL √ C.head一>next=head D.headl=NULL
考查单链表的特点。注意C为循环链表为空的条件。
12.将长度为n的单链表链接在长度为m的单链表后面的算法的时间复杂度采用大0形式表示应该是____。【北京航空航天大学2007年】 A.0(1) B.0(n) C.0(m) √ D.0(n+m)
考查单链表的链接。两个单链表的链接，需要将第一个单链表的尾结点指向第二个单链表的第一个结点。找到第一个链表的尾结点的时间与第一个链表的长度m成正比，所以算法时间复杂度为0(m)。 13.静态链表中指针表示的是____。【中南大学2003年】 A.下一元素的地址 B.内存储器的地址
C.下一元素在数组中的位置 √ D.左链或右链指向的元素的地址
考查静态链表的概念。静态链表中的指针所存储的不再是链表中的指针域，而是其下一结点在一维数组中的位置其实就是数组下标。
14.非空的循环单链表head的尾结点p满足____。【武汉大学2000年】 A.p->link。head √
B.p->link=NULL C.p=NULL D.p=head
考查循环单链表的特点。尾结点指针应该指向链表头。
15.某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next=head成立时，线性表长度可能是____。【华中科技大学2007年】 A.0 B.1 √ C.2 D.3
考查循环单链表的特点。通过画图可以很清晰地看到，head->next指向头指针后一个结点，
head->next->next指向head，所以总共有两个结点。头结点不存储线性表元素，所以线性表长度为1。 16.在什么情况下，应使用链式结构存储线性表L?____。【北京交通大学2006年】 A.需经常修改L中的结点值 B.需不断对L进行删除插入 √ C.需要经常查询L中结点值 D.L中结点结构复杂
考查链式结构的特点。链式结构与顺序结构相比可以方便地对线性表进行插入、删除操作。 17.与单链表相比较，双向链表的优点之一是____。【北京航空航天大学2005年】 A.可以省略头结点指针 B.可以进行随机访问 C.插入、删除操作更简单 D.顺序访问相邻结点更灵活 √
考查双向链表的特点。A不对，双向链表也可以有头指针。B是顺序存储的特点。C与单链表相比，双向链表增加了指针数量，使得插入、删除操作更麻烦。D正确，因为双向链表即可以访问前驱结点，也可以访问后继结点。
18.某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素，采用____作为存储结构，能使其存储效率和时间效率最高。【华中科技大学2007年】 A.单链表
B.仅用头指针的循环单链表 C.双向循环链表
D.仅用尾指针的循环单链表 √
考查链式存储的各种实现。首先看题意，要方便删除第一个数据元素，必须要能方便获取指向头结点的指针；要在最后一个元素后添加新元素，则要有一个指向尾结点的指针。单链表显然不行，最后结点后添加新结点需要遍历线性表，效率太低。仅用头指针的循环单链表在获取尾指针时也需要遍历。双向循环链表的存储效率太低。仅用尾指针的循环单链表，可以很方便地获得头指针，满足两个条件。
19.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用____存储方式最节省运算时间。【北京理工大学2000年】 A.单链表 B.双链表 C.单循环链表
D.带头结点的双循环链表 √
考查链式存储的各种实现。A、B、C都需要遍历才能得到尾结点的指针。D可以通过头结点方便地得到尾结点。
20.对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够反映数据之间的逻辑关系，则应用____。【浙江大学2004年】【哈尔滨工业大学2005年】 A.顺序方式存储 B.散列方式存储 C.链接方式存储 √
D.以上方式均可
考查链式存储的各种实现。要想能够反映数据之间的逻辑关系，必须是线性表，而又要求能够进行较快地插入和删除，则应该选择链接方式存储。
21.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。【哈尔滨工业大学2001年】 A.顺序表 √ B.双链表
C.带头结点的双循环链表 D.单循环链表
考查线性表两种存储的特点。本题较易出错，存取任一指定序号的元素，很显然应该是顺序表。顺序表不方便进行插入和删除操作，不过本题只要求在最后进行插入和删除，顺序表完全满足要求。所以应选择顺序表。
22.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式为____。【北京理工大学2004年】 A.单链表 B.双向链表 C.单循环链表 D.顺序表 √
考查线性表各种存储方式的特点。随机存取第i个元素最快捷的方式是采用顺序存储，而且，顺序表中元素存储地址相邻，可以方便地存取其前驱和后继元素。
23.下面哪一条是顺序存储结构的优点?____。【江苏大学2006年】 A.插入运算方便
B.可方便地用于各种逻辑结构的存储表示 C.存储密度大 √ D.删除运算方便
考查两种存储结构的特点。A和D属于链式结构的优点，B属于线性表的优点。 24.下面关于线性表的叙述中，错误的是____。【北方交通大学2001年】 A.线性表采用顺序存储，必须占用一批连续的存储单元。 B.线性表采用顺序存储，便于进行插入和删除操作。 √ C.线性表采用链接存储，不必占用一片连续的存储单元。 D.线性表采用链接存储，便于插入和删除操作。
考查线性表两种存储结构的特点。顺序存储占用连续单元，插入和删除需要移动大量数据，所以不利于插入和删除操作。
25.在非空线性链表中由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=p 考查单链表的插入操作。
26.在非空双向循环链表中由q所指的链接点前面插入一个由p指的链接点的过程是依次执行语句p．>rlink=q：p->llink=q．>llink~q->llink=p；____。【北京航空航天大学2007年】 A.q->rlink->llink=p； B.q->llink->rlink=p C.p->rlink->llink=p； D.p->Uink->rlink=p； √
考查双向链表的插入操作。执行完以上三步之后，只需要再将原线性表前面结点的rlink指向p即可。所以题目答案为p->llink->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->rlink=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； 考查双向链表的删除操作。
二、 综合题(总题数：21，分数：42.00)
29.利用顺序表的操作，实现以下函数：1)从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2)从顺序表中删除第i个元素并由函数返回被删除元素的值。如果j不合理或顺序表为空则显示出错信息并退出运行。3)向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。4)从顺序表中删除具有给定值x的所有元素。5)从顺序表删除其值在给定值s与t之间(要求s小于t)的所有元素。如果s或t不合理或者顺序表为空，则显示错误信息并退出。6)从有序顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素。如果s或t不合理或顺序表为空，则显示错误信息并退出。7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。8)从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
__________________________________________________________________________________________ 正确答案：(正确答案：考查顺序表各种操作的实现。线性表这一章出综合题的概率很大，且出题灵活。但是不论出什么样的题目，同学们应扎实掌握线性表的基础操作，以不变应万变。1)实现删除具有最小值元素的函数。算法的基本设计思想：从前向后遍历线性表，用～个变量记录最小值，同时用另一个变量记录最小值位置。遍历之后将最小值删除。算法的代码： DataType deleteMin(SeqL 5．st &L，DataType &Value) { if(L．n==0) return false； ／／表空，终止操作返回 value=L.data[0]; ／／假定0号元素的值最小 int i，pos=0； for(i=1；iL．n) return false; ／／表空或者i不合理，终止操作 value=L．data[i]； for(int j=i+1；jL．n) return false; ／／表空或者i不合理，终止操作 value=L．data[i]； for(int j=i+1；jL．n) return falSe; ／／表满或者参数不合理，终止操作 for(int J=L．n; J>i；J一一) L．data[J]=L．data[J一1]j L．data[i]=value， ／／从第i个位置插入 L．n++； retUrn true ; ／／insertnoi 4)从顺序表中删除具有给定值X的所有元素。 算法的基本设计思想：从后向前遍历，一直找到具有x值的元素，然后依次将此后的元素前移。 算法的代码： void deleteValue(SeqLiSt＆L，DataType value)} int i，J； for(i=L．n一1;i>=0ji一一) { ／／循环，寻找具有X值的元素并删除
if(L．data[i]==value) ／／删除具有x值的元素 { for(J=i+1；J=t) retu．rn false； int i，j， for(i=L．n一1；i>=0；i一一) { ／／循环，寻找在给定范围内的元素并删除它 if(L．data[i]>=s＆＆L．data[i]<=t) ／／删除 { for(J=i+1；J=t) return false； int i，J，k，u； for(i=0j i __________________________________________________________________________________________ 正确答案：(正确答案： 算法的基本设计思想：将第一个结点摘下，并将其指针域置空作为尾结点。然后从第二个结点开始，直到最后一个结点为止，依次前插入到新链表的前面，则实现了链表的逆置。算法的代码： LinkList invert(LinkLiSt L){ p：L一>nextj ／／p为工作指针。本文中所有未定义指针都假设为全局定义 L->next=NULL； ／／第一个结点成为尾结点 while(P!=NULL) { r=P一>next； p一>next=L； ／／将P结点插到L结点前面。 L=pj ／／L指向新的链表“第一”元素结点。 p=r； } return L; }／／invert) 31.有一个单链表L(至少有1个结点)，其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。【燕山大学2001年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想： 将头结点摘下，然后从第一个结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。 算法的代码： LinkList invert(LinkList la){／／la是带头结点的单链表 p=la一>next， ／／p为工作指针 1a一>next=NULL； while(p!=NULL) { r=p一>next; ／／暂存P的后继 p一>next=la一>next; ／／将P结点前插入头结点后 la->next=p; p=r; } return 1a； }／／invert) 32.设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：1)找出最小值结点，且打印该数值。2)若该数值是奇数，则将其与直接后继结点的数值交换。3)若该数值是偶数，则将其直接后继结点删除。【东北大学2000年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想： 通过遍历的方式查找最小值结点，当找到最小值结点之后，判断是奇数还是偶数。若是奇数，通过赋值语句交换数值：若是偶数，删除后继结点。 算法的代码： VOid MiniValue(LinkLiSt 1a){ ／／la是数据域为正整数且无序的单链表，本算法查找最小值结点且打印 ／／若最小值结点的数值是奇数，则与后继结点值交换；否则，删除其直接后继结点 p=la一>next; ／／设la为头指针，P为：p作指针 pre=p； ／／pre指向最小值结点，初始假定首元结点值最小 while(p一>next!=NULL) ／／p->next是待比较的当前结点 {) 33.给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data，next)，data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求：不允许使用数组作辅助空间)。【华中科技大学2000年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想： 对链表进行遍历，在每趟遍历中查找出整个链表的最小值元素，输出并释放结点所占空间；再查次小值元素，输出并释放空间，如此下去，直至链表为空：最后释放头结点所占存储空间。 算法的代码： VOid MiniDelete(LinkLiSt head){ ／／head为带头结点的单链表的头指针，本算法按递增顺序输出单链表中 ／／各结点的数据元素，并释放结点所占的存储空间 while(head一>next!=NULL) ／／循环到仅剩头结点 { pre=head； ／／pre为元素最小值结点的前驱结点的指针 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.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将较小的结点链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列，故在合并的同时，将链表结点逆置。算法的代码： LinkList Union(LinkList la，LinkList ib){ ／／本算法将两链表合并成一个按元素值递减次序排列的单链表 pa=la一>next； pb=ib一>next； ／／pa，pb分别为链表la和ib的工作指针 la一>next=NULL； ／／la作结果链表的头指针，先将结果链表初始化为空 while(pa!=NULL＆＆pb!=NULL) ／／当两链表均不为空时 { if(pa->data<=pb->data、 { r=pa一>next； ／／将pa的后继结点暂存于r pa->next=la->next； ／／将pa结点链入结果表中，同时逆置 1a一>next=pa； pa=r; ／／恢复pa为当前待比较结点 } else { r=pb->next； ／／将pb的后继结点暂存于r pb一>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一>next=la一>next； la一>next=pb； pb=r； } retUrn ｜a； {／／Union 上面两链表均不为空的表达式也可简写为while(pa&&pb)。两递增有序表合并成递减有序表时，本题算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者效率高。算法中最后两个while语句，不可能执行两个，只能二者取 一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。这一点与顺序表的合并相似，其实不论是顺序表还是链表、线性表的合并算法思路基本是一样的。所以，关键是要理解解题思路，不同的数据结构，只是表述不同。) 35.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(7，10，10，21，30，42，42，42，51，70)将变为(7，10，21，30，42，51，70)。【北京工业大学1996年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：因为是递增有序的线性表，每处理到一个结点，看其后是否有与其数值相同的元素存在，通过被删除元素结点的前驱结点删除数值相同的元素。算法的代码： LinkList DelSame(LinkList la) { ／／la是递增有序的单链表，本算法去掉数值相同的元素，使表中不再有重复的元素 pre=la一>next； ／／pce为p所指向的前驱结点的指针 p=pre一>next； ／／P为工作指针。设链表中至少有一个结点 while(p I=NULL) { if(p一>data==pre一>data) ／／处理相同元素值的结点 { u=p； p=p一>next； free(u)； ／／释放相同元素值的结点 } else { ／／处理前驱和后继元素值不同的情况 pre一>next=p ； pre=p； p=p一>next ； } } pre一>next=p； ／／置链表尾 return la； }／／ DelSame 算法中假设链表至少有一个结点，即初始时pre不为空，否则p->next无意义。算法中最后pre->next=p是必需的，因为可能链表最后有数据域值相同的结点，这些结点均被删除，指针后移使p=NuLL而退出while循环，所以应有pre->next=p使链表有尾。若链表尾部没数据域相同的结点，pre和p为前驱和后继，pre->next=p也是对的。顺便提及，题目中所说的递增并非严格递增，因为“严格递增”是说各结点数据域值不同，一个值比一个值大，不会存在相同值元素。) 36.试编写在带头结点的单链表中删除一个最小值结点的高效算法：voiddelete(Linklist&L)。【北京理工大学2001年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。算法的代码： LinkLiSt Delete(LinkList L){ ／／L是带头结点的单链表，本算法删除其最小值结点 D：L一>next；lip为工作指针，指向待处理的结点。假定链表非空 pre：L； ／／pre用来指向最小值结点的前驱 q：p， ／／q指向最小值结点，初始假定第一元素结点是最小值结点 while(p->next!=NULL) ／／查找最小值结点 { if(p一>next一>datadata) { Pre=p； q=p一>next； } p=p一>next ； ／／指针后移 } pre一>next=q一>next； ／／从链表上删除最小值结点 free(q)； ／／释放最小值结点空间 return L； }／／Delete) 37.已知两个单链表A和B，其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。【中国矿业大学2000年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：从第一个元素起开始计数，记到第i个时开始数len个，然后将第i一1个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结点。再查B链表的第J个元素，将A链表插入之。算法的代码： LinkList DelInsert(LinkList heada，LinkList headb，int i，int J，int len){ if(i<1｜｜lennext； } if(p==NULL) ／／i太大，退出算法 { printf(u给的％d太大＼n”，i)； retUrn NULL ; } q=p一>next； ／／q为工作指针，初始指向A链表第一个被删除结点 k=0； while(q!=NULL＆＆knext ; 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(q!=NULL＆＆knext ; } if(q==NULL) { printf(”给的％d太大＼n”，J); return NULL； } p->next=q->next， ／／将A链表链入 q一>next=heada一>next ; ／／A的第一元素结点链在B的第J一1个结点之后 }／／if free(heada); ／／释放A表头结点 return headb； }／／DelInsert) 38.已知非空线性链表由list指出，链结点的构造为(data，link)。请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面(要求：不得额外申请新的链结点)。【北京航空航天大学2007年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：首先耍查找最小值结点，然后将该结点从链表上摘下，再插入到链表的最前面。算法的代码： LinkList Delinsert(LinkList 1ist){ ／／本算法将链表中数据域值最小的那个结点移到链表的最前面 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 本算法中假定list带有头结点，否则，插入操作变为q->next=list；list=q。) 39.带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合，两表中的元素皆为递增有序。请写一算法求A和B的并集AUB，要求该并集中的元素仍保持递增有序，且要利用A和B的原有结点空间。【北京邮电大学1992年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：将两个链表归并，同时注意如果有元素值相等的元素，则应删掉一个。算法的代码： LinkList Union(LinkList ha，LinkList hb){ ／／线性表A和B代表两个集合，元素递增有序。ha和hb分别为其链表的头指针 ／／本算法求A和B的并集Au B，仍用线性表表示，结果链表元素也是递增有序 pa=ha一>next； ／／设工作指针pa和pb pb=hb一>next； pc=ha； ／／pc为结果链表当前结点的前驱指针 while(pa＆＆pb) { if(pa一>datadata) { pc一>next=pa； Pc=pa； pa=pa一>next； } else if(pa一>data>pb一>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； ／／若ha表未空，则链入结果表 else pc一>next=pb， ／／若hb表未空，则链入结果表 free(hb)； ／／释放hb头结点 return ha； }／／Union) 40.已知两个链表A和B分别表示两个集合，其元素递增排列。编写一函数程序，求A与B的交集，并存放于A链表中。【南京航空航天大学2007年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：对两个链表进行归并，但只有同时出现在两集合中的元素才出现在结果表中。算法的代码： LinkList Union(LinkList la，LinkList ib){ pa=la一>next ; ／／设工作指针pa和pb pb=ib一>next； pc=la； ／／结果表中当前合并结点的前驱指针 while(pa＆＆pb) { if(pa一>data==pb一>data)／／交集链入结果表中 { Pc一>next=pa ; Pc=pa； pa=pa一>next； u=pb： pb=pb一>next; free(u)； } else if(pa一>datadata) { u=pa， pa=pa一>next； free(u)； } else { u=pb； pb=pb一>next； free(u)； } } while(pa) { u=pa； pa=pa一>next ; free(u)； ／／释放结点空间 } while(pb) { u=pb; pb=pb一>next ; free(u)， ／／释放结点空间 } pc一>next=NULL； ／／置链表尾标记 free(ib)； ／／注：本算法中也可对B表不作释放空间的处理 return 1a; }／／Union 对两个链表进行归并的题目在各学校历年真题中出现的频率很高，考生应扎实地掌握此类问题。) 41.设计一个求两个集合A和B之差C=A—B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是c中的一个元素。集合用有序链表实现，初始时，A、B集合中的元素按递增排列，C为空；操作完成后，A、B保持不变，C中元素按递增排列。下面的函数append(1ast，e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A，B)实现集合运算A—B，并返回表示结果集合C的链表的首结点的地址。在执行A—B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A—B运算执行完毕后，再删除并释放表示结果集合的链表的表头结点。【上海大学2000年】 typedef struct node( int element； struct node*link； }NODEj NODE*A，*B，*C； NODE *append (NODE *last，in七e) { last一>link=(NODE*)malloc(sizeof(NODE))； last一>link一>element=e； return (1ast一>link); } NODE*dlf ference(NOI)E*A，N0 L)E*B) { } __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：对两个链表进行归并，但当A的一个元素不是B中的一个元素时，才将其加入到新链表C中。算法的代码： LNode *difference(LNode*A，LNode*B)( LNode*C，*1ast， C=1ast=(LNode*)malloc(Sizeof(LNode))， while(A!=NULL＆＆B!=NULL) ／／两表均未空时循环 { if(A->elementelement) { last=append(1ast，A一>element)； A=A->1ink; } else if(A一>element==B一>element) { ／／两表中相等元素不作结果：元素 A=A->1ink; B=B一>1ink； } else B=B一>link； ／／向后移动B表指针 } whlle(A!=NULL) { 1ast=append(1ast，A一>element)， A=A一>1ink； } 1ast一>1ink=NULL; ／／置链表尾 1ast=C; C=C一>1ink; free(1ast); return C; }／／difference) 42.设一单向链表的头指针为head，链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照key递增的次序进行就地排序。【中科院计算所1999年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：本题明确地指出单链表带头结点，这时只需从第二结点开始，将各结点采用插入排序法依次插入到有序链表中，即可实现就地排序。算法的代码： LinkList LinkListInsertSort(LinkList la){ ／／本算法利用直接插入原则将链表整理成递增的有序链表 if(1a->next!=NULL) ／／链表不为空表 { p=la一>next->next； ／／p指向第一结点的后继 la一>next一>next=NuLL; ／／第一元素有序，从第二元素起依次插入 while(P!=NULL) { r=p->next； ／／暂存P的后继 q=1a， while(q一>next!=NULL＆＆q一>next一>datadata) q=q->next ; ／／查找插入位置 p->next=q->next； ／／将P结点链入链表 q一>next=p； P=r; } } return 1a； }／／LinkListInsertSort) 43.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于等于零的结点(链表A的元素类型为整型，要求B、C表利用A表的结点)。【北京理工大学2000年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：先初始化B和C表，然后从前向后遍历A表，如果结点数值小于零，则链入B表；如果大于等于零，则链入C表。算法的代码： LinkList DisCreat(LinkList A){ ／／A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成 ／／两个单链表B和C，B中结点的数值小于零，C中结点的数值大于等于零。处理 ／／之后，B表的头指针即为A表头指针，只需返回C表头指针即可 B=A； C：(LinkList)malloc《sizeof(LNode))；／／为C申请结点空间 c一>next：NULL； ／／c初始化为空表 p：A一>next； ／／p为工作指针 B一>next=NULL； ／／B表初始化 while(P!=NULL) I r=p一>next； ／／暂存P的后继 if(p一>datanext。B一>next； B一>next=p； ／／将小于0的结点链入B表 } else { P一>next=C一>next； C一>next=P ； } p=r； ／／p指向新的待处理结点 } return C； }／／DisCreat) 44.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。1)写出其类型定义。2)写出算法。【山东工业大学2000年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：基本思想与上题一样，使用一指向表尾的指针，采用在链表尾插入，可使分解后两表中元素结点的相对顺序不变。算法的代码： LinkLiSt DiSCreat(LinkList A){ ／／A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含 ／／原表中序号为奇数的结点，B表中含原表中序号为偶数的结点。相对顺序不变 i：0； ／／i记链表中结点的序号 B=(LinkList)malloc(sizeof(LNode))；／／创建B表表头 B->next=NULL； ／／B表的初始化 LinkList ra，rb； ／／re和rb将分别指向将创建的A表和B表的尾结点 ra=A； rb=B； p=A一>next； ／／p为链表工作指针，指向待分解的结点 A一>next=NULL； ／／置空新的A表 while(P!=NULL) { r=p一>next； ／／暂存P的后继 i++； if(i％2=0) ／／处理原序号为偶数的链表结点 { P一>next=NULL； ／／在B表尾插入新结点 rb一>next=p ； rb=p； ／／rb指向新的尾结点 } else ／／处理原序号为奇数的结点 { P一>next=NULL； ra一>next=P; ra=p， } p=r； ／／将P恢复为指向新的待处理结点 } return B； }／／DiSCreat) 45.两个整数序列A=a 1 ,a 2 ，a 3 ，…，a n 和B=b 1 ，b 2 ,b 3 ，…，b n 已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。【东北大学1999年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针：若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一个结点开始比较，直到B链表到尾表示匹配成功。A链表到尾B链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下趟匹配时好从其后继开始。算法的代码： int Pattern(LinkedLiSt A，LinkedLiSt B){ ／／A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列’ ／／如是，返回1；否则，返回0 p=A； ／／p为A链表的工作指针，本题假定A和B均无头结点 pre=p； ／／pre记住每趟比较中A链表的开始结点 q=B; ／／q为B链表的工作指针 while(p＆＆q) if(p一>data==q一>data) { P=P一>next； q=q一>next； } e1Se { Pre=pre一>next ; p=pre； ／／A链表新的开始比较结点 q=B； } ／／q从B链表第一个结点开始 if(q==NULL) return 1； ／／B是A的子序列 e1Se return 0 ; ／／B不是A的子序列 }／／Pattern) 46.已知线性表(a 1 ，a 2 ，a 3 ，…，a n )按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值(假设0为正数)元素前边的算法。例如：(x，一x，一x，x，x，一x，…，x)变为(一x，一x，一x，…，x，x，x)。【东北大学1998年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：采用快速排序的思想来实现，只是暂存的第一个元素(枢轴)并不作为以后的比较标准，比较的标准是元素是否为负数。算法的代码： void Rearrange(SeqList a，int n){ ／／本算法重排线性表a，使所有值为负数的元素移到所有值为正数的元素前面 int i=0，J=n一1； lli，J为工作指针(下标)，初始分别指向线性表a的第一个和第n个元素 t：a[0]； ／／暂存枢轴元素 while(i=0) J一一： ／／若当前元素为大于等于0，则指针前移 if(i 48.设用带头结点的双向循环链表表示的线性表为L=(a ，a ，…，a )。写出算法将L改造成：L=(a ，1 2 n 1 a 3 ，…，a n ，…，a 4 ，a 2 )。【华中科技大学2007年】结点和结点指针类型定义如下：typedefstrUCtnode{ElemTypedata；strLICtnode*prior，next；}*DLinkList； __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：依次访问数据元素a 1 ，a 2 ，…，a n-1 将其序号为偶数的结点先删除，再插入到a。的后面。算法的代码： void Adj uSt(DLinkLiSt L){ DLinkList tail=L一>priOr，p=L一>next; int i=0； while(P!=tail) { i++； q=p一>next ; if(i％2==0) { P一>prior一>next=q； q一>prior=P一>prior ; tail一>next一>prior=p； P一>next=tail一>next ; P一>prior=tail； tail一>next=P； } p=q； } }／／AdjUSt) 49.设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针)域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Loga,te(L，x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学1997年】 __________________________________________________________________________________________ 正确答案：(正确答案：算法的基本设计思想：首先在双向链表中查找数据值为x的结点，查到后，将结点从链表上摘下，然后再顺结点的前驱链查找该结点的位置。算法的代码： DLinkList 10cate(DLinkLiSt L，ElemType x){ ／IL是带头结点的按访问频度递减的双向链表，本算法先查找数据X，查找成功 ／／时结点的访问频度域增l，最后将该结点按频度递减插入链表中适当的位置 DLinkLiSt p=L一>next，q； ／／P为L表的工作指针，q为P的前驱，用于查找插入位置 while(p＆＆p一>data!=x) ／／查找值为x的结点 P=P一>next； if(!P) { printf(“不存在值为x的结点＼n”)j return NULL； } 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; ／／返回值为x的结点的指针 }／／locate) 因篇幅问题不能全部显示，请点此查看更多更全内容