跳转至

难题练习 — 程序填空题

练习说明

  • 共 8 道程序填空题，难度高于模拟考试
  • 每题包含 2~3 个填空，标记为 #**********begin********** 和 #**********end**********
  • 建议每题用时 5~8 分钟

📝 程序填空题

第1题：冒泡排序优化

题目： 对列表进行冒泡排序，并添加提前退出优化（如果某轮没有发生交换，说明已有序）。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def bubble_sort(lst):
    n = len(lst)
    for i in range(n - 1):
        #**********begin1**********
        _______
        #**********end1**********
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                #**********begin2**********
                _______
                #**********end2**********
        #**********begin3**********
        _______
        #**********end3**********
    return lst

nums = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(nums))
第2题：二分查找

题目： 在已排序列表中使用二分查找算法查找目标元素，返回其索引，找不到返回-1。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def binary_search(lst, target):
    left = 0
    #**********begin1**********
    _______
    #**********end1**********
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            #**********begin2**********
            _______
            #**********end2**********
        else:
            #**********begin3**********
            _______
            #**********end3**********
    return -1

nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(nums, 7))
print(binary_search(nums, 8))
第3题：选择排序

题目： 实现选择排序算法，每轮从未排序部分选出最小元素放到已排序部分末尾。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def selection_sort(lst):
    n = len(lst)
    for i in range(n - 1):
        #**********begin1**********
        _______
        #**********end1**********
        for j in range(i + 1, n):
            #**********begin2**********
            _______
            #**********end2**********
        #**********begin3**********
        _______
        #**********end3**********
    return lst

nums = [29, 10, 14, 37, 13]
print(selection_sort(nums))
第4题：字符串去重保持顺序

题目： 去除字符串中重复的字符，保持字符首次出现的顺序。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def remove_duplicate_chars(s):
    result = ""
    #**********begin1**********
    _______
    #**********end1**********
        if ch not in result:
            #**********begin2**********
            _______
            #**********end2**********
    return result

s = "programming"
print(remove_duplicate_chars(s))  # 输出: progamin
第5题：矩阵乘法

题目： 计算两个矩阵的乘积。A是m×n矩阵，B是n×p矩阵，结果C是m×p矩阵。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def matrix_multiply(A, B):
    m = len(A)
    n = len(A[0])
    p = len(B[0])
    #**********begin1**********
    _______
    #**********end1**********
    for i in range(m):
        for j in range(p):
            #**********begin2**********
            _______
            #**********end2**********
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
print(matrix_multiply(A, B))  # 输出: [[19, 22], [43, 50]]
第6题：统计单词频率

题目： 统计一段英文中每个单词出现的次数，按频率从高到低排序输出。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def word_frequency(text):
    #**********begin1**********
    _______
    #**********end1**********
    for word in words:
        word = word.lower()
        if word in freq:
            freq[word] += 1
        else:
            freq[word] = 1
    #**********begin2**********
    _______
    #**********end2**********
    return sorted_freq

text = "the cat sat on the mat the cat ate the rat"
result = word_frequency(text)
for word, count in result:
    print(f"{word}: {count}")
第7题：递归求幂

题目： 使用递归实现快速幂运算，计算x的n次方。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def fast_pow(x, n):
    if n == 0:
        return 1
    #**********begin1**********
    _______
    #**********end1**********
    if n % 2 == 0:
        #**********begin2**********
        _______
        #**********end2**********
    else:
        #**********begin3**********
        _______
        #**********end3**********

print(fast_pow(2, 10))   # 输出: 1024
print(fast_pow(3, 5))    # 输出: 243
第8题：文件单词统计

题目： 读取文件内容，统计每个单词出现的次数，将结果写入新文件。

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def count_words(input_file, output_file):
    word_count = {}
    #**********begin1**********
    _______
    #**********end1**********
        for line in f:
            words = line.strip().split()
            for word in words:
                #**********begin2**********
                _______
                #**********end2**********

    #**********begin3**********
    _______
    #**********end3**********
        for word, count in sorted(word_count.items()):
            f_out.write(f"{word}: {count}\n")