第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
算法导论试题.docx
一、选择题
1.算法分析中，记号 O 表示（B），记号Ω标售（A）,记号Θ表示（D）
A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界
2.以下关于渐进记号的性质是正确的有：（A）
A f(n) =Θ(g(n)),g(n) =Θ(h(n))⇒f(n) =Θ(h(n))
B f(n) =O(g(n)),g(n) =O(h(n))⇒h(n) =O(f(n))
D f(n) = O(g(n))⇔g(n) = O(f(n))
C O(f(n))+O(g(n)) = O(min{f(n),g(n)})
3. 记号 O 的定义正确的是（A）。
A O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n≥n0 有：0≤ f(n) ≤ cg(n) }；
B O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n≥n0 有：0≤ cg(n) ≤ f(n) }；
C O(g(n)) = { f(n) | 对于任何正常数 c>0，存在正数和 n0 >0 使得对所有 n≥n0 有：0 ≤
f(n)0，存在正数和 n0 >0 使得对所有 n≥n0 有：0 ≤cg(n)
< f(n) }；
4. 记号Ω的定义正确的是（B）。
A O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n≥n0 有：0≤ f(n) ≤ cg(n) }；
B O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n≥n0 有：0≤ cg(n) ≤ f(n) }；
C (g(n)) = { f(n) | 对于任何正常数 c>0，存在正数和 n0 >0 使得对所有 n≥n0 有：0 ≤
f(n)0，存在正数和 n0 >0 使得对所有 n≥n0 有：0 ≤cg(n)
< f(n) }；
5. T（n）表示当输入规模为 n 时的算法效率，以下算法效率最优的是( C )
A T（n）= T（n – 1）+1，T（1）=1
B T（n）= 2n2
C T（n）= T（n/2）+1，T（1）=1
D T（n）= 3nlog2n
6. 动态规划算法的基本要素为（C）
A 最优子结构性质与贪心选择性质
B 重叠子问题性质与贪心选择性质
C 最优子结构性质与重叠子问题性质
D 预排序与递归调用
7.下列不是动态规划算法基本步骤的是（ A ）。
A 找出最优解的性质
C 算出最优解
8.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）
A 最优子结构性质与贪心选择性质
D 定义最优解
B 构造最优解
B 动态规划法
D 回溯法
B 构造最优解
D 最优子结构性质
B 重叠子问题性质与贪心选择性质
C 最优子结构性质与重叠子问题性质
D 预排序与递归调用
9.下面是贪心算法的基本要素的是（ C ）。
A 重叠子问题 B 构造最优解 C 贪心选择性质 D 定义最优解
10（ D ）是贪心算法与动态规划算法的共同点。
A 重叠子问题
C 贪心选择性质
11.使用分治法求解不需要满足的条件是（A ）。
B 子问题不能够重复
A 子问题必须是一样的
C 子问题的解可以合并
D 原问题和子问题使用相同的方法解
12.实现循环赛日程表利用的算法是（ A ）。
A 分治策略
C 贪心法
13.使用分治法求解不需要满足的条件是（A ）。
B 子问题不能够重复
A 子问题必须是一样的
C 子问题的解可以合并
D 原问题和子问题使用相同的方法解
14.下列算法中不能解决 0/1 背包问题的是（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
15.以下( C )不能不能在线性时间完成排序
A 计数排序 B 基数排序 C 堆排序 D 桶排序
16.下列哪一种算法是随机化算法（ D ）
A 贪心算法 B 回溯法 C 动态规划算法 D 舍伍德算法
17. 下列算法中通常以自底向上的方式求解最优解的（ B ）。 A 分治法 B 动态规
划法 C 贪心法 D 回溯法
18. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒
定。如下 ( A ) 说法不正确？A
A 让水桶大的人先打水，可以使得每个人排队时间之和最小
B 让水桶小的人先打水，可以使得每个人排队时间之和最小
C 让水桶小的人先打水，在某个确定的时间 t 内，可以让尽可能多的人打上水
D 若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样
19.哈弗曼编码的贪心算法所需的计算时间为 (
A O(n2n)
D O(n)
20.下面关于 NP 问题说法正确的是( B
A NP 问题都是不可能解决的问题
B P 类问题包含在 NP 类问题中
C NP 完全问题是 P 类问题的子集
B O(nlogn)
C O(2n)
B )。
)
C O(2n)
C 4k
D 2k
C O(2n)
D O(n)
B O(nlogn)
B O(nlogn)
D NP 类问题包含在 P 类问题中
21.背包问题贪心算法所需的计算时间为( B )
A O(n2n)
D O(n)
22.背包问题的回溯算法所需的计算时间为（ A ）
A O(n2n)
23.采用最大效益优先搜索方式的算法是（ A ）
A 分支界限发 B 动态规划法 C 贪心法 D 回溯法
24. 在棋盘覆盖问题中，对于 2k×2k 的特殊棋盘（有一个特殊方块），所需的 L 型骨牌的
个数是 （ A ）
A ( 4k – 1）/3 B 2k /3
25. 下列随机算法中运行时有时候成功有时候失败的是（C ）
A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法
26. 实现大整数的乘法是利用的算法（ C ）。
A 贪心法 B 动态规划法 C 分治策略 D 回溯法
二、填空题
1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。
2.矩阵连乘问题的算法可由 动态规划 设计实现。
3.从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。
4.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。
5.快速排序算法的性能取决于 划分的对称性 。
6.使用二分搜索算法在 n 个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复
杂性为 O（ 1 ），在最坏情况下，搜索的时间复杂性为 O（ logn ）。
三、解答题
1. 给定已按升序排好序的 n 个元素 a[0:n-1]，现要在这 n 个元素中找出一特定元素 x，返回
其在数组中的位置，如果未找到返回-1。 写出二分搜索的算法，并分析其时间复杂度
2. 分析最有搜索二叉树和 0/1 背包的时间复杂度
3. 试用动态规划算法实现最大子矩阵和问题：求 n×m 矩阵 A 的一个子矩阵，使其各元素
之各为最大
4 已知输入向量 a=（1,3,4，-2），给出用 FFT 的蝶形操作求输出向量 y 的结果，并分析出
FFT 的计算时间复杂度。
1.采用递归算法求递归方程 F(n)=F(n-1(+F(n-2)，算法描述如下（就是递归 fibonacci！）
问：算法共需要进行多少次递归调用（算法中没引用 F(i)一次称为一次递归调用）。有没有
更好的算法来计算 F(n)?若有请描述算法并分析复杂度。
2.如下算法是否产生平均分布的随即置换？为什么？
Permute-With-All(A)
n←length(A)
for i←1 to n
swap(A[i],A[RANDOM(1,n)])
注：RANDOM(1,n)随机、等可能地返回整数 k，1≤k≤n
3. 能否在给定的 s[n]中判断是否存在两个数的和为 x，并且时间复杂度是 nlgn，如果可以写
出程序的伪代码，否则给出理由。
6. 活动选择问题
（1）递归的时间复杂度分析
（2）动态规划的时间复杂度分析
（3）写出一个更优的算法，并且对其进行时间复杂度分析
7. 多项式乘法问题
描述一个高效的算法来解决复数之间的多项式乘法，多项式的系数为复数，未知数也为复数。
并且对此进行时间复杂度分析。
算法 2013 考试题
郑 55
填空：
给一系列的函数，根据渐进性，从大到小排列 n^3/2,nlgn,lgn,e^n,n!,n^2
动归的两个性质
贪心的两个性质
1）NP 问题： 2）P 问题
面试问题 雇一个人的概率： ，雇 n 个人的概率：
复杂度分为： 和 ；动归是牺牲 复杂度换取 复杂度
使用二分搜索算法在 n 个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂
性为 O（ 1 ），在最坏情况下，搜索的时间复杂性为 O（ logn ）。
选择：
1 摊还排序是（）情况下的（）代价
A 最优 B 最坏 C 平均 D 最好
2 动态规划的设计思想是 a
(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左
3 贪心算法的设计思想是 b
(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左
4 以下哪一个更可能描述实际一个有效的算法 d
(a)
5 蝶形操作的设计思想是 a
(a)分治法 (b)贪心算法 (c)动态规划 (d)回溯
6 以下哪一个不是 NPC 问题
(a)单源最短路径 (b)巡回售货员问题 (c)布尔可满足性问题 (d)大数分解
7 以下哪个不是几何研究中的基本操作
(b)
(c)
(d)
(b)n^2
(c)nlgn
(b)n^2
(c)nlgn
(a)+ (b)— (c)× (d)/
8 哪个问题不能用贪心算法解决
(a)活动安排 (b)哈夫曼编码 (c)分数背包 (d)0-1 背包
9 哪个问题不能用动态规划解决 c
(a)分数背包 (b)0-1 背包 (c)最长简单路径 (d)最短简单路径
10 插入排序的最好时间复杂度是 a
(a)n
(d)lgn
11 归并排序的时间复杂度是 c
(a)n
(d)lgn
12 算法分析中，记号 O 表示（B），记号Ω标售（A）,记号Θ表示（D）
A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界
13.n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。
如下 ( A ) 说法不正确？A
A 让水桶大的人先打水，可以使得每个人排队时间之和最小
B 让水桶小的人先打水，可以使得每个人排队时间之和最小
C 让水桶小的人先打水，在某个确定的时间 t 内，可以让尽可能多的人打上水
D 若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样
14.哈弗曼编码的贪心算法所需的计算时间为 (
A O(n2n)
D O(n)
15.下面关于 NP 问题说法正确的是( B
A NP 问题都是不可能解决的问题
B P 类问题包含在 NP 类问题中
C NP 完全问题是 P 类问题的子集
D NP 类问题包含在 P 类问题中
大题
B O(nlogn)
C O(2n)
B )。
)
四路归并排序：分解时分成四个，合并等其他步骤与二路归并相似，请写出核心算法，并分
析时间复杂度。
1. 矩阵链乘积的递归算法
n=1
T（n）= 1
n>=2
请详细分析该算法的时间复杂度
1. 给出最优二叉搜索树的程序代码和 p，q 概率
根据概率 1）求 e,w,root，2）画出二叉树的结构 3）请说出 root[i,j]有什么意义
（见 3621 大班试卷影印版的第五题）
1. FFt 蝶形操作 见 3621 大班试卷的影印版第九题
2. 字符串自动机构造，见书
2006-2007 学年第二学期《计算机算法设计与分析》试题
院系：软件学院
专业：软件工程
年级：2004 级
一．简答题（共 10 分）
略
f(n)=3n，g(n)=2n
f(n)=log n + 5，g(n)=log n2
f(n)=log n，g(n)=
二．计算题（35 分）
１．(6 分) 对下列各组函数 f(n)和 g(n)，确定 f(n)=O(g(n))或 f(n)=Ω(g(n))或 f(n)=θ(g(n))。
(1)
(2)
(3)
答：
(1)
(2)
(3)
f(n) = Ω(g(n))
f(n) = θ(g(n))
f(n) = O(g(n))
(2 分)
(2 分)
(2 分)
2．（８分）采用动态规划策略，计算 a=｛5,-3,7,-4,-5,9,-2,10,-3,2｝的最大子段和，并给出
这个最大子段和的起始下标和终止下标。［设数组 a 中的元素下标从１开始。］要求给出过
程。
答：
b[1]=5；
b[2]=max{b[1]+a[2]，a[2]}=max{2,-3}=2
b[3]=max{b[2]+a[3]，a[3]}=max{9,7}=9
b[4]=max{b[3]+a[4]，a[4]}=max{5,-4}=5
b[5]=max{b[4]+a[5]，a[5]}=max{0,-5}=0
b[6]=max{b[5]+a[6]，a[6]}=max{9,9}=9
b[7]=max{b[6]+a[7]，a[7]}=max{7,-2}=7
b[8]=max{b[7]+a[8]，a[8]}=max{17,10}=17
b[9]=max{b[8]+a[9]，a[9]}=max{14,-3}=14
b[10]=max{b[9]+a[10]，a[10]}=max{16,2}=16
(上述每两行１分，共５分)
最大子段和为 17（1 分）
（若数组下标从１开始）起始下标：６（１分），终止下标：８（１分）
（若数组下标从０开始）起始下标：５（0.5 分），终止下标：7（0.5 分）
３．（11 分）设有３件工作分配给３个人，将工作 i 分配给第 j 个人所花的费用为 Cij，现
将为每一个人都分配１件不同的工作，并使总费用达到最小。设：
要求：
（1）画出该问题的解空间树；（６分）
（2）写出该问题的剪枝策略(限界条件)；（1 分）
（3）按回溯法搜索解空间树，并利用剪枝策略对应该剪掉的子树打´；（２分）
（4）最终给出该问题的最优值和最优解。（２分）
答：
（1）
1
2
2
3
3
1
3
1
1
1
2
2
2
3
3
3
2
3
1
2
1
16
16
╳
9
9
9
╳
9
╳
╳
（每个分枝 1 分，或者是每层 2 分，共 6 分）
（2）当耗费大于等于当前最优值时，剪枝。（1 分）
（3）见上图。（每 2 个╳ 1 分，共 2 分）
（4）最优值： 9 （1 分）
最优解：2，1，3
４．（８分）给定两个序列 X=，Y=，请采用动态规划策略求出其
最长公共子序列。要求给出过程。
2
3
答：
j 0
1
yi B D
i
0 xi
0
0
0
1 A 0
2 B 0
1
1
3 C 0
4 B 0
1
0
0
1
1
1
4
C
0
0
1
2
2
5
A
0
1
1
2
2
B
0
1
2
2
3
5 Ａ 0
1
2
2
2
3
（上述表内每一行一分，共６分）
最长公共子序列为
（２分）
5．（2 分）考虑 n=3 时的 0-1 背包问题的实例：W={15,10,10}，P={50,30,30}，c=20。当 x[1]=1，
x[2]=0 时，请计算 Bound(2)。
答：
Bound(3)=50+5/10 * 20 = 65
(2 分)
三、算法填空题（共 10 分，每空 2 分）
给定 n 种物品和一个背包，物品 i 的重量是 w[i], 其价值是 p[i], 背包的容量为 c。设物品已
按单位重量价值递减的次序排序。每种物品不可以装入背包多次，但可以装入部分的物品 i。
求解背包问题的贪心算法如下：
float Knapsack (float x[ ], float w[ ], float p[ ],float c, int n)
{ float maxsum=
// maxsum 表示装进包的物品价值总和
for ( int i=1;i<=n; i++) x[i]=0 // x[i]=0 表示第 i 个物品未装进包
for (
;
)
)
if(
{ x[i] =1;
;
maxsum+=
c- = w[i];
}
else break;
;}
if (c>0) {x[i]=c/w[i];
return maxsum;
}
答：(共５个空，每空 2 分，总计 10 分)
０
int i=1；i<=n；ｉ++
w[i]<=C
p[i]
maxsum+ = p[i] * c / w[i]
四、算法设计及分析题（共 45 分）
1．（20 分）请用分治策略设计递归的二分检索算法，并分析其时间复杂性（要求给出每个
阶段所花的时间，在此基础上列出递归方程，并求出其解的渐进阶）。
答：（此题解法不唯一）
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
