《2022年数据结构线性表有关题目及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构线性表有关题目及答案 .pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、个人收集整理仅供参考学习1 / 24 第 2 章线性表一选择题1下述哪一条是顺序存储结构的优点？（） 【北方交通大学 2001 一、 4（2 分） 】A存储密度大 B 插入运算方便 C 删除运算方便 D 可方便 地 用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（） 【北方交通大学 2001 一、 14（2 分） 】A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n 个（）的有限序列（n0） 。 【清华大学 1998 一
2、、 4（2 分） 】A表元素 B字符 C数据元素 D数据项 E信息项文档来自于网络搜索4 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。【哈尔滨工业大学 2001 二、 1（2 分） 】文档来自于网络搜索A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。【南开大学 2000 一、 3】文档来自于网络搜索A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表文档来自于网络搜索6设一个链表最常用的操作是在末尾插入
3、结点和删除尾结点，则选用( )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表【合肥工业大学 2000 一、 1（2 分） 】7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学 2000 一、 1（2 分） 】文档来自于网络搜索A单链表 B双链表 C单循环链表 D带头结点的双循环链表8. 静态链表中指针表示的是（） . 【北京理工大学 2001 六、 2（2 分） 】A 内存地址 B数组下标 C下一元素地址 D左 、右孩子地址9. 链表不具有的特点是（） 【福州大学 1998 一
4、、 8 (2分) 】A插入、删除不需要移动元素 B 可随机访问任一元素 C 不必事先估计存储空间 D 所需空间与线性长度成正比10. 下面的叙述不正确的是（） 【南京理工大学 1996 一、 10（2 分） 】A线性表在链式存储时，查找第i 个元素的时间同i 的值成正比 B. 线性表在链式存储时，查找第i 个元素的时间同i 的值无关C. 线性表在顺序存储时，查找第i 个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i 个元素的时间同i 的值无关11. 线性表的表元存储方式有( （1）) 和链接两种。试指出下列各表中使用的是何种存储方式：表1 是( （2）) 存储方式；表2 是 (（
5、3）) 存储方式；表3 是( （ 4）) 存储方式；表4是(（5）)存储方式。表左的s指向起始表元。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 24 页个人收集整理仅供参考学习2 / 24 文档来自于网络搜索表 1 s表 2 s表 3 s表 4 s供选择的答案：A. 连续 B.单向链接 C. 双向链接 D.不连接 E. 循环链接F. 树状 G.网状 H.随机 I.顺序 J.顺序循环【上海海运学院 1995 二、 1（5 分） 】12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以 ，它存取表中第 i 个元素的时间与i
6、无关。文档来自于网络搜索 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（） 【南京理工大学 2000 一、 3（1.5 分） 】 A （ 1） ， （ 2）B （ 1）C （1） ， （2）,(3) D.（2）文档来自于网络搜索13. 若长度为n 的线性表采用顺序存储结构， 在其第 i 个位置插入一个新元素的算 法 的 时 间 复 杂 度 为 （）(1=iLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；文档来自于网络搜索B. p-Llink
7、=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 的结点，正确的操作是：（） 。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;文档来自于网络搜索Cp-next=s;p-next=s-next; D
8、p-next=s-next;p-next=s;文档来自于网络搜索【青岛大学 2001 五、 3（2 分） 】25对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（）Ahead=NULL B headnext=NULL Cheadnext=head Dhead!=NULL文档来自于网络搜索【北京工商大学 2001 一、 5（3 分） 】26. 在双向链表存储结构中，删除p 所指的结点时须修改指针（） 。A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink;文档来自于网络搜索B p.llink:=(p.llink).llink
9、(p.llink).rlink:=p;文档来自于网络搜索C (p.rlink).llink:=p p.rlink:=(p.rlink).rlink文档来自于网络搜索D p.rlink:=(p.llink).llink p.llink:=(p.rlink).rlink;文档来自于网络搜索【西安电子科技大学 1998 一、 1（2 分） 】27. 双向链表中有两个指针域，llink和 rlink分别指向前趋及后继，设p 指向链表中的一个结点， 现要求 删去 p 所指结点，则正确的删除是（） （链中结点数大于2，p 不是第一个结点）文档来自于网络搜索Ap.llink.rlink:=p.llink;
10、p.llink.rlink:=p.rlink; dispose(p);文档来自于网络搜索Bdispose(p); p.llink.rlink:=p.llink; p.llink,rlink:=p.rlink;文档来自于网络搜索Cp.llink.rlink:=p.llink; dispose(p); p.llink.rlink:=p.rlink;文档来自于网络搜索D以上 A ，B，C都不对。【南京理工大学 1997 一、 1（2 分） 】二、判断1. 链表中的头结点仅起到标识的作用。( )【南京航空航天大学 1997 一、 1（ 1 分） 】2. 顺序存储结构的主要缺点是不利于插入或删除操作。(
11、 )【南京航空航天大学1997 一、2（1 分） 】文档来自于网络搜索3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 【北京邮电大学 1998 一、 2（2 分） 】4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 【北京邮电大学 2002 一、 2（1 分） 】5. 对任何数据结构链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 24 页个人收集整理仅供参考学习5 / 24 一、 3（1 分） 】文档来自于网络搜索6顺序存储
12、方式只能用于存储线性结构。( ) 【中科院软件所 1999 六、 1-2 （2 分） 】 【上海海运学院 1997 一、 1（1 分） 】7集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、 5 ( 1分) 】文档来自于网络搜索8. 所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 2000 二、 1（1 分） 】9. 线性表的特点是每个元素都有一个前驱和一个后继。( )【合肥工业大学2001 二、 1（1 分） 】文档来自于网络搜索10. 取线性表的第i 个元素的时间同i 的大小有关 . ( )【南京理工大学 1997 二、9（2分） 】文档来自于网络搜索
13、11. 循环链表不是线性表. ( )【南京理工大学 1998 二、 1（2 分） 】12. 线性表只能用顺序存储结构实现。( )【青岛大学 2001 四、 2（1 分） 】13. 线性表就是顺序存储的表。( )【青岛大学 2002 一、 1（1 分） 】14为了很方便的插入和删除数据，可以使用双向链表存放数据。( ) 【上海海运学院 1995 一、 1（1 分） 】【上海海运学院 1997 一、 2（ 1 分） 】15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 【上海海运学院 1996 一、 1（1 分） 】【上海海运学院 1999 一、 1（1 分） 】16. 链表是
14、采用链式存储结构的线性表, 进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 【上海海运学院 1998 一、 2（1 分） 】文档来自于网络搜索三、填空1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【北方交通大学 2001 二、 4】文档来自于网络搜索2线性表L=（a1,a2, ,an ）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。 【北方交通大学 2001 二、9】文档来自于网络搜索3设单链表的结点结构为(data,next)，next为指针域，已知指针px 指向单链
15、表中data为 x 的结点，指针py 指向 data 为 y 的新结点 , 若将结点y 插入结点x 之后，则需要执行以下语句 :_ ； _; 【华中理工大学 2000 一、 4（2 分） 】文档来自于网络搜索4在一个长度为n 的顺序表中第i 个元素（ 1=i0 DO BEGIN (2); (3); (4); (5); read（k） END; q.next ：=NIL; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 24 页个人收集整理仅供参考学习7 / 24 END; 【北京师范大学1999 三】21. 已给如下关于单链表的类型说明
16、： TYPE list=node ; node=RECORD data: integer; next: list; END; 以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p 和 q.文档来自于网络搜索PROCEDURE mergelink(VAR p,q:list): VAR h,r: list; BEGIN （1）_ h.next:= NIL; r:=h; WHILE(pNIL) AND (qNIL) DO IF (p.data=q.data) THEN BEGIN （2）_； r:=p; p:=p.next； END EL
17、SE BEGIN （3） _； r:=q; q:=q.next; END; IF (p=NIL) THEN r.next:=q; （4）_； p:=h.next; dispose(h); END;【厦门大学 2000 三、 2 （ 8 分）】22假设链表p 和链表 q 中的结点值都是整数, 且按结点值的递增次序链接起来的带表头结点的环形链表。 各链表的表头结点的值为max,且链表中其他结点的值都小于max ，在程序中取 max为 9999。在各个链表中，每个结点的值各不相同，但链表p 和链表 q 可能有值相同的结点（表头结点除外）。下面的程序将链表q 合并到链表p 中，使得合并后的链表是按结点
18、值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达式，链表的结点类型如下文档来自于网络搜索TYPE nodeptr=nodetype； nodetype=RECORD data：integer； link： nodeptr; END ；CONST max=9999; PROCEDURE merge(VAR p:nodeptr;q:nodeptr); VAR r,s: nodeptr; BEGIN r:=p; WHILE (A)_ DO BEGIN WHILE r.link.dataq.link.data THEN BEG
19、IN s:=(C)_;(D)_:=s.link; s.link:=(E)_;(F)_ _:=s; (G)_; END文档来自于网络搜索精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 24 页个人收集整理仅供参考学习8 / 24 ELSE BEGIN (H)_; s:=q.link; (I)_; dispose(s) END文档来自于网络搜索 END; dispose(q) END;【复旦大学 1997 五（ 18 分） 】23 PROC ins_linklist(la:linkisttp; i:integer; b:elemtp);文档
20、来自于网络搜索la为指向带头结点的单链表的头指针，本算法在表中第i 个元素之前插入元素b p:=(1) ; j:=(2) ;指针初始化，j 为计数器 WHILE (pNIL) AND (3) ) DO p:=(4) ; j:=j+1； 文档来自于网络搜索寻找第 i-1 个结点 IF (p=NIL) OR (5) ) THEN error (No this position) ELSE new(s) ; s.data:=b; s .next:=p.next; p.next:=s;文档来自于网络搜索ENDP;ins-linklist【燕山大学 1998 四、 1（15 分） 】24. 已知双链表中
21、结点的类型定义为：TYPE dpointer=list; list=RECORD data:integer; left,right:dpointer; END; 如下过程将在双链表第i 个结点 （i=0 ）之后插入一个元素为x 的结点， 请在答案栏给出题目中 _处应填入的语句或表达式，使之可以实现上述功能。文档来自于网络搜索PROCEDURE insert(VAR head:dpointer;i,x:integer); VAR s,p:dpointer; j: integer; BEGIN new(s); s.data:=x; IF(i=0)THEN BEGIN s.right:=head;
22、(1)_ head:=s END如果 i=0, 则将 s 结点插入到表头后返回文档来自于网络搜索ELSE BEGIN p:=head; (2)_； 在双链表中查找第i 个结点 , 由 p 所指向 文档来自于网络搜索 WHILE (pNIL) AND (ji) DO BEGIN j:=j+1; (3) _ END;文档来自于网络搜索 IF pNIL THEN IF （p.right=NIL） THEN BEGIN p.right:=s; s.right:=NIL; (4) _END ELSE BEGIN s.right:=p.right; (5) _;p.right:=s; (6) END文档来
23、自于网络搜索 ELSE writeln(can not find node!) END END;【厦门大学 2002 二 （12 分）】25阅读以下算法，填充空格， 使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。文档来自于网络搜索 CONST maxlen=30 TYPE sqlisttp=RECORD 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 24 页个人收集整理仅供参考学习9 / 24 elem:ARRAY1.maxlen OF integer; last:0.maxlen END; P
24、ROC exam21(VAR L:sqlisttp); j:=1; i:=2; WHILE (1)_ DO IF L.elemiL.elemj THEN (2)_; (3)_;文档来自于网络搜索 i:=i+1 (4) _; ENDP;【同济大学 2000 二、 1 (10 分) 】26在本题的程序中，函数过程Create_link_list(n)建立一个具有n 个结点的环形链表;程序过程 josephus(n,i,m)对由 Create_link_list(n)所建立的具有n个结点的环形链表按一定的次序逐个输出并删除链表中的所有结点，参数 n(n0)指明环形链表的结点个数，参数 i(1=i0)
25、 是步长，指明从起始结点或前次被删除并输出的结点之后的第m个结点作为本次被输出并删除的结点。例如，对于下图中具有6 个结点的环形链表，在调用 josephus(6,3,2)后，将输出 5,1,3,6,4,2 请在横线处填上适当内容，每空只填一个语句。文档来自于网络搜索TYPE nodeptr=nodetype; nodetype=RECORD data: intrger; link: nodeptr END; VAR n,i,m: integer; FUNCTION Create_link_list(n: integer): nodeptr; VAR head,p,q: nodeptr; i:
26、integer; BEGIN head := NIL; IF n0 THEN BEGIN new(head); p: =head; FOR i:=1 TO n-1 DO BEGIN p.data:=i; new(q); (A)_; (B)_ END； p.data:=n; (C)_; END; Creat_link_list:=head END; PROCEDURE josephus(n,i,m:integer); VAR p,q:nodeptr; j:integer; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 24 页个人收集整
27、理仅供参考学习10 / 24 BEGIN p:=Creat_link_list(n); WHILE i1 DO BEGIN p:=p.link; i:=i-1 END; (D)_ ; WHILE jn DO BEGIN FOR i:=1 TO m-1 DO p:=p.link; (E)_; write(q.data:8); (F)_ ; dispose(q); j:=j+1 END END;【复旦大学 1997 四（ 12 分） 】27对于给定的线性链表head , 下面的程序过程实现了按结点值非降次序输出链表中的所有结点， 在每次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适
28、当的内容，使之成为一个完整的程序过程，每个空框只填一个语句。文档来自于网络搜索TYPE nodeptr = nodetype；nodetype = RECORD data : integer；link : nodeptr END; VAR head : nodeptr；PROCEDURE sort_output_delete (head : nodeptr); VAR p,q,r,s: nodeptr; BEGIN WHILE head NIL DO BEGIN p:= NIL ；q:= head ； r:= q ；s:=q.link ； WHILE s NIL DO BEGIN IF s.d
29、ata q.data THEN BEGIN (1)_; (2)_ END ；文档来自于网络搜索 r:= s ； (3)_ END；write(q.data : 5) ；IF p=NIL THEN (4)_ ELSE (5)_ ； dispose (q) ； END； writeln END ； 【复旦大学 1996 七（ 20 分） 1995 一（ 12 分）与本题相似】28下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链环上检索关键值为x 的结点，对该结点访问频度计数，并维护该链环有序。若未找到，则插入该结点。所有结点的频度域初值在建表时都为零。请将程序中四处空缺补写完整。文档来
30、自于网络搜索 TYPE link=node node=RECORD key:char; freq:integer; pre,next:link; END; VAR l:link; FUNCTION loc(l:link;x:char):link; VAR p,q:link; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 24 页个人收集整理仅供参考学习11 / 24 BEGIN p:=l.next; （ 1）_； WHILE p.keyx DO p:=p.next; IF p=l THEN new(q); q.key:=x; q.f
31、req:=0 ELSE 找到 p.freq:=p.freq+1; q:=p; （2）_；WHILE q.freqp.pre.freq DO p:=p.pre; IF pq THEN （3）_ ； IF （4） _ THEN q.next:=p, q.pre;=p.pre; p.pre.next:=q; p.pre:=q文档来自于网络搜索return(q); END;【北京工业大学 1999 五 (12 分) 】29循环链表a 和 b 的结点值为字母，其中 a 表非递减有序， 下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在a，b 两链表中出现的字母，且c 中字母不重复，请补上程序
32、中空缺的部分，并估计算法的时间复杂度。（设 a，b 的结点数分别为m ，n）文档来自于网络搜索 TYPE link=node; node=RECORD key:char; next:link END; PROC jj(a,b:link; VAR c:link); VAR p,q,r,s:link; BEGIN new(c);c.next:=c; q:=a; p:=a.next; WHILE pa DO （1）_；WHILE p.key=p.next.key DO q:=p; p=p.next;跳过相同字母文档来自于网络搜索r:=b.next ; （ 2）_; WHILE r.key p.key
33、 DO r:=r.next; IF rb THEN s:=p; q.next:=p.next; （3） ; s.next:=c.next; c.next:=s; c:=s ELSE q:=p; p:=p.next ; c:=c.next；END; 算法时间复杂度为O（4）_ 【北京工业大学 2000 四 (15分) 】30. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。void reverse(pointer h) /* h为附加头结点指针；类型pointer同算法设计第3 题*/ pointer p,q; p=h-next; h-next=NULL; while(
34、1)_) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 24 页个人收集整理仅供参考学习12 / 24 q=p; p=p-next; q-next=h-next; h-next=(2)_; 文档来自于网络搜索【西南交通大学 2000 一、 9】31. 下面是用 c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用 L 返回逆置后的链表的头指针，试在空缺处填入适当的语句。文档来自于网络搜索void reverse（linklist &L） p=null ；q=L；while （q！=null ） (1) ; q-next=p
35、；p=q；(2)_ ; (3)_; 【北京理工大学 2001 九、 1 （6 分） 】32下面程序段是逆转单向循环链表的方法，p0 是原链表头指针，逆转后链表头指针仍为p0。（可以根据需要增加标识符） p:= p0; q0:=NIL; WHILE （1）_ DO BEGIN （2）_; （3）_; （4）_; （5）_ END;文档来自于网络搜索 p.next:= q0; p0 .next:=p; p0:=p; 【中国人民大学 2000 二、 1（4 分）】文档来自于网络搜索33一个无头结点的线性链表( 不循环 ) 有两个域。数据域data ，指针域 next ，链首 head，下面算法用re
36、ad(num) 读入数据，当num小于 0 时，输入结束。建立一个数据以递增序组成的链表。文档来自于网络搜索 PROC insert( head, x); 在链首为 head 的表中按递增序插入x new(r);r.data:=x; IF head=NIL THEN head:=(1) _; r.next:= (2)_ ELSE IF (3)_ THEN r .next:=head; head:=r ELSE p:=head; WHILE (4)_ AND (p .next NIL ) DOq:=p; (5)_ ;文档来自于网络搜索 IF (6)_ THEN q .next:=(7)_; r
37、.next:= (8)_; 文档来自于网络搜索ELSE p .next:=(9)_; r .next:= (10)_; ENDP; PROC creat(head); head:= (11)_; read(num); WHILE num0 DO insert(head,num); read(num) ENDP;【南京理工大学 1999 三、 4（11 分） 】34. 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef ，指数域exp和指针域 next ；现对链表求一阶导数，链表的头指针为ha，头结点的exp 域为1。文档精选学习资料 - - - - - - - - - 名师归纳
38、总结 - - - - - - -第 12 页，共 24 页个人收集整理仅供参考学习13 / 24 来自于网络搜索 derivative(ha) q=ha ; pa=ha-next; while( (1)_) if ( (2)_) ( (3)_); free(pa); pa= ( (4) _); 文档来自于网络搜索 else pa-coef ( (5) _); pa-exp( (6)_); q=( (7) _);文档来自于网络搜索 pa=( (8)_); 【南京理工大学 2000 三、 3（10 分） 】35. 下面是删除单链表L 中最大元素所在结点的类PASCAL 语言算法， 请在横线填上内容
39、，完成其功能。 TYPE pointer =node； node=RECORD data:integer; next: pointer END; PROCEDURE delmax (L:pointer); VAR p,q,r:pointer; m:integer; BEGIN r:=L； p:=L .next; IF pNIL THEN m:=p .data; (1)_; p:=p .next; WHILE pNIL DO IF(2)_THEN (3)_ ; m:=p.data; 文档来自于网络搜索(4)_; p:=p.next; q:=r .next; (5)_; dispose(q); E
40、ND;【北京科技大学 1998 二】36对单链表中元素按插入方法排序的C语言描述算法如下，其中 L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。文档来自于网络搜索typedef struct node int data; struct node *next; linknode,*link; void Insertsort(link L) link p,q,r,u; p=L-next; (1)_; while(2)_) r=L; q=L-next; while(3)_& q-datadata) r=q; q=q-next;文档来自于网络搜索 u=p-next; (4)_; (5)_;
41、 p=u; 【北京科技大学 2001 二 （10 分） 】精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 24 页个人收集整理仅供参考学习14 / 24 37下面是一个求两个集合A和 B之差 C=A-B的程序， 即当且仅当e 是 A的一个元素， 但不是 B中的一个元素时，e 才是 C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空；操作完成后A，B保持不变， C中元素按递增排列。下面的函数append(last,e)是把值为e 的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数diff
42、erence(A,B)实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。 在执行 A-B 运算之前， 用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B 运算执行完毕，再删除并释放表示结果集合的链表的表头结点。文档来自于网络搜索程序 (a) （编者略去这个PASCAL 程序）程序（ b） typedef struct node int element; struct node *link;文档来自于网络搜索 NODE; NODE *A ， *B，*C; NODE *append (NODE *last,int e) last-link=(NODE*) ma
43、lloc (sizeof(NODE); last-link-element=e; return(last-link); NODE *difference(NODE *A,NODE *B) NODE *C,*last; C=last=(NODE*) malloc (sizeof(NODE); while (1)_ if (A-elementelement) last=append(last,A-element); A=A-link; 文档来自于网络搜索else if (2) _ A=A-link; B=B-link; ELSE (3) _ ;文档来自于网络搜索while (4) _ last=a
44、ppend(last,A-element); A=A-link; (5) _; last=C; C=C-link; free (last); return (C);文档来自于网络搜索 /*call form:C=difference(A,B);*/【上海大学 2000 一、 4 （10 分） 】文档来自于网络搜索四应用题1线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？文档来自于网络搜索（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的
45、速度存取线性表中的元素，那么应采用哪种存储结构？为什么？【西安电子科技大学 1999 软件二、1 （5 分） 】文档来自于网络搜索2线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计， 必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。【重庆大学 2000 二、 5】文档来自于网络搜索3 若较频繁 地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？【北京航空航天大学 1998 一、 2（4 分） 】精选学习资料 - - - - - - -
46、 - - 名师归纳总结 - - - - - - -第 14 页，共 24 页个人收集整理仅供参考学习15 / 24 4线性结构包括_、_、 _和_。线性表的存储结构分成_和_。请用类 PASC L 语言描述这两种结构。 【华北计算机系统工程研究所1999 一、2 （ 10分） 】文档来自于网络搜索5线性表（ a1， a2， an）用顺序映射表示时，ai和 ai+1（1=in 的物理位置相邻吗？链接表示时呢？文档来自于网络搜索【东南大学 1996 一、 1 （5 分） 】6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。【厦门大学 2000 五、 1 （1
47、4%/3 分）】7. 试述头结点 , 首元结点 , 头指针这三个概念的区别. 【武汉交通科技大学 1996 二、 2 (3分) 】 【西安电子科技大学2001 计应用二、 1（5 分） 】8. 已知有如下定义的静态链表： TYPE component=RECORD data:elemtp; next:0.maxsize END VAR stalist:ARRAY0.maxsize OF component; 以及三个指针 :av 指向头结点，p 指向当前结点，pre 指向前驱结点，现要求修改静态链表中 next 域中的内容，使得该静态链表有双向链表的功能，从当前结点p 既能往后查找，也能往前查
48、找：文档来自于网络搜索（ 1）定义 next 域中的内容。 ( 用老的 next 域中的值表示 ) ；（ 2）如何得到当前结点p 的前驱（ pre ）的前驱，给出计算式; （ 3）如何得到p 的后继，给出计算式; 【中科院计算所 2000 四（ 10 分） 】9. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 【西安电子科技大学1999 计应用一、 1 （5 分） 】10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？【中国人民大学 2001 二、 4 （2 分）】11. 下面是一算法的核心部分，试说明该算法的功能。pre:=L .next; L 是
49、一单链表，结点有数据域 data和指针域 next IF preNIL THEN WHILE pre.nextNIL DO BEGIN p:=pre .next; IF p .data=pre .data THEN pre:=p ELSE return(false) END;文档来自于网络搜索return(true); 【燕山大学 2000 七、 1 （7 分） 】12. 设单链表结点指针域为next ，试写出删除链表中指针p 所指结点的直接后继的C语言语句。【北京科技大学 2000 一、 3】13. 设单链表中某指针p 所指结点（即p 结点）的数据域为data ，链指针域为next ，请写出
50、在 p 结点之前插入s 结点的操作（ PASCAL 语句） 。 【北京科技大学 1999 一、 2 （2 分） 】文档来自于网络搜索14. 有线性表 (a1,a2, ,an), 采用单链表存储， 头指针为H，每个结点中存放线性表中一 个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。文档来自于网络搜索精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 24 页个人收集整理仅供参考学习16 / 24 （1）线性表中元素无序。（ 2）线性表中元素按递增有序。（ 3）线性表中元素按递减有序。【北京邮电大学 1