学校 ________________ 班级 ____________ 姓名 ____________ 考场 ____________ 准考证号 ………………………… 密…………封…………线…………内…………不…………要…………答…………题…………………………上海欧华职业技术学院《算法设计及应用》2023-2024 学年第一学期期末试卷题号一二三四总分得分一、单选题（本大题共 15 个小题，每小题 1 分，共 15 分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、假设正在研究一个算法的渐近分析，当输入规模趋向无穷大时，以下哪种说法是正确的？（ ）A. 低阶项对时间复杂度的影响可以忽略B. 常数因子对时间复杂度的影响很大C. 所有项对时间复杂度的影响都相同D. 以上说法都不正确2、在设计一个算法来解决一个 NP 完全问题时，如果希望在合理的时间内找到一个较好的近似解，以下哪种策略可能是有用的？（ ）A. 启发式搜索B. 随机化算法C. 局部搜索D. 以上策略都可以3、考虑一个算法的空间复杂度，如果算法需要保存大量的中间结果，可能会导致什么情况？（ ）A. 运行速度变慢B. 占用过多内存C. 难以扩展D. 以上情况都可能发生4、在动态规划算法中，需要找到最优子结构并建立递推关系。假设要计算从一个矩阵的左上角到右下角的最短路径，其中每个单元格都有一定的代价，以下关于最优子结构的描述，哪个是正确的（ ）A. 从当前位置到右下角的最短路径只取决于当前位置右边和下边的单元格B. 从当前位置到右下角的最短路径只取决于当前位置左边和上边的单元格C. 从当前位置到右下角的最短路径取决于之前经过的所有单元格D. 以上都不对5、想象一个需要对一个有序链表进行插入操作，同时保持链表的有序性。以下哪种算法可能是最有效的？（ ）A. 从头开始遍历链表，找到合适的位置插入新节点B. 使用二分查找找到插入位置，然后插入新节点C. 在链表尾部插入新节点，然后进行排序D. 先将链表转换为数组，插入后再转换回链表第 1 页，共 5 页学校 ________________ 班级 ____________ 姓名 ____________ 考场 ____________ 准考证号 ………………………… 密…………封…………线…………内…………不…………要…………答…………题…………………………6、算法的正确性是指算法能够正确地解决给定的问题。以下关于算法正确性的说法中，错误的是：算法的正确性可以通过数学证明来保证。测试用例可以帮助验证算法的正确性，但不能...
