下面的程序中，x,y都是正整数，完成的算法是（ ）
def chenadai(x, y):
while y:
x, y = y, x % y
return x
最小公倍数
最大公约数
数字x能够整除y的最小数
数字x与数字y的所有公约数
下列程序中实现的是（ ）
def chenadai(x, y):
return x * y // (x,y的最大公约数)
实现了求x,y的最小公约数
实现了求x,y的最大公约数
实现了求x,y的最小公倍数
实现了求x,y的平均值
欧几里得算法又称作辗转相除算法，下面程序中是这种算法的是（ ）
def gcd(a,b):
if b == 0:
return a
return gcd(b, a % b)
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
a,b = b,a%b
return b
def gcd(a,b):
if b == 0:
return a
return gcd(a, a % b)
def gcd(a,b):
if b == 0:
return a
return gcd(b, b % a)
下列程序是二分法的程序，横线处应该填上（ ）。
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
_________________________
return -1
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid
else:
left = mid
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
if arr[mid] == target:
return mid
else:
left = mid + 1
下面折半查找程序的时间复杂度为（ ）
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
high = mid - 1
else:
low = mid + 1
return -1
O(n*logn)
O(n)
O(logn)
O(n^2)
下列程序中，使用了埃氏筛法，横线处应该填写的是（）
def aishishai(n):
if n < 2:
return []
prime = [True] * (n + 1)
prime[0] = prime[1] = False
——————————————————————————————————
if prime[p]:
for i in range(p * p, n + 1, p):
prime[i] = False
return [p for p in range(n + 1) if prime[p]]
for p in range(2, n ** 0.5 + 1):
for p in range(2, int(n ** 0.5) + 1):
for p in range(2, int(n ** 0.5) + 0.5):
for p in range(2, n ** 0.5 + 0.5):
18到100之间的所有素数的和为多少( )
1060
1004
1002
1052
下面程序是对2024进行唯一分解，最后的结果应该是（ ）。
def weiyi(n):
factors = {}
for i in range(2, n+1):
while n % i == 0:
if i in factors:
factors[i] += 1
else:
factors[i] = 1
n //= i
return factors
1,2,3,13,23
2,7,11,23
2:3,11:1,23:1
2,3,13,23
下面关于循环链表的说法正确的是（ ）。
循环链表的最后一个结点指向头结点，形成一个闭环
必须通过特定结点才可以遍历整个链表
不属于链式存储结构
在长度为n的顺序表下标为i的位置前插入一个元素（1 ≤ i ≤ n+1），元素的移动次数为n-i+1
下列归并算法程序中，横线处应该填入的是（ ）
def merge_sort(array):
if len(array) == 1:
return array
_________________________
return merge(left, right)
def merge(left, right):
left_index, right_index, merge_array = 0, 0, list()
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
merge_array.append(left[left_index])
left_index += 1
else:
merge_array.append(right[right_index])
right_index += 1
merge_array = merge_array + left[left_index:] + right[right_index:]
return merge_array
left = merge_sort(array[:len(array)-1//2])
right = merge_sort(array[len(array)-1//2:])
left = merge_sort(array[len(array)//2-1])
right = merge_sort(array[len(array)//2:])
left = merge_sort(array[len(array)//2-1])
right = merge_sort(array[len(array)//2])
left = merge_sort(array[:len(array)//2])
right = merge_sort(array[len(array)//2:])
关于算法复杂度，下列说法不正确的是（）
简单的for循环的时间复杂度是O(1)
归并排序的时间复杂度是O(nlog(n))
选择排序中的内循环时间复杂度是(O(n^2))
递归的 Fibonacci 数列计算时间复杂度是O(2^n)
下列程序中，实现了16进制转到8进制。横线处应该填入的是（ ）
def dec_conversion_n(n, base):
str_list = "0123456789ABCDEF"
if n < base:
return str_list[n]
else:
__________________________
return dec_conversion_n(n // base, base) + str_list[n % base]
return dec_conversion_n(n // base, n) + str_list[n % base]
return dec_conversion_n(n // base, base) + str_list[n // base]
return dec_conversion_n(n // base, n) + str_list[n // base]
水仙花数是指一个 3 位数，它的每个数位上的数字的 3次幂之和等于它本身。下面代码是计算100到n之间有多少个水仙花数的程序，横线处应该填写的一行或多行代码是（ ）。
n = int(input("输入一个正整数N:"))
sum = 0
for i in range(100,n+1):
_______________________
print(sum)
ge = i%10
shi = i//10%10
bai = i//100
if i == ge*ge*ge+shi*shi*shi+bai*bai*bai:
sum+=1
ge = i%10
shi = i%10%10
bai = i//100
if i == ge*ge*ge+shi*shi*shi+bai*bai*bai:
sum+=1
ge = i%10
shi = i//10%10
bai = i%100
if i == ge*ge*ge+shi*shi*shi+bai*bai*bai:
sum+=1
ge = i%10
shi = i%10%10
bai = i%100
if i == ge*ge*ge+shi*shi*shi+bai*bai*bai:
sum+=1
下面程序输出的是
def func(x):
if x%2 == 1:
return x+1
else:
return func(x-1)
print(func(9))
print(func(6))
10
6
9
6
10
7
9
7
旋转数组是一种常见的数据结构问题，通常是指一个有序数组经过旋转后，使得所有元素逆序排列。整数数组 nums 按升序排列，数组中的值互不相同。在预先未知的某个下标 k（0 <= k <nums.length）上进行了旋转，使数组变为 [nums[k], nums[k + 1],..., nums[n - 1], nums[0], nums[1],..., nums[k - 1]]（下标从 0 开始计数）。现在给定旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回-1。
下面程序中（）处应填入的程序是：例如，给定一个数组 [4,5,6,7,0,1,2]，它可能经过旋转变为 [0,1,2,4,5,6,7]。二分查找算法搜索旋转排序数组的程序，下面横线中，应填入的一行或多行代码是（ ）
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[mid] > nums[right]：
if nums[mid] > target or nums[left] <= target:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < nums[right]:
__________________________
else:
right -= 1
return False
if nums[mid] < target or nums[right] >= target:
lleft = mid - 1
else:
lright = mid + 1
if nums[mid-1] < target and nums[right+1] >= target:
left = mid + 1
else:
right = mid - 1
if nums[mid] < target or nums[right] >= target:
lleft = mid
else:
lright = mid
if nums[mid] < target and nums[right] >= target:
lleft = mid + 1
else:
lright = mid - 1
两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数
对
错
任何一个大于1的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。
对
错
要得到不大于某个自然数 （不等于0）的所有素数，只要在2至 中将不大于根号n的素数的倍数全部划去即可
对
错
任何一个大于1的自然数，要么所有质因子都小于等于根号n，要么只有一个质因子大于根号n，其余质因子都小于根号n。
对
错
贪心算法的空间复杂度通常是O(1)
对
错
归并排序的空间复杂度为O(n)
对
错
时间复杂度对比
对
错
对于任意整数
对
错
下列程序输出的是21
def digui(n):
if n <= 1:
return n
else:
return digui(n-1) + digui(n-2)
print(digui(8))
对
错
CCF(十六进制) = 1653(13进制)
对
错
