第二章 程序设计基本知识

第6节 链表

1.【NOIP2014】链表不具有的特点是( )。

A. 不必事先估计存储空间 B. 可随机访问任一元素 C. 插入删除不需要移动元素 D. 所需空间与线性表长度成正比

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

A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可

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

A. 0(1) B. O(log n) C. 0(n) D. 0(n log n)

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

A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4

5.【NOIP2014】有以下结构体说明和变量定义，如图所示，指针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;

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

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;

不定项选择题

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