1.2 链式存储结构的存储结构和实现

1.2 链式存储结构的存储结构和实现

　　考试大纲涉及本节的知识点有：线性链表、循环链表和双向链表。

一、选择题

　　1．选择题题目部分
　　● 线性表的链式存储结构，其地址 （1） 。
　　（1）A．必须是连续的 B．一定是不连续的
　　C．部分地址必须是连续的 D．连续与否都可以
　　● 线性表的链式存储结构不具备的特点是 （2） 。
　　（2）A．插入和删除不需要移动元素 B．可以随机地访问任意节点
　　C．不必事先估计存储空间 D．所需空间与线性长度成正比
　　● 下面关于线性表的叙述中，错误的是 （3） 。
　　（3）A．线性表采用顺序存储，必须占用一片连续的存储单元
　　B．线性表采用顺序存储，便于进行插入和删除操作
　　C．线性表采用链接存储，不必占用一片连续的存储单元
　　D．线性表采用链接存储，便于插入和删除操作
　　● 线性表的链式存储结构中增加一个头节点是为了 （4） 。
　　（4）A．使链式存储结构中至少有一个节点 B．标识表节点中首元节点的位置
　　C．方便运算的实现 D．说明单链表是线性表的链式存储
　　● 将长度为n的单链表接到长度为m的单链表后面的算法的时间复杂度为 （5） 。
　　（5）A．O(1) B．O(n) C．O(m) D．O(n+m)
　　● 若某线性表最常用的操作是存取任意指定序号的元素和在线性表尾进行插入和删除运算，则利用 （6） 存储方式最节省时间。
　　（6）A．顺序存储线性表 B．双链表
　　C．带头节点的双循环链表 D．循环链表
　　● 7．以下关于静态链表的描述中，正确的是 （7） 。
　　（7）A．静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关
　　B．静态链表不需要一开始就分配所有的存储空间，可以在插入数据元素时再申请
　　C．静态链表与动态链表在元素的插入、删除上类似，不需要移动元素
　　D．静态链表的指针域存储的是数据元素的内存地址
　　● 非空的循环单链表L的尾节点p满足 （8） 。
　　（8）A．p->next=L B．p->next=NULL C．p=NULL D．p=L
　　● 设一个链表最常用的操作是在末尾插入节点和删除尾节点，则选用 （9） 最节省时间。
　　（9）A．带头节点的双循环链表 B．单循环链表
　　C．带尾指针的单循环链表 D．单链表
　　● 双向循环链表中，在p所指向的节点之后插入s指向的节点，其修改指针的操作是 （10） ，其中p指向的不是最后一个节点。
　　（10）A．p->next=s; s->prev=p; p->next->prev=s; s->next=p->next;
　　B．p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
　　C．s->prev=p; s->next=p->next; p->next=s; p->next->prev=s ;
　　D．s->prev=p; s->next=p->next; p->next->prev=s; p->next=s;
　　● 对于一个头指针为head的带头节点的双向循环链表，可以作为判定该线性表为空表的条件是（11） 。
　　（11）A．head==NULL B．head->next==NULL
　　C．head->next==head D．head!=NULL
　　● 以下关于线性表采用链式存储时的删除节点运算描述，正确的是 （12） 。
　　A．带头节点的线性链表删除节点时，不需要更改头指针
　　B．带头节点的线性链表删除第一个节点时，需要更改头指针
　　C．不带头节点的线性链表删除节点时，需要更改头指针
　　D．不带头节点的线性链表删除第一个节点时，不需要更改头指针
　　● 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 （13） 存储方式最节省时间。
　　（13）A．单链表 B．仅有头指针的单循环链表
　　C．双向链表 D．仅有尾指针的单循环链表
　　● 静态链表中指针表示的是 （14） 。
　　（14）A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址
　　● 在单链表指针为p的节点之后插入指针为s的节点，正确的操作是 （15） 。
　　（15）A．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．选择题的答案与分析
　　题号（1）答案 D
　　习题分析：
　　这道题考查对于线性表的链式存储结构定义的理解。链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。也就是说存储单元之间可以是连续的，也可以是不连续的。
　　题号（2）答案 B
　　习题分析：
　　顺序表可以随机访问表中的任意节点，而链表必须从第一个数据节点出发，按照节点在表中的位置才能查找。即顺序表是随机访问，而链表是顺序访问。因此答案B是链表不具备的特点。
　　题号（3）答案 B
　　习题分析：
　　线性表采用顺序存储时，进行插入和删除操作都需要移动大量元素，因此显然B是错误的。
　　题号（4）答案 C
　　习题分析：
　　头节点的好处有两个：第一，有头节点后，插入和删除数据元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除一个元素；第二，不论链表是否为空，链表的头指针不变。因此可以看出，设置头节点的目的就是为了方便运算的实现。
　　题号（5）答案 C
　　习题分析：
　　这道题考查对于线性表链式存储结构的操作的理解。设长度为n的单链表头指针为Ln，长度m的单链表的头指针为Lm，首先从指针Lm出发找到该链表的最后一个节点，若该节点的指针为p，则使用语句p->next=Ln即可实现将链表Ln链接在链表Lm的后面。因此该操作所需要的时间主要集中在查找链表Lm的最后一个节点上，即其时间复杂度为O(m)。
　　题号（6）答案 A
　　习题分析：
　　存取任意指定序号的元素即线性表的随机访问，这正是顺序表的优势，因此排除答案B、C和D。而线性表顺序存储结构在线性表尾执行插入和删除操作时不需要移动数据元素，所以符合本题要求的结构是线性表的顺序存储结构，即答案A。
　　题号（7）答案 C
　　习题分析：
　　（1）虽然静态链表使用了一片连续的存储空间，但是线性表中第i个数据元素不一定存储在第i块存储单元中，因此不能被随机访问。事实上为了访问静态链表的第i个数据元素，仍然需要从首个数据元素开始遍历i个数据元素。
　　（2）静态链表使用一片连续的空间存储数据元素，因此必须一次性分配其所需要的存储空间。
　　（3）静态链表每个节点都有指针域，执行插入和删除操作时只需更改指针域即可，无需移动数据元素。
　　（4）静态链表的指针域中保存的是数组的下标，而不是数据元素的绝对存储地址。事实上在数组中，根据数组下标就可以很快地访问数组元素。因此，答案为C。
　　题号（8）答案 A
　　习题分析：
　　本题考查对于循环单链表定义的理解。非空循环单链表尾节点的指针域应该指向该单链表的首节点，即p->next=L，这也是遍历循环链表时判断是否到达了队列尾部的方法。因此，答案为A。
　　题号（9）答案 A
　　习题分析：
　　在链表的末尾插入和删除节点，需要修改其相邻节点的指针域。当我们从链表的第一个节点开始寻找尾节点及尾节点的直接前驱节点时，只有带头节点的双循环链表所要经过的节点数最少。因此，答案为A。
　　题号（10）答案 D
　　习题分析：
　　本题考查对于双向循环链表的插入操作的理解。其插入方法如图1-1所示。
　　一般情况下，做此类题的一个捷径是判断代码“p->next=s”后是否还有通过指针“p->next”访问p以前的直接后继的引用，有则错误。因为一旦执行完代码“p->next=s”，p的直接后继就更改为s，此后“p->next”不再是p以前的直接后继。比如题中A、B和C选项均在“p->next=s”之后使用了“p->next”，所以选项A、B和C错误，根据排除法，选项D正确。另外强烈建议读者在编写插入代码时，将“p->next=s”写成插入算法的最后一步。
　　因此，本题答案为D。

