2023-2024学年高一上学期浙教版(2019)必修一3.3 简单算法及其程序实现

2023-2024学年高一上学期浙教版(2019)必修一3.3 简单算法及其程序实现 一、选择题 1．关于python语句功能描述正确的（   ） A．ord(chr(x)+26)    #若字符变量x是大写字母即变成小写字母 B．str(x)+str(y)    #求两数之和 C．"abcd"[2:4]    #运行结果为"bcd" D．2**3*2/2 % 5    #结果3 2．有如下程序段： a = 3; b = 4; c = 5 a = a * b a = a % c c = c // b print(a + c) 运行之后，输出结果为（   ） A．2 1 B．3 C．3 1 D．4 3．经过中国国家登山队的测量，2020年12月8日，中尼两国共同宣布了珠穆朗玛峰的最新高度为海拔8848．86米。现有一张白纸的厚度大约是0．08毫米，对折一次，厚度变0．16毫米，再对折一次，厚度变为0．32毫米，……，每对折一次，其厚度均变为对折前的两倍，假设这张纸足够大，可以对折任意次，那么这张纸至少对折多少次后，其厚度将超过珠穆朗玛峰的高度？以下是求解以上问题的程序片段，请你补全代码： 请选择适当的代码填入程序①处。（    ） A．while B．for C．output D．input 4．程序中的“顺序结构”指的是什么？（   ） A．按照代码的先后顺序逐行执行 B．根据条件选择执行不同的代码块 C．重复执行某段代码直到满足特定条件 D．递归调用自身直到达到终止条件 5．将一个难以直接解决的大问题，分解成一些规模较小的同类问题，以便各个击破的算法是（  ） A．递推 B．递归 C．穷举 D．分治 6．动态规划算法适用于解决（   ）问题。 A．具有重叠子问题 B．具有最优子结构 C．具有递推关系 D．以上都是 7．运行以下Python程序段，结果是（   ） A．Python B．C++ C．Welcome D．True 8．有如下Python程序段，执行该程序段后，一共输出列表a中的多少个元素（   ） a=[1,2,3,4,5,6,7] for i in range(5):     print(a[i]) A．7 B．5 C．2 D．3 9．动态规划算法通常用于解决哪一类问题？（  ） A．具有重叠子问题和最优子结构的问题 B．具有最小生成树的问题 C．具有最短路径的问题 D．以上都不是 10．以下哪个选项不是有效的循环控制语句？（   ） A．break B．continue C．return D．goto 11．有如下 Python 段程序： a=[6,12,9,20,8,11,4] for j in  range(1,len(a)) if   a[j] < a[j-1]: a[j]=a[j]+a[j-1];a[j-1]=a[j]-a[j-1];a[j]=a[j]-a[j-1] 执行该段程序后，列表 a 的值是（      ） A．[4,6,12,9,20,8,11] B．[4,6,8,12,9,20,11] C．[6,9,12,8,11,4,20] D．[6,9,8,11,4,12,20] 12．某算法的流程图如图所示，下列说法不正确的是（   ） A．执行该流程后，i的值是 15 B．执行该流程后，输出 s的结果是 33 C．执行该流程后，“i←i+2”共执行 3次 D．交换“s←s+i”和“i←i+2”的位置不会影响输出结果 13．桶排序并非常规的排序算法，它实际上是一种分治思想的实践。桶排序的过程可以分为4步：1-根据数据的特征将数据分为若干的桶，给每个桶规定可以存储的值的范围；2-将原数列的数据放入各个桶中；3-对每个桶都进行排序；4-按照桶的顺序将桶内数据重新链接。有如下Python程序段： def bucket_sort(a):     bucket=[]     b=[]     bucketnum=(max(a)-min(a))//len(a)+1    #根据数据特征确定桶数量     for i in range(bucketnum):    #建桶         ①     for x in a:        #入桶         num=(x-min(a))//len(a)         ②     for i in range(bucketnum):         bucket[i].sort()        #详见“注意”         b+=bucket[i]     return b a=[77,7,26,14,11,21,60,51,30,78] print(bucket_sort(a)) #运行结果 [[7,11,14],[21,26],[30],[],[51],[60],[],[77,78]] 注意：桶排序更多适用与数据值域较大但分别较均匀的情况，其本质也只是用于分段，对于桶内数据一般不会再使用桶排序递归，而是采用更高效的排序算法。故在桶内排序时也直接使用了sort()方法加以区分和说明。 根据题意，划线处①、②两个空分别填入的代码为（   ） A．①bucket.append([]) ②bucket[num].append([]) B．①bucket.append(i)  ②bucket[num].append(x) C．①bucket.append(i)  ②bucket[num].append([]) D．①bucket.append([])  ②bucket[num].append(x) 14．在算法执行过程中，用于立即终止当前循环并跳出循环体的语句是（   ） A．break B．continue C．return D．exit 15．有如下Python程序段： import random defselect（s，k）：     for i in range（k）：        j=i+1        if j< len（s）：            s=s[：j]+s[j+1：]        else：            s=s[：len（s）-1]     connect（i，s，k） def connect（i，s，k）：     list1=''     if i< k-1：         listl=listl+s+'-'     else：         list1=listl+s     print（listl，end=''） s="hello" k=random.randint（1，4） select（s，k） 执行该程序段后，输出结果可能是（    ） A．hllo- B．hllo-hll-hl C．hllo-hlo D．hllo-hlo-hl-1 二、填空题 16．在解析递归算法时，我们通常需要关注算法的 。 17．小申设计了一个算法，能够根据输入的三条线路的距离，找出最短距离，请将流程图空白处填写完整：① ② ③ 18．动态规划通常用于解决具有 和 特点的问题。 19．动态规划通常用于解决具有 性质的问题。 三、操作题 20．点击开始作答按钮，打开文件，删除序号[1]、[2]、[3]并填写正确的代码实现题目所述功能，调试完成后点击“保存并返回”按钮。 阅读以下材料内容，完成程序的补充。 正整数的阶乘是所有小于及等于该数的正整数的积。即: n!=1*2*3*...*n， 举例说明: 3的阶乘就是1*2*3，要求编写 程序，计算正整数n的阶乘。 输入样例: 请输入一个正整数: 5 输出样例: pd= 120 注:程序修改时，请把序号删除，不能删除注释语句。 #请删除原题里的序号“1]、[2] 、[3]”，填写正确代码。 四、简答题 21．简述贪心算法和动态规划的主要区别。 22．请简述什么是编程中的循环，并说明循环的基本类型。 23．请简述动态规划算法的基本思想。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 2．B 3．A 4．A 5．D 6．D 7．B 8．B 9．A 10．D 11．C 12．D 13．D 14．A 15．C 16．递归深度 17． a<b a<c b<c 18． 重叠子问题 最优子结构 19．重叠子问题 20．【1】n 【2】pd 【3】print 21．贪心算法在每个决策点都做出当前最优的选择，而不考虑全局最优；动态规划则通过综合考虑所有可能的子问题解来找到全局最优解。 22．循环是编程中重复执行一段代码直到满足特定条件的控制结构。循环的基本类型包括：for循环（迭代已知次数的元素序列）、while循环（只要条件为真就迭代）和do-while循环（至少执行一次，然后只要条件为真就继续迭代）。 23．动态规划算法的基本思想是将原问题分解为子问题，从最小的子问题开始求解，将每个子问题的解存储起来，以便后续使用，从而避免重复计算。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$