GESP Python 5级 2025.03
链表不具备的特点是
可随机访问任何一个元素
插入、删除操作不需要移动元素
无需事先估计存储空间大小
所需存储空间与存储元素个数成正比
双向链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。现要求删除结点 p ，则下述语句中错误的是
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
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
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
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
假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为 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()
self.head.next = self.tail
self.tail.prev = self.head
self.head.next = self.head
self.tail.prev = self.tail
self.head.next = self.tail
self.tail.next = self.head
self.head.prev = self.tail
self.tail.next = self.head
用以下辗转相除法（欧几里得算法）求gcd(84, 60)的步骤中，第二次调用gcd()函数计算的数是
def gcd(a, b):
big = max(a, b)
small = min(a, b)
if big % small == 0:
return small
return gcd(small, big % small)
84和60
60和24
24和12
12和0
根据唯一分解定理，下面整数的唯一分解是正确的
18 = 3 × 6
28 = 4 × 7
36 = 2 × 3 × 6
30 = 2 × 3 × 5
下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，横线上应填的最佳代码是
def sieve_linear(n):
is_prime = [True] * (n + 1)
primes = []
if n < 2:
return primes #
is_prime[0] = is_prime[1] = False
for i in range(2, n // 2 + 1):
if is_prime[i]:
primes.append(i)
j = 0
_____________________________________
is_prime[i * primes[j]] = False
if i % primes[j] == 0:
break
j += 1
for i in range(n // 2 + 1, n + 1):
if is_prime[i]:
primes.append(i)
return primes
while j < len(primes) and j * primes[j] <= n:
while j < len(primes) and i * primes[j] <= n:
while j < len(primes) and j * primes[i] <= n:
while i < len(primes) and i * primes[j] < n:
在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
系统分配的栈空间溢出
系统分配的堆空间溢出
系统分配的队列空间溢出
系统分配的链表空间溢出
对下面两个函数，说法错误的是
def factorialA(n):
if n <= 1:
return 1
return n * factorialA(n - 1)
def factorialB(n):
if n <= 1:
return 1
res = 1
for i in range(2, n + 1):
res *= i
return res
两个函数的实现的功能相同。
两个函数的时间复杂度均为O(n) 。
factorialA采用递归方式。
factorialB采用递归方式。
以下算法中，（ ）是不稳定的排序。
选择排序
插入排序
归并排序
冒泡排序
考虑以下python代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
_________________________________
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
if arr[i] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
if arr[j] < pivot:
j += 1
if arr[i] < pivot:
j += 1
arr[i], arr[i] = arr[j], arr[i]
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]