2022年2022年链表习题 .pdf

《2022年2022年链表习题 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表习题 .pdf（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、重点习题0 基本概念1、静态链表中指针表示的是（B）.【北京理工大学2001 六、2（2 分）】A内存地址B数组下标.C下一元素地址D左、右孩子地址2、线性表（a1,a2,an）以链接方式存储时，访问第i 位置元素的时间复杂性为（C）AO（i）BO（1）CO（n）.DO（i-1）3、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）Ahead=NULL Bhead next=NULL.Chead next=head Dhead!=NULL 1.链表的插入和删除1、完成在双循环链表结点p 之后插入s的操作是（D）A p.next:=s;s.priou:=p;p.next.p

2、riou:=s;s.next:=p.next;B p.next.priou:=s;p.next:=s;s.priou:=p;s.next:=p.next;Cs.priou:=p;s.next:=p.next;p.next:=s;p.next.priou:=s;D s.priou:=p;s.next:=p.next;p.next.priou:=s;p.next:=s;.2、双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 p 指向链表中的一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（D）A.p .llink:=q;q .rlink:=p;p

3、.llink .rlink:=q;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -q.llink:=p.llink;B.q.llink:=p.llink;p.llink.rlink:=q;q.rlink:=p;p.llink:=q.rlink;C.q.rlink:=p;p.rlink:=q;p.llink.rlink:=q;q.rlink:=p;D.p.llink.rlink:=q;q.rlink:=p;q.llink:=p.llink;p.llink:=q;.3、在单链表指针为p 的结点之后插入指针为s 的结点，正确的操作是：（B）。Ap-next=s;s-next=

4、p-next;B s-next=p-next;p-next=s;.Cp-next=s;p-next=s-next;D p-next=s-next;p-next=s;4、(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i 个元素的时间与i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（B）A（1），（2）B（1）.C （1），（2）,(3)D.（2）5、对单链表中元素按插入方法排序的C 语言描述算法如下，其中 L 为链表头结点指针。请填充算法中标出的空白处，

5、完成其功能。typedef struct node int data;struct node*next;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -linknode,*link;void Insertsort(link L)link p,q,r,u;p=L-next;(1)_L-next=null_;while(2)_p!=null_)r=L;q=L-next;while(3)_q!=null_&q-datadata)r=q;q=q-next;u=p-next;(4)_p-next=r-next_;(5)_r-next=p_;p=u;(1)L-next=null(2

6、)p!=null(3)q!=null(4)p-next=r-next(5)r-next=p 算法设计（1）给定(已生成)一个带表头结点的单链表，设head 为头指针，结点的结构为(data,next),data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)解答：对链表进行遍历，在每趟遍历中查找出整个链表的最小值元素，输出并释放结点所占空间；再查次最小值元素，名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间。当

7、然，删除结点一定要记住该结点的前驱结点的指针。（2）已知一单链表中一结点p,设计一算法在p 之前插入结点 s,注意该单链表没有头指针。(3)设计一个算法删除单链表L 中值为 x 的结点的直接前(4)设计一个算法删除一递增单链表值域重复的结点(5)设计一个算法删除一非有序单链表值域重复的结点(6)链表的运算(交集 并集)2.链表的逆置1 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。void reverse(pointer h)pointer p,q;p=h-next;h-next=NULL;while(1)_p!=null_)q=p;p=p-next;q-next=h

8、-next;h-next=(2)_q_;(1)p!=null 链表未到尾就一直作(2)q 将当前结点作为头结点后的第一元素结点插入3 循环链表和双向链表名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -(1)设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频

9、度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法(2)已知一带有尾指针的循环单链表(结点数目大于1)，设计一算法完成链表首尾倒置。4.链表操作的复杂度1 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A顺序表.B双链表C带头结点的双循环链表D单循环链表2 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表.名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -3 设一个链表最常用的操作是在末尾插入一个元素和删除一个元素，则采用（C）存储方式最节省运算时间。A单链表B单循环链表C带头结点的循环双链表.D仅有尾指针的单循环链表4 线性表（a1,a2,an）以链接方式存储时，访问第i 位置元素的时间复杂性为（C）AO（i）BO（1）CO（n）.DO（i-1）名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -