算法分析与设计_在线真题试卷与模拟练习_算法分析与设计_考试宝

更新时间：试题数量：购买人数：提供作者：

有效期：个月

章节介绍：共有个章节

收藏

我的练习

我的错题
(0道)

我的收藏
(0道)

我的斩题
(0道)

我的笔记
(0道)

专项练习

顺序练习 0 / 0

随机练习 自定义设置练习量

题型乱序 按导入顺序练习

模拟考试 仿真模拟

题型练习 按题型分类练习

易错题 精选高频易错题

学习资料 考试学习相关信息

搜索

题库预览

算法要对异常情况进行适当的处理，就是算法的（）。

一切合法的输入数据都能得出满足要求的结果，包括典型的、苛刻的输入数据也能够得出满足要求的结果。这个含义对应算法的（）。

算法分析包括最好情况下的时间复杂度(时间复杂度下界)、最坏情况下的时间复杂度(时间复杂度上界)和平均情况下的时间复杂度（时间复杂度均值）。实践表明可操作性最好的，且最有实际价值的，是（）。

T(n)=T(n/3)+T(2n/3)+n

BinRec(n)

//输入：正的十进制整数n

//输出：n的二进制表示位数

if n = 1

return 1

else

return BinRec(n/2) + 1

计算时间复杂度，正确是（）。

【主定理case1】求解递推方程

T(n) = 2T(n/2)+logn

【主定理case1】求解递推方程

T(n) = 8T(n/2)+n²

假设有一台高性能计算机，其中CPU包含专用k>2个优化寄存器。假设已经存储在寄存器中的数不超过k个，那么这些寄存器支持在O(1)时间插入键值对（x,y）的操作。此外，这些寄存器支持在O(1)时间删除和返回具有最小关键字x的键值对（x,y）。证明：可使用这台高性能计算机用（）时间对n个数排序。

半数集问题：

给定一个自然数n，右n开始可以依次产生半数集set(n)中的数如下：

1）n加入set(n)；

2）在n的左边加一个自然数，但该自然数不能超过最近添加的数的一半；

3）按此规则处理，直到不能添加自然数为止。元素允许重复。

计算半数集set(n)中元素个数。

设f(n)是半数集set(n)中元素个数，它的递推公式是（）。

贪心算法则通常以（）的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

给定A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1，霍夫曼编码是什么？

活动安排问题：有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个会议室，活动之间不能交叠，求最多安排多少个活动。正确的贪心选择（）。

最优装载问题：有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要选出尽可能多的集装箱装上轮船，使它们的重量之和不超过W。可以采用贪心策略求解最优装载问题。

各集装箱重量w[]={0,5,2,6,4,3};

N=5,W=10;

最优装载的集装箱是（）。

设有n个独立的作业{1，2，…，n}，由m台相同的机器{1，2， …，m}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但未完工前不允许中断，任何作业也不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
贪心法求解多机调度问题的贪心策略是（）。

最小延迟时间问题：假定有一单个的资源在一个时刻只能处理一个任务。现给定一组任务，其中的每个任务 i 包含一个持续时间 ti 和截止时间 di 。任务i开始时间si的结束时间fi=si+ti。每个任务的延迟时间li=max(0, fi-di)。
设计与实现一个算法，对n组任务给出一个最优调度方案，使其对所有任务的最大延迟之和最小化，即求L=max lj，1≤j≤n.
问题可以采用贪心策略求解，贪心策略是（）。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，主要差别（）。

证明问题具有最优子结构性质最常见的方法是（）。

应用动态规划法解决问题的基本活动如下：
(E)找出最优解的性质
(D)刻划其结构特征。
(C)递归地定义最优值。
(B)以自底向上的方式计算出最优值。
(A)根据计算最优值时得到的信息构造最优解。
正确的步骤排序是（）。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。该问题具有（）个不同的子问题。

当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树问题复杂性通常是（）。