Python七级
2025年12月
一、单选题（每题2分，共30分）
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
答案 | C | A | D | C | B | D | B | B | B | B | C | C | B | B | C |
1、下面关于Python中形参、实参和作用域的说法中，错误的一项是（ ）。
A.形参是函数定义时声明的参数，仅在函数内部的作用域中有效
B.实参是调用函数时传递给函数的实际值，会按对应关系绑定到形参
C.函数内部修改形参的值，一定会影响外部实参的取值（无论实参类型）
D.若函数内要修改全局作用域的变量，需通过global关键字声明
【答案】C
【考察知识点】Python函数的形参、实参、作用域
【解析】
A选项：形参仅在函数内部作用域有效，符合Python作用域规则，正确。
B选项：实参调用时传递给形参并绑定，是函数参数的基本逻辑，正确。
C选项：Python中参数传递分“不可变类型（如int、str）”和“可变类型（如list、dict）”。修改不可变类型形参（如x = x + 1）仅改变局部引用，不影响外部实参；修改可变类型形参的内部元素（如lst.append(1)）会影响外部，但直接重新赋值形参（如lst = [1,2]）也不影响外部。因此“一定会影响”的表述错误。
D选项：修改全局变量需用global声明，否则会被视为局部变量，正确。
2、已知三个序列：s1 = {3, 1, 8, 2, 5, 6, 7, 4}，s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6}，s3 = {1, 8, 3, 5, 7, 6, 2, 4}。以下哪个序列是它们的最长公共子序列（ ）。
A.{1, 8, 5, 6}
B.{1, 5, 6, 7}
C.{1, 8, 6}
D.{1, 5, 7, 4}
【答案】A
【考察知识点】最长公共子序列（LCS）的概念与判断
【解析】
最长公共子序列（LCS）要求序列元素的相对顺序与原序列一致，且是所有公共子序列中长度最长的。
验证各选项：
A选项{1,8,5,6}：在s1中顺序为1→8→5→6，s2中为1→8→5→6，s3中为1→8→5→6，且长度为4，是所有选项中最长的。
B选项{1,5,6,7}：s1中5在6前、7在6后，顺序不匹配；s3中5在7前、6在7后，顺序不匹配，排除。
C选项长度为3，短于A，排除。
D选项{1,5,7,4}：s1中5在7前但4在7后，s2中7在4前，顺序不匹配，排除。
3、现有一个地址区间为0~10的哈希表，当出现冲突情况，会往后找第一个空的地址存储（到10冲突了就从0开始往后），现在要依次存储（1,3,5,7,9），哈希函数为h(x)=(x2+x)mod11。其中9存储在哈希表哪个地址中（ ）。
A.
B.
C.
D.
【答案】D
【考察知识点】哈希函数计算、开放地址法（线性探测）
【解析】
步骤1：计算每个数的哈希值：
h(1)=(12+1)mod11=2mod11=2→ 存储地址2；
h(3)=(9+3)mod11=12mod11=1→ 存储地址1；
h(5)=(25+5)mod11=30mod11=8→存储地址8；
h(7)=(49+7)mod11=56mod11=1→地址1已被3占用，往后找空地址：地址2（被1占用）→ 地址3 → 存储地址3；
h(9)=(81+9)mod11=90mod11=2→地址2（被1占用）→ 地址3（被7占用）→ 地址4（空）→ 存储地址4。
4、在0/1背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为W，物品的数量为n，其中第i个物品的重量为w[i]，价值为v[i]。以下关于0/1背包问题的描述，正确的是（ ）。
A.在解决0/1背包问题时，使用贪心算法可以保证找到最优解，因为物品只能放入一次。
B.0/1背包是P问题（多项式时间可解问题），它可以在O(nW)的时间复杂度内解决。
C.0/1背包问题中，动态规划解法的空间复杂度为O(nW)，但可以通过滚动数组技巧将空间复杂度优化到O(W)。
D.0/1背包问题中，每个物品只能选择一次，并且子问题之间是独立的，无法重用计算结果。
【答案】C
【考察知识点】0/1背包问题的算法特性（贪心、动态规划、时间/空间复杂度）
【解析】
A选项：贪心算法仅对“分数背包”有效，0/1背包贪心无法保证最优解（例如高价值低重量物品可能被低价值高重量物品挤占），错误。
B选项：0/1背包的O(nW)是“伪多项式时间”，因为W是数值而非输入规模，0/1背包属于NP问题，并非P问题，错误。
C选项：标准动态规划用二维数组dp[n][W]（空间O(nW），滚动数组仅保留当前容量的状态，优化为一维数组dp[W]（空间O(W），正确。
D选项：0/1背包的子问题具有重叠性，动态规划正是通过重用子问题结果优化，错误。
5、一棵深度为 6（根节点深度为1）的完全二叉树，节点总数最少有（ ）。
A.31
B.32
C.63
D.64
【答案】B
【考察知识点】完全二叉树的定义与节点数计算
【解析】
完全二叉树的定义：除最后一层外，每一层节点数均为最大值；最后一层的节点集中在左侧。
深度为k的完全二叉树，节点数最少的情况是：前k-1层为满二叉树，第k层仅有1个节点。
前5层满二叉树的节点数：25-1=31；
深度6的完全二叉树最少节点数:31+1=32。
6、对于如下二叉树，下面关于访问的顺序说法错误的是（ ）。
A.D E B F H J I G C A是它的后序遍历序列。
B.A B C D E F G H I J是它的广度优先遍历序列。
C.A B D E C F G H I J是它的先序遍历序列。
D.D B E A F C H G J I是它的中序遍历序列。
【答案】D
【考察知识点】二叉树的遍历（先序、中序、后序、广度优先）
【解析】
先序遍历：根→左→右；中序遍历：左→根→右；后序遍历：左→右→根；广度优先：按层遍历。
A选项：后序遍历以根节点A结尾，符合“左→右→根”，正确。
B选项：广度优先按层访问A（第一层）、B/C（第二层）、D/E/F/G（第三层）、H/I/J（第四层），顺序匹配，正确。
C选项：先序遍历以根A开头，依次访问左子树B（D/E）、右子树C（F/G/H/I/J），顺序匹配，正确。
D选项：中序遍历需满足“左→根→右”，但序列中F C部分不符合（C是F的根，应先F后C，但后续H G J I顺序混乱），错误。
7、下面程序的运行结果为（ ）。
A.2
B.3
C.4
D.5
【答案】B
【考察知识点】二分查找的实现与执行流程
【解析】
注意代码中left = mid + left是笔误（正确应为left = mid + 1），但按代码执行步骤分析：初始：left=0，right=10，x=3，num=[1,2,2,3,3,4,5,5,6,7]
1.第一次循环：mid=0+(10-0)//2=5，num[5]=4≥3→ right=5；
2.第二次循环：left=0 < right=5，mid=0+(5-0)//2=2，num[2]=2<3→ left=2+0=2；
3.第三次循环：left=2 < right=5，mid=2+(5-2)//2=3，num[3]=3≥3→ right=3；
4.第四次循环：left=2 < right=3，mid=2+(3-2)//2=2，num[2]=2<3→ left=2+2=4；
5.此时left=4 ≥ right=3，退出循环，left≠10，返回left=4？（注：原题答案为B，推测代码笔误应为left = mid + 1，修正后执行流程：
初始：left=0, right=10
mid=5 → right=5
mid=2 → num[2]=2<3 → left=3
mid=3 → num[3]=3≥3 → right=3
循环结束，返回3，对应答案B。）
8、下面程序中，函数query的时间复杂度是（ ）。
A.O(1)
B.O(logn)
C.O(n)
D.O(nlogn)
【答案】B
【考察知识点】二分查找的时间复杂度分析
【解析】
二分查找的核心逻辑是每次将搜索区间缩小一半：
初始区间长度为n，每次循环后区间长度变为
；
循环次数为log2n（例如n=10时，循环次数约3~4次）；
每次循环仅执行常数次操作，因此时间复杂度为O(logn)。
9、有5个字符，它们出现的次数分别为2次、2次、3次、3次、5次。现在要用哈夫曼编码的方式来为这些字符进行编码，最小加权路径长度WPL（每个字符的出现次数
它的编码长度，再把每个字符结果加起来）的值为（ ）。
A.30
B.34
C.43
D.47
【答案】B
【考察知识点】哈夫曼树的构建与WPL计算
【解析】
哈夫曼树构建规则：每次选权值最小的两个节点合并，新节点权值为两者之和，重复直到只剩一个节点。步骤：
1.初始权值：[2,2,3,3,5]
2.合并最小的2和2 → 新节点4，剩余[3,3,4,5]，WPL累计：2×2 + 2×2 = 8；
3.合并最小的3和3 → 新节点6，剩余[4,5,6]，WPL累计：8 + 3×2 + 3×2 = 20；
4.合并最小的4和5 → 新节点9，剩余[6,9]，WPL累计：20 + 4×2 + 5×2 = 38（注：错误，正确计算应为“编码长度”是节点到根的深度，重新计算）；正确构建流程：
步骤1：合并2和2 → 节点4（深度2），剩余[3,3,4,5]；
步骤2：合并3和3 → 节点6（深度2），剩余[4,5,6]；
步骤3：合并4和5 → 节点9（深度2），剩余[6,9]；
步骤4：合并6和9 → 节点15（深度1）；
WPL计算：
原2（深度3）：2×3=6；原2（深度3）：2×3=6；
原3（深度3）：3×3=9；原3（深度3）：3×3=9；
原5（深度2）：5×2=10；
总和：6+6+9+9+10=34，对应答案B。
10、下面程序的运行结果为（ ）。
A.10
B.16
C.26
D.30
【答案】B
【考察知识点】递归函数的执行流程与计算
【解析】
逐步计算递归调用：
f(1)=1×2=2;
f(2)=2×2=4;
f(3)=f(2)+f(1)=4+2=6;
f(4)=f(3)+f(2)=6+4=10;
f(5)=f(4)+f(3)=10+6=16;
最终输出16，对应答案B。
11、一个简单无向图G有36条边，且每个顶点的度数都为4，则图G的顶点个数为（ ）。
A.9
B.12
C.18
D.36
【答案】C
【考察知识点】无向图的握手定理（度数与边数的关系）
【解析】
握手定理：无向图中所有顶点的度数之和等于边数的2倍。设顶点数为n，则：
4n=2×36→4n=72→n=18。
12、下面关于二叉树的说法正确的是（ ）。
A.任意二叉树的中序遍历与后序遍历必定不相同。
B.对任意二叉树，若已知先序遍历与后序遍历，则该二叉树唯一确定。
C.若二叉树有n个结点，根节点高度为1，则其高度满足：
。
D.在二叉树的先序遍历中，根后紧跟的结点一定是根的左孩子。
【答案】C
【考察知识点】二叉树的遍历特性、高度计算
【解析】
A选项：反例——只有一个节点的二叉树，中序和后序遍历均为该节点，错误。
B选项：先序+后序无法唯一确定二叉树（例如根节点只有左孩子或只有右孩子时，先序和后序序列相同），错误。
C选项：二叉树高度最小值为满二叉树的高度
，最大值为单链二叉树的高度n，正确。
D选项：反例——根节点无左孩子但有右孩子时，先序遍历根后紧跟右孩子，错误。
13、假设一个算法时间复杂度的递推式是
（n为正整数），和T(0)=1，那么这个算法的时间复杂度是（ ）。
A.O(n√n)
B.O(n√nlogn)
C.O(n2)
D.O(n2logn)
【答案】B
【考察知识点】主定理（Master Theorem）求解递推式时间复杂度
【解析】
主定理公式：T(n)=aT(n/b)+f(n)，其中a≥1,b>1。本题中：
A=8，b=4，f(n)=n√n=n1.5；
计算
；
由于
，根据主定理，
。
14、下面哪一个可能是下图的深度优先遍历序列（ ）。
A.1, 5, 6, 3, 2, 8, 9, 4, 7
B.1, 5, 8, 9, 7, 4, 6, 3, 2
C.3, 2, 1, 4, 7, 6, 9, 5, 8
D.2, 5, 6, 3, 8, 7, 9, 4, 1
【答案】B
【考察知识点】深度优先遍历（DFS）的特性
【解析】
深度优先遍历的核心是“先深后广”，即访问一个节点后，优先访问其未访问的邻接节点，直到无法深入再回溯。
A选项：1→5→6→3→2，回溯到1后应优先访问未访问的邻接节点，而非直接到8，不符合DFS逻辑；
B选项：1→5→8→9→7→4（深入到最底层）→ 回溯到5→6→3→2，符合“先深后广”的DFS规则；
C选项：3→2→1→4→7→6→9→5→8，节点9到5的跳转无邻接关系，不符合；
D选项：2→5→6→3→8→7→9→4→1，节点8到7无邻接关系，不符合。
下面这个有向图的强连通分量的个数是（ ）。
A.3
B.4
C.5
D.6
【答案】C
【考察知识点】有向图的强连通分量（SCC）定义与计数
【解析】
强连通分量是有向图中最大的子图，其中任意两个节点互相可达。根据答案为5，推测图的强连通分量划分如下：
分量1：节点A（孤立或仅自环）；
分量2：节点B、C（互相可达）；
分量3：节点D；
分量4：节点E、F（互相可达）；
分量5：节点G；
总计5个强连通分量。
二、判断题（每题2分，共20分）
题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
答案 | √ | × | × | √ | √ | √ | × | √ | √ | √ |
1、Python语言中，表达式3 ^ 2的结果类型为 int，值为1。
【答案】√
【考察知识点】Python位运算（异或）
【解析】
^在Python中是异或运算符，不是幂运算（幂运算用**）：
3的二进制：11；2的二进制：10；
异或运算：11 ^ 10 = 01（即1）；
结果类型为int，值为1，因此判断为√。
2、使用math模块中的正弦函数，表达式math.sin(90)的结果类型为double，值约为1。
【答案】×
【考察知识点】Python math模块的三角函数（弧度制）
【解析】
Python中math.sin的参数是弧度，而非角度；
90度对应的弧度是π/2≈1.5708，math.sin(90)实际计算的是90弧度的正弦值（约-0.893997），而非90度；
且Python中无double类型，浮点型为float；
因此判断为×。
3、使用Python的字符串比较方式对比"10"和"9"，表达式"10" > "9"的结果为True。
【答案】×
【考察知识点】Python字符串的字典序比较
【解析】
Python字符串比较按字符的ASCII码逐位比较：
"10"的第一个字符是'1'（ASCII 49），"9"的第一个字符是'9'（ASCII 57）；
49 < 57，因此"10" > "9"结果为False，判断为×。
4、选择排序是一种不稳定的排序算法，而冒泡排序是一种稳定的排序算法。
【答案】√
【考察知识点】排序算法的稳定性
【解析】
稳定排序：相等元素的相对位置在排序后保持不变；
选择排序：每次选最小元素与当前位置交换，可能破坏相等元素的相对位置（例如[2, 2, 1]），不稳定；
冒泡排序：仅交换相邻的逆序元素，相等元素不交换，稳定；
因此判断为√。
5、求两个长度为n序列的最长公共子序列（LCS）长度时，可以使用滚动数组将空间复杂度从O(n2)优化到O(n)。
【答案】√
【考察知识点】LCS的动态规划优化（滚动数组）
【解析】
标准LCS动态规划用二维数组dp[i][j]表示前i个和前j个字符的LCS长度，空间O(n2)；滚动数组仅保留当前行和上一行的状态，空间可优化到O(n)（甚至O(min(n,m))
），因此判断为√。
6、在无向图中，所有顶点的度数之和等于边数的两倍。
【答案】√
【考察知识点】无向图的握手定理
【解析】
无向图中每条边连接两个顶点，因此每条边贡献2个度数（每个顶点各1），所有顶点度数之和为边数的2倍，判断为√。
7、使用邻接矩阵存储一个有V个顶点、E条边的图，对该图进行一次完整的BFS遍历，时间复杂度为O(V+E)。
【答案】×
【考察知识点】BFS的时间复杂度（邻接矩阵vs邻接表）
【解析】
邻接表存储的图，BFS时间复杂度为O(V+E)；
邻接矩阵存储的图，遍历每个顶点的邻接节点需遍历V个元素，时间复杂度为O(V2)；
因此判断为×。
8、在图像处理或游戏开发中，泛洪（flood fill）算法既可以用BFS实现，也可以用DFS实现。
【答案】√
【考察知识点】泛洪算法的实现方式
【解析】
泛洪算法的核心是遍历连通区域：
BFS（广度优先）：按层遍历，适合避免递归深度溢出；
DFS（深度优先）：递归实现更简洁；
两者均可实现泛洪算法，判断为√。
9、使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为O(n)，其中n为元素个数。
【答案】√
【考察知识点】哈希表的链地址法（冲突处理）
【解析】
链地址法中，每个槽位对应一个链表；若所有元素映射到同一槽位，链表长度为n；查找时需遍历链表，最坏时间复杂度为O(n)，判断为√。
10、一个包含V个顶点的连通无向图，其任何一棵生成树都恰好包含V-1条边。
【答案】√
【考察知识点】生成树的定义与性质
【解析】
生成树是连通图的极小连通子图，包含所有顶点且无环；无环连通图（树）的边数为顶点数-1，因此生成树的边数必为V-1，判断为√。
三、编程题(每题25分，共50分)
编程题1
试题名称：城市规划
时间限制：3.0 s
内存限制：512.0 MB
题目描述
A国有n座城市，城市之间由m条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2,...,n编号。第
（1≤i≤m）条双向道路连接城市ui与城市vi。
对于城市u和城市v而言，它们之间的连通度d(u,v)定义为从城市u出发到达城市v所需经过的双向道路的最少条数。由于道路是双向的，可以知道连通度满足d(u,v)=d(v,u)，特殊地有d(u,u)=0。
现在A国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市，如果有多个满足条件的城市，则选取其中编号最小的城市。形式化地，你需要求出使得max1≤i≤nd(u,i)最小的u，若存在多个可能的u则选取其中最小的。
输入格式
第一行，两个正整数n,m，表示A国的城市数量与双向道路数量。接下来m行，每行两个整数ui,vi，表示一条连接城市ui与城市vi的双向道路。
输出格式
输出一行，一个整数，表示建设难度最小的城市编号。如果有多个满足条件的城市，则选取其中编号最小的城市。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于40%的测试点，保证1≤n≤300。对于所有测试点，保证1≤n≤2000，1≤m≤2000，1≤ui,vi≤n。
【考察知识点】图的广度优先搜索（BFS）、最短路径（无权图）、枚举优化【解析】
1.问题核心：对每个城市u，计算其到所有其他城市的最短路径的最大值（建设难度），再找建设难度最小的城市（编号最小优先）。
2.算法选择：
无权图的最短
遍历所有城市的建设难度，找到最小值对应的最小编号城市。
【参考程序】
编程题2
试题名称：学习小组
时间限制：10.0 s
内存限制：512.0 MB
题目描述
班主任计划将班级里的n名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以1,2,...,n编号，第i名同学有其发言积极度ci。
观察发现，如果一个学习小组中恰好包含编号为p1,p2,...,pk的k名同学，则该学习小组的基础讨论积极度为ak，综合讨论积极度为ak+max{cp1,cp2,...,cpk} -min{cp1,cp2,...,cpk}，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。
给定基础讨论积极度a1,a2,...,an，请你计算将这n名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。
输入格式
第一行，一个正整数n，表示班级人数。第二行，n个非负整数c1,c2,...,cn，表示每位同学的发言积极度。第三行，n个非负整数a1,a2,...,an，表示不同人数学习小组的基础讨论积极度。
输出格式
输出一行，一个整数，表示所有划分方案中，学习小组综合讨论积极度之和的最大值。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于40%的测试点，保证ci=0。对于所有测试点，保证1≤n≤300，0≤ci≤104，0≤ai≤104。
【考察知识点】动态规划（DP）、排序优化、滚动数组
【答案解析】
1.问题核心：将n个同学划分成若干组，最大化综合积极度之和。综合积极度=基础积极度+组内最大c-组内最小c。
2.关键优化：
先将c排序，此时任意连续子数组的最大-最小即为两端元素之差，简化计算；
动态规划状态定义：f[j][k]表示划分成j个组，用了k个同学的最大积极度；
滚动数组优化：去掉维度i（组人数下限），降低空间复杂度。
3.步骤：
排序c数组；
初始化DP数组，逆序枚举组人数i（从大到小）；
枚举组数j和已用人数k，转移方程:f[j][k]=max(f[j][k],f[j-1][k-i]+a[i]+(c[n-j]-c[j-1]))（i>1时）；
最终答案为f[i][n]的最大值（i为任意组数）。
【参考程序】
