山东科技大学《信息与计算科学（工程算法建模研究版）》2024-2025 学年第一学期期末试卷

班级班级学号姓名本科．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．密．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．封．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．线．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．试卷说明：1、试卷满分100分，120分钟完成试卷；2、钢笔或圆珠笔直接答在试题中（除题目有特殊规定外）；3、答卷前将密封线内的项目填写清楚。题号一二三四五总分合分人复核人满分100得分一、精心选一选（本大题总共15小题，每题2分，共30分）1.以下哪种算法不属于数值计算算法？A.牛顿迭代法B.冒泡排序法C.高斯消元法D.龙格-库塔法2.关于算法的时间复杂度，以下说法正确的是？A.时间复杂度是衡量算法执行时间的唯一标准B.时间复杂度为O(n)的算法一定比时间复杂度为O(n)的算法慢C.时间复杂度与问题规模n有关D.时间复杂度只取决于算法中的循环次数3.若要对一个有序数组进行快速查找，哪种数据结构最合适？A.栈B.队列C.哈希表D.二叉排序树4.以下哪个不是常见的建模方法？A.层次分析法B.灰色系统建模法C.最小二乘法D.神经网络建模法5.对于一个具有n个顶点的无向连通图，其最小生成树的边数为？A.nB.n-1C.n+1D.2n-16.以下哪种算法常用于求解线性规划问题？A.动态规划算法B.分支限界算法C.单纯形法D.回溯算法7.已知一个算法的时间复杂度为O(nlogn)，当n增大时，其运行时间的增长趋势是？A.线性增长B.指数增长C.对数增长D.先线性后对数增长8.关于矩阵乘法，以下说法错误的是？A.矩阵乘法满足结合律B.矩阵乘法满足交换律C.两个n阶方阵相乘的时间复杂度为O(n)D.矩阵乘法可用于线性变换9.哪种数据结构适合实现广度优先搜索算法？A.栈B.队列C.链表D.二叉树10.以下哪个是用于求解最短路径问题的算法？A.迪杰斯特拉算法B.普里姆算法C.克鲁斯卡尔算法D.弗洛伊德算法11.对于一个递归算法，其时间复杂度的分析通常采用？A.迭代法B.递归树法C.主定理法D.以上都是12.已知一个算法在处理规模为n的数据时运行时间为T(n)=2T(n/2)+n，其时间复杂度为？A.O(n)B.O(nlogn)C.O(n)D.O(logn)13.以下哪种建模语言常用于数学建模？A.PythonB.MatlabC.C++D.Java14.关于算法的空间复杂度，以下说法正确的是？A.空间复杂度是衡量算法执行过程中所需存储空间的唯一标准B.空间复杂度与时间复杂度无关C.空间复杂度只取决于算法中的变量个数D.空间复杂度也与问题规模n有关15.对于一个有向图，若要判断是否存在环，可采用以下哪种算法？A.深度优先搜索算法B.广度优先搜索算法C.拓扑排序算法D.以上都可以二、谨慎填一填（本大题总共5题，每题4分，共20分）1.常见的数值计算误差有__、__和__。2.算法的五大特性分别是__、__、__、__和__。3.对于一个n阶方阵A，若存在一个n阶方阵B，使得AB=BA=I（单位矩阵），则称A为__，B为A的__。4.图的遍历方法主要有__和__。5.线性规划问题的标准形式中，目标函数是__，约束条件是__。三、细心判一判（本大题总共6题，每题4分，共24分）1.任何算法都可以用三种基本结构（顺序结构、选择结构、循环结构）来描述。（）2.一个算法的时间复杂度为O(n)，则其最坏情况下的运行时间一定比时间复杂度为O(nlogn)的算法长。（）3.哈希表查找的平均时间复杂度为O(1)。（）4.所有的数值计算算法都能得到精确解。（）5.对于一个无向图，若其顶点度数之和为偶数，则该图一定存在欧拉回路。（）6.动态规划算法的基本思想是将问题分解为若干个相互重叠的子问题，通过求解子问题来得到原问题的解。（）四、灵活答一答（本大题总共2题，每题6分，共12分）1.简述数值计算中误差分析的重要性及常见的误差分析方法。2.请说明深度优先搜索算法的基本步骤及适用场景。五、综合用一用(14分)给定一个实际问题，要求建立数学模型并设计算法求解。假设某工厂生产A、B两种产品，已知生产A产品每件需消耗原材料甲2千克、原材料乙3千克，生产B