没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
《算法分析与设计》试题库(一)
一、 选择题
1.应用 Johnson 法则的流水作业调度采用的算法是()
A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法
2.Hanoi 塔问题如下图所示。现要求将塔座 A 上的的所有圆盘移到塔座 B 上,并
仍按同样顺序叠置。移动圆盘时遵守 Hanoi 塔问题的移动规则。由此设计出解
Hanoi 塔问题的递归算法正确的为:()
Hanoi 塔
A.
B.
C.
3.动态规划算法的基本要素为()
最优子结构性质与贪心选择性质
.重叠子问题性质与贪心选择性质
.最优子结构性质与重叠子问题性质
预排序与递归调用
4. 算法分析中,记号 O 表示( ) , 记 号 表示 ( ), 记号 表示
()。
A.渐进下界
B.渐进上界
C.非紧上界
D.紧渐进界
E.非紧下界
5. 以下关于渐进记号的性质是正确的有:(A)
A.
B.
C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})
D.
6.能采用贪心算法求最优解的问题,一般具有的重要性质为:()
最优子结构性质与贪心选择性质
.重叠子问题性质与贪心选择性质
.最优子结构性质与重叠子问题性质
预排序与递归调用
D.
回溯法在问题的解空间树中,按()策略,从根结点出发搜索解空间树。
A.广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先
8. 分支限界法在问题的解空间树中,按()策略,从根结点出发搜索解空间
树。
A. 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先
9. 程序块(A)是回溯法中遍历排列树的算法框架程序。
A.
B.
C.
D.
backtrack
!"
#$%$&&
"' () ()
!*!+,#+,&
"' () ()
+,#+,
!"
#$%$&&
()$
!*!+,#+,&
+,#+,
!"
#$%$&&
()$
!*!+,#+,
backtrack
!"
#$%$&&
"' () ()
!*!+,#+,&
10. 回溯法的效率不依赖于以下哪一个因素?(C )
A. 产生 x[k]的时间;
B. 满足显约束的 x[k]值的个数;
C. 问题的解空间的形式;
D. 计算上界函数 bound 的时间;
11. 常见的两种分支限界法为(D)
A. 广度优先分支限界法与深度优先分支限界法;
B. 队列式(FIFO)分支限界法与堆栈式分支限界法;
C. 排列树法与子集树法;
D. 队列式(FIFO)分支限界法与优先队列式分支限界法;
-, 带图灵机的空间复杂性 .是指()
, 带图灵机处理所有长度为 的输入时,在某条带上所使用过的最大方格
数。
, 带图灵机处理所有长度为 的输入时,在 , 条带上所使用过的方格数的
总和
, 带图灵机处理所有长度为 的输入时,在 , 条带上所使用过的平均方格
数。
, 带图灵机处理所有长度为 的输入时,在某条带上所使用过的最小方格
数。
13. N/ 类语言在图灵机下的定义为()
A. 0/$121 是一个能在非多项式时间内被一台 034 所接受的语言;
B. 0/$121 是一个能在多项式时间内被一台 034 所接受的语言;
C. 0/$121 是一个能在多项式时间内被一台 34 所接受的语言;
0/$121 是一个能在多项式时间内被一台 034 所接受的语言;
14. 记号 O 的定义正确的是(A)。
5*$2存在正常数 + 和 使得对所有
有:
+*;
5*$2存在正常数 + 和 使得对所有
有: +*
;
5*$2对于任何正常数 +,存在正数和
使得对所有
有: %+*;
5*$2对于任何正常数 +,存在正数和
使得对所有
有: +*%;
15. 记号 的定义正确的是(B)。
5*$2存在正常数 + 和 使得对所有
有:
+*;
5*$2存在正常数 + 和 使得对所有
有: +*
;
*$2对于任何正常数 +,存在正数和
使得对所有
有: %+*;
D. *$2对于任何正常数 +,存在正数和
使得对所有
有: +*%;
二、 填空题
1. 下面程序段的所需要的计算时间为( )。
4 .67"7"8
"$
#$%$&&
""$
#8$8%$8&&
""&$(8)
"""
"$""
"$
"8$8
##"
剩余57页未读,继续阅读
资源评论
dream5678
- 粉丝: 2
- 资源: 29
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功