第4单元 计算与问题解决 2024-2025学年高中信息技术教科版(2019) 必修1

第4单元 计算与问题解决 一、选择题 1．下面关于深度优先搜索的说法，哪个是正确的（   ） A．它总是能找到问题的最短解 B．它适用于所有类型的问题 C．它使用递归来实现 D．它从图的任意节点开始搜索 2．下列不能通过计算机算法得到唯一解或最优解的是（  ） A．列举1-100之间所有偶数 B．楼宇电梯会合理停靠在相应的楼层 C．铁路网络订票系统会按照一定的设置，高效服务用户 D．求出一个无理数所有位数之和 3．深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。请问，深度优先搜索使用什么数据结构来存储待访问的节点（   ） A．栈 B．队列 C．数组 D．链表 4．在求一元二次方程实数根的算法中，当方程不存在实数根，也要输出“方程无实数根”，这一要求主要体现了算法特征中的（   ） A．有穷性 B．确定性 C．有1个或多个输出 D．有0个或多个输出 5．某算法的部分流程图如下图所示，执行这部分流程后，变量X和Y的值分别为（   ） A．3 和-8 B．4 和 6 C．-5 和 10 D．10 和 -5 6．某算法的部分流程图如图所示，以下说法正确的是（    ） A．该流程执行后，变量k的值是-1 B．该流程执行后，变量a的值是16 C．该流程用于计算并输出1+8-16的值 D．该流程共循环了2次，“a<32?”共执行了3次 7．某算法的部分流程图如图所示。执行这部分流程，分别输入4、13、5、17、51、17则输出值依次为（    ） A．112，120 B．112，110 C．112，120，8 D．112，120，7 8．某算法的部分流程图如右图所示，执行这部分流程，输出的s值为（   ） A．28 B．162 C．280 D．945 9．某算法的流程图如下图所示，关于该算法下列说法正确的是（   ） 图1 A．执行这部分流程后，变量i的值为7 B．k的值为1*2*3*4*5*6*7的结果 C．该流程图是双重循环结构 D．将“i≤x/2”改成“i<x”，输出k的值发生变化 10．算法的特征不包括（     ） A．输入项 B．确切性 C．输出项 D．唯一性 11．为提高学校师生就餐结账的速度，某学校食堂开通了刷脸支付方式。其支付算法中验证刷卡支付对象是否正确的伪代码如下图所示，则以下流程图符号与伪代码表达内容匹配的是（   ） A． B． C． D． 12．以下关于算法基本结构嵌套的叙述中，正确的有(   ) ① 分支结构可以嵌套分支结构   ② 分支结构可以嵌套循环结构 ③ 循环结构可以嵌套分支结构    ④ 循环结构可以嵌套循环结构 A．4个 B．3个 C．2个 D．1个 13．流程图是算法的一种图形化表示方法，其中菱形框表示（  ） A．开始/结束（圆角矩形） B．运算/处理（矩形） C．输入/输出（平行四边形） D．判断 14．下列关于算法的描述正确的是（  ） A．算法只能用流程图来表示 B．一个算法，当没有输入时，也没有输出 C．一个算法的执行步骤可以是无限的 D．一个算法可以没有输入 15．状态空间中的节点代表什么？（   ） A．问题的解 B．问题的状态 C．问题的约束条件 D．问题的目标 16．下列选项中，关于算法的描述正确的是（   ） A．算法就是一种高级程序设计语言 B．算法必须在有限步骤内实现 C．算法可以有零个或多个输入，但只能有一个输出 D．算法只能用自然语言描述 二、填空题 17．下图所示的算法流程图： 执行情况如下： 当输入a、b的值分别为3、8时，输出结果为5 当输入a、b的值分别为11、7时，输出结果为4 问题一：下列流程图填入虚线框中，符合条件的是 。 A                            B                                        C 问题二：依据问题一所选流程图，当输入a、b的值分别为9、6时，输出结果为 。 18．函数执行完成后，由 将表达式的值返回给调用者，结束函数。 19．在α-β剪枝算法中，α值表示当前节点的父节点的 可能得分。 20．在算法中， 是用来衡量算法在执行过程中所需的存储资源。 21．以下算法的输出结果是： 。 三、判断题 22．顺序控制结构的程序是自上而下依次执行，必须有一个输入和一个输出。( ) 23．算法在程序设计中可有可无，它不会影响程序设计的效率。( ) 24．算法是解决“做什么”和“怎么做”的具体步骤的描述，一个算法必须具有有穷性、确定性、有一个或多个输入、有一个或多个输出、可行性这五个基本特征。 四、操作题 25．现代生活半径的扩大和生活节奏加快使出行成本不断增长。滴滴快车应运而生，其以灵活快速的响应和经济实惠的价格为大众提供更高效、更经济、更舒适的出行服务，给人们生活带来了美好的变化。小C是滴滴快车忠实的粉丝，经常出行就提前预约，乘坐滴滴快车。小C就在思考这个滴滴快车是怎么计费的？可否用所学的Python语言也编写一个计费程序。于是小C开展了有关这个项目活动的探究。根据实际情况，回答问题。 （一）收集、分析数据，运用数理思维建模 登录滴滴出行官网，得到了如下信息，即“滴滴快车（普通型）计价规则”： 滴滴快车（普通型）计价规则 时段 起步价 里程费 时长费 普通时段 8.00元 1.35元/公里 0.20元/分钟 00：00-06：30 8.50元 2.40元/公里 0.50元/分钟 06：30-09：00 8.50元 1.50元/公里 0.45元/分钟 21：00-23：00 8.50元 1.50元/公里 0.40元/分钟 23：00-00：00 8.50元 2.40元/公里 0.50元/分钟 注意： 1.起步价包含里程3.3公里，包含时长9分钟，里程费、时长费合计不足基础费时，直接按照基础费计费。 2.实时计价是基于订单服务内容（里程、时长、时段），按各种费用项定价标准计算订单价格的计价方式，实际费用由两部分里程费与时长费累加而得。 小C同学19：33从“南内环恒地大厦停车场－入口”到“坞城新纪元大酒店（长风店）”乘坐滴滴快车（普通车型），里程4.1公里，时长约21分钟，按照表中的计费规则，小C同学此次出行应该支付的车费是：车费=8+（4.1-3.3）×1.35+（21-9）×0.2=9.68。 （1）小C登录滴滴出行官网搜索并下载“计价规则”，所采用的数字化工具： A．数字化可视化表达工具    B．信息加工工具 C．三维设计工具    D．信息检索工具 （2）假设Tot1表示时长费，Tot2表示里程费，S表示实际里程，T表示实际时长，Cost表示应支付费用。运用数学解析式归纳出计费公式为： 如果时长超过9分钟，则Tot1= 。如果里程小于等于3.3公里则Tot2= ，否则Tot2= 。应支付费用：Cost= 。 （二）运用算法描述方法将问题解决步骤化 小C明晰了滴滴快车车费的计算方法之后，设计求解滴滴快车普通时段车费的算法，并用自然语言和流程图的方式表述出来。 （3）自然语言描述： 第一步： 第二步：计算时长费Totl 第三步：计算里程费Tot2 第四步： 第五步： （4）流程图描述：（如图）流程图中，表示计算与赋值的是 ，表示算法流向的是 。 A．    B．    C．     D．      E. （5）算法描述中，用到了三种基本控制结构，分别是 、 和 。如图示中的流程图使用的控制结构是 和 。（选填：顺序结构、选择结构、循环结构、树型结构） （6）一个算法必须有 或多个数据输入。有 或多个数据输出。（选填：零个/一个） （三）编写、调试、运行程序，验证算法并解决问题 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查算法。 深度优先搜索通常使用递归或栈来实现。它并不总是能找到问题的最短解，而是根据搜索路径的不同可能找到不同的解。此外，深度优先搜索可以从指定的起始节点开始搜索，而不是从任意节点。故正确答案为：选项C。 2．D 【详解】本题考查计算机算法。求出一个无理数所有位数之和：这是一个不能通过计算机算法得到唯一解的问题，因为无理数的位数是无穷无尽的，不可预知。计算机无法一一列举所有位数。故答案为：D。 3．A 【详解】本题考查算法。 深度优先搜索使用栈这种数据结构来存储待访问的节点，以便实现后进先出的遍历顺序。故正确答案为：选项A。 4．C 【详解】本题考查的是算法特征。算法的特征：有穷性、确定性、数据输入、数据输出、可行性。数据输出：一个算法有一个或多个数据输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的。故本题应选C。 5．C 【详解】本题主要考查算法流程图的执行。X=10，Y=5，X=X+Y=15，Y=X-Y=15-5=10，X=Y-X=10-15=-5，不满足X>Y，程序结束，此时变量X和Y的值分别为-5和10，故本题选C选项。 6．D 【详解】本题主要考查算法流程图的执行。s=1，k=1，a=8，第一次循环，满足a<32，执行s=s+k*a=1+1*8=9，k=1-k=0，a=2*a=16；第二次循环，满足a<32，执行s=s+k*a=9+0*16=9，k=1-k=1，a=2*a=32；第三次循环，不满足a<32，输出s=9。故该流程执行后，变量k的值是1；该流程执行后，变量a的值是32；k的值是0和1交替变化，该流程不是用于计算并输出1+8-16的值；该流程共循环了2次，“a<32?”共执行了3次，故本题选D选项。 7．D 【详解】本题主要考查算法流程图知识点。i=1，s=0，第一遍循环，m=4，m=4 mod 3=1，s=s*10+m=1，i=i+2=3；第二遍循环，m=13，m=13 mod 3=1，s=s*10+m=11，i=i+2=5；第三遍循环，m=5，m=5 mod 3=2，s=s*10+m=112，输出s=112，i=i-1=4，s=s\100=1；第四遍循环，m=17，m=17 mod 3=2，s=s*10+m=12，i=i+2=6；第五遍循环，m=51，m=51 mod 3=0，s=s*10+m=120，输出s=120，i=i-1=5，s=s\100=1；第六遍循环，m=17，m=17 mod 3=2，s=s*10+m=12，i=i+2=7，循环结束，输出i=7，故执行这部分流程，分别输入4、13、5、17、51、17则输出值依次为112，120，7，故本题选D选项。 8．C 【详解】本题考查的是流程图识读。阅读流程图可知计算的是s=1*4*7*10=280，故选C。 9．D 【详解】本题考查算法表示相关内容。A选项，在执行完流程后，i的值变为8，A错误；B选项，k的值为1*2*7，结果为14，B错误；C选项，通过观察流程图，可知该流程图为单循环结构，C错误；D选项，将将“i≤x/2”改成“i”后，输出k的值变为2，D正确。故本题答案为D选项。 10．D 【详解】本题考查算法相关内容。算法具有如下特征：（1）有穷性：算法必须能在执行有限个步骤之后终止；（2）确切性：算法的每一步骤必须有确切的定义；（3）输入项：一个算法有0个或多个输入；（4）输出项：一个算法有一个或多个输出，没有输出的算法是毫无意义的；（5）可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。故本题答案是D选项。 11．B 【详解】本题主要考查算法流程图。该伪代码是一个条件分支结构。菱形是条件判断框，平行四边形是数据输入/输出框，圆角矩形是开始/结束框，矩形是数据处理框，故本题选B选项。 12．A 【详解】本题主要考查算法基本结构。关于算法基本结构嵌套，① 分支结构可以嵌套分支结构 ② 分支结构可以嵌套循环结构③ 循环结构可以嵌套分支结构 ④ 循环结构可以嵌套循环结构，故本题选A选项。 13．D 【详解】本题考查的是流程图。流程图中菱形是条件判断框，平行四边形是数据输入/输出框，圆角矩形是开始/结束框，矩形是数据处理框。故选D。 14．D 【详解】本题考查算法相关内容。算法的描述方式有：自然语言、流程图、N-S图、伪代码和程序设计语言。一个算法可以没有输入，但是必须有输出。算法必须在有限步骤之内完成。ABC选项说法错误，D选项正确。故本题答案是D选项。 15．B 【详解】本题考查算法。 在状态空间中，每个节点代表问题的一个状态，状态是问题的一个具体实例或情况。故正确答案为：选项B。 16．B 【详解】本题主要考查算法的描述。算法不是程序设计语言，算法必须在有限步骤内实现，算法至少具有一个或多个输出，算法可以用自然语言、伪代码等描述，故本题选B选项。 17． C 3 【详解】本题考查的是流程图识读。（1）依据执行情况，可知输出的c值是大的数减小的数，故列流程图填入虚线框中，符合条件的是C选项。（2）依据问题一所选流程图，当输入a、b的值分别为9、6时，输出结果为：9-6=3。 18．return语句 【详解】本题考查的是Python函数。函数执行完成后，由return语句将表达式的值返回给调用者，结束函数。 19．最小 【详解】本题考查启发式搜索算法。在α-β剪枝算法中，α值表示当前节点的父节点的可能得分的最小值。α值用于剪枝过程中的最大化节点，表示当前已知的最大下界。如果当前节点的得分低于α值，则不需要进一步搜索该节点的子节点，因为它不会影响最终的决策。 20．空间复杂度 【详解】本题考查算法相关内容。算法的空间复杂度是指执行这个算法所需要的内存空间，一个算法所占用的存储空间包，括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行中所需要的额外空间，其中，额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的，在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。故本题答案是：空间复杂度。 21．-2 【详解】本题主要考查算法流程图的执行。a=18，b=-2，a>b，d=b=-2，c=7，d<c，输出d的值为-2。 22．错误 【详解】本题主要考查算法控制结构。顺序控制结构的程序是自上而下依次执行，可以有0个或多个输入，但至少有一个输出，故表述错误。 23．错误 【详解】本题考查算法相关内容。算法就是用计算机求解某一问题的方法是能被机械地执行的动作或指令的有穷集合。算法是程序的灵魂，它独立于任何一种程序设计语言，一个算法可以用多种程序设计语言来实现。良好的算法设计，不仅可以提高程序的执行效率，起到事半功倍的效果，而且可以以算法设计为基础，通过寻求不同问题存在的相互联系，从计算机角度对不同问题的共性进行算法设计，实现程序编写的举一反三。算法设计是整个程序设计的核心。故本题答案是：错误。 24．错误 【详解】本题考查算法特性相关内容。算法的特性有：有穷性、确定性、有零个或多个输入、有一个或多个输出。一个算法可以没有输入。故本题答案是：错误。 25． D Tot1=（T-9）×0.2 Tot2=8 Tot2=8+（S-3.3）×1.35 Cost=Totl+Tot2 第一步：输入实际里程S和实际时长T 第四步：计算应支付费用Cost 第五步：输出应支付费用Cost E A 顺序结构 选择结构 循环结构 顺序结构 选择结构 零个 一个 略 【详解】本题主要考查算法及程序设计。①小C登录滴滴出行官网搜索并下载“计价规则”，所采用的数字化工具：信息检索工具，故选D选项。②如果时长超过9分钟，则Tot1=（T-9）×0.2。③如果里程小于等于3.3公里则Tot2=8。④里程大于3.3公里，则Tot2=8+（S-3.3）×1.35。⑤应支付费用：Cost=Totl+Tot2。⑥第一步：输入实际里程S和实际时长T。⑦第四步：计算应支付费用Cost。⑧第五步：输出应支付费用Cost。⑨流程图中，表示计算与赋值的是矩形框，即选项E。⑩表示算法流向的是箭头，即选项A。算法描述中，用到了三种基本控制结构，分别是⑪顺序结构⑫选择结构⑬循环结构。如图示中的流程图使用的控制结构是⑭顺序结构⑮选择结构。⑯一个算法必须有零个或多个数据输入。⑰有一个或多个数据输出。⑱略 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$