下载此文档

算法设计分析.doc


文档分类:IT计算机 | 页数:约11页 举报非法文档有奖
1/11
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/11 下载此文档
文档列表 文档介绍
第2次作业
一、单项选取题(本大题共60分,共 20 小题,每小题 3 分)
1.
一种长度为n英寸钢管最优切割问题,总共有多少个不同子问题?(   )
A. n+1
B.
n2
C.
nlogn
D.
logn
2. 实现迅速排序算法如下:
QuickSort (A,p,r)
IF p < r
THEN q ← Partition(A,p,r)
  (    )
  QuickSort(A,q+1,r)
A. quickSort(p,q-1)
B. quickSort(p+1,q-1)
C. quickSort(p,q+1)
D. quickSort(p,q-2)
3. 在钢管切割问题里,咱们用如下递归表达式表达原问题最优解最优值:
请问,其中i是指什么?(  )
A. 1英寸钢管价值
B. 子问题钢管长度
C. 第一刀所切割钢管长度
D. 价值/长度比
4. 在最优二叉搜索树问题中,咱们优化目的是(   )。
A. 只通过至少次数比较就可以找到概率最大元素
B. 通过最多次数比较就可以找到概率最小元素
C. 找到每个元素所需要平均比较次数为最小
D. 元素搜索代价数学盼望为最小
5. Edmonds-Karp算法中寻找增广途径办法是(  )。
A. 深度优先算法
B. 广度优先算法
C. Prim算法
D. Dijkstra算法
6.
关于0,1背包问题下述形式化公式描述:
下述说法不对的是(  )。
A. i 表达物品重量
B. C表达背包容量
C. xi=0表达编号为i物品不被选取
D. 求解目的是最大化装入背包内物品总价值
7. 在活动安排问题中,如果把所有活动按照结束时间递增序排序后,按贪心算法,咱们总是安排 (   )。
A. 当前可选活动中结束时间最早活动
B. 当前可选活动中开始时间最早活动
C. 当前可选活动中冲突数量至少活动
D. 当前可选活动中持续时间最长活动
8.
找零钱问题中,定义 C[j]为兑换j 所需要硬币至少数量,考虑下述递归表达式,
下列关于对i寻优最恰当描述是(   )。
A. 考虑找出第一种硬币面值各种也许性
B. 考虑先找给客户几分钱
C. 考虑最多可以用几种硬币
D. 考虑至少可以用几种硬币
9. 算法必要具备输入、输出和( )等5个特性。
A. 可执行性、可移植性和可扩充性
B. 可行性、拟定性和有穷性
C. 拟定性、有穷性和稳定性
D. 易读性、稳定性和安全性
10. 当问题规模n趋向无穷大时,( )数量级(阶)称为算法渐进时间复杂度。
A. 时间复杂度
B. 空间复杂度
C. 冗余度
D. 迭代次数
11. 最优二叉搜索树时间复杂度为(  )。
A. O(n)
B. O(n!)
C. O(n2)
D. O(n3)
12. 递归函数f(n)=f(n-1)+n(n>1)递归出口是( )。
A. f(0)=0
B. f(1)=1
C. f(0)=1
D. f(n)=n
13.
在最优二叉搜索树问题中,定义e[i,j ]为  ki,...,kj最优二叉查找树盼望搜索成本,而咱们拟定根结点下标为r,则其左子树下标范畴是(   )。
A. i..r
B. i..r-1
C. i..r+1
D. i+1..r
14. 下面是贪心算法基本要素是(   )。
A. 重叠子问题
B. 构造最优解
C. 贪心选取性质
D. 定义最优解
15. 分治法所能解决问题应具备核心特性是( )。
A. 该问题规模缩小到一定限度就可以容易地解决
B. 该问题可以分解为若干个规模较小相似问题
C. 运用该问题分解出子问题解可以合并为该问题解
D. 该问题所分解出各个子问题是互相独立
16. 在钢管切割问题里,如果用rn表达长度为n英寸钢管最优切割方案所获得最大收益,且已知rn所代表最优解里,第一刀切下了3英寸,则下述公式哪一种是对的?(    )
A. r
n  = p3 + rn-3
B.
rn  = rn – 3
C.
rn  = rn-3 + 3
D.
rn  = r3 + p3
17. (   )是贪心算法与动态规划算法共同点。
A. 重叠子问题
B. 构造最优解
C. 贪心选取性质
D. 最优子构造性质
18.
使用分治法求解不需要满足条件是( )。
A. 子问题必要是同样
B. 子问题不可以重复
C. 子问题解可以合并
D. 原问题和子问题使用相似办法解
19. 递归算法不

算法设计分析 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数11
  • 收藏数0 收藏
  • 顶次数0
  • 上传人书犹药也
  • 文件大小54 KB
  • 时间2021-12-07