下载掌阅APP，畅读海量书库
立即打开
例1．用单链表方式存储队列（有头、尾指针，非循环），在进行删除运算时（ ）。【2018年杭州电子科技大学】
A．仅修改头指针
B．仅修改尾指针
C．头、尾指针都要修改
D．头、尾指针可能都要修改
【答案】 D
【解析】 本题考查链队的性质与操作。对于由无虚拟头结点、不循环的链表实现的队列而言，如果队列长度为1，在删除队首之后，不仅要修改队首指针为空结点，也要修改队尾指针为空结点，故选择D选项。
单链表设计中的虚拟头结点是指在单链表的头结点前加入一个空结点，即不存放实际的数据元素，仅仅起到连接作用的一个结点。虚拟头结点的存在有以下几个作用。
（1）简化代码实现：虚拟头结点可以使得所有结点的处理方式一致，避免了在处理头结点时需要对特殊情况进行特殊处理的情况，简化了代码的实现。
（2）方便插入和删除结点：在删除或者插入结点时，虚拟头结点可以使得代码的实现更加简单，不需要对头结点和非头结点做特殊处理。
（3）避免空链表特判：在不使用虚拟头结点的情况下，对于空链表的判断需要特别处理，而使用虚拟头结点可以将空链表看作只有一个虚拟头结点的链表，省去了对空链表的特判。
综上所述，使用虚拟头结点可以简化代码实现，方便操作，避免特殊情况的处理，提高代码的可读性和可维护性。
例2．h为不带头结点的单链表。在h的前面插入一个新结点t的语句是（ ）。【2010年浙江大学】
A．t->next=h; h=t;
B．h=t; t->next=h;
C．t->next=h-> next; h=t;
D．h=t; t->next=h->next;
【答案】 A
【解析】 本题考查单链表的操作。一个没有虚拟头结点的单链表的头插入，需要先将待插入结点的后继指针指向链表的头，再修改链表的头为待插入结点，故选择A选项。
例3．从一个具有n个结点的单链表中检索值等于x的结点时，在检索成功的情况下，需平均比较的结点个数是（ ）。【2013年重庆大学】
A．n/2
B．n
C．（n+1）/2
D．（n−1）/2
【答案】 C
【解析】 本题考查链表的性质与操作。链表的检索需要从头开始遍历，所以比较的次数等于被检索元素在链表中的次序。因此检索第1个元素需要比较1次，检索第2个元素需要比较2次……检索第n个元素需要比较n次。平均比较次数=总比较次数/总元素个数=（1+2+…+n）/n=（（n+1）n/2）/n=（n+1）/2，故选择C选项。
例4．以下关于链式存储结构的叙述中，（ ）是不正确的。【模拟题】
A．结点中存在数据域和指针域
B．可以高效随机存取
C．插入和删除都不用移动结点
D．逻辑上相邻的结点在物理上可以不相邻
【答案】 C
【解析】 本题考查链式存储结构的特点。高效随机存取是顺序表的特性。链表结点中通常存在指针域和数据域，并且在插入、删除的过程中，使用指针域实现逻辑邻接，因此不用移动结点，并且在逻辑上相邻的结点，在物理上可以是不相邻的。
顺序表是一种线性结构，采用连续存储结构来存储数据元素。每个元素在表中占用一个固定位置，这使得顺序表支持随机存取数据。随机存取数据意味着可以通过索引直接访问元素，即在O（1）时间复杂度内可以访问任何一个元素，这是顺序表的一个重要特点。顺序表中的元素地址是连续的，因此只需要知道它的索引，就可以通过简单的计算获得它的地址，从而直接访问这个元素。
例5．用单链表存储两个各有 n个元素的有序表，若要将其合并成一个有序表，最少的比较次数是（ ）。【2017年北京邮电大学】
A．n−1
B．n
C．2n−1
D．2n
【答案】 B
【解析】 本题考查链表合并的过程。将两个有序链表合并时，最好情况下为一个链表的元素整体比另一个链表的小，因此只需要比较n次。
例1．设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。【2017年暨南大学】
A．p->next=s; s->prior=p; p->next->prior=s; s->prior=p->next;
B．s->prior=p; s->next=p->next; p->next=s; s->next->prior=s;
C．p->prior=s; p->next->prior=s; s->prior=p; s->next=p->prior;
D．s->prior=p; s->next=p->next; p ->next=s; p->next->prior=s;
【答案】 B
【解析】 本题考查双向链表的操作。操作顺序如图2-1所示。
图2-1
例2．在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ ）存储方式。【2018年昆明理工大学】
A．顺序表
B．用头指针标识的单循环链表
C．用尾指针标识的单循环链表
D．双向链表
【答案】 D
【解析】 本题考查链表的性质与操作。在保证效率的前提下，如果经常需要删除链表的最后一个结点，就需要高效查询删除前的倒数第二个结点，即最后一个结点的前驱结点。在4个选项中，可以快速查询前驱结点，并且可以快速进行尾部插入的链表只有D选项，故选择D选项。
例1．已知头指针h指向一个带头结点的非空单循环链表，结点结构为data | next，其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是（ ）。【2021年全国统考】
A．h->next=h->next->next; q=h->next; free（q）;
B．q=h->next; h->next =h->next->next; free（q）;
C．q=h->next; h->next=q->next; if（p != q）p=h; free（q）;
D．q=h->next; h->next=q->next; if（p == q）p=h; free（q）;
【答案】 D
【解析】 本题考查单链表的操作。操作顺序如图2-2所示。
图2-2
例2．只含有next指针的循环链表的主要优点是（ ）。【模拟题】
A．从任意结点都可以遍历整个链表
B．完全不需要头结点
C．更容易进行插入、删除操作
D．更容易找到结点的前驱结点
【答案】 A
【解析】 本题考查循环链表的性质。头指针的作用在于方便对空链表进行操作，循环链表也可以使用头结点；循环链表的插入和删除的效率与普通链表的相差不明显；只有next指针的循环链表想找到前驱结点必须遍历整个链表，其效率不如双向链表。
例．对于长度为n的非空线性表，下列4种操作中，在顺序表上实现比在链表上实现效率更高的是（ ）。【2019年北京航空航天大学】
A．输出表中第i个数据元素的值（1≤i≤n）
B．依次输出表中所有数据元素的值
C．求首个值为item 的数据元素在表中的位置
D．交换表中前两个数据元素在表中的位置
【答案】 A
【解析】 本题考查顺序表和链表的比较。对于A选项，顺序表可以使用首地址+偏移量的方式，以常数级别的时间复杂度查询，但是链表则需要遍历到第i个结点，因此顺序表的效率更高；对于B选项，两种数据结构的效率相近；对于C选项，两种数据结构都需要从头开始遍历，因此效率相近；对于D选项，链表只需要比顺序表多一次操作（找到头结点后的结点），因此效率相近。故选择A选项。