链表选择题练习

链表选择题练习

1、已知L是带头节点的单链表，节点P既不是头节点（第⼀个节点)，也不是尾节点，删除P节点直春节食物 接后继节点的语句序列是（C）

A、P = P -> next;

B、P -> next = P;

C、P - > next = P -> next -> next;

D、P=P -> next -> next;

题解：

将当前节点的下⼀个的下⼀个赋给当前的P -> next,这样就直接跳过了P节点的直接后继节点。

2、在⼀个单链表中，若删除p所指结点的后续结点，则执⾏（C）

A、p = p->next; p->next = p->next->next;

B、p->next = p->next;

C、p->next = p->next->next；。

D、p = p->next->next；

题解：

如果删除p的后续节点则是图中的q，我们只需让p的next指向q的next，也就是p->next->next，所以选C。

3、带头结点的单链表head为空的判定条件属猴和属鼠的合不合 是（B）

A、head= =NULL

B、head->next= =NULL

C、head->next= =head

D、head!=NULL

题解：

带头节点的单链表的头节点head总是不空的，但不存储内容，下⼀个节点才是存储内容的开始，若没有下⼀个节点，则表⽰该链表没有存

储内容，即head -> next = NULL。

如果不带头节点，head为第⼀个节点，要是内容为空，则整个链表为空，即head = NULL。

4、如果使⽤⽐较⾼效的算法判断单链表有没有环的算法中，⾄少需要⼏个指针？（B）

A 1

B 2

C 3

D 4

题解：

通过快慢指针来实现，两个指针的速度不⼀样，如果相遇则表⽰有环，否则表⽰⽆环。

因为链表的环不⼀定是⾸尾相连的，所以⼀个指针⽆法判断。

5、在双向链表存储结构中，删除p所指的结点时需要修改指针______ 。（A）

A p->next->prior=p->prior; p->prior->next=p->next

B p->next=p->next->next; p->next->prior=p

C p->prior->next=p; p->prior=p->prior->prior

D p->prior=p->next->next; p->next=p->prior->prior

题解：

将p节点的下⼀个节点的prior指向p节点的上⼀个节点，再将p节点的前⼀个节点的next指向p节点的下⼀个节点。

6、不属于链表特点的是（C）

A 适⽤频繁插⼊

B 适⽤于频繁删除

C 存取速度快

D ⽅便扩充

题解：

链表的特点如下：

长度不固定，可以任意增删，插⼊或删除节点时，只需改变相应节点的指针指向即可，⽆需移动⼤量元素。

存储空间不连续，数据元素之间使⽤指针相连，每个数据元素只能访问周围的⼀个元素（根据单链表还是双链表有所不同），所以黄文绣 易于

扩展。

存储密度⼩，因为每个数据元素都需要额外存储⼀个指向下⼀个元素的指针（双链表需要两个指针）。

要访问特定元素，链表必须从链表头开始，依次向后查找，平均需要0(n)的时间，存取速度慢。

所以选C存储速度快不是链表的特点。

7、如果最常⽤的操作是取第i个结点及其前驱，则采⽤（D）存储⽅式最节省时间。

A 单链表

B 双链表

C 单循环链表

D 顺序表

题解：

对于顺序结构的特点就是利于存取，所以对于取第i个节点，很明显采⽤顺序结构更加合理，所以选择顺序表。

链式结构的特点是更利于插⼊和删除操作。

8、若某线性表最常⽤的操作是存取任⼀指定序号的元素和在最后进新硬盘 ⾏插⼊和删除运算,则利⽤（A）存储⽅式最节省时间。

A 顺序表

B 双链表

C 带头结点的双循环链表

D 单循环链表

题解：

根据题中需要获取任⼀指定序号则需要采⽤顺序结构工作岗位 ，虽然会进⾏插⼊和删除操作，但是因为是在尾部插⼊和删除，所以可以使⽤顺序结

构，顺序结构不利于在中间进⾏插⼊和删除操作。

9、关于双链表的搜索给定元素操作的说法正确的是?（B）

A 从两个⽅向搜索双链表，⽐从⼀个⽅向搜索双链表的速度慢

B 从两个⽅向搜索双链表，⽐从⼀个⽅向搜索双链表的⽅差要⼩

C 从两个⽅向搜索双链表，⽐从⼀个⽅向搜索双链表速度要快

D 以上说法都不正确

题解：

如果链表是⽆序的，则单向搜索与双向搜索相同

如果链表是有序的，要搜索的数据距离最⼩值较近，这种情况双向搜索更快。

如果是有序的，双向链表的⽅差更⼩。

10、对于只在表的⾸、尾两端进⾏插⼊操作的线性表，宜采⽤的存储结构为( C）

A 顺序表

B ⽤头指针表⽰的单循环链表

C ⽤尾指针表⽰的单循环链表

D 单链表

题解：

带尾指针的单循环链表找表头结点和表尾结点耗时都是O（1）

带头结点的单循环链表找头结点时间耗费为O（1），找表尾结点时间耗费为O（n）