文档介绍：该【2025年NOIP全国信息学奥赛模拟试卷（基础算法与程序设计）——Python编程挑战题集 】是由【朱老师】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【2025年NOIP全国信息学奥赛模拟试卷（基础算法与程序设计）——Python编程挑战题集 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2025年NOIP全国信息学奥赛模拟试卷（基础算法与程序设计）——Python编程挑战题集
一、编程题
要求：编写一个Python程序，实现以下功能：
1. 编写一个函数，用于计算两个整数的最大公约数（Greatest Common Divisor，GCD）。函数接收两个整数参数，返回它们的最大公约数。
2. 编写一个函数，用于判断一个整数是否为素数。素数是只能被1和自身整除的大于1的自然数。函数接收一个整数参数，返回一个布尔值，表示该整数是否为素数。
3. 编写一个函数，用于计算一个整数序列中所有素数的和。函数接收一个整数序列作为参数，返回该序列中所有素数的和。
4. 编写一个函数，用于判断一个整数序列是否包含连续的素数。连续素数是指序列中相邻的两个素数。函数接收一个整数序列作为参数，返回一个布尔值，表示该序列是否包含连续的素数。
5. 编写一个函数，用于找出一个整数序列中连续素数的最大长度。函数接收一个整数序列作为参数，返回该序列中连续素数的最大长度。
二、阅读程序题
要求：阅读以下程序，回答问题。
```python
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**) + 1):
if n % i == 0:
return False
return True
def prime_sum(nums):
sum = 0
for num in nums:
if is_prime(num):
sum += num
return sum
def max_consecutive_prime_length(nums):
max_length = 0
current_length = 0
for i in range(len(nums) - 1):
if is_prime(nums[i]) and is_prime(nums[i + 1]):
current_length += 1
else:
max_length = max(max_length, current_length)
current_length = 0
max_length = max(max_length, current_length)
return max_length
nums = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print("Sum of primes:", prime_sum(nums))
print("Max consecutive prime length:", max_consecutive_prime_length(nums))
```
1. 程序中的`is_prime`函数是如何判断一个整数是否为素数的？
2. 程序中的`prime_sum`函数是如何计算一个整数序列中所有素数的和的？
3. 程序中的`max_consecutive_prime_length`函数是如何找出一个整数序列中连续素数的最大长度的？
4. 程序执行后，输出结果是什么？
5. 如果将`nums`数组中的元素全部改为偶数，程序输出结果会发生变化吗？为什么？
三、算法分析题
要求：分析以下算法的时间复杂度和空间复杂度。
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
```
1. 算法的时间复杂度是多少？
2. 算法的空间复杂度是多少？
四、编程题
要求：编写一个Python程序，实现以下功能：
1. 编写一个函数，用于判断一个字符串是否为回文。回文是指从前往后和从后往前读都一样的字符串。函数接收一个字符串参数，返回一个布尔值，表示该字符串是否为回文。
2. 编写一个函数，用于计算一个字符串中所有字符的频率。函数接收一个字符串参数，返回一个字典，字典的键为字符，值为该字符在字符串中出现的次数。
3. 编写一个函数，用于将一个字符串中的所有空格替换为下划线。函数接收一个字符串参数，返回替换后的字符串。
4. 编写一个函数，用于找到字符串中第一个重复的字符。如果字符串中没有重复的字符，则返回`None`。函数接收一个字符串参数，返回重复字符的值。
5. 编写一个函数，用于将一个字符串中的单词首字母大写。函数接收一个字符串参数，返回首字母大写的字符串。
五、阅读程序题
要求：阅读以下程序，回答问题。
```python
def is_palindrome(s):
return s == s[::-1]
def character_frequency(s):
freq = {}
for char in s:
if char in freq:
freq[char] += 1
else:
freq[char] = 1
return freq
def replace_spaces(s):
return (" ", "_")
def find_first_repeated_char(s):
seen = set()
for char in s:
if char in seen:
return char
(char)
return None
def capitalize_words(s):
return " ".join(() for word in ())
text = "A man a plan a canal Panama"
print("Is palindrome:", is_palindrome(text))
print("Character frequency:", character_frequency(text))
print("Replace spaces:", replace_spaces(text))
print("First repeated char:", find_first_repeated_char(text))
print("Capitalize words:", capitalize_words(text))
```
1. 程序中的`is_palindrome`函数是如何判断一个字符串是否为回文的？
2. 程序中的`character_frequency`函数是如何计算一个字符串中所有字符的频率的？
3. 程序中的`replace_spaces`函数是如何将一个字符串中的所有空格替换为下划线的？
4. 程序中的`find_first_repeated_char`函数是如何找到字符串中第一个重复的字符的？
5. 程序中的`capitalize_words`函数是如何将一个字符串中的单词首字母大写的？
六、算法设计题
要求：设计一个算法，实现以下功能：
1. 编写一个函数，用于找出一个整数数组中的所有重复元素。函数接收一个整数数组作为参数，返回一个包含所有重复元素的列表。
2. 编写一个函数，用于对整数数组进行排序。要求使用归并排序算法实现。
3. 编写一个函数，用于判断一个整数数组是否为有序数组。函数接收一个整数数组作为参数，返回一个布尔值，表示该数组是否有序。
4. 编写一个函数，用于计算两个整数数组的最长公共子序列的长度。函数接收两个整数数组作为参数，返回最长公共子序列的长度。
5. 编写一个函数，用于找出一个整数数组中的所有缺失元素。函数接收一个整数数组作为参数，返回一个包含所有缺失元素的列表。
本次试卷答案如下：
一、编程题
1. 最大公约数（GCD）可以通过辗转相除法（也称欧几里得算法）来计算。以下是一个实现该算法的函数：
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
```
2. 判断素数的函数可以通过尝试从2到`n-1`的所有整数去除`n`，如果没有一个能整除`n`，则`n`是素数。以下是实现该功能的函数：
```python
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**) + 1):
if n % i == 0:
return False
return True
```
3. 计算素数和的函数可以通过遍历序列中的每个数，使用`is_prime`函数检查它是否为素数，如果是，则累加到总和中。以下是实现该功能的函数：
```python
def prime_sum(nums):
return sum(num for num in nums if is_prime(num))
```
4. 判断连续素数的函数可以通过遍历序列，检查每个元素及其后续元素是否都是素数。以下是实现该功能的函数：
```python
def has_consecutive_primes(nums):
for i in range(len(nums) - 1):
if is_prime(nums[i]) and is_prime(nums[i + 1]):
return True
return False
```
5. 找出连续素数最大长度的函数可以通过维护一个当前连续素数长度和最大长度的变量，遍历序列时更新这些变量。以下是实现该功能的函数：
```python
def max_consecutive_prime_length(nums):
max_length = 0
current_length = 0
for num in nums:
if is_prime(num):
current_length += 1
max_length = max(max_length, current_length)
else:
current_length = 0
return max_length
```
二、阅读程序题
1. `is_prime`函数通过从2开始循环到`n`的平方根，检查是否有任何数能够整除`n`。如果没有，则`n`是素数。
2. `prime_sum`函数通过遍历`nums`列表，使用列表推导式和`is_prime`函数检查每个数是否为素数，然后将所有素数累加。
3. `max_consecutive_prime_length`函数通过遍历`nums`列表，使用一个循环来检查连续的素数对，并更新当前连续素数长度和最大长度的变量。
4. 程序执行后，输出结果为：
```
Sum of primes: 440
Max consecutive prime length: 5
```
5. 如果将`nums`数组中的元素全部改为偶数，程序输出结果会发生变化，因为所有偶数都不是素数，所以素数和将会是0，连续素数的长度也将是0。
三、算法分析题
1. 算法的时间复杂度是O(n^2)，因为它包含两个嵌套循环，外层循环执行n次，内层循环在最坏的情况下执行n次。
2. 算法的空间复杂度是O(1)，因为它不需要额外的存储空间，除了输入数组`arr`之外。
四、编程题
1. 判断回文的函数可以通过比较字符串的前半部分和反转的后半部分是否相同来实现。以下是实现该功能的函数：
```python
def is_palindrome(s):
return s == s[::-1]
```
2. 计算字符频率的函数可以通过遍历字符串中的每个字符，并使用字典来记录每个字符的出现次数来实现。以下是实现该功能的函数：
```python
def character_frequency(s):
freq = {}
for char in s:
freq[char] = (char, 0) + 1
return freq
```
3. 替换空格的函数可以使用字符串的`replace`方法来实现。以下是实现该功能的函数：
```python
def replace_spaces(s):
return (" ", "_")
```
4. 找到第一个重复字符的函数可以使用一个集合来记录已经见过的字符，遍历字符串时检查每个字符是否已经在集合中。以下是实现该功能的函数：
```python
def find_first_repeated_char(s):
seen = set()
for char in s:
if char in seen:
return char
(char)
return None
```
5. 首字母大写的函数可以通过将字符串分割成单词，然后将每个单词的首字母转换为大写，最后将它们重新连接起来。以下是实现该功能的函数：
```python
def capitalize_words(s):
return " ".join(() for word in ())
```