《《数据结构》期末考试复习题第2章线性表.pdf》由会员分享，可在线阅读，更多相关《《数据结构》期末考试复习题第2章线性表.pdf（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章 线性表 选择题1 .下述哪一条是顺序存储结构的优点？（）A.存 储 密 度 大 B.插 入 运 算 方 便 C.删 除 运 算 方 便 D.可方便地用于各种逻辑结构的存储及示2.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。3 .线性表是具有n个（）的有限序列（n 0）A.表元素 B.字符 C.数据元素 D.数据项 E.信息项4 .若某线性表最常用的操作是存取任指定序号的元素和在最后进行插入和删
2、除运算,则 利 用（）存储方式最节省时间。A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则 采 用（）存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表6 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。A.单链表 B.单循环链表 C.带尾指针的单循环链表 D.带头结点的双循环链表7 .若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采 用（）存储方式最节省运算时间。A.单链表 B.双链表 C.单
3、循环链表 D.带头结点的双循环链表8 .静态链表中指针表示的是（）.A.内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址9 .链表不具有的特点是（）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比1 0 .下面的叙述不正确的是（）A.线性表在链式存储时，查找第i 个元素的时间同i 的值成正比B.线性表在链式存储时，查找第i 个元素的时间同i 的值无关C.线性表在顺序存储时，查找第i 个元素的时间同i 的值成正比D.线性表在顺序存储时，查找第i 个元素的时间同i 的值无关1 1.线性表的表元存储方式有（1）和链接两种。试指出下列各
4、表中使用的是何种存储方式：表 1 是（2）存储方式；表 2 是（3）存储方式；表 3是（4）存储方式；表4是（5）存储方式。表左的s 指向起始表元。表元编号货号数量表元间联系16 1 84 02220 52331 0 31 5445 0 120557 8 11 7669 1 0240表 1s-表元编号货号数量表元间联赛16 1 84 05220 52131 0 31 5445 0 120257 8 11 7669 1 0243表 2表元编号货号数量表元间联赛16 1 84 05220 52131 0 31 5445 0 120057 8 11 7669 1 0243s-表元编号货号数量表元 间
5、联系1216 1 84 052220 521031 0 31 54645 0 1200357 8 11 76169 1 02435s-表 3表 4A.连 续 B.单 向 链 接 C.双向链接 D.不 连 接 E.循环链接F.树状 G.网状 I I.随 机 I.顺 序 J.顺序循环1 2.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i 个元素的时间与i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是()A.(1),(2)B.(1)C.(1),(2),(3)
6、D.(2)1 3 .若长度为n的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为()(l =i Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink二q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=:q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;24.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：()。A.
7、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;2 5.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是()A.hea d=NU LL B.hea d-n ext=NU LL C.hea d n ext=hea d D.hea d!=NU LL2 6 .在双向链表存储结构中，删除p所指的结点时须修改指针（）。A.(p*.llin k)*.r l in k:=p r l in kB.p.llin k:=(p.llin k).llin
8、 kC.(p*.r lin k)*.llin k:=pD.p.r lin k:=(p.llin k).llin k(p.r lin k)llin k:=p*.llin k;(p二 llin k)r lin k:=p;p.r lin k:=(p.r lin k).r lin kp llin k:=(p r lin k)r lin k2 7 .双向链表中有两个指针域，llin k和r lin k分别指向前趋及后继，设p指向链表中的一个结点，现要求删去P所指结点，则正确的删除是（）（链中结点数大于2,p不 是 第 个结点）A.p-.llin k.r lin k:=p llin k;p-.llin k
9、.r lin k:=p-.r lin k;dispo se（p）;B.dispo se（p）;p.llin k.r lin k:=p*.llin k;p.llin k,r lin k:=p r lin k;C.p-.llin k.r lin k:=p*.llin k;dispo se（p）;p*.llin k.r lin k:=p.r lin k;D.以上A,B,C都不对。二、判断1 .链表中的头结点仅起到标识的作用。（）2.顺序存储结构的主要缺点是不利于插入或删除操作。（）3 .线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）4 .顺序存储方式插入和删除时效率太低，因此它不
10、如链式存储方式好。（）5 .对任何数据结构链式存储结构一定优于顺序存储结构。（）6 .顺序存储方式只能用于存储线性结构。（）7 .集合与线性表的区别在于是否按关键字排序。（）8 .所谓静态链表就是一直不发生变化的链表。（）9 .线性表的特点是每个元素都有一个前驱和个后继。（）1 0 .取线性表的第i个元素的忖间同i的大小有关.（）1 1.循环链表不是线性表.（）1 2 .线性表只能用顺序存储结构实现。（）1 3 .线性表就是顺序存储的表。（）1 4 .为了很方便的插入和删除数据，可以使用双向链表存放数据。（）1 5.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）1 6 .链表是采
11、用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（）三、填空1 .当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。2 .线 性 表L=（a l,a 2,a n）用数组表示，假定删除表中任一元素的概率相同，则删除个 元 素 平 均 需 要 移 动 元 素 的 个 数 是。3 .设单链表的结点结构为（da t a,n ext）,n e x t为指针域,已知指针p x指向单链表中da t a为x的结点，指针p y指向da t a为y的新结点，若将结点y插入结点x之后，则需要执行以下语句:；;4 .在一个长
12、度为n的顺序表中第i个 元 素（l=i 0 D OBE G I N(2)_；生如re ad (k)E N D;n e x t：=N I L;END;2 1.已给如下关于单链表的类型说明：T YP El i s t=n o d e ;n o d e=R E C O R Dd at a:i n t e g e r;n e x t:l i s t;E N D;以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性(升 序)，这里两链表的头指针分别为P 和 q.P R O C E D U R E m e rg e l i n k(V A R p,q:l i s t):V A R
13、 h,r:l i s t;BE G I Nh T.n e x t:=N I L;r:=h;WHI L E (p O N I L)A N D (q O N I L)D OI F (p d at a=q d at a)T HE N BE G I N ；r:=p;p:=p n e x t；E N DE L S E BE G I N (3)；r:=q;q:=q n e x t;E N D;I F (p 二 N I L)T HE N rn e x t:=q;；p:二 h 二 n e x t;d i s p o s e(h);E N D;2 2.假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链
14、接起来的带表头结点的环形链表。各链表的表头结点的值为m ax,且链表中其他结点的值都小于m ax,在程序中取 m ax 为 9 9 9 9。在各个链表中，每个结点的值各不相同，但链表P和链表q可能有值相同的结点(表头结点除外)。下面的程序将链表q 合并到链表p中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达式，链表的结点类型如下T YP E n o d e p t r=n o d e t yp e；n o d e t yp e 二 R E C O R Dd at a：i n t e g e
15、r；l i n k：n o d e p t r;E N D；C O N S T m ax=9 9 9 9;P R O C E D U R E m e rg e(V A R p:n o d e p t r;q:n o d e p t r);V A R r,s:n o d e p t r;BE G I Nr:=p;WHI L E (A)D OBE G I NWHI L E r l i n k .d at a q l i n k ,d at aT HE N BE G I N s:=(C);(D):=s .l i n k;s .l i n k:三 ;(F):=s;(G);E N DE L SE B E
16、 GIN (H);s:=q l in k;(I)；d is po s e(s)E N DE N D;d is po s e(q)E N D;2 3 .P RO C in s _ l in k l is t(l a:l in k is t t p;i:in t e g e r;b z e l e m t p);l a 为指向带头结点的单链表的头指针，本算法在表中第i 个元素之前插入元素b)P：=0)；j：=U);指针初始化，j 为计数器W HIL E (pO N IL)A N D )D O p:=(4);j:=j+l;寻 找 第 i T 个结点IF (p=N IL)O R()THE N e r
17、r o r (N o t his po s it io n)E L SE n e w(s);s f .d a t a:=b;s t .n e x t:=p t .n e x t;p t .n e x t:=s;E N D P;in s-l in k l is t 2 4 .已知双链表中结点的类型定义为：TYP E d po in t e r=*l is t;l is t=RE C O RDd a t a:in t e g e r;l e f t,r ig ht:d po in t e r;E N D;如下过程将在双链表第i 个结点(i=0)之后插入一个元素为x的结点，请在答案栏给出题目中 处应
18、填入的语句或表达式，使之可以实现上述功能。P RO C E D URE in s e r t(VA R he a d:d po in t e r;i,x:in t e g e r);VA R s,p:d po in t e r;j:in t e g e r;B E GINn e w(s);s d a t a:=x;IF(i=0)THE N B E GIN s r ig ht:二 he a d;0)he a d:二 s E N D 如果 i=0,则将 s 结点插入到表头后返回E L SE B E GIN p:二 he a d;(2)；在双链表中查找第i 个结点，山p 所指向W HIL E (pO
19、 N IL)A N D (j 0)指明环形链表的结点个数，参数 i(l i 0 THE NB E GIN n e w(he a d);p:二 he a d;F O R i:=l TO n-1 D OB E GIN p d a t a:=i;n e w(q);(A);(B)E N D；p d a t a:=n;(C);E N D;C r e a t _l in k _l is t:=he a dE N D;P RO C E D URE jo s e phu s(n,i,m:in t e g e r);VA R p,q:n o d e pt r;j:in t e g e r;B E GIN p:二
20、 C r e a t _l in k is t (n);W HIL E i l D O B E GIN p:=p l in k;i:=i-l E N D;(D)；W HIL E j n D OB E GINF O R i:=1 TO m-1 D O p:=p l in k;(E);w r it e(q .d a t a:8);(F);d is po s e(q);j：=j+lE N DE N D;2 7 .对于给定的线性链表h e a d,下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为一个完整的程
21、序过程，每个空框只填一个语句。TYP E n o d e pt r 二 n o d e t y pe；n o d e t y pe =RE C O RDd a t a :in t e g e r；l in k :n o d e pt rE N D;VA R he a d :n o d e pt r；P RO C E D URE s o r t o u t pu t d e l e t e (he a d :n o d e pt r);VA R p,q,r,s:n o d e pt r;B E GIN W HIL E he a d N IL D OB E GIN p:=N IL ；q:=he a
22、 d；r:=q ；s:=q l in k ；W HIL E s N IL D OB E GIN IF s 二 d a t a p p r e.fr eq DO p:=p p r e;IF p Oq THEN j(3);IF(4)THEN q*.n ex t:=p,q p r e;=p .p r e;p*.p r e*,n ex t:=q;p p r e:=q r et u r n (q);END;29.循环链表a和 b 的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环链表c,其中结点的值为同时在a,b 两链表中出现的字母，且 c 中字母不重复，请补上程序中空缺的部分，并估
23、计算法的时间复杂度。(设 a,b 的结点数分别为m,n)TYPEl in k=n o de;n o de=RECORDk ey:cha r;n ex t:l in kEND;PROC jj(a,b:l in k;VAR c:l in k);VAR p,q,r,s:l in k;BEGINn ew(c);c n ex t:=c;q:=a;p:=a n ex t;WHILE p Oa DOL ；WHILE p k ey=p n ex t k ey DO q:=p;p=p .n ex t ;跳过相同字母r:=b n ex t ;(2);WHILE r k ey p k ey DO r:=r n ex
24、 t;IF r Ob THEN s:=p;n ex t:=p n ex t;(3);s n ex t:=c n ex t;c n ex t:=s;c:=s ELSE q:=p;p:=p n ex t ;c:=c n ex t；END;算法时间复杂度为0 30.以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。v o id r ev er s e(p o in t er h)/*h 为附加头结点指针；类 型 p o in t er 同算法设计第3 题*/p o in t er p,q;p=h-n ex t;h-n ex t=NU LL;w hil e()q=p;p=p-n
25、ex t;q-n ex t=h-n ex t;h-n ex t=(2);31.下 面 是 用 c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L 返回逆置后的链表的头指针，试在空缺处填入适当的语句。v o id r ev er s e(l in k l is t&L)p 二 n u l l；q=L；w hil e(q!=n u l l)(1)；q-n ex t=p；p=q；(2);(3);32.下面程序段是逆转单向循环链表的方法，p o 是原链表头指针，逆转后链表头指针仍为POo(可以根据需要增加标识符)P：二 Po；q o：=NIL;WHILE DOBEGIN(2);(3);(
26、4);(5)END;p n ex t:=q0;p0 n ex t:=p;p o:=p;【中国人民大学 2000 二、1 (4 分)】33.一个无头结点的线性链表(不循环)有两个域。数据域da t a,指 针 域 n ex t,链首hea d,下面算法用r ea d(n u m)读入数据，当 n u m小于0 时，输入结束。建立一个数据以递增序组成的链表。PROC in s er t (hea d,x);在链首为hea d的表中按递增序插入x n ew(r);r .da t a:二 x;IF hea d=NILTHEN hea d:=(l);r 八.n ex t:=(2)ELSE IF(3)TH
27、EN r .n ex t:=hea d;hea d:二 r ELSE p:=hea d;WHILE X 4)AND(p 八.n ex t NIL)DOq:=p;；IF(6)THEN q .n ex t:二 ；r 八.n ex t:=(8);ELSE p 人.n ex t:=(9);r 人.n ex t :=(1 0)；ENDP;PROC cr ea t(hea d);hea d:=(11);r ea d(n u m);WHILE n u m0 DO in s er t(hea d,n u m);r ea d(n u m)ENDP;34.一元稀疏多项式以循环单链表按降基排列，结点有三个域，系数域
28、co ef,指数域ex p和指针域n ex t；现对链表求一阶导数,链表的头指针为h a,头结点的ex p 域 为-1。der iv at iv e(ha)q=ha;p a=ha-nex t;w hile(1)if(2)(3);fr ee(p a);p a=(4);els e p a-coef(5);p a-ex p(6);q=(7);p a二(8);)35.下面是删除单链表L中最大元素所在结点的类P A S C A L 语言算法，请在横线填上内容，完成其功能。T YP E p oint er =t node；node=R EC O R Ddat a:int eger;nex t:p oint
29、 erEN D;P R O C EDU R E delmax (L:p oint er);V A R p,q,r:p oint er;m:int eger;B EGI Nr:=L；p:=L t .nex t;I F p O N I L T H EN m:=p f .dat a;(1);p:=p t .nex t;W H I L E p O N I L DO IF(2)THE N ;m:=p t .dat a;(4)_;p:=p t .nex t;Fq:=r f .nex t;(5)；dis p os e(q);EN D;36.对单链表中元素按插入方法排序的C 语言描述算法如下，其中L为链表头结
30、点指针。请填充算法中标出的空白处，完成其功能。t y p edef s t r u ct node int dat a;s t r u ct node*nex t;linknode,*link;v oid I ns er t s or t(link L)link p,q,r,u;p=L-nex t;_(1)_；w hile(2)r=L;q=L-nex t;w hile(3)&q-dat a dat a)r=q;q=q-nex t;u=p-nex t;_(4)_;1 5);p=u;)37.下面是一个求两个集合A和 B之差C=A-B 的程序，即当且仅当e 是 A的一个元素，但不是 B中的一个元素时
31、，e 才是C中的一个元素。集合用有序链表实现，初始时，A,B 集合中的元素按递增排列，C为空；操作完成后A,B保持不变，C中元素按递增排列。下面的函数ap p end(las t,e)是把值为e 的新结点链接在由指针las t 指向的结点的后面，并返回新结点的地址；函数differ ence(A,B)实现集合运算A-B,并返回表示结果集合C的链表的首结点的地址。在执行A-B 运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当 A-B 运算执行完毕，再删除并释放表示结果集合的链表的表头结点。程序(a)(编者略去这个P A S C A L 程序)程 序(b)t y p
32、 edef s t r u ct node int element;s t r u ct node*link;N 0DE;N O DE*A,*B,*C;N O DE ap p end(N O DE*las t,int e)las t-link=(N O DE*)malloc(s iz eof(N O DE);las t-link-element=e;r et u r n(las t-link);N O DE*differ ence(N O DE*A,N O DE*B)N O DE*C,*las t;C=las t=(N O DE*)malloc(s iz eof(N O DE);w hile
33、if(A-element element)las t=ap p end(las t,A-element);A=A-link;els e if X 2)A=A-link;B=B-link;EL S E U);w hile(4)las t=ap p end(las t,A-element);A=A-link;(5)：las t=C;C=C-link;fr ee(las t);r et u r n(C);)/*call for m:C=differ ence(A,B);*/四 应 用 题1.线性表有两种存储结构：一是顺序表，二是链表。试问：(1)如 果 有 n 个线性表同时并存，并且在处理过程中各表
34、的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？(2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？2 .线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素;其二，山于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三,表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。3.若较频繁地对个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？4.线 性 结 构 包 括、和。线性表的存储结构分成 和。请用类P
35、 A S C A L 语言描述这两种结构。5 .线 性 表(a,a?,，)用顺序映射表示时，&和 an,(K=i n)的物理位置相邻吗？链接表示时呢？6 .说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。7 .试述头结点,首元结点,头指针这三个概念的区别.8 .己知有如下定义的静态链表：T Y P E c o m po n e n t=R E C O R Dd ata:e l e m tp;n e x t:0.m ax sizeE N DV A R stal ist:A R R A Y 0.m ax size O F c o m po n e n t;以及三
36、个指针:a v 指向头结点，p 指向当前结点，pre 指向前驱结点，现要求修改静态链表中 n e x t域中的内容，使得该静态链表有双向链表的功能，从当前结点p 既能往后查找，也能往前查找：(1)定义n e x t域中的内容。(用老的n e x t域中的值表示)；(2)如何得到当前结点p 的 前 驱(pre)的前驱，给出计算式；(3)如何得到p 的后继，给出计算式；【中科院计算所2 0 0 0 四(1 0 分)】9 .在单链表和双向链表中，能否从当前结点出发访问到任何一个结点？1 0 .如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？1 1 .下面是一算法的核心部分，试
37、说明该算法的功能。pre:=L t .n e x t;（L是一单链表，结点有数据域d ata和指针域n e x t）I F p r eO N I L T H E NW H I L E p r e t .n ext O N I L D OB E G I N p:=p r e t .n ext;I F p t .d a t a 二p r e t .d a t a T H E N p r e:=p E L S Er et u r n（f a l s e）E N D;r et u r n （t r u e）;【燕山大学2 0 0 0七、1 （7分）】1 2.设单链表结点指针域为n ext,试写出删除链
38、表中指针p所指结点的直接后继的C语言语句。1 3.设单链表中某指针p所指结点（即p结点）的数据域为d a t a,链指针域为n ext,请写出在P结点之前插入s结点的操作（P A S C A L语句）。【北京科技大学1 999 一、2 （2分）】1 4.有线性表（正 的,a）采用单链表存储，头指针为H,每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。（1）线性表中元素无序。（2）线性表中元素按递增有序。（3）线性表中元素按递减有序。1 5.设p a,p b分别指向两个带头结点的有序（从小到大）单链表。仔细阅读如下的程序，并回答问题：
39、（1）程序的功能。（2）s i,s 2中值的含义。（3）p a,p b中值的含义。P RO C E D U RE exa m（p a,p b）B E G I Np l:=p a t .n ext;p 2:=p b t .n ext;p a t .n ext:=A;s i:=0;s 2:=0;W H I L E p l K 八 A N D p 2 H 八 D O C A S E p l t .d a t a p 2 t .d a t a:p 2:=p 2 t .n ext;p l t .d a t a二p 2 t .d a t a:p:=p l;p l:=p l t .n ext;p t .n
40、ext:=p a t .n ext;p a f .n ext:=p;p 2:=p 2 f .n ext;s l:=s l+l;E N D；W H I L E p l#=A D O p:=p l;p l:=p l f .n ext;d i s p os e（p）;s 2:=s 2+l E N D;1 6 .写出下图双链表中对换值为2 3和1 5的两个结点相互位置时修改指针的有关语句。结点结构为：（1 1 i n k,d a t a,r l i n k）【北京邮电大学1 992三、4 （2 5/4分）】1 7 .按照下列题目中的算法功能说明，将算法描述片段中的错误改正过来。（1）（4分）下面的算法
41、描述片段用于在双链表中删除指针变量p所指的结点：p r l i n k-p二 l l i n k r l i n k;p l l i n k-p.r l i n k .l l i n kd i s p os e（p）;（2）（6分）下面的算法描述片段用于在双链表中指针变量p所指结点后插入一个新结点：n ew(q);q l l i n k-p;p r l i n k-q;q 二 r l i n k*-p r l i n k;q-p r l i n k 二l l i n k;【山东 大 学 1 999八(1 0 分)】1 8 .已知L是一个数据类型l i n k ed l i s t 的单循环链表
42、，p a 和 p b 是指向L中结点的指针。筒述下列程序段的功能。T YP E l i n k ed!i s t=t n od e;n od e=RE C O RDd a t a:d a t a t y p e;n ext:l i n k ed l i s tE N D;P RO C M p(p a,p b:l i n k ed l i s t);P RO C s u b p(s,q:l i n k ed l i s t);p：=s;W H I L E p t .n ext O q D O p:=p t .n ext;p t .n ext:=sE N D P;s u b p (p a,p b)
43、;s u b p (p b,p a);E N D P;1 9.设双向循环链表中结点的数据域、前驱和后继指针域分别为d a t a,p r e和 n ext,试写出在指针P所指结点之前插入一 s 结点的C 语言描述语句。2 0 .本题给出一个子程序的框图，如图2,试填空完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表f l,f 2,f 3 中的相同整数。假定在调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1 的例子所示。图 1：da t a l in kala 2图2：found*-false注：在图2 的框图中:f o u n d和 e xit 均为布
44、尔型的变量,可取值为t r u e 和 f a l s e。va l是整型变量，用来存放第一个均出现在f l,f 2,f 3中的相同整数。若 f l,f 2和 f 3中无相同的整数，f o u n d的值为f a l s e,否 则 f o u n d的值为t r u e。f l t .l in k 表示访问f l 所指结点的l in k 域。21.一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法：(1)说明该算法的功能。(2)在空缺处填写相应的语句。vo id u n k n o wn (B NO DET P *L)p=L-n e xt;q=p-n e xt;r=q-n e xt
45、；whil e (q!=L)whil e (p!=L)&(p-da t a q-da t a)p=p-p r io r；q-p r i o r-n e xt=r ；_(1)_ _ _ _ _ _ _;q-n e xt=p-n e xt；q-p r io r=p；(2)；3)_ _ _ _ _ _ _;q=r：p=q-p r io r：(4)；)五、算法设计题1.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。类似本题的另外叙述有:(1)设有两个无头结点的单链表,头指针分
46、别为ha,hb,链中有数据域da t a,链域n e xt,两链表的数据都按递增序存放,现要求将hb 表归到ha 表中，且归并后ha 仍递增序,归并中ha表中一有的数据若hb 中也有,则hb 中的数据不归并到ha 中,hb 的链表在算法中不允许破坏。【南京理工大学19 9 7四、3(15 分)】P R O CEDUR E m e r g e(ha,hb);(2)已知头指针分别为l a 和 1 b 的带头结点的单链表中，结点按元素值非递减有序排列。写 出 将 l a 和 1 b 两链表归并成一个结点按元素值非递减有序排列的单链表(其头指针为1c),并计算算法的时间复杂度。2.图(编者略)中带头结
47、点且头指针为ha 和 hb 的两线性表A和 B分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和 B的并集A UB。要求该并集中的元素仍保持递增有序。且要利用A和 B的原有结点空间。类似本题的另外叙述有:(1)己知递增有序的两个单链表A,B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A UB(2)已知两个链表A和 B分别表示两个集合，其元素递增排列。编一函数，求 A与 B的交集，并存放于A链表中。(3)设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法(即L in L 2)要求结果链表仍是从小到大排序，但无重复元素。(4)己知两个线性表A ,B均
48、以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A与 B的交集C,要求C 另开辟存储空间，要求C 同样以元素值的递增序的单链表形式存贮。(5)已知递增有序的单链表A,B和 C 分别存储了一个集合，设计算法实现A：=A U(B A C),并使求解结构A仍保持递增。要求算法的时间复杂度为O(|A|+|B 1+|C|)。其中，|A|为集合A的元素个数。3.知 L I、L 2分别为两循环单链表的头结点指针，m,n 分别为L I、L 2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。类似本题的另外叙述有:(1)试用类 P a s c a l 语言编
49、写过程 P R O C j o in (V A R l a：l in k；l b：l in k)实 现 连接线性表l a 和 l b(l b 在后)的算法，要求其时间复杂度为0 (1),占用辅助空间尽量小。描述所用结构。（2）设有两个链表，h a 为单向链表，h b 为单向循环链表。编写算法，将两个链表合并成个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学1 9 9 7 四（8 分）】4.顺序结构线性表L A与 L B 的结点关键字为整数。L A 与 L B 的元素按非递减有序，线性表空间足够大。试用类P AS CAL 语言给出一种高效算法，将 L B 中元素合到L A 中，使新
50、的L A的元素仍保持非递减有序。高效指最大限度的避免移动元素。5.已知不带头结点的线性链表l i st,链表中结点构造为（d a ta、l i n k）,其中d a ta 为数据域，l i n k 为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。6.设 L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。类似本题的另外叙述有:（1）设一单向链表的头指针为h e a d,链表的记录中包含着整数类型的k e y域,试设计算法,将此链表的记录按照k e