算法设计与分析C++语言描述(陈慧南版)课后答案

算法设计与分析C语⾔描述（陈慧南版）课后答案第⼀章15P1-3. 最⼤公约数为1。

快1414倍。

主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环）若考虑其他语句，则没有这么多，可能就601倍。

第⼆章32P2-8.（1）画线语句的执⾏次数为log n 。

(log )n O 。

划线语句的执⾏次数应该理解为⼀格整体。

（2）画线语句的执⾏次数为111(1)(2)16jnii j k n n n ===++=∑∑∑。

3()n O 。

（3）画线语句的执⾏次数为。

O 。

（4）当n 为奇数时画线语句的执⾏次数为(1)(3)4n n ++，当n 为偶数时画线语句的执⾏次数为 2(2)4n +。

2()n O 。

2-10.（1）当 1n ≥ 时，225825n n n -+≤，所以，可选 5c =，01n =。

对于0n n ≥，22()5825f n n n n =-+≤，所以，22582()n n n -+=O 。

（2）当 8n ≥ 时，2222582524n n n n n -+≥-+≥，所以，可选 4c =，08n =。

对于0n n ≥，22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。

（3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以22582()n n n -+=Θ。

2-11. (1) 当3n ≥时，3log log n n n <<，所以()20log 21f n n n n =+<，3()log 2g n n n n =+>。

可选 212c =，03n =。

对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。

注意：是f (n )和g (n )的关系。

算法设计与分析基础习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。

以下是一些典型的算法设计与分析习题及其答案。

习题1：二分查找算法问题描述：给定一个已排序的整数数组，编写一个函数来查找一个目标值是否存在于数组中。

答案：二分查找算法的基本思想是将数组分成两半，比较中间元素与目标值的大小，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

这个过程会不断重复，直到找到目标值或搜索范围为空。

```pythondef binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return Trueelif arr[mid] < target:low = mid + 1else:high = mid - 1return False```习题2：归并排序算法问题描述：给定一个无序数组，使用归并排序算法对其进行排序。

答案：归并排序是一种分治算法，它将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。

```pythondef merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1arr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print("Sorted array is:", arr)```习题3：动态规划求解最长公共子序列问题问题描述：给定两个序列，找到它们的最长公共子序列。

C语言课后习题标准答案第1章C语言概述一、简答题1．(1)语言简洁、紧凑,使用方便、灵活;（２）运算符丰富；(3)具有丰富的数据类型;（４)具有结构化的控制语句;(5）语法限制不太严格，程序设计自由度大；（6)C语言允许直接访问物理地址,能进行位（bit)操作，能实现汇编语言的大部分功能，可以直接访问硬件；(7）生成目标代码质量高,程序执行效率高;（8)用C语言写的程序可移植性好，基本上不作修改就能用于各种型号的计算机和各种操作系统。

2.顺序结构，分支结构,循环结构3.所谓算法就是为解决一个问题而采取的方法和步骤。

算法的特性：有穷性、确定性、输入、输出、可行性。

