资源简介

(共39张PPT)
第五章　数据结构与算法
验收卷(四)　数据结构与算法
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.下列有关数据结构的叙述中正确的是(　　)
A
解析　栈是限定在一端进行插入和删除的线性表，而另一端封闭，队列是限定仅在一端进行插入，在另一端进行删除的线性表，因此B选项错误；数据结构与算法有着密不可分的关系，数据结构的不同选择会影响算法的运行效率，因此，在设计算法需要考虑选用何种数据结构，故C选项错误；链式存储结构不一定优于线性表的线性存储结构，例如查找时，链式存储结构需要从头开始找，而线性表可直接通过下标找到，因此D选项错误；算法的设计和选择总是依赖于数据结构，它们两者是相辅相成的，因此，答案为A。
A.算法的设计和选择总是依赖于数据结构
B.栈是限定仅在一端进行插入，在另一端进行删除的线性表
C.数据结构与算法是相互独立的，设计算法时不用考虑选用何种数据结构
D.链式存储结构优于线性表的线性存储结构
D
2.递归算法的执行过程，一般来说，可先后分为递推阶段和(　　)
解析　本题主要考查的是递归算法的执行过程。递归算法的执行过程分为递推和回归两个阶段，因此，答案为D。
A.合并阶段 B.返回阶段
C.回溯阶段 D.回归阶段
A
3.定义如下函数：
def fn(n，num1，num2):
　if n＝＝1：
　 return num1
　return fn(n－1，num2，num1＋num2)
下列说法正确的是(　　)
A.该算法的时间复杂度是O(n)
B.fn(10，1，2)的效果等价于1＋2＋3…＋10
C.fn(5，1，1)的结果是22
D.fn(1，1，1)与fn(1，1，2)的返回结果不同
解析　A选项函数将调用n次，因此时间复杂度是O(n)。B选项该函数的功能是实现斐波那契数列效果；C选项，fn(5，1，1)的结果是 5；D选项fn(1，1，1)与fn(1，1，2)的返回结果相同，都是 1。
4.下列有两段程序：
D
关于两个程序段的说法，正确的是(　　)
A.程序段 1 和程序段 2 的输出结果不相同
B.程序段 1 和程序段 2 都采用了递归算法
C.若问题规模为 n，程序段 2 的时间复杂度为O(n2)
D.程序段 1 中，①和②两方框处中的数字 1 同时修改为 0，输出结果不变
解析　本题考查递归和迭代、时间复杂度的计算阅读程序段 1，可知为递归算法实现 10＋9＋…＋1 的和；阅读程序段 2，可知为迭代算法实现 1＋2＋…＋10。因此两段程序输出结果相同，A 错误；程序段 2 为迭代算法，B 错误；程序段 2 中只有一层循环，时间复杂度为O(n)，C 错误；修改程序段 1 代码，仅仅多递归一层函数，但是返回值＋0 并不会影响输出结果，D 正确。
D
5.下列四段程序中，时间复杂度为O(n)的是(　　)
解析　选项A、B中程序段的时间复杂度均为O(n2)，因此，AB选项错误；选项C中程序段的时间复杂度均为O(log2n)，因此C选项错误；选项D中程序段，外循环的时间复杂度均为O(log2n)，内循环的执行次数为20＋21＋…＋2k(k＝log2n)，根据等比数据求和公式，其和为n－1，即时间复杂度为O(n)，因此答案为D。
6.有如下Python 程序段：
def fx(x)：
if x>3：
ans＝x*fx(x－1)
elif x>1：
ans＝x＋fx(x－1)
else：
ans＝2
return ans
n＝int(input(″please input n：″))
print(fx(n))
C
程序执行时，输入n的值为6，则输出的结果为(　　)
A.127 B.720 C.840 D.1440
解析　本题主要考查的是递归算法。n＝6，ans＝6*5*4*f(3)，而f(3)＝3＋2＋f(1)，已知f(1)＝2，因此ans＝840，故答案为C。
D
A.10，5，32，6，7，9，17，24，4
B.10，5，32，6，7，9，4，17，24
C.10，5，32，4，6，7，9，17，24
D.4，10，5，32，17，9，24，6，7
解析　冒泡的方向可以从前往后排序，后面的数据先有序；也可以从后往前排序，前面的数据先有序。第一遍排序后的结果把最小的数排到了最前面，因此可以推断是升序排列。
A
8.采用冒泡排序算法对某数据序列进行排序，第一轮排序后的结果是“2，8，6，3，5，7，9”，则第二轮排序需要交换的次数为(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
解析　本题考查冒泡排序算法的相关知识。由第一轮数据“2，8，6，3，5，7，9”可知，采用冒泡排序对数据进行升序排序，但有两种可能，一种是从后往前的冒泡升序，则第二轮排序后的数据为“2，3，8，6，5，7，9”，交换2次，另一种是从前往后的冒泡升序，则第二轮排序后的数据为“2，6，3，5，7，8，9”，交换4次。
9.有如下Python 程序段：
a＝[3，1，9，6]
#将以空格隔开的输入数以列表的形式存储
m＝len(a)
while m！＝1：
　　for i in range(m－1):
　if a[i]>a[i＋1]：
　　　　a[i]，a[i＋1]＝a[i＋1]，a[i]
　　　m－＝1
print(a)
A
执行程序后，输出的结果为(　　)
A.[1，3，6，9] B.[9，6，3，1]
C.[1，6，3，9] D.[9，3，6，1]
解析　本题考查冒泡排序的算法思想。从前往后冒泡实现升序排列，共排了m－1趟。
C
10.互不相等的 10 个列表元素 s[0]、s[1]、s[2]……s[9]，有如下Python 程序段：
n＝10
for i in range( 5 ) ：
　for j in range(1，n－i):
　 if s[j]>s[j－1]：
　　 　s[j]，s[j－1]＝s[j－1]，s[j]
该程序段实现的是(　　)
A.s[0]到 s[5]的降序排列 B.s[0]到 s[5]的升序排列
C.s[5]到 s[9]的降序排列 D.s[5]到 s[9]的升序排列
解析　本题考查冒泡排序算法思想。分析冒泡排序内循环的代码，是从左(前)向右(后)冒泡、降序。外循环只进行了5次，所以只有最后5个数(s[5]到 s[9])是有序的。
11.某二分查找算法的Python程序段如下：
i，j＝0，24
n＝0
while i<＝j：
　　　m＝(i＋j＋1)∥2
　　　n＝n＋1
　　　if key＝＝a[m]：
　　　　　break
　　　if key>a[m]：
　　　　　i＝m＋1
　　　else：
　　　　　j＝m－1
print(n)
A
解析　n的值为查找次数，7查找次数为2，其余查找次数是4。
12.有如下Python程序段：
import random
a＝[1，3，3，8，8，10，10，14，16，17]
key＝random.randint(0，9)*2
ans＝－1; f＝0
L＝0；R＝9
while L<＝R：
　　m＝(L＋R＋1)∥2
　　if a[m]＝＝key ：
　ans＝m
　break
　　if a[m]>key：
D
　R＝m－1
　f－＝1
　　else：
　L＝m＋1
　 f＋＝1
运行该程序段后，关于f和ans的结果，下列说法正确的是(　　)
A.f可能的最小值为－3 B.f的值可能为－1
C.ans的值可能为1 D.ans的值不可能为3
解析　查找一个0－18之间的随机偶数key，画出相应的二叉树。A选项查找0，向左查找4次，f的值为－4。B选项向右查找1次，找到的数为3，不是偶数。C选项a[1]的值为3，不是偶数。D选项ans的值若为3，a[3]的值为8，而找到的第1个8的索引位置是4。
二、非选择题(本题共3小题，共26分)
13.(9分)根据申请人的QA和QB值，从m个申请人中挑选2人组队参加某挑战赛。条件一是2人的QA值都必须大于指定参数h；条件二是2人的QA值之差(较大值减较小值)小于h。在满足上述两个条件的所有2人组合中，挑选QB值之和最大的一个组合。(QA、QB和h的值均为正整数)
编写Python程序，实现上述挑选功能。运行程序，输入参数h后，按QA值降序显示满足条件一的申请人信息，最后显示组队结果。程序运行界面如下图所示。
请输入h的值：60
符合条件一的申请人
编号　QA值　QB值
11 200 25
10 139 18
17 132 10
14 99 21
9 83 20
1 67 34
8 66 24
组队结果：1号，8号
实现上述功能的Python程序如下，请回答下列问题：
m＝20　 #m表示申请人个数
id＝qa＝qb＝[0]*m
n＝0　 #变量n存储满足条件一的申请人个数
s＝″″
#读取全部申请人的编号、QA和QB值，分别存入数组id、qa和qb，代码略
h＝int(input(″请输入h的值：″))
n＝m
for i in range(1，m)：
for j in range(m－1，i－1，－1)：
print(″编号″，″ QA值″，″QB值″)
for i in range(n)：
print(″%3d%3d%3d″%(id[i]，qa[i]，qb[i]))
maxx＝0
s＝″没有满足条件的组合″
#在满足条件的组合中，寻找QB值之和最大的组合，若有并列，只保留第一个
for i in range(0，n－1)：
j＝i＋1
while ②________________：
if qb[i]＋qb[j]>maxx：
　　　　s＝″组队结果：″＋str(id[i])＋″号，″＋str(id[j])＋″号″
　　　　③________________
j＋＝1
print(s)
(1)代码中加框处代码有错误请改正。
加框处的代码应修改为_________________________________________________；
(2)请在划线①②③处填入合适的代码。
划线①处应填入的代码是____________________________________________；
划线②处应填入的代码是_______________________________________________；
划线③处应填入的代码是_____________________________________________。
答案　(1)qa[j]>h and qa[j]>qa[j－1] 或qa[j]>qa[j－1]
(2)①n＝i－1　②j<＝n－1 and abs(qa[i]－qa[j])解析　本题主要考查的是冒泡排序算法及其综合应用。(1)程序首先使用冒泡排序算法找出所有符合条件一的申请人，根据程序运行窗口可知数据是按QA值降序排序的，并将满足条件一的人数记录在变量n中。排序方式有两种，只将符合条件一的申请人进行降序排序，即加框处语句修改为qa[j]>h and qa[j]>qa[j－1]，将所有申请人进行降序排序，即加框处语句修改为qa[j]>qa[j－1]；(2)如果申请人不满足条件一，则排序可以提前结束，满足条件人数为i
－1人，因此，程序划线①处代码为n＝i－1；划线②处所在的循环语句的功能是使用枚举所有满足条件一、条件二的申请人进行组队，记录组队人QB值之和为最大的2个人，因此，②处代码为j<＝n－1 and abs(qa[i]－qa[j])14.(7分)已知某水果店有 n 种水果，编号依次为 0～n－1，每种水果存量若干份。现为每位顾客分配两份不同种类且该顾客喜欢的水果，为合理分配，每位顾客分别勾选自己喜欢的水果编号，每人至少勾选两种(包含两种)以上水果。编写程序，根据水果存量数据以及顾客勾选数据，输出水果是否能分配完成。请回答下列问题：
(1)若n为5，分配前每种水果存量数据如图a所示，顾客勾选数据如图b所示，则最后水果________(选填：能/不能)完成分配。
(2)实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。
def sort_f(x，y)：
　 for i in range(y)：
　for j in range(①______)：
　　 　　if num[fruit[j]]　　　 　fruit[j]，fruit[j＋1]＝fruit[j＋1]，fruit[j]
　　　return fruit
#读取每种水果的存量数据，存入字典 num，例如：num＝{0：5，1：4，2：7，3：1，4：3，5：6}，代码略。
#读取每位顾客的勾选数据，存入列表 tch，例如：tch＝[[0，3，5]，[1，2]]，代码略。
fruit＝[0，1，2，3，4，5] #存储水果编号
fruit＝sort_f(0，len(fruit)－1)
②__________
for k in range(len(tch)):
　 c＝[]；p＝0
　while ③______________：
if fruit[p] in tch[k]:
　　　　num[fruit[p]]－＝1
　　　　c.append(p)
p＋＝1
　if len(c)<2：
flag＝False　　
break
　fruit＝sort_f(c[0]，2)
if flag：
　　　print(″水果能分配完成！″)
else：
　　print(″水果不能分配完成！″)
答案　(1)能　(2)①x，len(fruit)－i－1　②flag＝True　③len(c)<2 and num[fruit[p]]>0
解析　(1)由于每位顾客分配两种水果，因此只勾选两种水果的顾客只分配给他们勾选的水果，剩余勾选2种以上的顾客，从剩余水果中选取还有存量的水果分配给他们。“1，2”“1，3”分配好后，剩余“5，2，6，0，3”，此时还有“0，3，4”“1，3，4”需从中选取分配，3号水果存量为0，不作考虑，0，1，4号水果存量均大于等于2，足够分配。因此能完成分配。
(2)分配时，按照水果存量情况降序排列，将列表fruit中水果编号按水果存量降序排列。枚举每位顾客勾选数据，从列表fruit中从左往右，依次选取水果存量大的检测是否为该顾客喜欢水果，如果是则将此水果分配给该顾客，一共选取两种水果，用列表c存储分配的水果编号的索引。该顾客分配完成后，利用列表c存储的第一种水果编号索引作为再排序的起始位置，因为0～c[0]－1范围内的水果存量未变，只要对列表c中两个水果存量进行再排序，fruit按照最新存量进行降序排列，排2次即可。如果在分配过程中该顾客喜欢的水果无法分配两份，则分配失败。
15.(10分)将十进制数 n(264≥n≥3)转化为 k(k≥2)进制数，若所有数位全为 1，则称 k 是 n 的一个好进制数。例如，十进制数 31 可以转化为(11)30 和(11111)2，因此 30 和 2 均是 31 的好进制数，其中 2 为 31 的最小好进制数。请回答下列问题：
(1)十进制数“21”的最小好进制数 k 是________。
(2)小明编写程序，找出 n 的最小好进制数 k，请在划线处填入合适的代码。
n＝int(input(″输入一个十进制数： ″))
def check(k，m): #计算 m 位全为 1 的 k 进制的十进制值，如(111)2 的十进制值为 7
　　　ans＝0
　　　for i in range(m)：
　　　　①____________
　　　return ans
ans＝n
for length in range(2，65)：
　②____________
　 j＝n－1
　 while i<＝j：
　 mid＝(i＋j)∥2
　tmp＝check(mid，length)
　if tmp＝＝n：
　　　if ans>mid：
　　　　ans＝mid
　　　　break
　elif ③____________：
　　 　i＝mid＋1
　else：
　　　j＝mid－1
print(n，″的最小好进制数是″，ans)
答案　(1)4　(2)①ans＝ans*k＋1 或 ans＝ans＋k**i 或 ans＝ans＋k**(m－i－1)　②i＝2　③tmp解析　本题考查进制转换、对分查找等相关知识。(1)21＝16＋4＋1＝(111)4，故最小的好进制数是4。①空实现 k 进制、m 位 1 转换为十进制数的过程，此处可采用累乘相加，即 ans＝ans*k＋1或 ans＝ans＋k**(m－i－1)等。②处填 i 的初始值。已知函数 check 的第 1 个参数为进制，第 2 个参数为 1 的位数，结合 tmp＝check(mid，length)这一句，可知 mid 为进制。本题的进制最小值为 2，进制最大值为 n－1(例如 64＝63＋1＝(11)63)。③外循环枚举所有可能的位数，循环中采用对分法测试结果，即先找到进制的中位数 mid，计算 mid 进制下，length 位个 1 转换为十进制数的 tmp。若 tmp＝＝n，则保留 mid 的最小值，进入下一轮大循环，查找更长的位数(位数越长意味着进制越小)。若 tmp(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.下列有关数据结构的叙述中正确的是(　　)
A.算法的设计和选择总是依赖于数据结构
B.栈是限定仅在一端进行插入，在另一端进行删除的线性表
C.数据结构与算法是相互独立的，设计算法时不用考虑选用何种数据结构
D.链式存储结构优于线性表的线性存储结构
2.递归算法的执行过程，一般来说，可先后分为递推阶段和(　　)
A.合并阶段 B.返回阶段
C.回溯阶段 D.回归阶段
3.定义如下函数：
def fn(n，num1，num2):
　if n＝＝1：
　 return num1
　return fn(n－1，num2，num1＋num2)
下列说法正确的是(　　)
A.该算法的时间复杂度是O(n)
B.fn(10，1，2)的效果等价于1＋2＋3…＋10
C.fn(5，1，1)的结果是22
D.fn(1，1，1)与fn(1，1，2)的返回结果不同
4.下列有两段程序：
#程序段1 def rec(n)： if ：　　#① 　　 #② else： 　　return n＋rec(n－1) print(rec(10)) #程序段2 def rec(n)： ans＝0 for i in range(1，n＋1，1)： 　　ans＝ans＋i return ans print(rec(10))
关于两个程序段的说法，正确的是(　　)
A.程序段 1 和程序段 2 的输出结果不相同
B.程序段 1 和程序段 2 都采用了递归算法
C.若问题规模为 n，程序段 2 的时间复杂度为O(n2)
D.程序段 1 中，①和②两方框处中的数字 1 同时修改为 0，输出结果不变
5.下列四段程序中，时间复杂度为O(n)的是(　　)
6.有如下Python 程序段：
def fx(x)：
if x>3：
ans＝x*fx(x－1)
elif x>1：
ans＝x＋fx(x－1)
else：
ans＝2
return ans
n＝int(input(″please input n：″))
print(fx(n))
程序执行时，输入n的值为6，则输出的结果为(　　)
A.127 B.720 C.840 D.1440
7.有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24该数组的原始顺序不可能的是(　　)
A.10，5，32，6，7，9，17，24，4
B.10，5，32，6，7，9，4，17，24
C.10，5，32，4，6，7，9，17，24
D.4，10，5，32，17，9，24，6，7
8.采用冒泡排序算法对某数据序列进行排序，第一轮排序后的结果是“2，8，6，3，5，7，9”，则第二轮排序需要交换的次数为(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
9.有如下Python 程序段：
a＝[3，1，9，6]
#将以空格隔开的输入数以列表的形式存储
m＝len(a)
while m！＝1：
　　for i in range(m－1):
　if a[i]>a[i＋1]：
　　　　a[i]，a[i＋1]＝a[i＋1]，a[i]
　　　m－＝1
print(a)
执行程序后，输出的结果为(　　)
A.[1，3，6，9] B.[9，6，3，1]
C.[1，6，3，9] D.[9，3，6，1]
10.互不相等的 10 个列表元素 s[0]、s[1]、s[2]……s[9]，有如下Python 程序段：
n＝10
for i in range( 5 ) ：
　for j in range(1，n－i):
　 if s[j]>s[j－1]：
　　 　s[j]，s[j－1]＝s[j－1]，s[j]
该程序段实现的是(　　)
A.s[0]到 s[5]的降序排列 B.s[0]到 s[5]的升序排列
C.s[5]到 s[9]的降序排列 D.s[5]到 s[9]的升序排列
11.某二分查找算法的Python程序段如下：
i，j＝0，24
n＝0
while i<＝j：
　　　m＝(i＋j＋1)∥2
　　　n＝n＋1
　　　if key＝＝a[m]：
　　　　　break
　　　if key>a[m]：
　　　　　i＝m＋1
　　　else：
　　　　　j＝m－1
print(n)
列表a中各元素值依次为1～25，若查找键key为下列选项的值，程序段执行后，输出结果与其他三项不同的是(　　)
A.7 B.12 C.19 D.22
12.有如下Python程序段：
import random
a＝[1，3，3，8，8，10，10，14，16，17]
key＝random.randint(0，9)*2
ans＝－1; f＝0
L＝0；R＝9
while L<＝R：
　　m＝(L＋R＋1)∥2
　　if a[m]＝＝key ：
　ans＝m
　break
　　if a[m]>key：
　R＝m－1
　f－＝1
　　else：
　L＝m＋1
　 f＋＝1
运行该程序段后，关于f和ans的结果，下列说法正确的是(　　)
A.f可能的最小值为－3
B.f的值可能为－1
C.ans的值可能为1
D.ans的值不可能为3
二、非选择题(本题共3小题，共26分)
13.(9分)根据申请人的QA和QB值，从m个申请人中挑选2人组队参加某挑战赛。条件一是2人的QA值都必须大于指定参数h；条件二是2人的QA值之差(较大值减较小值)小于h。在满足上述两个条件的所有2人组合中，挑选QB值之和最大的一个组合。(QA、QB和h的值均为正整数)
编写Python程序，实现上述挑选功能。运行程序，输入参数h后，按QA值降序显示满足条件一的申请人信息，最后显示组队结果。程序运行界面如下图所示。
请输入h的值：60 符合条件一的申请人 编号　QA值　QB值 11 200 25 10 139 18 17 132 10 14 99 21 9 83 20 1 67 34 8 66 24 组队结果：1号，8号
实现上述功能的Python程序如下，请回答下列问题：
m＝20　 #m表示申请人个数
id＝qa＝qb＝[0]*m
n＝0　 #变量n存储满足条件一的申请人个数
s＝″″
#读取全部申请人的编号、QA和QB值，分别存入数组id、qa和qb，代码略
h＝int(input(″请输入h的值：″))
n＝m
for i in range(1，m)：
for j in range(m－1，i－1，－1)：
　　 　if ：
　　　　　qa[j]，qa[j－1]＝qa[j－1]，qa[j]
　　　　　qb[j]，qb[j－1]＝qb[j－1]，qb[j]
　　　　　id[j]，id[j－1]＝id[j－1]，id[j]
if qa[j－1]<＝h：
　①________________
　break
print(″符合条件一的申请人″)
print(″编号″，″ QA值″，″QB值″)
for i in range(n)：
print(″%3d%3d%3d″%(id[i]，qa[i]，qb[i]))
maxx＝0
s＝″没有满足条件的组合″
#在满足条件的组合中，寻找QB值之和最大的组合，若有并列，只保留第一个
for i in range(0，n－1)：
j＝i＋1
while ②________________：
if qb[i]＋qb[j]>maxx：
　　　　s＝″组队结果：″＋str(id[i])＋″号，″＋str(id[j])＋″号″
　　　　③________________
j＋＝1
print(s)
(1)代码中加框处代码有错误请改正。
加框处的代码应修改为_________________________________________________；
(2)请在划线①②③处填入合适的代码。
划线①处应填入的代码是________________________________________________；
划线②处应填入的代码是_______________________________________________；
划线③处应填入的代码是________________________________________________。
14.(7分)已知某水果店有 n 种水果，编号依次为 0～n－1，每种水果存量若干份。现为每位顾客分配两份不同种类且该顾客喜欢的水果，为合理分配，每位顾客分别勾选自己喜欢的水果编号，每人至少勾选两种(包含两种)以上水果。编写程序，根据水果存量数据以及顾客勾选数据，输出水果是否能分配完成。请回答下列问题：
(1)若n为5，分配前每种水果存量数据如图a所示，顾客勾选数据如图b所示，则最后水果________(选填：能/不能)完成分配。
(2)实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。
def sort_f(x，y)：
　 for i in range(y)：
　for j in range(①______)：
　　 　　if num[fruit[j]]　　　 　fruit[j]，fruit[j＋1]＝fruit[j＋1]，fruit[j]
　　　return fruit
#读取每种水果的存量数据，存入字典 num，例如：num＝{0：5，1：4，2：7，3：1，4：3，5：6}，代码略。
#读取每位顾客的勾选数据，存入列表 tch，例如：tch＝[[0，3，5]，[1，2]]，代码略。
fruit＝[0，1，2，3，4，5] #存储水果编号
fruit＝sort_f(0，len(fruit)－1)
②__________
for k in range(len(tch)):
　 c＝[]；p＝0
　while ③______________：
if fruit[p] in tch[k]:
　　　　num[fruit[p]]－＝1
　　　　c.append(p)
p＋＝1
　if len(c)<2：
flag＝False　　
break
　fruit＝sort_f(c[0]，2)
if flag：
　　　print(″水果能分配完成！″)
else：
　　print(″水果不能分配完成！″)
15.(10分)将十进制数 n(264≥n≥3)转化为 k(k≥2)进制数，若所有数位全为 1，则称 k 是 n 的一个好进制数。例如，十进制数 31 可以转化为(11)30 和(11111)2，因此 30 和 2 均是 31 的好进制数，其中 2 为 31 的最小好进制数。请回答下列问题：
(1)十进制数“21”的最小好进制数 k 是________。
(2)小明编写程序，找出 n 的最小好进制数 k，请在划线处填入合适的代码。
n＝int(input(″输入一个十进制数： ″))
def check(k，m): #计算 m 位全为 1 的 k 进制的十进制值，如(111)2 的十进制值为 7
　　　ans＝0
　　　for i in range(m)：
　　　　①____________
　　　return ans
ans＝n
for length in range(2，65)：
　②____________
　 j＝n－1
　 while i<＝j：
　 mid＝(i＋j)∥2
　tmp＝check(mid，length)
　if tmp＝＝n：
　　　if ans>mid：
　　　　ans＝mid
　　　　break
　elif ③____________：
　　 　i＝mid＋1
　else：
　　　j＝mid－1
print(n，″的最小好进制数是″，ans)
验收卷(四)　数据结构与算法
1.A　[栈是限定在一端进行插入和删除的线性表，而另一端封闭，队列是限定仅在一端进行插入，在另一端进行删除的线性表，因此B选项错误；数据结构与算法有着密不可分的关系，数据结构的不同选择会影响算法的运行效率，因此，在设计算法需要考虑选用何种数据结构，故C选项错误；链式存储结构不一定优于线性表的线性存储结构，例如查找时，链式存储结构需要从头开始找，而线性表可直接通过下标找到，因此D选项错误；算法的设计和选择总是依赖于数据结构，它们两者是相辅相成的，因此，答案为A。]
2.D　[本题主要考查的是递归算法的执行过程。递归算法的执行过程分为递推和回归两个阶段，因此，答案为D。]
3.A　[A选项函数将调用n次，因此时间复杂度是O(n)。B选项该函数的功能是实现斐波那契数列效果；C选项，fn(5，1，1)的结果是 5；D选项fn(1，1，1)与fn(1，1，2)的返回结果相同，都是 1。]
4.D　[本题考查递归和迭代、时间复杂度的计算阅读程序段 1，可知为递归算法实现 10＋9＋…＋1 的和；阅读程序段 2，可知为迭代算法实现 1＋2＋…＋10。因此两段程序输出结果相同，A 错误；程序段 2 为迭代算法，B 错误；程序段 2 中只有一层循环，时间复杂度为 O(n)，C 错误；修改程序段 1 代码，仅仅多递归一层函数，但是返回值＋0 并不会影响输出结果，D 正确。]
5.D　[选项A、B中程序段的时间复杂度均为O(n2)，因此，AB选项错误；选项C中程序段的时间复杂度均为O(log2n)，因此C选项错误；选项D中程序段，外循环的时间复杂度均为O(log2n)，内循环的执行次数为20＋21＋…＋2k(k＝log2n)，根据等比数据求和公式，其和为n－1，即时间复杂度为O(n)，因此答案为D。]
6.C　[本题主要考查的是递归算法。n＝6，ans＝6*5*4*f(3)，而f(3)＝3＋2＋f(1)，已知f(1)＝2，因此ans＝840，故答案为C。]
7.D　[冒泡的方向可以从前往后排序，后面的数据先有序；也可以从后往前排序，前面的数据先有序。第一遍排序后的结果把最小的数排到了最前面，因此可以推断是升序排列。]
8.A　[本题考查冒泡排序算法的相关知识。由第一轮数据“2，8，6，3，5，7，9”可知，采用冒泡排序对数据进行升序排序，但有两种可能，一种是从后往前的冒泡升序，则第二轮排序后的数据为“2，3，8，6，5，7，9”，交换2次，另一种是从前往后的冒泡升序，则第二轮排序后的数据为“2，6，3，5，7，8，9”，交换4次。]
9.A　[本题考查冒泡排序的算法思想。从前往后冒泡实现升序排列，共排了m－1趟。]
10.C　[本题考查冒泡排序算法思想。分析冒泡排序内循环的代码，是从左(前)向右(后)冒泡、降序。外循环只进行了5次，所以只有最后5个数(s[5]到 s[9])是有序的。]
11.A　[n的值为查找次数，7查找次数为2，其余查找次数是4。]
12.D　[查找一个0－18之间的随机偶数key，画出相应的二叉树。A选项查找0，向左查找4次，f的值为－4。B选项向右查找1次，找到的数为3，不是偶数。C选项a[1]的值为3，不是偶数。D选项ans的值若为3，a[3]的值为8，而找到的第1个8的索引位置是4。]
13.(1)qa[j]>h and qa[j]>qa[j－1] 或qa[j]>qa[j－1]
(2)①n＝i－1　②j<＝n－1 and abs(qa[i]－qa[j])j<＝n－1 and qa[i]－qa[j]解析　本题主要考查的是冒泡排序算法及其综合应用。(1)程序首先使用冒泡排序算法找出所有符合条件一的申请人，根据程序运行窗口可知数据是按QA值降序排序的，并将满足条件一的人数记录在变量n中。排序方式有两种，只将符合条件一的申请人进行降序排序，即加框处语句修改为qa[j]>h and qa[j]>qa[j－1]，将所有申请人进行降序排序，即加框处语句修改为qa[j]>qa[j－1]；(2)如果申请人不满足条件一，则排序可以提前结束，满足条件人数为i－1人，因此，程序划线①处代码为n＝i－1；划线②处所在的循环语句的功能是使用枚举所有满足条件一、条件二的申请人进行组队，记录组队人QB值之和为最大的2个人，因此，②处代码为j<＝n－1 and abs(qa[i]－qa[j])14.(1)能　(2)①x，len(fruit)－i－1　②flag＝True　③len(c)<2 and num[fruit[p]]>0
解析　(1)由于每位顾客分配两种水果，因此只勾选两种水果的顾客只分配给他们勾选的水果，剩余勾选2种以上的顾客，从剩余水果中选取还有存量的水果分配给他们。“1，2”“1，3”分配好后，剩余“5，2，6，0，3”，此时还有“0，3，4”“1，3，4”需从中选取分配，3号水果存量为0，不作考虑，0，1，4号水果存量均大于等于2，足够分配。因此能完成分配。
(2)分配时，按照水果存量情况降序排列，将列表fruit中水果编号按水果存量降序排列。枚举每位顾客勾选数据，从列表fruit中从左往右，依次选取水果存量大的检测是否为该顾客喜欢水果，如果是则将此水果分配给该顾客，一共选取两种水果，用列表c存储分配的水果编号的索引。该顾客分配完成后，利用列表c存储的第一种水果编号索引作为再排序的起始位置，因为0～c[0]－1范围内的水果存量未变，只要对列表c中两个水果存量进行再排序，fruit按照最新存量进行降序排列，排2次即可。如果在分配过程中该顾客喜欢的水果无法分配两份，则分配失败。
15.(1)4　(2)①ans＝ans*k＋1 或 ans＝ans＋k**i 或 ans＝ans＋k**(m－i－1)　②i＝2　③tmp解析　本题考查进制转换、对分查找等相关知识。(1)21＝16＋4＋1＝(111)4，故最小的好进制数是4。①空实现 k 进制、m 位 1 转换为十进制数的过程，此处可采用累乘相加，即 ans＝ans*k＋1或 ans＝ans＋k**(m－i－1)等。②处填 i 的初始值。已知函数 check 的第 1 个参数为进制，第 2 个参数为 1 的位数，结合 tmp＝check(mid，length)这一句，可知 mid 为进制。本题的进制最小值为 2，进制最大值为 n－1(例如 64＝63＋1＝(11)63)。③外循环枚举所有可能的位数，循环中采用对分法测试结果，即先找到进制的中位数 mid，计算 mid 进制下，length 位个 1 转换为十进制数的 tmp。若 tmp＝＝n，则保留 mid 的最小值，进入下一轮大循环，查找更长的位数(位数越长意味着进制越小)。若 tmp

展开更多......

收起↑