第五章 数据结构与算法 单元测试 2022-2023学年浙教版（2019）高中信息技术选修1

浙教版（2019）选修1《第五章 数据结构与算法》2022年单元测试卷 一、填空题 1．数组d中存储某班级50位同学的语文和数学成绩，偶数位（第0位，第2位……）存储对应该同学的语文成绩，奇数位（第1位，第3位……）存储数学成绩。该数组已经按照两科总成绩升序排序。依据二分查找思想，设计一个在数组d中查找总成绩key的程序，如果查找成功输出语文成绩在数组中的位置。 实现该功能的python程序段如下，请在划线部分填上合适的语句或表达式。 key＝int（input（“请输入成绩“）） i，j，flag＝0，99，True while i＜＝j and flag： m＝（i+j）//2 if ①　 　 m＝m﹣1 sum＝②　 　 if key＝sum： flag＝False elif ③　 　 i＝m+2 else： j＝m﹣2 if i＞j： print（“没有找到！“） else： print（“总分符合要求的语文成绩位置为：“，str（m）） 2．某二分查找算法的python程序段如下： import random a＝[4，7，9，15，24，32，37，54，75，90] key＝random.randint（0，31）*3+3 s＝0；i＝0；j＝9 while i＜＝j： m＝（i+j）//2 if key＝＝a[m]： break if key＞a[m]： i＝m+1；s＝3*s+2 else： j＝m﹣1；s＝3*s 执行该程序段后，s的值可能有 　 　。（请写全面） 3．某二分查找算法的python程序段如下： import random a＝[4，7，9，15，24，32，37，54，75，90] key＝random.randint（0，31）*3+3 s＝0；i＝0；j＝9 while i＜＝j： m＝（i+j）//2 if key＞a[m]： i＝m+1；s＝3*s+2 else： j＝m﹣1；s＝3*s 执行该程序段后，s的值可能有 　 　。（请写全面） 4．某二分查找算法的python程序段如下： import random d＝[1，3，4，5，7，8，11，13，15，18] key＝random.randint（1，10） if key＞5： key＝key+5 i＝0；j＝9；n＝0 while i＜＝j： m＝（i+j）//2 if key＜d[m]： j＝m﹣1；n＝n﹣1 elif key＞d[m]： i＝m+1；n＝n+1 else： break 执行该程序段后，变量n的值可能有 　 　。（请写全面） 5．某二分查找算法的python程序段如下： import random d＝[1，3，4，5，7，8，11，13，15，18] key＝random.randint（1，10） if key＞5： key＝key+5 i＝0；j＝9；n＝0 while i＜＝j： m＝（i+j）//2 if key＜d[m]： j＝m﹣1；n＝n﹣1 else： i＝m+1；n＝n+1 执行该程序段后，变量n的值可能有：　 　。（请写全面） 浙教版（2019）选修1《第五章 数据结构与算法》2022年单元测试卷（1） 参考答案与试题解析 一、填空题 1．数组d中存储某班级50位同学的语文和数学成绩，偶数位（第0位，第2位……）存储对应该同学的语文成绩，奇数位（第1位，第3位……）存储数学成绩。该数组已经按照两科总成绩升序排序。依据二分查找思想，设计一个在数组d中查找总成绩key的程序，如果查找成功输出语文成绩在数组中的位置。 实现该功能的python程序段如下，请在划线部分填上合适的语句或表达式。 key＝int（input（“请输入成绩“）） i，j，flag＝0，99，True while i＜＝j and flag： m＝（i+j）//2 if ①　m%2＝＝1　 m＝m﹣1 sum＝②　d[m]+d[m+1]　 if key＝sum： flag＝False elif ③　key＞sum　 i＝m+2 else： j＝m﹣2 if i＞j： print（“没有找到！“） else：