表示算法的方式:（1）用自然语言表示;(２）用流程图表示；(3)用N—Ｓ流程图表示；(4)用伪代码表示；（5）用计算机语言表示。

二、算法1．瓶子A里盛有醋瓶子B里盛有酱油那一个空瓶C将A中的醋倒入Ｃ将B中的酱油倒入Ａ将C中的醋倒入B2．输入一个数放在ａ中max＝a以下步骤重复9次:输入一个数放在a中如果a＞mａx，max=b打印mａx的值3．如果ﻩﻩa＜ｂtemp=aﻩa=bﻩﻩb＝teｍｐ如果ｃ＞aﻩtemｐ1=aﻩﻩｔｅmp2=ba=ｃﻩb＝tｅmp1ﻩｃ=temｐ2否则ﻩ如果ﻩｃ＞bﻩｔｅmp=bﻩb=cﻩc=ｔemp打印a，b，c的值4．i＝1sum=0以下程序循环１00遍：sum＝sum＋iﻩi＝ｉ+1打印sｕm的值5．如果（n除以3的余数为0并且n除以5的余数为０）n能够同时被3和5整除否则ﻩｎ不能够同时被3和5整除6．i=101以下语句循环５０遍：ﻩj=2ﻩflag=1ﻩ当j<(ｉ除以2的整数部分)时循环以下语句：ﻩﻩ如果i除以j的余数为零ﻩﻩﻩfｌaｇ=０ﻩﻩﻩ退出该循环如果flaｇ＝1ﻩﻩﻩ打印ｉ的值ﻩｉ=i+17．如果m<ｎﻩﻩtemp＝mﻩﻩm=nｎ=temｐi＝nj＝1做以下循环,直到m能够被i/j整除：如果i能够被j整除并且m能够被i／j整除i/j即是ｍ和n的最大公约数ﻩ跳出循环否则ﻩj=j+1打印ｉ/j的值8．ｄａta=b＊b—4*a＊c如果ｄata>０否则如果data=０ﻩx1=x2=—ｂ／2否则无实数解三、编程题1．mａin(){ﻩpｒintf（“########＃＃#########＃######＃＃##\n”）;ﻩｐrinｔf(“How do yoｕdo?\n”）;ﻩprintf(“＃###＃####＃###＃###＃######＃＃##＃#\n”)；}2．mａin(）｛adata b x2)(1+-=a data b x2)(2--=。

第11章 内 排 序
First 12
q 21
p 33
sorted
…
55
unsorted
26
42
…
(a)
First
③
q
p
sorted
unsorted
12
21
33
…
55
26
42
…
① ②
(b)
图11－3 链表的直接插入排序 (a) 插入26前；(b) 插入26后
第11章 内 排 序
与顺序表的直接插入排序一样，链表上的直接插入排序算 法首先将第一个记录视为只有一个记录的有序子序列，将第二 个记录插入该有序子序列中，再插入第三个记录，……，直到 插入最后一个记录为止。每趟插入，总是从链表的表头开始搜 索适当的插入位置。程序11－3中，指针p指示表中与待插入的 记录比较的结点，q指示p的前驱结点。指针sorted总是指向单链 表中已经有序的部分子表的尾部，而指针unsorted指向sorted的 后继结点，即待插入的记录结点，见图11－3(a)。如果待插入的 记录小于第一个记录，则应将其插在最前面。请注意，下面的 while循环总会终止。
1)
n(n 4
1)
(n
1)
O(n 2
)
(11－5)
AM(n)
n1
i1
i 2
2
1 2
n 1 i1
i＋2(n
1)
n(n 1) 4
2(n
1)
O(n 2
）
(11－6)
第11章 内 排 序
2．链表上的直接插入排序
直接插入排序也可以在链表上实现。程序11－3是在单 链表上的直接插入排序算法的C语言程序。单链表采用程序 11－1中描述的单链表结构类型。在单链表表示下，将一个 记录插入到一个有序子序列中，搜索适当的插入位置的操作 可从链表的表头开始。图11－3中，从11到55之间的记录已 经有序，现要插入26。我们从表头开始，将26依次与12、21 和33比较。直到遇到大于或等于26的记录33为止，将26插在 21与33之间。该插入操作如图11－3(b)所示。

第6章 树 例如，设有序表为(21, 25, 28, 33, 36, 43)，若要在表中 查找元素36，通常的做法是从表中第一个元素开始，将待查元素 与表中元素逐一比较进行查找，直到找到36为止。粗略地说，如 果表中每个元素的查找概率是相等的，则平均起来，成功查找一 个元素需要将该元素与表中一半元素作比较。如果将表中元素组 成图6－3所示的树形结构，情况就大为改观。我们可以从根结点 起，将各结点与待查元素比较，在查找成功的情况下，所需的最 多的比较次数是从根到待查元素的路径上遇到的结点数目。当表 的长度n很大时，使用图6－3所示的树形结构组织表中数据，可 以很大程度地减少查找所需的时间。为了查找36，我们可以让36 与根结点元素28比较，36比28大，接着查右子树，查找成功。显 然，采用树形结构能节省查找时间。
第6章 树
E
E
A
F
B
G
CD
LJ
M
N
T1
X
YZ
U T2
B
F
A
DC
G
JL
T3 N
M
(a)
(b)
图6－2 树的例子
(a) 树T1和T2组成森林；(b) 树T3
第6章 树
6.2 二 叉 树
二叉树是非常重要的树形数据结构。很多从实际问题中抽 象出来的数据都是二叉树形的，而且许多算法如果采用二叉树 形式解决则非常方便和高效。此外，以后我们将看到一般的树 或森林都可通过一个简单的转换得到与之相应的二叉树，从而 为树和森林的存储及运算的实现提供了有效方法。
第6章 树
图6－1描述了欧洲部分语言的谱系关系，它是一个后裔图， 图中使用的描述树形结构数据的形式为倒置的树形表示法。在 前几章中，我们学习了多种线性数据结构，但是一般来讲，这 些数据结构不适合表示如图6－1所示的层次结构的数据。为了 表示这类层次结构的数据，我们采用树形数据结构。在本章中 我们将学习多种不同特性的树形数据结构，如一般树、二叉树、 穿线二叉树、堆和哈夫曼树等。

因此 T (n) (n 2 ) （3） a 28, b 3, f n cn3
nlogb a nlog3 28 n3.033 ，则 f (n) c n 2 (nlogb a - ) ，其中可取 =0.04 。符合主定理
的情况 1 ，因此 T (n) (n3.033 )
21 21 当 n n0 时， f n g n ，所以 f n = g n 2 2
（2） f n n 2 logn ， g n n log 2 n
2 当 n 4 时， f n n 2 logn n 2 ， g n n log 2 n n 。因此可取 n0 4, c 1 ，当
g n
（1） f n 20n logn ， g n n+ log 3 n
f n 20n logn 21n ， g n n+ log 3 当 n 3 时， logn n log3 n 2n n 因此
因此可取 n0 3, c
f n g n ，所以 f n = g n
2-12 将下列时间函数按增长率的非递减次序排列
3 2
n
， log n ， log 2 n ， n log n ， n ! ， log(log(n)) ， 2 n ， n1 log n ， n 2
答： n1 log n
f ( n ) ( n m )
证明：
f (n) am nm am1nm1 a1n a0 F (n) am n m am1 n m1
a1 n a0
由 F (n) 单调性易知，存在 nt 0 ，使得 F (n) 取 n 1 ，且 nt0 nt ， F (nt0 ) 0 ，则 当 n nt0 时， F (n) 0 即： f (n) am n m am1 n m1

③ 其余元素
w[0][2] q[2] p[2] w[0][1] 15
k 1: c[0][0] c[1][2] c[0][2] min k 2 : c[0][1] c[2][2] w[0][2] 22 r[0][2] 2



17000
s[0][2]

0
m[1][3]

min
k k
1: m[1][1] m[2][3] 2 : m[1][2] m[3][3]
p1 p2 p4 p1 p3 p4


10000
s[1][3]

2
m[1][3]

min

k k

0 : m[0][0] m[1][3] 1: m[0][1] m[2][3]
第七章课后习题
姓名：赵文浩 学号：16111204082 班级：2016 级计算机科学与技术 7-1 写出对图 7-19 所示的多段图采用向后递推动态规划算法求解时的计算过程。
3
1
3
1
6
5
0
2
6
6
3
4
4 6
5
2
7
8
3
2
8
5
2
7
解析：
V 5 cost(5,8) 0 d (5,8) 8
V4
cos t(4, 6) minc(6,8) cos t(5,8) 7 cos t(4, 7) minc(7,8) cos t(5,8) 3
k 1: c[0][0] c[1][3] c[0][3] min k 2 : c[0][1] c[2][3] w[0][3] 25

此时i1即在本次循环中先执行swapa0a1将第二个元素与第一个元素互换下面执行perma1n根据假设可知该语句产生以a1为第一个元素余下k1个元素的全排列
第一章课后习题
姓名：赵文浩 学号：16111204082 班级：2016 级计算机科学与技术
1-4 证明等式 gcd(m,n)=gcd(n mod m, m) 对每对正整数 m 和 n，m>0 都成立。
1-13 写一个递归算法和一个迭代算法计算二项式系数：
#include<stdio.h> int Coef_recursive(int n,int m);//递归算法 int Coef_iteration(int n,int m);//迭代算法 int Factorial(int n);//计算 n 的阶乘 int main() { int n,m;
1-12 试用归纳法证明程序 1-7 的排列产生器算法的正确性。
证明：主函数中，程序调用 perm(a,0,n)，实现排列产生器。 ① 当 n=1 时，即数组 a 中仅包含一个元素。函数内 k=0，与(n-1)=0 相等，因此函 数内仅执行 if(k==n-1)下的 for 语句块，且只执行一次。即将 a 数组中的一个元 素输出，实现了对一个元素的全排列。因此当 n=1 时，程序是显然正确的； ② 我们假设程序对于 n=k-1 仍能够满足条件， 将 k-1 个元素的全排列产生并输出； ③ 当 n=k 时，程序执行 else 下语句块的内容。首先执行 swap(a[0],a[0])，然后执 行 Perm(a,1,n)，根据假设②可知，该语句能够产生以 a[0]为第一个元素，余下 (k-1)个元素的全排列； 然后再次执行 swap(a[0],a[0])， 并进行下一次循环。 此时 i=1， 即在本次循环中， 先执行 swap(a[0],a[1])， 将第二个元素与第一个元素互换， 下面执行 Perm(a,1,n)， 根据假设②可知， 该语句产生以 a[1]为第一个元素， 余下(k-1)个元素的全排列； 以此类推，该循环每一次将各个元素调到首位，通过执行语句 Perm(a,1,n)以及 基于假设②，能够实现产生 k 个元素的全排列。 因此 n=k 时，程序仍满足条件。 ④ 综上所述，该排列器产生算法是正确的，证毕。

《算法分析与设计C》复习总成绩=平时成绩（30%）+考试成绩（70%）考试时间：2015年06月28日(16:00-17:50)试卷题型：一、 选择题（每空2分，共20分）二、 填空题（每空2分，共20分）三、 证明题（每题5分，共10分）四、 问答题（每题10分，共50分）第一章 算法求解基础算法的概念算法特征（输入、输出、确定性、可行性、有穷性）——掌握每种特征的含义、算法和程序的区别描述算法的方法（自然语言、流程图、伪代码、程序设计语言）欧几里德算法（辗转相除法）——递归/迭代程序实现及其变形常见算法种类——精确算法、启发式算法、近似算法、概率算法第二章 算法分析基础算法复杂度——运行一个算法所需的时间和空间。

好算法的四个特征（正确性、简明性、效率、最优性）正确性vs健壮性vs可靠性最优性——算法（最坏情况下）的执行时间已达到求解该类问题所需时间的下界。

影响程序运行时间的因素（程序所依赖的算法、问题规模和输入数据、计算机系统性能）算法的渐近时间复杂度 ——数量级上估计（Ο、Ω、Θ）最好、最坏、平均时间复杂度——定义——课后习题2-8（通过考察关键操作的执行次数）时间复杂度证明——课后习题2-10，2-13，2-17算法按时间复杂度分类：多项式时间算法、指数时间算法多项式时间算法：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3) 指数时间算法：O(2n)<O(n!)<O(n n)第五章 分治法分治法——求解的基本要素：将一个难以直接求解的复杂问题分解成若干个规模较小、相互独立但类型相同的子问题，然后求解这些子问题；如果这些子问题还比较复杂而不能直接求解，还可以继续细分，直到子问题足够小，能够直接求解为止；最后将子问题的解组合成原始问题的解。

这种问题求解策略称为分治法。

分治法很自然的导致一个递归算法。

平衡子问题思想递归算法的时间复杂度分析:递推式T(n)=aT(n/b)+cn k，T(1)=c——递推式中每部分的含义——求解得到算法的渐近时间复杂度（分三种情况）——改进思路求最大最小元二分搜索算法框架对半搜索——程序实现——对半搜索二叉判定树（树的构成）——对半搜索二叉判定树性质（左右子树结点数、树高等）——对半搜索的时间复杂度分析（搜索成功/失败、最好/最坏/平均）。

int main() { int n, x, *a; cin >> n; a = new int[n]; for (int i = 0; i < n; i++) cin >> a[i]; cin >> x; if (Triple_search(a, 0, n - 1, x) == -1) cout << "NotFound!" << endl; else cout << Triple_search(a, 0, n - 1, x) << endl; delete []a; return 0; } int Triple_search(int a[], int l, int r, int x) { if (l <= r) { int m1 = l + (r-l)/3; int m2 = l + (r-l)*2/3; if (a[m2]<x) return Triple_search(a, m2 + 1, r, x); else if (a[m1] < x && a[m2] > x) return Triple_search(a, m1 + 1, m2 - 1, x); else if (a[m1] > x) return Triple_search(a, l, m1 - 1, x); else if (a[m1] == x) return m1; else if (a[m2] == x) return m2; } return -1; }
（3） 分析算法的时间复杂度 上述算法的时间复杂度为 n 2
5-19 给定 n 个点， 其坐标为 xi , y j 0 i n 1 ， 要求使用分治策略求解设计算 法，算出其中距离最近的两个点。两点间的距离公式为： （1） 写出算法的伪代码；

第9章 跳表和散列表 typedef int KeyType; typedef struct entry{ KeyType Key; DataType Data ; }Entry; typedef Entry T; typedef struct skipnode{ T Element; struct skipnode* Link[1]; } SkipNode;
函数CreateSkipList同时为表头结点、表尾结点和Last数组 分配空间。表头结点中有MaxLevel+1个用于指向各级链的指针， 它们被初始化为指向表尾结点。
第9章 跳表和散列表
9.2.2 跳表的搜索
本小节中我们介绍两个搜索跳表的函数 Search和SaveSearch。 前者是字典(集合)上定义的函数，后者是为了实现插入和删除 运算而设计的私有函数，并不面向用户。SaveSearch函数除了 包括Search函数的全部功能外，还把每一级遇到的最后一个结 点的地址存放在数组Last中。
第9章 跳表和散列表
例如要在图9－1(c)的跳表中搜索关键字值43。首先由第2层 表头指针开始向右搜索，令22与43比较，因为22<43，向右搜索； 令与43比较，现有≥43，所以下降到1层；令48与43比较，这 时 有 48≥43 ， 再 次 下 降 到 第 0 层 ； 最 后 令 43 与 43 比 较 ， 这 时 有 43≥43。在第0层的元素关键字值与待查关键字值比较后，还需 最后进行一次比较，以确定两关键字值是否相等，若两者相等， 则搜索成功，否则搜索失败。所以，在搜索过程中，与待查关 键字值43比较的跳表中的关键字值依次为22，，48，43，43。
第9章 跳表和散列表
当我们用C语言描述结点结构类型SkipNode时，我们定义 了长度为1的指针数组struct skipnode* Link[1]，事实上，数组 Link的实际长度在动态分配跳表的结点空间时确定。函数 SkipNode* NewSkipNode(int lev)用于在动态创建跳表结点时， 根据所确定的该结点的级数(层次)申请元素域和指定数目的指 针域所需的空间大小。数组名称Link是该数组存储块的地址。

令c1=min（a1,b1）,c2=max(a2，b2)，则
C1*(g1+g2）<= t1(n)+t2(n) <=c2（g1+g2）—----(3）
不失一般性假设max(g1（n）,g2(n))=g1（n)。
显然，g1(n)+g2（n）<2g1（n)，即g1+g2〈2max(g1，g2）
又g2（n）〉0，g1（n)+g2(n)>g1(n)，即g1+g2>max（g1，g2).
算法设计与分析基础课后练习答案
习题1.1
4。设计一个计算 的算法，n是任意正整数。除了赋值和比较运算，该算法只能用到基本的四则运算操作。
算法求
//输入:一个正整数n 2
//输出：。
step1：a=1；
step2:若a*a<n转step 3，否则输出a；
step3：a=a+1转step 2;
5. a．用欧几里德算法求gcd（31415,14142）。
b。该算法稳定吗?
c.该算法在位吗?
解：
a。该算法对列表”60,35，81,98,14,47”排序的过程如下所示:
b.该算法不稳定.比如对列表"2，2＊”排序
c.该算法不在位.额外空间for S and Count[]
4.(古老的七桥问题)
第2章
习题2。1
7。对下列断言进行证明：(如果是错误的，请举例)
Else return A[n—1］
a.该算法计算的是什么?
b.建立该算法所做的基本操作次数的递推关系并求解
解：
a.计算的给定数组的最小值
b.
9。考虑用于解决第8题问题的另一个算法,该算法递归地将数组分成两半。我们将它称为Min2（A［0..n-1］）

参考答案第1章一、选择题1. C2. A3. C4. C A D B5. B6. B7. D 8. B 9. B 10. B 11. D 12. B二、填空题1. 输入；输出；确定性；可行性；有穷性2. 程序；有穷性3. 算法复杂度4. 时间复杂度；空间复杂度5. 正确性；简明性；高效性；最优性6. 精确算法；启发式算法7. 复杂性尽可能低的算法；其中复杂性最低者8. 最好性态；最坏性态；平均性态9. 基本运算10. 原地工作三、简答题1. 高级程序设计语言的主要好处是：（l）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好、重用率高；（4）把复杂琐碎的事务交给编译程序，所以自动化程度高，发用周期短，程序员可以集中集中时间和精力从事更重要的创造性劳动，提高程序质量。

2. 使用抽象数据类型带给算法设计的好处主要有：（1）算法顶层设计与底层实现分离，使得在进行顶层设计时不考虑它所用到的数据，运算表示和实现；反过来，在表示数据和实现底层运算时，只要定义清楚抽象数据类型而不必考虑在什么场合引用它。

这样做使算法设计的复杂性降低了，条理性增强了，既有助于迅速开发出程序原型，又使开发过程少出差错，程序可靠性高。

（2）算法设计与数据结构设计隔开，允许数据结构自由选择，从中比较，优化算法效率。

（3）数据模型和该模型上的运算统一在抽象数据类型中，反映它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，灵活地满足用户要求。

（4）由于顶层设计和底层实现局部化，在设计中出现的差错也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、删、改也都是局部的，因而也都容易进行。

b.该算法稳定吗?
c.该算法在位吗?
解:
a.该算法对列表”60,35,81,98,14,47”排序的过程如下所示:
b.该算法不稳定.比如对列表”2,2*”排序
c.该算法不在位.额外空间for S and Count[]
4.(古老的七桥问题)
第2章
习题2.1
7.对下列断言进行证明:(如果是错误的,请举例)
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)
7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?
Hint:
对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n,即
b.有a可知计算gcd（31415，14142）欧几里德算法做了11次除法。
连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142和2·14142之间，所以欧几里德算法比此算法快1·14142/11≈1300与2·14142/11≈2600倍之间。
Else temp1←Min2(A[l..(l+r)/2])
Temp2←Min2(A[l..(l+r)/2]+1..r)
If temp1≤temp2 return temp1
Else return temp2
a.建立该算法所做的的操作次数的递推关系并求解
b.算法Min1和Min2哪个更快?有其他更好的算法吗?
1,2,5,10---分别代表4个人, f—手电筒
4.对于任意实系数a,b,c,某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)

