算法设计分析第次.doc

第1次作业
一、单项选取题（本大题共60分，共 20 小题，每小题 3 分）
1.
设 m[i，j] 为计算矩阵链Ai…j 所需乘法运算次数最小值，则矩阵链A1…n所需乘法运算次数最小值为（  ）。
A. m[0,n]
B. m[1,n-1]
C. m[1,n+1]
D. m[1,n]
2. 二分搜索算法是基于（ ）设计算法。
A. 分治法
B. 动态规划法
C. 贪心法
D. 穷尽法
3. 直接或间接调用自身算法称为（ ）。
A. 贪心算法
B. 递归算法
C. 迭代算法
D. 动态规划算法
4. 算法分析两个重要方面是（ ）。
A. 空间复杂度和时间复杂度
B. 对的性和简朴性
C. 可读性和文档性
5. 下述关于最优子构造说法，不对的是（   ）。
A. 原问题最优解包括子问题最优解
B. 原问题最优解建立在子问题最优解基本之上
C. 原问题最优解依赖于子问题最优解
D. 原问题最优解通过子问题非最优解合并而得
6. 当n越来越大时，下列函数中，增长速度最快应当是（　　）
A. y=100n
B. y=log100n
C. y=
D.
y=
7. 实现归并排序运用算法是（）。
A.
分治方略
B. 动态规划法 
C. 贪心法
D. 回溯法
8. 算法时间复杂度是指（）
A. 执行算法程序所需要时间
B. 算法程序长度
C. 算法执行过程中所需要基本运算次数
D. 算法程序中指令条数
9. 在活动安排问题中，下述哪项描述中活动A,B是相容 （   ）？
A. 活动A于活动B开始前开始
B. 活动A于活动B结束前开始
C. 活动A于活动B开始前结束
D. 活动A于活动B开始后开始
10. 衡量一种算法好坏原则是（ ）。
A. 运营速度快
B. 占用空间少
C. 时间复杂度低
D. 代码短
11.
在最长公共子序列问题中，如果定义 c[i，j] 为X1..i 和 Y1..j 最长公共子序列长度，则长度为mX序列与长度为nY序列最长公共子序列长度为（   ）。
A. c[0,0]
B. c[1,1]
C. c[1,m]
D. c[m,n]
12. 如下关于贪心算法，不对的说法是 （   ）。
A. 用于解决优化问题
B. 总是选取在当前看来最佳选取
C. 盼望通过局部最优达到全局最优
D. 所需求解问题可以不满足最优子构造性质
13. 一种p行q列矩形同一种q行r列矩形相乘，总共要作多少次乘法运算？（  ）
A.  p x r
B. q
2
C.  p x q x r
D. q3
14.
在最优二叉搜索树问题中，考虑如下BST:
如果要搜索k3 ，总共要通过多少次比较 （   ）。
A. 1次
B. 2次
C. 3次
D. 4次
15.
JAVA程序重要有如下两种类型（ ）
A. 应用程序和APPLET 应用程序和理论程序
B. 系统程序和应用程序
C. 系统程序和理论程序
D. D系统程序和APPLET应用程序
16.
如图所示Huffmann树，
字符s编码是（    ）。
A. 1010
B. 1110