课堂练习

1. 【NOIP2014】链表不具有的特点是( )。
   A. 不必事先估计存储空间
   B. 可随机访问任一元素
   C. 插入、删除不需要移动元素
   D. 所需空间与线性表长度成正比
   【答案】B
   【分析】链表无法随机访问任意元素，查找任一结点都需要进行复杂度为O(n)的顺序查找过程。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个结点或者访问特定编号的结点则需要O(n)的时间。
2. 【NOIP2015】线性表若采用链表存储结构，要求内存中可用存储单元地址( )。
   A. 必须连续
   B. 部分地址必须连续
   C. 一定不连续
   D. 连续不连续均可
   【答案】D
   【分析】考查数据结构基础知识。数组存储单元地址要连续，而链表可以在产生新结点的时候动态申请内存（不一定连续），也可以事先申请一部分连续的内存来给未来新增的结点预留空间。链表存储单元地址连续或者不连续都可以。
3. 【NOIP2011】在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度是( )。
   A. O(1)
   B. O(logn)
   C. O(n)
   D. O(nlogn)
   【答案】C
   【分析】在链表里查询一个数需要一个一个扫过去，最坏情况是最后一个才找到或未找到，所以是O(n)的。
4. 【NOIP2014】对长度为n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( )。
   A. $n / 2$
   B. $(n + 1) / 2$
   C. $(n - 1) / 2$
   D. $n/4$
   【答案】B
   【分析】第1个数需要检索1次，第2个数需要检索2次，第3个数需要检索3次，… 检索长度 = 总检索次数 / 个数 =$\frac{1 + 2 + 3 + \cdots + n}{n}=\frac{n + 1}{2}$ 。
5. 【NOIP2014】有以下结构体说明和变量定义，如图所示，指针P、q、r分别指向一个链表中的三个连续结点。

struct node{
    int data;
    node*next;
}*p, *q, *r;

现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( )。
A. q->next=r->next;p->next=r;r->next=q;
B. p->next =r; q->next =r->next; r->next =q;
C. q->next=r->next;r->next=q;p->next=r;
D. r->next =q; q->next =r->next; p->next =r;
【答案】D
【分析】本题考查指针的理解和应用。r->next =q;q->next =r->next;，第一步操作将r的后继指向了q，所以第二步操作的时候实质是将q的后继指向了q本身而不是原来r的后继。 6. 【NOIP2010】双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是( )。
A. p->llink->rlink=p->rlink;p->rlink->llink=p->llink;delete p;
B. p->llink->rlink=p->rlink;p->rlink->llink=p->llink;delete p;
C. p->rlink->llink =p->llink;p->rlink->llink->rlink =p->rlink;delete p;
D. p->llink->rlink =p->rlink;p->llink->rlink->llink =p->llink;delete p;
【答案】A
【分析】A中将p的后继的前驱改为指向p的后继，P的前驱的后继改为指向p的前驱，这样链表就中断了。

7. 【NOIP2015】双向链表中有两个指针域llink和rlink，分别指向前驱及后继，设P指向链表中的一个结点，q指向一待插入结点，现要求在P前插入q，则正确的插入为( )。
   A. p->llink =q; q->rlink =p; p->llink->rlink =q; 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;
   【答案】D
   【分析】 A选项的第一句已经把p->llink更改成了q；第三句p->llink->rlink =q;就等价于q->rlink=q，指向了自身，造成链接对象丢失； B选项的第二句p->llink->rlink =q;等价于p=q，结果导致P被替换； C选项，由于要求在P前插入q，因此第二句p->rlink=q;不需要更改； 只有D可以达到正确的插入要求。要在P之前插入q，首先应该让q的左右指针分别指向P的前驱和p，然后让另外两个指针指向p即可，即p的前驱的右指针和p的左指针。

不定项选择题

1. 【NOIP2009】在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有2个以上的结点。下面说法正确的是( )。
   A. 如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为p->next=clist->next;clist->next=p;
   B. 如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为p->next=clist;clist->next=p;
   C. 在头部删除一个结点的语句序列为p=clist->next;clist->next=clist->next->next;delete p;
   D. 在尾部删除一个结点的语句序列为p=clist;clist=clist->next;delete p;
   【答案】AC
   【分析】A选项是从前面插入p结点。

B选项要求在尾部插入结点，插完之后clist要指向这个新的尾结点，所以B应该改为p->next=clist->next;clist->next=p;clist=p;。 C选项的过程是删除第一个结点。

D中要循环找到尾指针的上一个元素才能进行删除。 2. 【NOIP2010】双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均为非空。现要求删除结点p，则下列语句序列中正确的是( )。
A. p->llink->rlink=p->rlink;p->rlink->llink=p->llink;delete p;
B. p->llink->rlink=p->rlink;p->rlink->llink=p->llink;delete p;
C. p->rlink->llink =p->llink;p->rlink->llink->rlink =p->rlink;delete p;
D. p->llink->rlink =p->rlink;p->llink->rlink->llink =p->llink;delete p;
【答案】BCD
【分析】选项A中的语句执行后，结点P右边的结点的左指针指向自身，左边的结点的右指针也指向自身。当p被释放后，其左、右结点之间便产生了断裂，不再是一个链表。其余选项经检验都是正确的。