第12章 文件和外排序
1) 串行处理文件 串行处理文件(图12－2)是无序的，对这样的文件按关键字 值的搜索只能采取顺序搜索的方法进行，即从文件的第一个记 录开始，依次将待查关键字值与文件中的记录的关键字值进行 比较，直到成功找到该记录，或直到文件搜索完毕，搜索失败 为止。因此通常搜索时间比较长。
一般情况下，设l和u分别是搜索范围内的最小块号和最大 块号，L和H分别是该搜索范围内的最小关键字值和最大关键字 值，则下一次读入内存的块号i为:
i
1
K-L H-L
(u
1)
(12－2)
第12章 文件和外排序
这时：
若K<Li，则下一次被搜索的块号的范围为[l, i－1]，并且新的 H将是Li；
若Li≤K≤Hi，则i即为所求的块，可在该块中去搜索待查关键字 值K；
对于无法事先知道记录被访问频率的应用，可以按第7章介 绍的自组织线性表的方式组织成自组织文件。具体方法有：计 数方法(count)、移至开头法(Move-To-Front)和互换位置法 (Transposition)。
第12章 文件和外排序
(2) 顺序处理文件 顺序处理文件已按关键字值排序。有序表上的各种搜索方 法原则上都可以用于顺序处理文件的搜索，如顺序搜索和二分 搜索等。但是由于文件是外存上的数据结构，在考虑算法时， 必须尽量减少访问外存的次数，因此顺序处理文件的搜索算法 有自己的特点。下面介绍顺序处理文件上的分块插值搜索。
第12章 文件和外排序
文件是存在外存储器上的。为了有效分配外存空间，我 们可以将多个扇区构成一个簇(cluster)。簇是文件的最小分配 单位。簇的大小由操作系统决定。文件管理器(file manager)是 操作系统的一部分，它负责记录一个文件由哪些簇组成。 UNIX操作系统按扇区分配文件空间，并称之为块(block)。为 了与逻辑文件和文件的逻辑记录相对应，文件存储器上的文 件称为物理文件(physical file)，一簇或块(物理块)中的信息称 为物理记录。用户读/写的记录是指逻辑记录，查找该逻辑记 录所在的物理块是操作系统的职责。

2i1T 2 2 i 1 n log n 2n 4n 2n i 2 2i1 4 2n log n log n 1 i 2 i 1 n
2n 2n log 2 n 2n log n log 2 n 3log n 2 n n log 2 n n log n

if(a[mid]<b[i]) left=mid; else if(a[mid]>b[i]) right=mid; else {cnt=mid; break;} }while(left<right-1) if(a[left]<b[i]) cnt=left; elsecnt=left-1; if(k>cnt) { if(cnt>0) { for(j=0;j<cnt;j++) { temp[j]=a[r]; r++; } left=cnt; k-=cnt; } else { temp[j]=b[i]; left=0; k--; } } else { for(j=0;j<k;j++) { temp[j]=a[r]; r++; } left=cnt; k-=cnt; return temp[k-1]; } } } } 第六章 1.由题可得：
E log n ， n 1 I n E 2n n E 成功搜索的平均时间复杂度为 As n 1 log n 。 n n n 其中， I 是二叉判定树的内路径长度， E 是外路径长度，并且 E I 2n 。 Au n
2-10. （ 1 ） 当 n 1 时 ， 5n 2 8n 2 5n 2 ， 所 以 ， 可 选 c 5 ， n0 1 。 对 于 n n0 ，