class Node:
def __init__(self, val):
self.val = val
self.next = None
def insert_after_head(head, x):
new_node = Node(x)
____________________
2分
登录后查看选项
02
下面代码遍历并输出一个循环单链表，其中 head 指向链表的第一个节点，横线处应填入的是（ ）。
class Node:
def __init__(self, val):
self.val = val
self.next = None
def printList(head):
if head is None:
return
p = head
_______________________
print()
2分
登录后查看选项
03
双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点） p ，写法正确的是（ ）。
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
2分
登录后查看选项
04
使用如下欧几里得算法求 gcd(105, 45) 时，函数 gcd(a, b) 的递归调用序列正确的是（ ）。
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
2分
登录后查看选项
05
下面代码实现线性筛（欧拉筛），以筛选出 n 以内的所有素数。横线处的代码应为（ ）。
def sieve(n):
is_prime = [True] * (n + 1)
primes = []
if n >= 0:
is_prime[0] = False
if n >= 1:
is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
j = 0
while j < len(primes) and i * primes[j] <= n:
is_prime[i * primes[j]] = False
if ________________: # 在此处填入代码
break
j += 1
return primes
2分
登录后查看选项
06
下面关于埃氏筛法的说法正确的是（ ）。
2分
登录后查看选项
07
下面代码实现了计算 的快速幂算法，该算法体现的编程思想是（ ）。
def power(x, n):
if n == 0:
return 1
res = power(x, n // 2)
if n % 2 == 0:
return res * res
else:
return res * res * x
2分
登录后查看选项
08
下面代码用于统计 n 中因子 2 出现了多少次。若 n = 40 ，输出是（ ）。
n = 40
cnt = 0
while n % 2 == 0:
cnt += 1
n = n // 2
print(cnt)
2分
登录后查看选项
09
在一个有序数组中查找第一个大于或等于 x 的元素位置，横线处应填写（ ）。
def lowerBound(a, x):
l = 0
r = len(a)
while l < r:
mid = l + (r - l) // 2
if a[mid] >= x:
________________ # 在此处填入代码
else:
l = mid + 1
return l
2分
登录后查看选项
10
有若干根木头，长度存于 wood 。每切一刀可以把一段木头分成两段。函数 check(wood, K, x) 返回：用不超过 K 刀，能否使所有木段长度都不超过 x 。下面代码使用二分答案查找最小可行的 x ，横线处应填（ ）。
def binary_cut(wood, K):
l = 1
r = 0
for length in wood:
r = max(r, length)
while l < r:
mid = l + (r - l) // 2
if check(wood, K, mid):
________________ # 在此处填入代码
else:
l = mid + 1
return l
2分
登录后查看选项
11
下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（ ）。
def partition(arr, low, high):
pivot = arr[low]
i = low
j = high
while i < j:
while i < j and arr[j] >= pivot:
j -= 1
while i < j and arr[i] <= pivot:
i += 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
________________ # 在此处填入代码
return i
MAXN = 100005
a = [0] * MAXN
tempArr = [0] * MAXN
def mergeArray(left, mid, right):
i = left
j = mid + 1
k = left
while i <= mid and j <= right:
if a[i] <= a[j]:
tempArr[k] = a[i]
i += 1
else:
tempArr[k] = a[j]
j += 1
k += 1
while i <= mid:
tempArr[k] = a[i]
i += 1
k += 1
while j <= right:
tempArr[k] = a[j]
j += 1
k += 1
for p in range(left, right + 1):
a[p] = tempArr[p]
def mergeSort(left, right):
if left >= right:
return
mid = left + (right - left) // 2
mergeSort(left, mid)
mergeSort(mid + 1, right)
mergeArray(left, mid, right)
if a[i] < b[i]:
a[i + 1] -= 1
________________
t = a[i] - b[i]
2分
登录后查看选项
判断题 共10道
16
数组的存储空间在物理上通常是连续的，而链表的结点可以存储在不连续的内存空间中。
2分
登录后查看选项
17
带哨兵头尾节点的双向循环链表，在表头插入节点 p ，以下四步操作无论什么顺序执行结果都正确。
# 1
p.next = head.next
# 2
p.prev = head
# 3
head.next.prev = p
# 4
head.next = p
2分
登录后查看选项
18
对任意正整数 a 、 b ，以下两种写法的 gcd 函数返回值完全相同。
def gcd1(a, b):
return gcd1(b, a % b) if b else a
def gcd2(a, b):
while b:
t = b
b = a % b
a = t
return a
2分
登录后查看选项
19
在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组 L 和 R 合并回原数组 arr中。
def merge(arr, left, mid, right):
n1 = mid - left + 1
n2 = right - mid
L = [0] * n1
R = [0] * n2
for i in range(n1):
L[i] = arr[left + i]
for j in range(n2):
R[j] = arr[mid + 1 + j]
i = 0
j = 0
k = left
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1