第2章线性表 qp^k^k:【山东大学1999八(10分)】 个数据类型inked list的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能。【山东科技大学 、2(5分)】 TYPE linked lis=1 node; node=RECO RD PROC M PROCsubp(sq:lnkedlist) p↑.next=s ENDP: subp (pa.pb) subp (pb.pa): ENDP: 19.设双向循环链表中结点的数据域、前驱和后继指针域分别为daa,pe和next试写出在指针p所指结点之前插入一结点的C语 言描述语句。【北京科技大学2001- 、32分）】 图1： data link a1 a2☐◆ ◆an NIL 图24 found+-false (A)并且fohd=fase了 yes no (B) yes valn↑dta n 结束 od←tuuw 2+2↑k yes ound+-false at←tnue
第2章 线性表 q←p^.rlink^.llink; 【山东大学 1999 八（10分）】 18．已知L是一个数据类型linkedlist的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能。【山东科技大学 2001 一、2 （5分）】 TYPE linkedlist=↑node; node=RECORD data:datatype; next:linkedlist END; PROC Mp(pa,pb:linkedlist); PROC subp(s,q: linkedlist); p:=s; WHILE p↑.next<>q DO p:=p↑.next; p↑.next:=s ENDP; subp(pa,pb); subp(pb,pa); ENDP; 19．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语 言描述语句。【北京科技大学 2001 一、3 （2分）】 20．本题给出一个子程序的框图，如图2，试填空完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表f1， f2，f3中的相同整数。假定在调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1的例子所 示。 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 12／17 页）2010-4-15 11:00:46
第2章线性表 no B≠nl并且fond=flee并且ette yes f3↑.data-f1↑.data2 (D yes 若且， 2和种无的型的变 可取值为u 是整型变量，用来存放第一个均： ue 域。 d的值为a, 表示访问所指结的m 【哈尔注工业大学1999三(15分)】 21.一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法 (1)说明该算法的功能。(2)在空缺处填写相应的语句。 void unknown (BN O DETPL) p=L->next:q=p->next;r=q->next wh正aL) (while (p=L)&&(p->dataq->data)p=p->prior: >pror>nextr: nexp-nextpr: q=r:p=q->pror 】【北京理工大学1999第二部分数据结构](8分)】 五、算法设计题 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值 递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 【北京大学1998 1(5分)】 类似本题的另外叙述有： (I)设有两个无头结点的单链表，头指针分别为ha,hb,链中有数据域data,链域next两链表的数据都按递增序存放，现要求将hb表 归到ha表中，且归并后ha仍递增序，归并中ha表中己有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破 坏。【南京理工大学1997四、3(15分)】 PRO CED URE m erge(ha,hb); (2)己知头指针分别为和凸的带头结点的单链表中，结点按元素值非递减有序排列。写出将h和b两链表归并成一个结点按 2元素值非逆减有 (其头指针为)，并计算算法的时间复杂度。，【燕山大学1998五 (20分） 百 为ha和hb ,两表中的元素皆为递 曾有序 请写 一算法 米似本题的另外叙述有： ①)已知递增有序的两个单链表A,B分别存储了一个集合。设计算法实现求两个集合的并集的运算A=AUB【合肥工业大学 000五 1(8分)) (2)已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航 天大学2001六(10分) (3)设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法（即L1L2)。要求结果链表仍是从 小到大排序，但无重复元素。【南京航空航天大学1996十 (10分)】 (4)己知两个线性表A,B均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A与B的交集C, 要求C另开辟存储空间，要求C同样以元素值的递增序的单链表形式存贮。 【西北大学2000五(8分)】 h审ing.com 1 entaoyan/使502h加（第13/17页）2010-4日511006
第2章 线性表 注：在图2的框图中：found和exit均为布尔型的变量，可取值为true和false。val是整型变量，用来存放第一个均出现在f1，f2，f3 中的相同整数。若f1，f2和f3中无相同的整数，found 的值为false，否则found的值为true。f1↑.link表示访问f1所指结点的link 域。 【哈尔滨工业大学 1999 三 （15分）】 21. 一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法： （1）说明该算法的功能。（2）在空缺处填写相应的语句。 void unknown (BNODETP *L) { . p=L->next; q=p->next; r=q->next； while (q!=L) { while (p!=L) && (p->data>q->data) p=p->prior； q->prior->next=r；(1) _； q->next=p->next；q->prior=p； (2) _；(3) _； q=r；p=q->prior； (4) _； } } 【北京理工大学 1999 第二部分 数据结构 [7] （8分）】 五、算法设计题 1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值 递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 【北京大学 1998 三、1 （5分）】 类似本题的另外叙述有： （1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表 归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破 坏。【南京理工大学1997 四、3（15分）】 PROCEDURE merge(ha,hb); （2）已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。写出将la 和 lb两链表归并成一个结点按 元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。【燕山大学 1998 五 （20分）】 2. 图（编者略）中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法 求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学 1992 二 （15 分）】 类似本题的另外叙述有： (1) 已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪B【合肥工业大学 1999 五、1（8分）】 （2）已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航 天大学 2001 六（10分）】 （3）设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法（即L1∩L2）。要求结果链表仍是从 小到大排序，但无重复元素。【南京航空航天大学 1996 十一（10分）】 （4）己知两个线性表A ，B均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A与B的交集C， 要求C另开辟存储空间，要求C同样以元素值的递增序的单链表形式存贮。 【西北大学 2000 五 ( 8分)】 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 13／17 页）2010-4-15 11:00:46
第2章线性表 递增有序的 单链表 【合的 C分别存储 个集合 ,设计算法实现A:=AU(B∩C)，并使求解结构A仍保持递增。要 A伪集合 的元系个 3知1， (8 的 结点指针， 并 带头结点的循环单链表】 【东北 分 L2表中数据结点个数。要求设计一算法，用最快速度将两表合 似本 (1)试用类Pascal语 编写讨得PROC bn(VAR Ink:b:Ink) 实现连接线性表和b在后)的算法，要求其时间复 杂度为0(1)， 占用辅助空间尽量小。描述所用结构。 【北京工业大学1997一 18分)】 (2)设有两个链表，h为单向链表，hb为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与 链表长度无关。 【南京航空航天大学1997四(8分)】 4.顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类PA SCAL语言给出 学种高效算法将LB中元素合到A中，使新的A的元素仍保持非递减有序。高效指最大限度的遮免移动元素。【北京工业透 链 中结点构造为(da、k) 其中da为数据 k为指 请写一算法，将该 拉结点数据 的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。【北京航空航天 L 与hh 其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递 增 的 【东北大学1996六14分)】 类似本题的另外叙 I)设一单向链表的头指针为head,链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照k©y递增的次序进行 就地排序.【中科院计算所1999五、1(10分)】 7.设L isthead为 一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域EXT组成，整数在单链表中是无序的。编 -PASCAL过程.将Iad陆中结占分成一个态将链知 一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序 中不得使用NEW过程申请空间。【山东大学1993六(15分)】 类似本趣的另外叙述有： (1)设计算法将 个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点，而 C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学2OO0四、2 (4分)】 链表的头指针，单链表的每个结点由 个整数域daa和指针域NEXT H， ,整数在单链表中是无序的。设计算 将链表中 结 数链和 数链，分别由P,Q指向，每个链中的数据按由小到大排列，算法中不得申请新 12分 点的单链表A和B,使得A表中含有原表中序号为奇数的元素，而B表中含 与出其类型定义 偶数的元素 且保持 相对 【山东大学1998九9分)】【山东工业大学 (9 )按顺 字于 试设计用最少时间把所有值为负数的元素移到全部正数 值元素前边的算法：例： x.XX.x x)为 【东北大学1998 15分)】 类似本题的另外叙述有： (1)设有一元素为整数的线性表L=(a1,2,3,.,a),存放在一维数组AN]中，设计一个算法，以表中a作为参考元素，将该表分为 左、右两部分，其中左半部分每个元素小于等于a,右半部分每个元素都大于，位于分界位置上腰求结果仍存放在AN]中)。 【北京理工大学1999八(6分)】 顺房 放入C中 存储的线性表A,其数据元素为整型，试编写一算法，将A拆成B和C两个表，使A中元素值大于等于0的元素放入B,小于0时 1)表B和C另外设置存储空间： 2)表B和C不另外设置，而利用A的空间.【山东大学2001九、112分)】 (3)知线性表(l,2,3,.m)按顺序存储，且每个元素都是整数均不相同，设计把所有奇数移到所有偶数前边的算法 (要求时间最少，辅助空间最少)【东北大学1997三15分)】 (④编写函数将一整数序列中所有负数移到所有正数之前，要求时间复杂度为0() 【南京航空航天大学2001八(10分)】 (⑤)已知一个由n(设n=1000)个整数组成的线性表，试设计该线性表的一种存储结构，并用标准pasa语言描述算法，实现将 中所有天手等于的整放在浙清小于的鑫之后要球量法的时度张度0空杂度0山。西麦交通 9.试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。vo过deke(Lkst&L) ht电hwg b diong.con/ooran付ocum en/h02h加（第14/17页）2010-4151100
第2章 线性表 （5）已知递增有序的单链表A,B和C分别存储了一个集合，设计算法实现A：=A∪（B∩C），并使求解结构A仍保持递增。要 求算法的时间复杂度为O(|A|+|B|+|C|)。其中,|A|为集合A的元素个数。 【合肥工业大学 2000 五、1（8分）】 3. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合 并成一个带头结点的循环单链表。【东北大学1996 二 (12分)】 类似本题的另外叙述有： （1）试用类Pascal语言编写过程PROC join（VAR la：link； lb：link） 实现连接线性表la和lb(lb在后)的算法，要求其时间复 杂度为0（1）， 占用辅助空间尽量小。描述所用结构。 【北京工业大学 1997 一、1 (8分)】 （2）设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与 链表长度无关。【南京航空航天大学 1997 四（8分）】 4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类PASCAL语言给出 一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。【北京工业大 学 1997 一、2 (12分)】 5. 已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。请写一算法，将该链 表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。【北京航空航天 大学 1998 五（15分）】 6. 设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递 增的有序单链表的算法。【东北大学 1996 六 (14分)】 类似本题的另外叙述有： （1）设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行 就地排序.【中科院计算所 1999 五、1（10分）】 7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编 一PASCAL过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序 中不得使用 NEW过程申请空间。【山东大学1993六( 15分)】 类似本题的另外叙述有： （1）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而 C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学 2000 四、2 （4分）】 (2) 设L为一单链表的头指针，单链表的每个结点由一个整数域 data和指针域NEXT组成，整数在单链表中是无序的。设计算 法，将链表中结点分成一个奇数链和一个偶数链，分别由P，Q指向，每个链中的数据按由小到大排列，算法中不得申请新的 结点空间。【青岛海洋大学 1999 三（12分）】 (3) 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含 有原表中序号为偶数的元素，且保持其相对顺序不变。 1) 写出其类型定义： 2) 写出算法。【山东大学 1998 九 (9分)】 【山东工业大学 2000 九（9分）】 8. 已知线性表（a1 a2 a3 .an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数 值元素前边的算法：例：（x,-x,-x,x,x,-x .x）变为（-x,-x,-x.x,x,x）。 【东北大学 1998 二 (15分)】 类似本题的另外叙述有： （1）设有一元素为整数的线性表L=(a1,a2,a3,.,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为 左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。 【北京理工大学 1999 八（6分）】 （2）顺序存储的线性表A,其数据元素为整型,试编写一算法,将A拆成B和C两个表,使A中元素值大于等于0的元素放入B,小于0的 放入C中. 要求: 1）表B和C另外设置存储空间; 2）表B和C不另外设置,而利用A的空间.【山东大学 2001 九、1 (12分)】 （3）知线性表（a1, a2,a3,.,an）按顺序存储，且每个元素都是整数均不相同，设计把所有奇数移到所有偶数前边的算法。 （要求时间最少，辅助空间最少）【东北大学 1997 三 (15分)】 (4) 编写函数将一整数序列中所有负数移到所有正数之前，要求时间复杂度为O（n） 【南京航空航天大学 2001 八（10分）】 (5) 已知一个由n（ 设n=1000）个整数组成的线性表，试设计该线性表的一种存储结构，并用标准pascal语言描述算法，实现将 n个元素中所有大于等于19的整数放在所有小于19的整数之后。要求算法的时间复杂度为O(n),空间复杂度O(1)。【西安交通大 学 1996 六（11分）】 9. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist &L） http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 14／17 页）2010-4-15 11:00:46
第2章线性表 【北言大2001 (8)】 10.己知非空线性链表由s指出， 链结占的物浩为(da恒k)诸写一算法，将锋表中据域值最小的那个精结占移到链表的 最前面。 要求：不得额外申请新的链结点。 【北京航空航天大学2001四(10分)】 11.己知p指向双向循环链表中的一个结点，其结点结构为daa、k、k三个域，写出算法change(p),交换p所指向的结点和它 的前缀结点的顺序。【首都经贸大学1997 2(15分)】 12.线性表a1,2,.,品)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成： (1)用最少时间在表中查找数值为x的元素。 2) 若找到 其到 使表中元素仍递增有序。 99 (12分)】 指针为h, 是知两个单表入和其指轩 对称 【首都 中dat域 写出算法dch,n),判断该链表的前n个字 分别为heada 编 大学程从单表A中除自第个元素起的共个元素，然后将 元素之前 2000 (10分) (1)hl、h2为两个链表的表头指针，结点结构为dat和hk两个域组成。写出算法ndel,h2,ijD,将链表hl从第个结点起的个 结点删除，并插入到2表的第个结点之前」 【首都经留大学1998二 、10(20分)】 15.设线性表存于A1se]的前num各分量中，且递增有序。请设计 ,个算法，将x插入到线性表的话当位署上，以保持线性表 的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。 【西安电子科技大学1999计应用1997二(10分)】 13,21, 28, 42,}中插入数据元素26的程序。（要求该程序用turbo Pascal语言编制并能在计算机上运 构) 1996二、116分) 6 结 a 其中daa为数据域pe为指针域，它的值为空指针(NL)mnk ,将此表改成双向循环链表。 己知递增有序的单链表 ，的元素所构成的集合 分别存储 ,请设计算法以求出两个集合A和B的差集AB(即仅由在A中出现而不在E 并以同样的形式存储，同时返回该集合的元素 个数 学2000计应用19 10分 18.已知 并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等 于其序号的平方减去其前驱的值，若满足则返回e,否则返回e 【西安电子科技大学2000软件1997二(10分)】 19.两个整数序列A=al,a2,a3,.,am和B=b1,b2,b3,.,bn己经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序 列。【东北大学1999二(10分)】 20.L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结 点顺序完全倒置的算法。【东北大学1997四(15分)】 例： 类似本题的另外叙述有： )知L为链表的头结点地址，表中共有m血>3)个结点，从表中第个结点1<Km)起到第m个结点构成一个循环部分链表，设 计将这部分循环链表中所有结点顺序完全倒置的算法。 【东北大学1998三15分)】 21.请写一个算法将顺序存储结构的线性表(1)逆置为)。【大连海事大学1996八(6分)】 ht电w.biiong.oon加 ocam entaowan/使52h加（第15/17页）2010-4日511006
第2章 线性表 【北京理工大学 2001 九、3 （8分）】 10. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的 最前面。要求：不得额外申请新的链结点。【北京航空航天大学 2001 四（10分）】 11. 已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它 的前缀结点的顺序。【首都经贸大学 1997 二、2（15分）】 12. 线性表(a1,a2,a3,.,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成： （1） 用最少时间在表中查找数值为x的元素。 （2） 若找到将其与后继元素位置相交换。 （3） 若找不到将其插入表中并使表中元素仍递增有序。【东北大学 1996 三 ( 12分)】 13. 设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字 符是否中心对称。例如 xyx, xyyx都是中心对称。【首都经贸大学1998三、9（15分）】 14. 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将 单链表A插入到单链表B的第j个元素之前。 【中国矿业大学 2000 三（10分）】 类似本题的另外叙述有： （1）h1、h2为两个链表的表头指针，结点结构为data和link两个域组成。写出算法inde(h1,h2,i,j,l),将链表h1从第i个结点起的l个 结点删除，并插入到h2表的第j个结点之前。 【首都经贸大学 1998 三、10（20分）】 15. 设线性表存于A[1.size]的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表 的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。 【西安电子科技大学 1999计应用 1997 二 （10分）】 类似本题的另外叙述有： (1) 试编制在线性表L={12,13,21,24,28,30,42,}中插入数据元素26的程序。（要求该程序用turbo Pascal语言编制并能在计算机上运 行，结点类型为链式结构）【大连海事大学 1996 二、1 (16分)】 16. 假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针（NIL）；link 为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学 1999软件 五（10分）】 17. 已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B 的差集A-B（即仅由在A中出现而不在B 中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 【西安电子科技大学2000计应用1997 二 （10分）】 18. 已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等 于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false. 【西安电子科技大学2000软件1997 二（10分）】 19．两个整数序列A=a1,a2,a3,.,am和B=b1,b2,b3,.,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序 列。【东北大学 1999 二 (10分)】 20．L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结 点顺序完全倒置的算法。【东北大学 1997 四 (１５分)】 例： 类似本题的另外叙述有： (1) 知L为链表的头结点地址，表中共有m(m>3)个结点，从表中第i个结点(1<i<m)起到第m个结点构成一个循环部分链表，设 计将这部分循环链表中所有结点顺序完全倒置的算法。 【东北大学 1998 三 (15分)】 21. 请写一个算法将顺序存储结构的线性表（a1.an）逆置为(an.a1)。【大连海事大学1996八(６分)】 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 15／17 页）2010-4-15 11:00:46
第2章线性表 外叙述 链表，编程将链表颠倒过来要求不用另外的数组或结点完成 【南 航空航天大学 的单向链表 数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为 (n 航空航天 51007 【南京航空航天大学1995十 :(10分)】 ⑤)试编写算法，将不设表头结点的、不循环的单向链表就地逆转。【北方交通大学1997五(10分)】 6)有 一个单链表L.(至少右1个结占) 其头结点指针为hd,编写一个过程将L逆置，即最后一个结点变成第一个结点，原来 到7草 二个结点变成第二个结点，如此等等。【燕山大学2001四、2(8分)】 22.设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： (1)找出最小值结点，且打印该数值： (2)若该数值是奇数，则将其与直接后继结点的数值交换： (3)若该数值是 学2000 L为没有头 的的 农中 结点数6分】 子 个字符 该字符可能是英文字母字符或数宁 编 头结 点的单循环链表表示的线性表，使每个表中只含同一类字符。（要求用最少的 增有序的 有数值 分注时 表中不 间复杂 【北 业大学199 5分) 将变作 “在输入数据无序 个数据值为整型的递增有序的顺序存储线性表L,且要求当输入相同数据值时，线性表 中不能存在数据值相同的数据元素，试写出其算法 顺序存储结构的线性表描述为 C0 NST m axken=线性表可能达到的最大长度： TYPE slistn=RECO RD ekm anay[1.m ax en]of n teger lst 0.m axen END RL:s幻st抑：【同济大学1998 :12分)】 26.设有 个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 用 0确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列20,20,17,16,15,15，山，10,87,75,4中比10大的数有 数按 减次序排列 个算 结点东北 01一17分）】 HEAD是i 孩链表的头指针，P指向该链表中某一结点。【吉材 001- 7分)】 本题的另外伏有 ①)己知非空线性链表第一个结点由Ls指出，请写一算法，交换p所指的结点与其下一个结点在链表中的位置（设即指向的不是 链表最后那个结点)。【北京航空航天大学1999五(10分)】 ②)已知任意单链表如图所示编者略去图)。Had为表头指针，指向表的第一个元素，p为指向表中任意结点的指针，试设计 个算法，将指向的结点和其后面结点交换位置（可采用任何高级语言描述算法）。 【山东大学1992 (12分)】 28.设键盘输入n个英语单词，输入格式为n,W1,W2“,wn其中表示随后输入英语单词个数，试编一程序，建立一个单向链 表，实现0除 则只在链表上保 (单考生 (2)除满足 1)的地 计数域 个单词（统考生做 大学1998力 记录该单词重复出现的次数，然后输出出现次数最多的前kk<= 【南京 29.已知一双向循还链 第 个结点至表尾递增有序， (设a〈x<a)如下图(“第二个结点至表尾”指4，因篇幅所 限，编者略去图)。试编写程序，将第一个结点副除并插入表中适当位置，使整个链表递增有序。【南京航空航天大学1998八 (10分)】 30.已知长度为的线性表A采用顺序存储结构，请写一时间复杂度为0)、空间复杂度为01)的算法，该算法删除线性表中所 有值为m的数据元素。(0(1)表示算法的辅助空间为常量)。 字2000五（10分) 31.设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相 m体Dn/02h加（第16/17页）2010-4-151100
第2章 线性表 类似本题的另外叙述有： (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<x<an）如下图(“第二个结点至表尾”指a1.an ，因篇幅所 限，编者略去图)。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。【南京航空航天大学1998八 （10分）】 30. 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所 有值为item的数据元素。（O（1）表示算法的辅助空间为常量）。 【北京航空航天大学 2000 五（10分）】 31．设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表 ，表中结点按乘客姓氏的字母序相 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 16／17 页）2010-4-15 11:00:46