湖南中医药大学
- 递归的基本要素包括( )。
- 一个算法的优劣可以用( )来衡量。
- 为了得到装入集装箱的数量以及装入的总重量和集装箱编号，在使用贪心算法求解最优装载问题时，每成功装入一个集装箱，则( )。
- 算法具备的性质包括( )。
- ( )属于搜索算法。
- 已知4个物品A、B、C、D的重量分别为[15, 10, 12, 7]，价值分别为[50, 20, 40, 40]，每一个物品均不能分解。现有一个容量为30的背包，选择物品( )可以使得背包中物品的总价值最大。
- 对于n皇后问题，需要满足( )。
- 在n皇后问题中，如果在棋盘的某一个位置(i,j)去除一个皇后，则( )。
- 关于Dijkstra算法中的数据结构，以下说法正确的是( )。
- 使用伪代码描述算法具有（ ）等优点。
- 关于备忘录法，以下说法正确的是( )。
- 以下表示方法中正确的包括( )。
- 关于使用回溯法求解0-1背包问题，以下说法正确的是( )。
- 在物品重量和背包容量都是正整数的情况下，0-1背包问题可以用( )求解。
- 关于分支限界法的基本思想，下列描述正确的是( )。
- 0-1背包问题与部分背包问题的区别在于( )。
- 在图的m着色问题中需要使用到的数据结构包括( )。
- 分支限界法最常见的实现方式包括( )。
- 下列关于贪心算法与动态规划算法说法正确的是( )。
- 关于快速排序的时间复杂度，( )是正确的。
- 使用贪心算法求解最优装载问题，其时间复杂度为O(n)。
- 动态规划的基本步骤是先找出最优解的性质，并刻画其结构特征，然后递归地定义最优值，以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造最优解。
- 在马的遍历问题中，对于棋盘上任意一点A(x,y)，有八个扩展方向，可以用数组fx[8]={1,2,2,1,-1,-2,-2,-1}, fy[8]= {2,1,-1,-2,-2,-1,1,2}来模拟马走“日”时下标的变化过程。
- 使用动态规划算法求解最长公共子序列问题的时间复杂度为O(m+n)，其中m和n为两条序列的长度。
- 对于同一背包和相同的一组物品，作为部分背包问题求解得到的总价值一定大于等于作为0-1背包问题求解得到的总价值。
- 在计算最长公共子序列的长度时，为了减少空间需求可以使用滚动数组。给定两个序列，长度分别为m和n，可以将短的序列作为行，长的序列作为列，最后可将空间需求减至O(min(m,n))。
- 解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划，需要排序的是回溯法和分支限界法。
- 如果一个给定装载问题有解，则采用的装载策略为：首先将第一艘轮船尽可能装满；再将剩余的集装箱装上第二艘轮船。
- Prim算法适合稠密图，其时间复杂度只与边的数目有关。
- 队列Queue具有先进后出的性质。
- 对于一个二维数组而言，同一条右斜线上的坐标x和y之和为一个相同的数。
- 采用贪心算法求解最优装载问题的主要计算量在于对集装箱进行排序。
- 在使用回溯法求解0-1背包问题时，为了能够更加高效地进行剪枝，可以通过将剩余物品的价值进行求和的方法得到右子树的最优上界。
- Dijkstra算法采用了和Prim算法类似的松弛操作，松弛操作的目的是减少dis[i]的值，如果从源点s到达i有更优的路径则更新dis[i]。
- 动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
- 在最好情况下、最坏情况下、平均情况下的时间复杂度中，可操作性最好的且最有实际价值的，是最坏情况下的时间复杂度。
- 使用分治设计算法来求解问题时，通常在分解问题时要求子问题的规模尽量一致。
- 使用贪心算法求解找硬币问题时，总能找到问题的最优解。
- 二分查找又称为折半查找，它是一种高效的查找方法，但是二分查找要求列表中的元素是有序的，是分治算法的典型实例之一。
- 动态规划算法通过保存已解决子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
- 优先队列式分支限界法将活结点表组织成一个优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
- 贪心算法中每次做出的贪心选择都是局部最优选择。
- 算法是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果，程序是算法用某种程序设计语言的具体实现。
- 对于有64片圆盘的汉诺塔问题，如果每移动一次圆盘需要1秒，则一小时以内可以完成全部圆盘的移动。
- 已知某楼房共30层，如果采用二分查找，请问最多猜( )次就能猜出任意一个楼层。
- 序列{4,2,1,5,2,2,4,3,4}的最长递增子序列的长度为( )。
- 线性查找的平均时间复杂度为( )【用大O表示法表示】。
- 整数序列[4, -3, 5, -2, -1, 2, 5, -2]的最大子段和为( )。
- 如果输入的活动无序，则使用贪心算法求解活动安排问题的时间复杂度为( )。
- 已知五个物品的重量分别为[10, 20, 30 ,40, 50]，价值分别为[20, 30, 66, 40, 60]，背包容量为100，采用部分背包问题求解可以得到的最大价值为( )。
- 已知12个活动的开始时间和结束时间如下：[1,3)、[3,4)、[0,7)、[3,8)、[15,19)，[15,20)，[10,15)、[8,18)、[6,12)、[5,10)、[4,14)和[2,9)，第一个值为活动的开始时间，第二个值为活动的结束时间。使用贪心算法最终可以求得( )个相容活动。
- ( )描述算法形象直观，且易于理解。
- A、B、C、D四个人，单独过河分别需要1、2、3、4分钟，最多两人同时过河，并且只有一个手电筒，每次都需要手电筒，两人一起按过河慢的时间算，总过河时间最少为( )分钟。
- 使用第一个元素作为划分基准，如果需要将数组由小到大排序，那么对于整数数组{6,5,4,3,2,1}，第一趟分区之后的结果为( )。
- 输入数组(6,-1,5,4,-7)，它的最大子段和以及子段的起始位置和结束位置(位置均从1开始)分别是( )、( )和( )。
- 一个长度为n的序列，它的连续子段共（ ）个。
- 以下代码的时间复杂度为( )。i = 1;while (i<=n) { i = i * 5;}
- 以下代码的时间复杂度为( )。for(i=1; i<=n; i++){ for(j=1; j<=n; j++) { c[i][j]=0; for(k=1; k<=n; k++) { c[i][j] = c[i][j]+a[i][k]*b[k][j]; } }}
- 如果斐波那契数列的第一项F(0)=1，第二项F(1)=1，则F(8)=___________。
- 实现快速排序所使用的算法是( )。
- 算法分析的目的是( )。
- 6个圆盘的汉诺塔，如果需要将全部圆盘从A柱移至C柱，最少需要移动( )步。
- 活动安排问题是要在所给的活动集合中选出最大的相容活动子集合。( )算法提供了一个简单、有效的方法，使得尽可能多的活动能兼容地使用公共资源。
- 函数f(n) = 1 + 1/n^2的渐近表达式为( )。
- 代码填空【汉诺塔问题（a柱为原始柱，b柱为辅助柱，c柱为目标柱）】：void hanoi(int n, char a, char b, char c) { if (n > 0) { _________(1)__________; move(n,a,c); //将n号圆盘从a柱移至c柱 _________(2)_____________; }}
- 已知一只青蛙一次可以跳上1级台阶，也可以跳上2级。该青蛙跳上一个5级的台阶总共有( )种跳法。
- 如果从最后一个物品开始装入背包，在能够装入的情况下，背包的最优价值m[i][j]=( )。
- 如果使用穷举法求解0-1背包问题，将产生（ ）种装物品的方案。
A:递归深度 B:递归表达式 C:递归结束条件 D:递归初始条件
答案:递归表达式###递归结束条件
A:逻辑复杂度 B:代码长度 C:时间复杂度 D:空间复杂度
答案:时间复杂度###空间复杂度
A:装入集装箱总数加1 B:更新轮船的剩余重量 C:更新轮船已装载总重量 D:记录装载的集装箱编号
答案:更新轮船已装载总重量###装入集装箱总数加1###更新轮船的剩余重量###记录装载的集装箱编号
A:有限性 B:0个或者多个输入 C:确定性 D:至少1个输出
答案:ABC
A:分支限界法 B:回溯法 C:贪心算法 D:动态规划
答案:回溯法###分支限界法
A:B B:A C:C D:D
答案:C###B###D
A:任意两个皇后不能处在同一列 B:任意两个皇后不能处在同一行 C:任意两个皇后不能处在同一左斜线 D:任意两个皇后不能处在同一右斜线
答案:任意两个皇后不能处在同一右斜线###任意两个皇后不能处在同一左斜线###任意两个皇后不能处在同一列###任意两个皇后不能处在同一行
A:M[j]=0 B:A[i][j]=0 C:L[i+j]=0 D:R[i-j+N]=0
答案:M[j]=0###L[i+j]=0###R[i-j+N]=0###A[i][j]=0
A:如果源点到某一个点i之间有一条边，则dis[i]的初始值为这条边的权重 B:如果源点到某一个点i没有直接的边相连，则dis[i]的初始值为无穷大 C:需要一个used[]数组用于记录一个点是否已访问过 D:需要一个dis[]数组用于保存源点到其他点的最短路径值
答案:需要一个used[]数组用于记录一个点是否已访问过###需要一个dis[]数组用于保存源点到其他点的最短路径值###如果源点到某一个点i之间有一条边，则dis[i]的初始值为这条边的权重###如果源点到某一个点i没有直接的边相连，则dis[i]的初始值为无穷大
A:容易修改 B:简单易懂 C:易于转化为程序语言代码 D:格式统一规范
A:引入一个备忘录用于存储已求解过的子问题的解 B:备忘录法又称为填表法 C:其算法结构与直接递归的结构相同 D:采用自顶向下分解的结构来求解问题
A:N^2+100NlogN+1=O(N^2) B:NlogN+2logN=O(N^3) C:2N=O(N) D:2N=O(N^2)
A:使用限界函数剪去得不到更优解的右子树（不装该物品）。 B:使用约束函数剪去不合理的左子树（装该物品）。 C:使用限界函数剪去得不到更优解的左子树（装该物品）。 D:使用约束函数剪去不合理的右子树（不装该物品）。
A:穷举法 B:动态规划算法 C:回溯法 D:贪心算法
A:每一个活结点只有一次机会成为扩展结点 B:活结点一旦成为扩展结点，就一次性产生其所有子结点 C:那些导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中 D:一直持续到找到所求的解或活结点表为空时为止 E:从活结点表中取下一结点成为当前扩展结点，并重复结点扩展过程
A:没有区别，它们的含义相同 B:若用贪心算法解决部分背包问题，只能得到近似最优解 C:在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分 D:若用贪心算法解决0-1背包问题，只能得到近似最优解
A:用一个二维数组以邻接矩阵的方式存储地图 B:用一个一维数组存储每一种颜色对应的点 C:用一个二维数组存储每一个点对应的可着颜色 D:用一个一维数组存储每一个点所着颜色
A:优先队列式分支限界法 B:备忘录式分支限界法 C:分层式分支限界法 D:队列式分支限界法
A:贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质 B:贪心算法与动态规划算法的主要区别是动态规划算法要求问题具有贪心选择性质 C:贪心算法与动态规划算法求解的问题都具有重复子问题性质 D:贪心算法与动态规划算法求解的问题都具备最优子结构性质
A:在最好情况下时间复杂度为O(nlogn) B:在最坏情况下时间复杂度为O(nlogn) C:在平均情况下时间复杂度为O(nlogn) D:在平均情况下时间复杂度为O(n^2)
A:错 B:对
A:错 B:对
A:错 B:对
A:对 B:错
A:错 B:对
A:对 B:错
A:错 B:对
A:对 B:错
A:错 B:对
A:对 B:错
A:对 B:错
A:对 B:错
A:错 B:对
A:错 B:对
A:对 B:错
A:错 B:对
A:对 B:错
A:错 B:对
A:对 B:错
A:对 B:错
A:对 B:错
A:对 B:错
A:错 B:对
A:错 B:对
A:5 B:10 C:4 D:6
A:2 B:5 C:3 D:4
A:O(logn) B:O(1) C:O(n) D:O(n^2)
A:12 B:11 C:9 D:10
A:O(nlogn) B:O(n^3) C:O(n^2) D:O(n)
A:156 B:166 C:160 D:164
A:5 B:7 C:4 D:6
A:伪代码 B:自然语言 C:高级程序设计语言 D:程序流程图
A:9 B:10 C:11 D:12
A:(1,5,4,3,2,6) B:(5,4,3,2,1,6) C:(6,5,4,3,2,1) D:(1,2,3,4,5,6)
A:14,1,3 B:14,1,4 C:15,1,4 D:15,1,3
A:(n+1)*n/2 B:n*n-1 C:2^n D:n-1
A:O(n/5) B:O(logn) C:O(n^5) D:O(n)
A:O(nlogn) B:O(n) C:O(n^2) D:O(n^3)
A:21 B:34 C:55 D:13
A:动态规划 B:回溯法 C:分治算法 D:贪心算法
A:
分析算法的易懂性和可靠性
B:找出算法中输入和输出之间的关系
C:分析算法的效率以求改进
D:找出数据结构的合理性A:31 B:32 C:63 D:64
A:回溯 B:动态规划 C:分治 D:贪心
A:O(1) B:O(n) C:O(1/n^2) D:O(1/n)
A:(1) hanoi(n-1, b, a, c)
(2) hanoi(n-1, a, c, b) B:(1) hanoi(n-1, a, c, b)
(2) hanoi(n-1, b, a, c) C:(1) hanoi(n-1, a, b, c)
(2) hanoi(n-1, b, c, a) D:(1) hanoi(n-1, b, c, a)
(2) hanoi(n-1, a, b, c)
A:5 B:7 C:8 D:13
A:m[i-1][j] B:max{m[i+1][j],m[i+1][j-wi]+vi} C:max{m[i-1][j],m[i-1][j-wi]+vi} D:m[i+1][j]
A:n(n+1)/2 B:n^2 C:2n D:2^n
温馨提示支付 ￥5.00 元后可查看付费内容,请先翻页预览!
