2023-2024学年高一上学期华东师大版(2020)必修1第三节 常用算法及其程序实现

2023-2024学年高一上学期华东师大版(2020)必修1第三节 常用算法及其程序实现 一、选择题 1．以下哪种算法思想不是用于解决优化问题的？（  ） A．分治策略 B．贪心算法 C．动态规划 D．回溯算法 2．穷举法在解决最优化问题时通常使用？（   ） A．线性规划 B．贪心算法 C．分支定界 D．A和C 3．我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何，为解决这个问题下列最适合的算法为（   ） A．折半法 B．冒泡法 C．枚举法 D．排序法 4．对于一个n*n的棋盘，使用穷举法进行八皇后问题的总数是多少？（   ） A．n! B．n^n C．2^n D．(n*n)! 5．在解析算法时，我们通常首先关注算法的（   ） A．效率 B．正确性 C．可读性 D．可扩展性 6．在非数值计算中，贪心算法通常用于求解（   ） A．最小化问题 B．最大化问题 C．确定性问题 D．非确定性问题 7．解决某问题的算法流程图如图a所示，程序代码如图b所示，两者均不完整。 图a s 1=input() s 2=input() num=0; i= 0 while  i  <=10:    a=int ( s1 [ i % len(s1) ])    b=int (s 2 [i % len(s 2) ])    if :       num+= 1    i  +=  1 print (num) 图b 若输入s1和s2的值分别为“012”，“121210”，结合流程图和程序代码，则输出的num的值为（   ） A．3 B．5 C．7 D．11 8．以下哪种算法设计方法适用于解决“最优化”问题（   ） A．分治法 B．动态规划 C．贪心算法 D．回溯法 9．计算圆周长的算法描述如下： ①输入圆半径r；  ②计算圆周长a（计算公式为a=2πr）；  ③输出结果；  ④结束。 上述算法属于（   ） A．枚举算法 B．排序算法 C．递归算法 D．解析算法 10．下列哪种搜索算法是基于链接的（   ） A．页面排名算法 B．向量空间模型算法 C．概率信息检索算法 D．以上都不是 11．解决某问题的算法流程图如图a所示，程序代码如图b所示，两者均不完整。     图a                     图b 若输入s1和s2的值分别为“012”，“121210”，结合流程图和程序代码，则输出的num的值为（   ） A．3 B．5 C．7 D．11 12．下列哪种算法不属于图论算法（   ） A．最短路径 B．最大流 C．最小生成树 D．背包问题 13．下列语句执行输出结果正确的是（    ） s=1 for i in range（2，12）：      if i%5==0：           continue      else：           s=s+i print（s） A．4 B．50 C．51 D．52 14．下列哪种算法不属于贪心策略（   ） A．最小生成树 B．背包问题 C．最长公共子序列 D．最短路径 15．动态规划算法适用于解决（   ）问题。 A．具有重叠子问题 B．具有最优子结构 C．具有递推关系 D．以上都是 二、填空题 16．动态规划算法适用于解决具有 和 的问题。 17．动态规划算法的关键在于找到状态转移方程。状态转移方程通常包括 、 和 三个部分。 18．解析法在算法实现中， 法常用于求解线性方程组。 19．在解析递归算法时，我们通常需要关注算法的 。 三、操作题 20．【算法探究】以下是一个用于计算求解1+1/2+1/3+1/4+1/5+......+1/99的算法流程图，请你分析此流程图算法后，修改编号①~⑤的内容，完成求解1*1/2*2/3*3/4*4/5*......*99/100的算法。 ① ② ③ ④ ⑤ 四、简答题 21．描述分治法在解决排序问题中的应用及其特点。 22．请简述解析算法时需要注意的几个关键点。 23．论述分治策略的优缺点。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 2．D 3．C 4．A 5．B 6．AB 7．B 8．B 9．D 10．A 11．B 12．D 13．C 14．C 15．D 16． 重叠子问题 最优子结构 17． 状态定义 状态转移关系 边界条件 18．高斯消元法 19．递归深度 20． s=1 n=1 n<=99 s=s*n/(n+1) n=n+1 21．分治法在解决排序问题中得到了广泛应用，如快速排序和归并排序等算法都是基于分治思想设计的。分治法的特点是将大问题分解为若干个较小的子问题来解决，然后将子问题的解合并为原问题的解。这种方法的优点是能够充分利用计算机的并行处理能力，从而实现高效的排序。 22．解析算法时需要注意的关键点包括：算法的正确性、效率、可读性、可扩展性和稳定性等。 23．分治策略的优点是可以将大规模问题分解成若干个较小规模的相同问题，降低问题的复杂度；缺点是需要解决子问题的合并问题，可能导致额外的计算开销。分治策略适用于解决具有重叠子问题和最优子结构的问题，如归并排序、快速排序等。在使用分治策略时，需要考虑子问题的划分和合并策略。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$