　　题号（11）答案 C
　　习题分析：
　　头节点为head的带头节点的双向循环链表为空的判断条件为：head->next=head或head->next=head= head->prev。
　　题号（12）答案 A
　　习题分析：
　　带头节点的线性链表的头指针指向其头节点，而该头节点是不能被删除的，所以这个头指针的值不需要更改，所以，选项B错误。不带头节点的线性链表在删除第一个节点后，需要将头指针指向新的第一个节点，所以，选择D错误，而如果删除其他节点，则不需要更改头指针，所以，选项C错误。因此，答案为A。
　　题号（13）答案 D
　　习题分析：
　　在有尾指针的单循环链表中，尾指针指向尾节点，而尾节点的next域指向的是表中的第一个节点，因此仅有尾指针的单循环链表用来存储经常需要在最后一个元素之后插入元素和删除第一个元素的线性表是非常合适的，也是最节省时间的。因此，答案为D。
　　题号（14）答案 B
　　习题分析：
　　静态链表是使用一维数组实现的链式存储结构，每个数组元素里附加一个指针，这个指针表示的是其下一个元素在数组中的位置，而不是下一个元素的实际地址。因此，本题答案为B。
　　题号（15）答案 B
　　习题分析：
　　在链表的插入和删除操作中，应该谨慎处理指针的修改情况。在单链表中，若在指针为p的节点之后插入指针为s的节点，其正确的顺序应为：s->next=p->next; p->next=s。解题的技巧可参照第10题。
　　3．训练自测表（如表1-3所示）

表1-3 选择题练习自测表