单选题

1. 下面的程序中，x,y都是正整数，完成的算法是（ ）

   def chenada1(x, y):
       while y:
           x, y = y, x % y
       return x
   

   {{ select(1) }}

• 最小公倍数
• 最大公约数
• 数字x能够整除y的最小数
• 数字x与数字y的所有公约数

2. 下列程序中实现的是（ ）

   def chenada1(x, y):
       return x * y // (x,y的最大公约数)
   

   {{ select(2) }}

• 实现了求x,y的最小公约数
• 实现了求x,y的最大公约数
• 实现了求x,y的最小公倍数
• 实现了求x,y的平均值

3. 欧几里得算法又称作辗转相除算法，下面程序中是这种算法的是（ ）

   def gcd(a,b):
       if b == 0:
           return a
       return gcd(b, a % b)
   

   {{ select(3) }}

• 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)

4. 下列程序是二分法的程序，横线处应该填上（ ）。

   def binary_search(arr, target):
       left = 0
       right = len(arr) - 1
       while left <= right:
           mid = (left + right) // 2
           return -1
   

   {{ select(4) }}

• 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
  

5. 下面折半查找程序的时间复杂度为（ ）

   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
   

   {{ select(5) }}

• ( O(n * \log n) )
• ( O(n) )
• ( O(\log n) )
• ( O(n^2) )

6. 下列程序中，使用了埃氏筛法，横线处应该填写的是（ ）

   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]]
   

   {{ select(6) }}

• 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):

7. 18到100之间的所有素数的和为多少()

   {{ select(7) }}

• 1060
• 1004
• 1002
• 1052

8. 下面程序是对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
   

   {{ select(8) }}

• 1,2,3,13,23
• 2,7,11,23
• 2,3,11:1,23:1
• 2,3,13,23

9. 下面关于循环链表的说法正确的是（ ）。

   {{ select(9) }}

• 循环链表的最后一个结点指向头结点，形成一个闭环
• 必须通过特定结点才可以遍历整个链表
• 不属于链式存储结构
• 在长度为n的顺序表下标为的位置前插入一个元素（1≤i≤n+1），元素的移动次数为n+i+1

10. 下列归并算法程序中，横线处应该填入的是（ ）

    def merge_sort(array):
        if len(array) == 1:
            return array
        ______
        return merge(left, right)
    

    {{ select(10) }}

• 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:])
  

11. 关于算法复杂度，下列说法不正确的是（）

    {{ select(11) }}

• 简单的for循环的时间复杂度是O(1)
• 归并排序的时间复杂度是O(nlog(n))
• 选择排序中的内循环时间复杂度是(O(n^2))
• 递归的Fibonacci数列计算时间复杂度是O(2^n)

12. 下列程序中，实现了16进制转到8进制。横线处应该填入的是（）

    def dec_conversion_n(n, base):
        str_list = "0123456789ABCDEF"
        if n < base:
            return str_list[n]
        else:
    

    {{ select(12) }}

• return dec_conversion_n(n // base, base) + str_list[n % base]
  

• return dec_conversion_n(n // base, n) + str_list[n % base]
  

• C.

  return dec_conversion_n(n // base, base) + str_list[n // base]
  

• return dec_conversion_n(n // base, n) + str_list[n // base]
  

13. 水仙花数是指一个3位数，它的每个数位上的数字的3次幂之和等于它本身。下面代码是计算100到n之间有多少个水仙花数的程序，横线处应该填写的一行或多行代码是（ ）。

    n = int(input("输入一个正整数N:"));
    sum = 0
    for i in range(100,n+1):
        ______
    print(sum)
    

    {{ select(13) }}

• 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
  

14. 下面程序输出的是

    def func(x):
        if x%2 == 1:
            return x+1
        else:
            return func(x-1)
    print(func(9))
    print(func(6))
    

    {{ select(14) }}

• 1 | 10
  2 | 6
  

• 1 | 9
  2 | 6
  

• 1 | 10
  2 | 7
  

• 1 | 9
  2 | 7
  

15. 旋转数组是一种常见的数据结构问题，通常是指一个有序数组经过旋转后，使得所有元素逆序排列。整数数组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]:
    

    {{ select(15) }}

• if nums[mid] < target or nums[right] >= target:
      left = mid - 1
  else:
      height = 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:
      left = mid
  else:
      height = mid
  

• if nums[mid] < target and nums[right] >= target:
      left = mid + 1
  else:
      height = mid - 1
  

判断题

1. 两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

   {{ select(16) }}

• 对
• 错

2. 任何一个大于 1 的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。

   {{ select(17) }}

• 对
• 错

3. 要得到不大于某个自然数 ( n )（不等于0）的所有素数，只要在 ( 2 \times n ) 中将不大于 ( \sqrt{n} ) 的素数的倍数全部划去即可

   {{ select(18) }}

• 对
• 错

4. 任何一个大于 1 的自然数，要么所有质因子都小于等于 ( \sqrt{n} )，要么只有一个质因子大于 ( \sqrt{n} )，其余质因子都小于 ( \sqrt{n} )。

   {{ select(19) }}

• 对
• 错

5. 贪心算法的空间复杂度通常是 ( O(1) )

   {{ select(20) }}

• 对
• 错

6. 归并排序的空间复杂度为 ( O(n) )

   {{ select(21) }}

• 对
• 错

7. 时间复杂度对比 (O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2 \log n) < O(n^3) < O(n^5))。

   {{ select(22) }}

• 对
• 错

8. 对于任意整数 (a = a \pmod{m})。

   {{ select(23) }}

• 对
• 错

9. 下列程序输出的是21

   def digui(n):
       if n <= 1:
           return n
       else:
           return digui(n-1) + digui(n-2)
   print(digui(8))
   

   {{ select(24) }}

• 对
• 错

10. CCF(十六进制) = 1653(13进制)

    {{ select(25) }}

• 对
• 错