河南农业大学-计算机科学与技术-算法分析与设计

[填空题,3.8分] 舍伍德算法总能求得问题的-------

答案是：一个解

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 算法的“确定性”指的是组成算法的每条----是清晰的，无歧义的

答案是：指令

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 问题的-------是该问题可用动态规划算法或贪心算法求解的关键特征

答案是：最优子结构性质

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 矩阵连乘问题的算法可由----------设计实现

答案是：动态规划

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 计算一个算法时间复杂度通常可以计算-------、-------或计算步

答案是：循环次数|基本操作的频率

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] ()是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别

答案是：贪心选择性质

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 矩阵连乘问题的算法可由由-----设计实

答案是：动态规划

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 数值概率算法常用于--------的求解

答案是：数值问题

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 算法的复杂性有----复杂性和------复杂性之分

答案是：时间|空间

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 算法是指解决问题的-----或-------

答案是：一种方法|一个过程

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 以深度优先方式系统搜索问题解的算法称为--------

答案是：回溯法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 拉斯维加斯算法找到的解一定是-----

答案是：正确解

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是--------，需要排序的是------，------

答案是：动态规划|回溯法|分支限界法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 利用概率的性质计算近似值的随机算法是__，运行时以一定的概率得到正确解的随机算法是__

答案是：数值概率算法|蒙特卡罗算法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 程序是---用某种程序设计语言的具体实现

答案是：算法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 从分治法的一般设计模式可以看出，用它设计出的程序一般是-----

答案是：递归算法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 回溯法是一种既带有-----又带有------的搜索算法

答案是：系统性|跳跃性

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 贪心算法的基本要素是-------质和------性质

答案是：贪心选择|最优子结构

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 大整数乘积算法是用------来设计的

答案是：分治法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,2.6分] 以广度优先或以最小耗费方式搜索问题解的算法称为--------

答案是：分支限界法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 拉斯维加斯算法

答案是：不会得到不正确的解|可能找不到解|概率随着它用的计算时间的增加而提高|求解失效的概率任意小

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] Flynn分类法，它按照指令流和数据流将计算机系统分为哪几类？

答案是：单指令单数据流计算机|单指令多数据流计算机|多指令单数据流计算机|多指令多数据流计算机

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 在公共总线互联SMP系统中，单总线SMP系统具有哪些优点？

答案是：成本低|容易实现|扩展性能好

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 蒙特卡罗算法

答案是：求问题的准确解|无法有效判断|得到的解|是否肯定正确

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解

答案是：解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),,(1,1,0

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 请说明动态规划方法为什么需要最优子结构性质

答案是：子问题|动态规划方法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 简述使用哈夫曼算法构造最优编码的基本步骤

答案是：构造最优编码树|贪心算法|所所有字符对应nn棵树构成的森林|合并产生一个新树|两棵子

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 概率算法大致分为

答案是：数值概率算法|蒙特卡罗算法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值

答案是：N1={1，3}，N2={2，4}|N1’={1，3}，，N2’={4，2}|最优值为：3

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 写出设计动态规划算法的主要步骤

答案是：问题具有最优子结构性质|构造最优值的递归关系表达式|最优值的算法描述|构造最优解

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 描述0-1背包问题

答案是：已知一个背包的容量为C|有n件物品|物品i的重量为Wi|价值为Vi|求应如何选择装入背包中的物品，使得装入背包中物品的总

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 衡量算法时间效率的方法有哪两种？

答案是：事后分析法|事前分析法

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 用于数字签名和信息认证技术的HASH函数必须满足那些条件

答案是：不可逆性|计算简单|冲突概率小|高度敏感性

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 数值概率算法

答案是：数值问题的求解|近似解|精度随计算时间的增加不断提高

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] STRASEN算法的主要意义

答案是：突破了矩阵乘法的O（n3）时间界限|矩阵求逆|计算行列式|解联立线性方程组|O（n3）时间计算的开销

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 舍伍德算法

答案是：总能求得问题的一个解|不是避免算法的最坏情况行为|设法消除

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 概率算法的一个基本特征

答案是：对所求解问题|同一实例|用同一概率算法求解|两次完全不同的效果

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[论述题,2.6分] 动态规划算法与贪心算法的不同点

答案是：动态规划|贪心方法|动态规划方法的条件|可用贪心方法的条件

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 对算法的分析必须脱离具体的（）（）

答案是：计算机结构|程序设计语言

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 由程序的控制和数据的相关性决定的是（）

答案是：软件并行性

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 并行算法的-------为求解相应问题的最快串行算法在最坏情况下的运行时间除以该并行算法在最坏情况下的求解该问题的运行时间

答案是：加速比

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 常用来支持细粒度和中粒度的并行计算是（）

答案是：共享变量通信

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] （）是指在同一时间间隔内增加操作数量的技术

答案是：并行处理技术

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[简答题,10分] 动态规划算法与贪心算法的相同点

答案是：都需要最优子结构性质，，都用来求有优化问

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[简答题,10分] 常见的两种分支限界法的算法框架

答案是：（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。。。（2）优先队列式分支

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,11.2分] 优先队列可用------数据结构实现

答案是：堆

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,11.1分] 回溯法中常见的两类典型的解空间树是子集树和-----

答案是：排列树

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,11.1分] 图的m着色问题可用------法求解，其解空间树中叶子结点个数是------，解空间树中每个内结点的孩子数是-----------

答案是：回溯|mn|m

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,11.1分] Prim算法利用-----策略求解------问题，其时间复杂度是--------

答案是：贪心|最小生成树|O(n2)

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,11.1分] 快速排序算法的性能取决于----------

答案是：划分的对称性

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

时序图检验

答案是：平稳序列波动的范围有界、无明显趋势及周期特征(因为平稳序列的均值和方差都为常数)；非平稳序列通常有明显趋势或周期特征

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

平稳性

答案是：若序列达到统计平衡状态，其统计特性不随时间变化，则称该序列具有平稳性

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[简答题,11.1分] 用分支限界法设计算法的步骤

答案是：(1)针对所给问题，定义问题的解空间（对解进行编码）；；；(2)确定易于搜索的解空间结构（按树或图组织解））；；； (3

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[简答题,11.1分] 分支限界法与回溯法的不同点

答案是：（1）求解目标不同；；；（2）搜索方式不同；；；（3）对扩展结点的扩展方式不同；；；（4）存储空间的要

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 任何可用计算机求解的问题所需的时间都与其------有关

答案是：规模

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 回溯法搜索解空间树时，常用的两种剪枝函数为-----和----

答案是：约束函数|限界函数

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 分支限界法主要有-----分支限界法和------分支限界法

答案是：队列式（FIFO）|优先队列式|优先队列式

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 快速排序算法的性能取决于-------

答案是：划分的对称性

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

[填空题,10分] 任何可用计算机求解的问题所需的时间都与其------有

答案是：规模

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计

相对误差

答案是：是指实际观测值与预测值之间差异的相对程度。常用的相对误差有百分误差（tR）、平均百分误差（MPE）和平均绝对百分误差（M

更新时间:2023/4/3 12:59:00
出自:河南农业大学-计算机科学与技术-算法分析与设计