算法设计与分析试卷A卷-20080525-参考答案-第二版-by zzm （含试题预测、课堂笔记）
试题答案：
一、简答题
1. 答：如果一个算法不需要额外的存储空间（除个别存储单元以外），我们把它称为是在
位的。 2. 答：如下图，求A到C的最短距离。Dijkstra算法只需一步，就计算出A到C最短路径
为A-C，长度为3；事实上，图中因为存在负权重的边，A到C的最短路径应是A-B-C，
长度为2。
A 3 C 4 B -2
3. 答：对问题的部分或全部输入做预处理，然后对获得的额外信息进行存储，以加速后面
问题的求解。我们把这个方法称为输入增强。
二、答： 解法一：
Mindist (A[0..n-1]) dist ← ∞
for i ← 0 to n-2 do for j ← i+1 to n-1 do if │A[i]-A[j]│ Mindist (A[0..n-1]) 将数组A复制到数组B； 用O(nlog n)的排序算法对Ｂ进行升序排序； dist ← B[1]-B[0]; dist ← │A[i]-A[j]│ for i ← 1 to n-2 do if B[i+1]-B[i] Return dist 解析：解法一将基本操作│A[i]-A[j]│ 三、答： （1） 求数组A中两个元素的最大差值； （2） 基本操作是：A[i] 其算法效率类型为O(n)。 1 解析：第（2）小题中，每次循环都要比较，但不是每次循环都要赋值，因而比较操作是基本操作。第（3）小题由于题目要求计算，最好写出基本计算过程。 四、答 kk-1k （1） x(2) = x(2) + 2； x(2k-1) = x(2k-2) + 2k-1； …… x(2) = x(1) + 2； x(1) = 1； kk k-1k+1 则x(2) = 2+ 2+ … + 2 +1 = 2 – 1 （2） O(log n) 五、答： 解法一： （1） 编码过程： D B C @ A 0.4 0.2 0.15 0.15 0 0.35 1 0 0 1.0 1 0 0.6 1 0.25 0.1 1 A，B，C，D，@的编码分别为111，100，101，0，110。 （2） 100010111001010解码后为：BDC@DCD 解法二： （1） 编码过程： D B C @ A 0.4 0.2 0.15 0.15 1 0.35 0 1 1 1.0 0 1 0.6 0 0.25 0.1 0 A，B，C，D，@的编码分别为000，011，010，1，001， （2） 100010111001010解码后为：DADBD@C 解析：哈夫曼树不唯一，且C和@出现频率相同，所以编码还有其他可能性，以上两解法仅供参考。 六、答： （1） h(30)=8；h(20)=9；h(56)=1；h(75)=9；h(31)=9；h(19)=8。开散列表如下： 2 0 1 56 …… 8 9 10 30 20 19 75 31 （2） 平均比较次数为：(1+1+2+1+2+3)/6 = 1.67 解析：数组里为散列值，元素存储在其散列值对应的链表中。 在（1）小题中，每次插入新的元素，是放在其散列值对应的链表的末端。例如：在以上基础上插入元素41的结果如下，请大家自己比较： 0 1 56 …… 8 9 10 30 20 19 75 41 31 七、答： （听说堆排序不做要求，估计会换成平衡二叉树的生成过程。） 八、答： （1） A = {1，3，4，9，13，34}和B = {2，5，16，22}合并为C的步骤如下： a) 1 < 2，故1插入C={}，得C={1}； b) 3 > 2，故2插入C={1}，得C={1，2}； c) 3 < 5，故3插入C={1，2}，得C={1，2，3}； d) 4 < 5，故4插入C={1，2，3}，得C={1，2，3，4}； e) 9 > 5，故5插入C={1，2，3，4}，得C={1，2，3，4，5}； f) 9 < 16，故9插入C={1，2，3，4，5}，得C={1，2，3，4，5，6}； g) 13 < 16，故13插入C={1，2，3，4，5，6}，得C={1，2，3，4，5，6，13}； h) 34 > 16，故16插入C={1，2，3，4，5，6，13}，得C={1，2，3，4，5，6，13， 16}； i) j) 34 > 22，故22插入C={1，2，3，4，5，6，13，16}，得C={1，2，3，4，5，6，13，16，22}； 34插入C={1，2，3，4，5，6，13，16，22}，得C={1，2，3，4，5，6，13，16，22，34}； （2） 因为合并排序就是交替遍历数组A和B，并把它们中的元素非递减地插入数组C中， 基本操作就是对A和B数组的遍历。假设A和B的规模分别为m和n，合并排序 3 算法最坏情况下的时间效率是O(m + n)。 解析：A和B自身内部已经排序 试题预测： 一、简答题 1. 简述什么是在位的算法？ 答：如果一个算法除了个别存储单元以外, 不需要额外的存储空间, 我们把它称为是在位的. 2. 简述什么是稳定的排序算法？ 答：如果一个排序算法保留了等值元素在输入中的相对顺序, 它就被称为是稳定的. 3. 某某排序算法的时间复杂度，是否稳定？ 4. 哪些排序算法是稳定的算法？哪些不是稳定的算法，请举出例子。 5. 哪些排序算法的时间复杂度是O(nlog n)？ 排序 直接插入排序 冒泡算法 快速排序 直接选择排序 希尔排序 堆排序 归并排序 基数排序 时间复杂度 平均情况 O(n) O(n) O(nlog n) O(n2) O(nlog n) O(nlog n) O(nlog n) O(d(n+r)) 22最坏情况 O(n) O(n) O(n2) O(n2) O(nlog n) O(nlog n) O(nlog n) O(d(n+r)) 22最好情况 O(n) O(n) O(nlog n) O(n2) O(nlog n) O(nlog n) O(d(n+r)) 空间复杂度 O(1) O(1) O(nlog n) O(1) O(1) O(1) O(1) O(n+r) 稳定性 稳定 稳定 不稳定 不稳定 不稳定 不稳定 稳定 稳定 解析：冒泡排序、快速排序、直接选择排序、直接插入排序比较基础，可能会考察。 6. 请简述符号t(n)∈θ(g(n)), t(n)∈Ω(g(n)),t(n)∈Ο(g(n))的含义。 答：t(n)∈θ(g(n))成立的条件是: 对于所有足够大的n, t(n)的上界由g(n)的常数倍所确定, 也就是说, 存在大于0的常数c和非负的整数n0, 使得: 对于所有的n>=n0来说, t(n)<=cg(n)； t(n)∈Ω(g(n))成立的条件是: 对于所有足够大的n, t(n)的下界由g(n)的常数倍所确定, 也就是说, 存在大于0的常数c和非负的整数n0, 使得: 对于所有的n>=n0来说, t(n)>=cg(n)； t(n)∈Ο(g(n)) 成立的条件是: 对于所有足够大的n, t(n)的上界和下界都由g(n)的常数倍所确定, 也就是说, 存在大于0的常数c1和C2和非负的整数n0, 使得: 对于所有的n>=n0来说, c2g(n)<=t(n)<=c1g(n) 解析：只要记住，θ(g(n))是t(n)<=cg(n)，也就是有上界；t(n)∈Ω(g(n)) 是t(n)>=cg(n)，也就是有下界；t(n)∈Ο(g(n))， c2g(n)<=t(n)<=c1g(n)，也就是上下界都有。C、C1、C2为某常数。其他语言可以自己组织，不影响大局。 7. 顺序查找和折半查找的时间效率类型。 答：O(n) ，O(log n) 4 二、分析代码效率类型 1. 常见的O(n)代码： Mindist (A[0..n-1]) dist ← ∞ for i ← 0 to n-1 do for j ← 0 to n-1 do if i≠j and │A[i]-A[j]│ 2. 常见的O(log n)代码： X（n） if i=1 return 1 2 return X(n/2)+n 3. 常见的O(n)代码： Secret(A[0..n-1]) min ← A[0]; max ← A[0] for i ← 1 to n do if A[i] < min min ← A[i] if A[i] > max max ← A[i] Return max-min 4. 常见的O(n3)代码： Sum(A[0...n-1][0..n-1][0..n-1]) S=0 for i ← 1 to n-1 do for j ← 1 to n-1 do for k ← 1 to n-1 do S+=A[i][j][k] Return S 5. 常见的O(nlog n)代码： 解析：分析代码效率类型，主要是观察代码形态。计算循环或递归的次数，认清基本 操作，对这两个进行分析，然后得出效率类型。 三、斐波那契数列 递归算法： Fib(n) 5