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()
class Block:
def __init__(self, idx, data, prev_block):
self.index = idx
self.data = data
self.prev = prev_block
class Blockchain:
def __init__(self):
self.tail = None
def init(self):
genesis_block = Block(0, "Genesis Block", None)
self.tail = genesis_block
def add_block(self, data):
____________________________________
def clear(self):
cur = self.tail
while cur is not None:
prev_block = cur.prev
cur.prev = None
cur = prev_block
self.tail = None
def print_chain(self):
cur = self.tail
chain = []
while cur is not None:
chain.append(f"Block {cur.index}: {cur.data}")
cur = cur.prev
for block_info in reversed(chain):
print(block_info)
2分
登录后查看选项
03
下面关于单链表和双链表的描述中，正确的是（ ）。
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
2分
登录后查看选项
04
假设我们有两个数 a=38 和 b=14，它们对模 m 同余，即 a==b (mod m)。以下哪个值不可能是 m？
2分
登录后查看选项
05
下面代码实现了欧几里得算法，下面有关说法，错误的是（ ）。
def gcd1(a: int, b: int) -> int:
return a if b == 0 else gcd1(b, a % b)
def gcd2(a: int, b: int) -> int:
while b != 0:
temp = b
b = a % b
a = temp
return a
2分
登录后查看选项
06
唯一分解定理描述的内容是（ ）。
2分
登录后查看选项
07
下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。
def linear_sieve(n):
if n < 2:
return []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for j in range(len(primes)):
p = primes[j]
if i * p > n:
break
__________________
if i % p == 0:
break
return primes
2分
登录后查看选项
08
下列关于排序的说法，正确的是( )。
2分
登录后查看选项
09
下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。
def merge(arr, temp, l, mid, r):
i = l
j = mid + 1
k = l
while i <= mid and j <= r:
if arr[i] <= arr[j]:
temp[k] = arr[i]
i += 1
else:
temp[k] = arr[j]
j += 1
k += 1
while i <= mid:
temp[k] = arr[i]
i += 1
k += 1
while j <= r:
temp[k] = arr[j]
j += 1
k += 1
for p in range(l, r + 1):
arr[p] = temp[p]
def merge_sort(arr, temp, l, r):
if l >= r:
return
mid = l + (r - l) // 2
merge_sort(arr, temp, l, mid)
merge_sort(arr, temp, mid + 1, r)
merge(arr, temp, l, mid, r)
def merge_sort_wrapper(arr):
if not arr:
return []
temp = [0] * len(arr)
merge_sort(arr, temp, 0, len(arr) - 1)
return arr
2分
登录后查看选项
10
下述python代码实现了快速排序算法，最差情况时间复杂度是（ ）。
def partition(arr, low, high):
i = low
j = high
pivot = arr[low]
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]
arr[i], arr[low] = arr[low], arr[i]
return i
def quick_sort(arr, low, high):
if low >= high:
return
p = partition(arr, low, high)
quick_sort(arr, low, p - 1)
quick_sort(arr, p + 1, high)
def quick_sort_wrapper(arr):
if not arr:
return []
quick_sort(arr, 0, len(arr) - 1)
return arr
2分
登录后查看选项
11
下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回arr.size() 。以下说法正确的是（ ）。
def lower_bound(arr, x):
l = 0
r = len(arr)
while l < r:
mid = l + (r - l) // 2
if arr[mid] >= x:
r = mid
else:
l = mid + 1
return l
2分
登录后查看选项
12
小杨要把一根长度为 L 的木头切成 K 段，使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x （ x 为正整数），则横线处应填写（ ）。
def check(L, K, x):
cuts = (L - 1) // x
return cuts <= K
def binary_cut(L, K):
l = 1
r = L
while l < r:
___________________
return l
if __name__ == "__main__":
L = 10
K = 2
result = binary_cut(L, K)
print(result)
2分
登录后查看选项
13
根据下面代码，以下说法正确的是（ ）。
def factorial1(n):
if n <= 1:
return 1
return n * factorial1(n - 1)
def factorial2(n):
result = 1
while n > 1:
result *= n
n -= 1
return result
class Task:
def __init__(self, deadline, profit):
self.deadline = deadline
self.profit = profit
def sort_by_profit(tasks):
tasks.sort(key=lambda x: x.profit, reverse=True)
def max_profit(tasks):
sort_by_profit(tasks)
max_time = 0
for task in tasks:
if task.deadline > max_time:
max_time = task.deadline
slot = [False] * (max_time + 1)
total_profit = 0
for task in tasks:
t = task.deadline
while t >= 1:
if not slot[t]:
__________________
t -= 1
return total_profit
2分
登录后查看选项
15
下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（ ）。
def add(a, b):
c = []
carry = 0
i = 0
while i < len(a) or i < len(b):
if i < len(a):
carry += a[i]
if i < len(b):
carry += b[i]
____________________
i += 1
if carry:
c.append(carry)
return c
2分
登录后查看选项
判断题 共10道
16
数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。
2分
登录后查看选项
17
假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm(a，b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。
import math
def lcm(a, b):
if a == 0 or b == 0:
return 0
return abs(a) // math.gcd(abs(a), abs(b)) * abs(b)
2分
登录后查看选项
18
在 Python 实现的单链表中，已知引用 p 指向要删除的节点（该节点不是尾节点），若想在 时间复杂度内删除这个节点，可行的做法是：用 p 的后继节点 p.next 的值覆盖 p 自身的值，再用 p 的后继节点的next 引用覆盖 p 的 next 引用，最后断开 p 的后继节点的引用以辅助垃圾回收。