链表 - Problem Detail - lizikid

ID: 17

Type: Objective

Difficulty: 8

Uploaded By:

Tags>

初赛选择题

链表不具有的特点是（）。 {{ select(1) }}

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

线性表若采用链表存储结构，要求内存中可用存储单元地址（）。 {{ select(2) }}

必须连续
部分地址必须连续
一定不连续
连续不连续均可

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

O(1)
O(log n)
O(n)
O(n log n)

对长度为n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为（）。 {{ select(4) }}

n/2
(n+1)/2
(n-1)/2
n/4

有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个连续结点。

现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是（）。 {{ select(5) }}

q->next = r->next; p->next = r; r->next = q;
p->next = r; q->next = r->next; r->next = q;
q->next = r->next; r->next = q; p->next = r;
r->next = q; q->next = r->next; p->next = r;

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

p->rlink->llink = p->rlink;p->llink->rlink = p->llink; delete p;
p->llink->rlink = p->rlink; p->rlink->llink = p->llink; delete p;
p->rlink->llink = p->llink;p->rlink->llink->rlink = p->rlink; delete p;
p->llink->rlink = p->rlink;p->llink->rlink->llink = p->llink; delete p;

双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）。 {{ select(7) }}

p->llink = q; q->rlink = p; p->llink->rlink = q; q->llink = p->llink;
q->llink = p->llink; p->llink->rlink = q; q->rlink = p; p->llink = q->rlink;
q->rlink = p; p->rlink = q; p->llink->rlink = q; q->rlink = p;
p->llink->rlink = q; q->rlink = p; q->llink = p->llink; p->llink = q;