20．L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。【东北大学 1997 四 (１５分)】 例：
类似本题的另外叙述有：
(1) 知L为链表的头结点地址，表中共有m(m>3)个结点，从表中第i个结点(1 【东北大学 1998 三 (15分)】 21. 请写一个算法将顺序存储结构的线性表（a1...an）逆置为(an...a1)。【大连海事大学1996八(６分)】 类似本题的另外叙述有： (1) 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成. 【南京航空航天大学 1999 八 （10分）】 (2) 设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（注：用程序实现）【南京航空航天大学 1997 七 （12分）】 (3) 试编写求倒排循环链表元素的算法。【南京航空航天大学 1995 十二 （10分）】 (4) 请设计算法将不带头结点的单链表就地逆置。【北方交通大学 2001 三 （12分）】 (5) 试编写算法 ，将不设表头结点的、不循环的单向链表就地逆转。【北方交通大学1997五（10分）】 (6) 有一个单链表（L至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。【燕山大学 2001 四、2（8分）】 22．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： （1）找出最小值结点，且打印该数值； （2）若该数值是奇数，则将其与直接后继结点的数值交换； （3）若该数值是偶数，则将其直接后继结点删除。【东北大学 2000 二 (15分)】 23．已知L为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。（要求用最少的时间和最少的空间）【东北大学 2002 三(15分)】 24．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。【北京工业大学 1996 三 (15分)】 25．在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。 顺序存储结构的线性表描述为： CONST maxlen={线性表可能达到的最大长度}； TYPE sqlisttp=RECORD elem:array[1..maxlen] of integer; last :0..maxlen END; VAR L: sqlisttp;【同济大学 1998 二 (12分 )】 26．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间） (1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）； (2) 在单链表将比正整数x小的数按递减次序排列； (3) 将正整数（比）x大的偶数从单链表中删除。【东北大学 2001 二 (17分)】 27. 编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。【吉林大学 2001 二、1 (7分)】 类似本题的另外叙述有： (1) 已知非空线性链表第一个结点由List指出，请写一算法，交换p所指的结点与其下一个结点在链表中的位置(设p指向的不是链表最后那个结点)【。北京航空航天大学 1999 五 （10分）】 (2) 已知任意单链表如图所示(编者略去图)。Head为表头指针，指向表的第一个元素，p为指向表中任意结点的指针，试设计一个算法，将p指向的结点和其后面结点交换位置（可采用任何高级语言描述算法）。 【山东大学 1992 二 ( 12分)】 28．设键盘输入n个英语单词，输入格式为n, w1, w2, ?,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：（10分） （1）如果单词重复出现，则只在链表上保留一个。（单考生做）。 （2）除满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k<=n)个单词（统考生做）。【南京航空航天大学 1998 九 （10分）】 29．已知一双向循还链表，从第二个结点至表尾递增有序，（设a1 【北京航空航天大学 2000 五（10分）】 31．设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。 序号 data Llink Rlink 1 Liu 6 5 2 Chan 4 9 3 Wang 5 7 4 Bao 0 2 5 Mai 1 3 6 Dong 8 1 7 Xi 3 0 8 Deng 9 6 9 Cuang 2 8 【北方交通大学 2000 六（17分）】 32．设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学 1997 二 （10分）】 33．给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data,next),data为整型元素，next为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)【华中理工大学 2000 八、2 （13分）】 34．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。【清华大学 1995 一 （15分）】 第2章 线性表 一．选择题 1.A2.B3.C4.A5.D6.D7.D8.C9.B10.B,C11.1I11.2I11.3E11.4B11.5C12.B13.C14.C15.C16.A17.A18.A19.D20.C21.B22.D23.C24.B25.B26.A27.D二．判断题 1. ×2.√3. √4.×5.×6. ×7. ×8.×9.×10.×11.×12.×13. ×14. √15.×16. √部分答案解释如下。 1、 头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度，或作监视哨。 4．两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。 7．集合中元素无逻辑关系。 9．非空线性表第一个元素无前驱，最后一个元素无后继。 13．线性表是逻辑结构，可以顺序存储，也可链式存储。 三．填空题 1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py 4 ．n-i+1 5．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。 6．O(1)，O(n) 7．单链表，多重链表，（动态）链表，静态链表 8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f; 9．p^.prior s^.prior^.next 10． 指针 11．物理上相邻 指针 12．4 2 13．从任一结点出发都可访问到链表中每一个元素。 14．u=p->next; p->next=u->next; free(u); 15．L->next->next==L 16．p->next!=null 17．L->next==L && L->prior==L 18．s->next=p->next;p->next=s; 19．(1) IF pa=NIL THEN return(true); (2) pb<>NIL AND pa^.data>=pb^.data (3) return(inclusion(pa,pb)); (4) pb:=pb^.next; (5) return(false); 非递归算法： (1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)pa:=pa^.next; pb:=pb->next; (4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IF pa=NIL THEN return(true) ELSE return(false); [注]：本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点（初始时为第一元素结点）。若主串与子串对应数据相等，两串工作指针pa和pb后移；否则，主串工作指针从pre的下一结点开始（这时pre又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若pa为空，则匹配成功，返回true，否则，返回false。 20．A．VAR head:ptr B. new(p) C. p^.data:=k D. q^.next:=p E. q:=p(带头结点) 21．（1）new(h);∥生成头结点，以便于操作。 （2）r^.next:=p; (3) r^.next:=q; (4) IF (q=NIL) THEN r^.next:=p; 22．A: r^.link^.data<>max AND q^.link^.data<>max B: r:=r^.link C: q^.link D: q^.link E: r^.link F: r^.link G: r:=s（或r:= r^.link） H: r:=r^.link I: q^.link:=s^.link 23．(1)la (2)0 (3)j (3)p:=p^.right ∥工作指针后移 (4)s^.left:=p (5)p^.right^.left:=s; ∥p后继的前驱是s (6)s^.left:=p; 25.(1)i<=L.last ∥L.last 为元素个数 (2)j:=j+1 ∥有值不相等的元素 (3)L.elem[j]:=L.elem[i] ∥元素前移 (4)L.last:=j ∥元素个数 26.(A)p^.link:=q;∥拉上链，前驱指向后继 (B)p:=q;∥新的前驱 (C)p^.link:=head;∥形成循环链表 (D)j:=0; ∥计数器，记被删结点 (E)q:=p^.link∥记下被删结点 (F)p^.link=q^.link ∥删除结点 27. (1)p:=r;∥r指向工作指针s的前驱，p指向最小值的前驱。 (2)q:=s;∥q指向最小值结点，s是工作指针 (3)s:=s^.link∥工作指针后移 (4)head:=head^.next;∥第一个结点值最小； (5)p^link:=q^.link;∥跨过被删结点（即删除一结点） 28．(1) l^.key:=x;∥头结点l这时起监视哨作用 (2) l^.freq:=p^.freq ∥头结点起监视哨作用 (3) q->pre->next=q->next; q->next->pre=q->pre; ∥先将q结点从链表上摘下 q^.next:=p; q^.pre:=p^.pre; p^.pre->next:=q; p^.pre:=q; ∥结点q插入结点p前 (4) q^.freq=0 ∥链表中无值为x的结点，将新建结点插入到链表最后（头结点前）。 29．(1)a^.key:=’@’∥a的头结点用作监视哨，取不同于a链表中其它数据域的值 (2)b^.key:=p^.key∥b的头结点起监视哨作用 (3)p:=p^.next∥找到a,b表中共同字母，a表指针后移 (4)0(m*n) 30. C 部分：(1)p!=null ∥链表未到尾就一直作 (2)q ∥将当前结点作为头结点后的第一元素结点插入 31. (1)L=L->next; ∥暂存后继 (2)q=L; ∥待逆置结点 (3)L=p; ∥头指针仍为L 32. (1) p^.next<>p0 (2)r:= p^.next (3) p^.next:= q0; (4) q0:= p; (5) p:=r 33. (1)r (2)NIL (3)x (2)pa->exp==0 ∥若指数为0，即本项为常数项 (3)q->next=pa->next ∥删常数项 (4)q->next ∥取下一元素 (5)=pa->coef*pa->exp (6)-- ∥指数项减1 (7)pa ∥前驱后移,或q->next (8)pa->next ∥取下一元素 35．(1)q:=p; ∥q是工作指针p的前驱 (2)p^.data>m ∥p是工作指针 (3)r:=q; ∥r 记最大值的前驱， (4)q:=p; ∥或q:=q^.next; (5)r^.next:=q^.next; ∥或r^.next:=r^.next^.next 删最大值结点 36．(1)L->next=null ∥置空链表,然后将原链表结点逐个插入到有序表中 (2)p!=null ∥当链表尚未到尾，p为工作指针 (3)q!=null ∥查p结点在链表中的插入位置，这时q是工作指针。 (4)p->next=r->next ∥将p结点链入链表中 (5)r->next=p ∥r是q的前驱，u是下个待插入结点的指针。 37．程序（a） PASCAL部分(编者略） 程序（b） C部分 (1)(A!=null && B!=null) ∥两均未空时循环 (2)A->element==B->element ∥两表中相等元素不作结果元素 (3)B=B->link ∥向后移动B表指针