206 链表

您的姓名：



单项选择题

1.【NOIP2014】链表不具有的特点是（）。

A.不必事先估计存储空间

B.可随机访问任一元素

C.插入删除不需要移动元素

D.所需空间与线性表长度成正比

2.【NOIP2015】链表不具备的特点是（）。

A.可随机访问任何一个元素

B.插入、删除操作不需要移动元素

C.无需事先估计存储空间大小

D.所需存储空间与存储元素个数成正比

3.【NOIP2015】线性表若采用链表存储结构，要求内存中可用存储单元地址（）。

A.必须连续

B.部分地址必须连续

C.一定不连续

D.连续不连续均可

4.【NOIP2011】在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（）。

A.O(1)

B.O(logn)

C.O(n)

D.O(n*logn)

5.【NOIP2014】对长度为 n 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为（）。

A.n/2

B.(n+1)/2

C.(n-1)/2

D.n/4

6.【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;

7.【NOIP2010】双向链表中有两个指针域 llink 和 rlink,分别指向该结点的前驱及后继。设 p 指向链表中的一个结点，它的左右结点均非空。现要求删除结点 p,则下面语句序列中错误的是（）。

A.p->rlink->llink=p->rlink; p->llink->rlink=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;

8.【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;

不定项选择题

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;

2.【NOIP2010】双向链表中有两个指针域 llink 和 rlink，分别指向该结点的前驱及后继。设 p 指向链表中的一个结点，他的左右结点均为非空。现要求删除结点 p，则下列语句序列中正确的是（）。【多选题】

A.p->rlink->llink=p->rlink;p->llink->rlink=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->link = p->llink;delete p;