链表的特点
-
2023年3月20日发(作者：冰心散文集)1
第一部分习题
一、选择
1、下列叙述中关于好的编程风格，正确的描述是：C
A、程序中的注释是可有可无的为了增强可读性我们要在必要语句之后加注释
B、对递归定义的数据结构不要使用递归过程递归的可读性强
C、递归应是封闭的，尽量少使用全局变量
D、多采用一些技巧以提高程序运行效率
2、通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。
以下解释错误的是(C)
A、正确性算法应能正确地实现预定的功能(即处理要求)
B、易读性算法应易于阅读和理解以便于调试修改和扩充
C、健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需
要的运行结果见课本14页
D、高效性即达到所需要的时间性能
3、以下说法正确的是(D)
A、数据元素是数据的最小单位
B、数据项是数据的基本单位
C、数据结构是带有结构的各数据项的集合
D、数据结构是带有结构的数据元素的集合
4、对于顺序表，以下说法错误的是（A）
A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
5、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（B）为标准操作
A、条件判断B、结点移动
C、算术表达式D、赋值语句
6、对于顺序表的优缺点，以下说法错误的是（C）
A、无需为表示结点间的逻辑关系而增加额外的存储空间
B、可以方便地随机存取表中的任一结点
C、插入和删除运算较方便
D、容易造成一部分空间长期闲置而得不到充分利用
7、链表不具有的特点是：A
A、可随机访问任一个元素B、插入删除不需要移动元素
C、不必事先估计存储空间D、所需空间与线性表长度成正比
8、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（D）存储方式节
省时间
A单链表B、双向链表C、单循环链表D、顺序表
9、有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（D）
A将“指针型变量”简称为“指针”
B将“头指针变量”称为“头指针”
C将“修改某指针型变量的值”称为“修改某指针”
D将“p中指针所指结点”称为“P值”
10．设指针P指向双链表的某一结点，则双链表结构的对称性可用（C）式来刻画
2
Ap->prior->next->==p->next->next
Bp->prior->prior->==p->next->prior
Cp->prior->next->==p->next->prior
Dp->next->next==p->prior->prior
11.以下说错误的是（A）
A对循环来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表
B对单链表来说，只有从头结点开始才能扫描表中全部结点
C双链表的特点是找结点的前趋和后继都很容易
D对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存
放在它的后继结点的前趋指针域中。
12．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置
分别是（B）
Arear和rear->next->next
Brear->next和rear
Crear->next->next和rear
Drear和rear->next
13.以下说错误的是(C)
A对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）
B读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机
存取结构
C在链表上实现读表元运算的平均时间复杂性为O（1）
D插入、删除操作在链表上的实现可在O（n）时间内完成
14．循环链表主要优点是（D）
A不再需要头指针了
B已知某个结点的位置后，能够容易找到它的直接前趋
C在进行插入、删除运算时，能更好地保证链表不断开
D从表中任一结点出发都能扫描到整个链表
15．以下说法错误的是（B）
A数据的物理结构是指数据在计算机内实际的存储形式
B算法和程序没有区别，所以在数据结构中二者是通用的
C对链表进行插人和删除操作时，不必移动结点
D双链表中至多只有一个结点的后继指针为空
16．以下说法正确的是C
A线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继
B线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现
效率要低
C在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置
有关
D顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作
只有近一半的元素需要移动
17．以下说法错误的是（D）
A求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储
结构时实现的效率低
B顺序存储的线性表可以随机存取
3
C由于顺序存储要求连续约存储区域所以在存储管理上不够灵活
D线形表的链式存储结构优于顺序存储结构
18．以下说法错误的是（B）
A线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻
B在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻
C在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻
D线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素
19．以下说法正确的是（C）
A在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点
进行查找任何一个元素
B在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机
存取的存储结构
C顺序存储方式只能用于存储线性结构
D顺序存储方式的优点是存储密度大、且插入、删除运算效率高
20.线性表L=(a1,a2,...,ai,...,an),下列说法正确的是(D)
A每个元素都有一个直接前驱和直接后继
B线性表中至少要有一个元素
C表中诸元素的排列顺序必须是由小到大或由大到小的
D除第一个元素和最后一个元素外其余每个元素都有一个数且仅有一个直接前
驱和直接后继
21.线性表若采用链表存储结构时，要求内存中可用存储单元的地址(D)
A必需是联系的B部分地址必须是连续的
C一定是不连续的D连续不连续都可以
22.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可
表示为(D)
Ap=rear;rear=rear->next;free(p)
Brear=rear->next;free(rear);
Crear=rear->next->next;free(rear);
Dp=rear->next->next;rear->next->next=p->next;free(p);
23.单链表中，增加头结点的目的是为了(C)
A使单链表至少有一个结点B标示表结点中首结点的位置
C方便运算的实现D说明单链表是线性表的链式存储实现
24线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代
表的数据元素具有相同的特性，这意味着C
A每个结点所代表的数据元素都一样。
B每个结点所代表的数据元素包含的数据项的个数要相等
C不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致
D结点所代表的数据元素有同一特点
25．带头结点的单链表Head为空的判定条件是B
AHead==NullBHead->next==NULLCHead->next==Head
26空的单循环链表L的尾结点*P,满足D(虽然C的条件也成立,但不空的单循环链表
也满足C)
AP->next==NULLBP==NULLCP->next==LDP==L
27.双向链表结点结构如下：
4
LLinkdataRLink
其中：LLink是指向前驱结点的指针域：data是存放数据元素的数据域；Rlink是
指向后继结点的指针域。
下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到
此双向链表中。能正确完成要求的算法段是C
AQ->LLink=P->LLink;Q->Rlink=P;P->LLink=Q;P->LLink->Rlink=Q;
错误原因为:P->LLink->Rlink=Q;P->LLink已在第三个赋值语句中修改了.
BP->LLink=Q;Q->Rlink=P;P->LLink->Rlink=Q;Q->LLink=P->LLink;
错误原因:将新结点*Q作为非空双向链表中的结点*p的前驱,应先修改插入结点的前驱
指针域,后修改结点*p的前驱指针域
CQ->LLink=P->LLink;Q->Rlink=P;P->LLink->Rlink=Q;P->LLink=Q;
28.循环队列的出队操作为(A)
=(+1)%maxsize
=+1
=(+1)%maxsize
=+1
29.循环队列的队满条件为(C)
A(+1)%mazsize==(+1)%maxsize;
B(+1)%maxsize==+1
C(+1)%maxsize==
==
30.循环队列的队空条件为(D)
A(+1)%maxsize==(+1)%maxsize
B(+)%maxsize==+1
C(+1)%maxsize==
==
31如果以链表作为栈的存储结构,则退栈操作时(C)
A必须判别栈是否满B判别栈元素的类型
C必须判别栈是否空D队栈不做任何判别
32.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是
s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（B）
A2B3C5D6
33．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列
中不可能出现的出栈序列是（A）
0123maxsize-1
Aa3,a1,a4,a2Ba3,a2,a4,a1Ca3,a4,a2,a1Da4,a3,a2,a1
34.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为（D）
(无头结点)
ATop->next=sBs->next=Top->next;Top->next=s
Cs->next=Top;Top=sDs->next=Top;Top=Top->next
35.从栈顶指针为Top的链栈中删除一个结点，并将被删结点的值保存到x中，其操作步骤
为（A）
a1a2a3
5
Ax=Top->data;Top=Top->nextBTop=Top->next;x=Top->data
Cx=Top;Top=Top->nextDx=Top->data
36.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（B）
Af->next=c;f=sBr->next=s;r=s
Cs->next=r;r=sDs->next=f;f=s
37．链栈与顺序栈相比，有一个比较明显的优点即（B）
A插入操作更方便B通常不会出现栈满的情况
C不会出现栈空的情况D删除操作更方便
38.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）
AedcbaBdecbaCdceabDabcde
39.一个队列的入队列顺序是1，2，3，4，则队列的输出系列是（B）
A4，3，2，1B1，2，3，4，C1，4，3，2D3，2，4，1
40．设计一个判别表达式中左、右括号是否配对的算法，采用（B）数据结构最佳。
A线性标的顺序存储结构B栈C队列D线性表的链式存储结构
41设循环队列中数组的下标范围是0—n-1，其头尾指针分别为f和r，则其元素的个数为
（D）
A、r-fB、r-f+1C、(r-f)%n+1D、(r-f+n)%n
42若一个栈的输入序列是1、2„„N，输出序列的第一个元素是N，则第I个输出元素为
（C）
A、N-IB、IC、N-I+1D、N-I-1
43队列操作的原则是（A）
A先进先出B、后进先出C、只能进行插入D、只能进行删除
44线性表是(A)。
A一个有限序列，可以为空；B一个有限序列，不能为空；
C一个无限序列，可以为空；D一个无序序列，不能为空。
二填空题、
1.以下为求单链表表长的运算，分析算法，请在____处填上正确的语句。
intlength_linklist(linklisthead)/*求表head的长度*/
{____p=head____;
j=0;
while(p->next)
{___p=p->next_____________;
j++;}
return(j);/*回传表长*/
}该算法也可以写成:
intlength_linklist(linklisthead)/*求表head的长度*/
{p=head->next;
j=0;
while(p)
{p=p->next;
j++;}
return(j);比较一下,特别是初始化与循环条件.原题中是while(p->next)即若p有后继,
则j加1,所以p的初始化为p=head
6
2.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。
linklistfind_lklist(linklisthead,inti)//查找第i个结点
{p=head;j=0;
while(_p&&(j {p=p->next;j++;} if(i==j)return(p); elsereturn(NULL); } 因为返回i结点的地址,所以函数类型为linklist,如果找到就不需要访问链表了, 所以应该是访问部分结点的这种情况,所以在循环条件中至少要有两个. 3.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 intlocate_lklist(lklisthead,datatypex) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head;j=0; while(p->next&&p->next->data!=x){p=p->next;j++;} if(p->next)return(j+1); elsereturn(0); } 这题也要注意处始化,p初值为head,即指向头结点的,所以是让*p的后继结点的数据域 和x进行比较.若p的初值指向第一个结点,循环条件就发生了变化,具体算法为: intlocate_lklist(lklisthead,datatypex) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head->next;j=1; while(p&&pdata!=x){p=p->next;j++;} if(p)return(j); elsereturn(0); } 这两个算法也要比较一下.在回顾一下我们上课所说采用链表编写算法的格式,这个格 式一定要放在脑子中. 4.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 voiddelete_lklist(linklisthead,inti) {p=find_lklist(head,i-1);//调用第2题 if(____p&&p->next_)//必须第i-1结点与第i结点存在 {q=__p->next___; p->next=q->next; free(q); } elseerror(“不存在第i个结点”) } 5.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 voidinsert_lklist(linklisthead,datatypex,inti) /*在表head的第I个位置上插入一个以x为值的新结点*/ {p=find_lklist(head,i-1); if(p==NULL)error(“不存在第i个位置”)； 7 else{s=(linklist)malloc(sizeof(lnode));s->data=x; s->next=__p->next;__; p->next=s; } } 6.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 Linklistcreate_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志 */ {ininiate_lklist(head); i=1; scanf(“%f”,&x); while(x!=’$’) {_insert_lklist(head,x,inti)__; _____i++___________; scanf(“%f”,&x); } return(head); } 改建表算法的时间复杂性约等于___O(N2)_____。 7.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 linklistcreate_lklist2()/*直接实现的建表算法。*/ {head=malloc(size); p=head; scanf(“%f”,&x); while(x!=’$’) {q=(linklist)malloc(sizeof(lnode)); q->data=x; p->next=q; _____p=q;___________; scanf(“%f”,&x); } ______p->next=null__________;//让最后一个结点的指针域为空 return(head); } 这题是从前往后建立单链表的与课本上算法2.11不一样,2.11是逆序建立的,大家把这 两个算法对比一下. 8．循环链表与单链表的区别仅仅在于其尾结点的链域值不是空指针，而是一个指向__头结 点_的指针。 9．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中 有两个方向不同的链，称为双向链表。 10、一个好的算法应当具有下列好的特性：正确性、（可读性）、（健壮性）和效率和低 存储需求。 11、算法的五个重要特征为（确定性）、（有穷性）、（可行性）和输入、输出。 8 12、采用顺序存储结构的线性表，其每个元素占用Ｌ个单元。第一个元素的地址为Ｎ，则 第i个元素的存储位置为（N+(i-1)*L）。 13、数据元素之间的关系在计算机中的表示有两种不同的表示方法，即（顺序映像） 和（非顺序映像），从而得到两种不同的存储结构（顺序存储结构）和（链式存 储结构）。 14、已知栈的输入序列为1、2、3„„n输出序列为a1,a2„„,an符合a2=n的输出序列 共有（n-1）种。 15．带头结点的单链表H为空的条件是__H->nexy==NULL_______。 16非空单循环链表L中*p是尾结点的条件是_p->next==l__。 17．在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->next=__p->next_; 和p->next=__s___的操作。 18．在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作： s->next=___p->next___; p->next=s; t=p->data; p->data=_s->data___; s->data=__t____; 19．在顺序表中做插入操作时首先检查_是否溢出___ 三判断题 1在顺序表中取出第i个元素所花费的时间与i成正比 不对,因为是可以随机存取. 2线性表的长度是线性表所占用的存储空间的大小 不对 3在对链队列作出队列操作，不会改变front指针的值 对 4双循环链表中，任一个结点的后继指针均指向其逻辑后继 不对,最后一个结点的后继指针不是指向其逻辑后继 5已知指针P指向链表L中某结点，执行语句P=P->next不会删除该链表中结点 对 6在链队列中，即便不设置尾指针也能进行入队列操作 对,但花费的时间较多 7栈和队列都是运算受限的线性表 对 8在带头结点的单循环链表中，任一结点的后继指针均不空 对 9线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是 O(N)，因而两种存储方式的插入、删除运算所花费的时间相同 不对 四、算法设计 (算法大多数是习题集上的,大家参考习题集答案,如果哪道题,有什么问题,我再给出具体 的分析和答案) 1．设A=（a 1 ,a 2 ,a 3 ,......a n ）和B=(b 1 ,b 2 ,...,b m )是两个线性表（假定所含数据元素均为 整数）。若n=m且a i =b i (i=1,...,n),则称A=B;若a i =b i (i=1,...,j)且a j+1 j+1 ,则称A 在其他情况下均称A>B。是编写一个比较A和B的算法，当AB是分别输出-1， 9 0或者1。 2．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。 3．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。 编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列 的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。 4．设有线性表A=(a 1 ,a 2 ,...,a m )和B=(b 1 ,b 2 ,...,b n ).试写合并A、B为线性表C的算法， 使得： C= n;m)am,...,1an,bn,an,...,1b,1a( ;nm)bn,1bm,bm,am,...,1b,1a( 当 当 假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储 结构并利用单链表A、B的结点空间。 5．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插 大表L申，使得L仍然有序。 6，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可 能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a 1 ，a 2 ,...,a n )逆置为 (a n ,...,a 2 ,a 1 )。 7．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即统一线性表中的元素各 不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。 试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。 8．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个 结点的指针，试编写算法删除结点*s的前趋结点。 9．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写 算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间 作为这三个表的结点空间(头结点可另辟空间)。 10、已知数据A[1。。K]中K个元素，另有一双向循环链表da，试以过程实现将数组中元素 插入到da中第i个结点之后。 11、已给单链表的表头指针H和一个元素x，设计一个过程，实现：若x在单链表H中， 则将x移到链尾；否则将x插入到链尾。 12．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不舌 头指针），试编写相应的初始化队列、入队列和出队列算法。 13．假设以数组cycque[m](假设数组范围在0..m)存放循环队列的元素，同时设变量rear 和quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满 条件，并写出相应的入队列和出队列的算法。 14．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]” 以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如 （...[...{...}...[...]...]...(...[...]...)。试利用栈的运算编写判断给 定表达式中所含括号是否正确配对出现的算法（可设表达式已存入字符型数组中）。 15．借助栈(可用栈的基本运算)来实现单链表的逆置运算。 16编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较 高的效率来实现。