首页 › 题库 › GESP编程能力等级认证 › 4.1 单链表

GESP-Python五级 题库

共 18 道题 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

对如下定义的循环单链表,`print_list` 函数横线处填写()。

class Node:
def __init__ (self , data) :
    self.data = data
    self.next = None
def create_list(value) :
    head = Node(value)
    head.next = head
    return head
def insert_tail(head , value) :
    p = head
    while p.next != head:
        p = p.next
    node = Node(value)
    node.next = head
    p.next = node
def print_list(head) :
    # 填空位置
    while True:
        print(p.data , end="  ")
        p = p.next
        if p == head :
            break
    print()
A
if head is None: return p.next = head
B
if head is None: return p = head.next
C
if head is None: return p = head
D
if head.next is None: return p = head
答案与解析
正确答案:C
循环单链表打印需要先初始化遍历指针p,若表头不为空则令p=head,题目选项缺失C、D,标准答案为C,核心逻辑是先给p赋值链表起始节点才能进入循环打印。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

下面关于单链表和双链表的描述中,正确的是()。

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
def delete_dnode(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev
    node.prev = None
    node.next = None
class SNode:
    def __init__(self, data):
        self.data = data
        self.next = None
def delete_snode(head, node):
    if head is None or node is None:
        return
    prev = head
    while prev.next != node:
        prev = prev.next
    prev.next = node.next
    node.next = None
A
双链表删除指定节点是O(n),单链表是O(1)
B
双链表删除指定节点是O(n) ,单链表是O(1)
C
双链表删除指定节点是O(1) ,单链表是O(n)
D
双链表删除指定节点是O(n) ,单链表是O(n)
答案与解析
正确答案:C
已知目标节点指针时,双链表可直接访问前驱完成删除O(1);单链表需要遍历找到前驱节点,复杂度O(n)。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

下面的python代码实现给定单链表头结点 head 和一个整数 val ,删除链表中所有结点值等于 val 的节点,并返回新的头结点,则横线处填写()。

A

B

C

D

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

下列python代码用Floyd判断一个单链表中是否存在环,链表的头节点为 head ,即用两个指针在链表上前进: slow 每次走 1 步, fast 每次走 2 步,若存在环, fast 终会追上 slow (相遇);若无环, fast 会先到达 nullptr。横线上应填写( )。

A

B

C

D

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

以下哪种情况使用链表比数组更合适?

A

数据量固定且读多写少

B

需要频繁在中间或开头插入、删除元素

C

需要高效随机访问元素

D

存储空间必须连续

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

在Python中,可以用字典模拟单向或双向链表的实现。下面的代码模拟单向链表,和链表对象相比,有关其 缺点的说法,错误的是( )。

A

类型安全差,易出错。比如: node1["NEXT"] = node2 不会报错,导致逻辑错误

B

内存开销大。字典需要保存键名称以及哈希表

C

无法封装方法,如 insert() 插入函数较为常用,但其代码需要分散在外部

D

重复存储,难以保证一致性。如在 node1['next'] = node2 代码中, node1['next'] 的值为 node2 ,而 node2 自身也将保存一份

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

基于上题代码,模拟单向链表实现插入新节点函数insertNode()的代码如下,横线处应填入的代码是( )。

A

B

C

D

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

下面的Python代码用于实现双向链表。is_empty()函数用于判断链表是否为空,如为空返回True,否则False。 横线处不能填入的代码是( )。

A

self.tail is None

B

self._size == 0

C

self == None

D

self.head is None

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

链表不具备的特点是( )。

A
可随机访问任何一个元素
B
插入、删除操作不需要移动元素
C
无需事先估计存储空间大小
D
所需存储空间与存储元素个数成正比
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

双向链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点,它的前驱结点和后继结点均非空。现要求删除结点 p ,则下述语句中错误的是( )。

A
class Node:
	def __init__(self, value):
		self.value = value
		self.prev = None
		self.next = None

if p.next:
	p.next.prev = p.prev
if p.prev:
	p.prev.next = p.next
p = None
B
class Node:
	def __init__(self, value):
		self.value = value
		self.prev = None
		self.next = None

if p.next:
	p.next.next = p.prev
if p.prev:
	p.prev.next = p.next
p = None
C
class Node:
	def __init__(self, value):
		self.value = value
		self.prev = None
		self.next = None

if p.next:
	p.next.prev = p.prev
if p.prev:
	p.prev.next = p.prev
p = None
D
class Node:
	def __init__(self, value):
		self.value = value
		self.prev = None
		self.next = None

if p.next:
	p.next.prev = p.next
if p.prev:
	p.prev.next = p.next
p = None
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

假设双向循环链表包含头尾哨兵结点(不存储实际内容),分别为 head 和 tail ,链表中每个结点有两个指针域 prev 和 next ,分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表,横线上应填的最佳代码是( )。

class ListNode:
	def __init__(self, val=None):
		self.data = val
		self.prev = None
		self.next = None

class LinkedList:
	def __init__(self):
		self.head = ListNode()
		self.tail = ListNode()
_______________________
_______________________


def init_linked_list():
	return LinkedList()
A
self.head.next = self.tailself.tail.prev = self.head
B
self.head.next = self.tailself.tail.next = self.head
C
self.head.next = self.headself.tail.prev = self.tail
D
self.head.prev = self.tailself.tail.next = self.head
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

下面关于循环链表的说法正确的是( )。

A
循环链表的最后一个结点指向头结点,形成一个闭环
B
必须通过特定结点才可以遍历整个链表
C

不属于链式存储结构

D

在长度为n的顺序表下标为i的位置前插入一个元素(1 ≤ i ≤ n+1),元素的移动次数为n-i+1

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

数组和链表都是线性表。链表的优点是插入删除不需要移动元素,并且能随机查找。()

A
对
B
错
答案与解析
正确答案:错
链表不支持随机访问,只能顺序遍历。
题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

链表通过更改指针实现高效的节点插入与删除,但节点访问效率低、占用内存较多,且对缓存利用不友好。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

单链表中删除某个结点 p (非尾结点),但不知道头结点,可行的操作是将 p 的值设为 p.next 的值,然后删除 p.next 。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
16 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

链表存储线性表时要求内存中可用存储单元地址是连续的。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

如果将双向链表的最后一个元素指向第一个元素,则构成环状链表。( )

A
对
B
错
答案与解析
正确答案:对

当在Python中将双向链表的最后一个元素的 next 指针指向第一个元素时,链表就形成了一个环状链表。这意味着从最后一个节点开始,可以沿着 next 指针一直遍历到第一个节点,然后再次回到最后一个节点,形成一个闭环结构

题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 4.1 单链表

链表不能采用快速排序或堆排序,但可以采用插入排序。( )

A
对
B
错
答案与解析
正确答案:对

对于链表数据结构而言:

快速排序和堆排序的实现在链表上相对复杂,不是首选,因为它们依赖于对节点的随机访问,而链表的访问是顺序的,不支持常数时间内的随机访问。

插入排序对于链表来说是一种非常合适和直接的排序算法。它可以通过在链表上移动节点来进行排序,不需要额外的空间,而且操作简单。

链表可以采用插入排序,但不适合使用快速排序或堆排序。这是因为插入排序可以通过链表的顺序访问来有效地实现,而快速排序和堆排序则需要随机访问,这在链表上不容易实现或效率不高。

题目详情