999kao.com
算法设计与分析(第2版)王红梅胡明习题答案
● 算法是问题求解过程的精确描述， 它为解决某一特定类型的问题规定了一个运算过程。以下关于算法的叙述中，错误的是（62）。
（62）
A.流程图（flow chart）是算法的一种图形表示方法
B.用伪代码描述的算法易于转换成程序
C.用 N/S盒图可以保证算法的良好结构（即由顺序、选择和重复结构来表示算法）
D.用 E-R 图可以同时描述算法步骤和数据模型
●试题一
阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R0..n
2．每循环一次插入一个R［i］
循环：i以1为步长，从2到n，反复执行
①准备
X<-R［i］； (1) ；high<-i-1；
②找插入位置
循环：当 (2) 时，反复执行
(3)
若X．key<R［mid］．key
则high<-mid-1
否则 (4)
③后移
循环：j以-1为步长，从 (5) ，反复执行
R［j+1］<-R［j］
④插入
R［low］<-X
3．算法结束
●试题一
【答案】(1)low<-1(2)low≤high(3)mid<-int((low+high)/2)(4)low<-mid+1
(5)i-1到low
【解析】这是一个通过自然语言描述二分插入排序的过程。整个过程由一个大循环来完成，在大循环中又包含两个循环，第一个循环是一个二分查找过程，第二循环是后移过程。
查找过程是在有序序列R［1］．R［i-1］中查找R［i］的过程，这是一个典型的折半查找过程。初始时指针low指向第一个元素，即R［1］，指针high指向第后一个元素，因此(1)空处应填写"low-1"。要查找R［i］，先与中间元素进行比较，中间元素使用mid指向，因此，(3)空处应填入"mid<-int((low+high)/2)"。当R［i］<R［mid］时，则在前半部分查找，将high<-mid-1，如果R［i］>R［mid］时，则在后半部分查找，因此(4)空处应填"low<-mid+1"。那什么时候结束呢?显然，一种情况是已经找该元素，由于题目中已经假设元素互不相同，这种情况不会发生，二是没有找到该元素，即指针low和指针high之间的没有元素了，所以(2)空处应填写"low≤high"。(5)空所在循环是进行数据移动，结合下面语句，可以判断循环是从i-1开始，到什么时候结束呢?通过分析，可以知道，最终要把R［i］放在R［low］的位置，循环要到low时结束，因此(5)空处应填写"i-1到low"。
A.具象图形，理性抽象图形，感性抽象图形。
B. 具象图形，冷抽象图形，热抽象图形。
C. 自然主义的形式，几何抽象形式，自由抽象形式。
D. 欧几里德形，非欧几里德形，随机图形。
阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)
[算法]
1．变量声明
X: Data Type
i,j,low, high,mid,r:0..n
2．每循环一次插入一个R[i]
循环：i以1为步长，从2到n，反复执行。
(1)准备
X←R[i];(1); high←i-1;
(2)找插入位置
循环：当(2)时，反复执行。
(3)
若X.key＜R[mid].key
则high←mid-1;
否则 (4)
(3)后移
循环：j以-1为步长，从(5)，反复执行。
R[j+1]←R[j]
(4)插入
R[low]←X
3．算法结束
(1)low←1 (2)low=high (3)mid←int((low+high)/2) (4)low←mid+1 (5)i-1到low 解析： 本题考查使用二分插入法对无序数组排序的伪码实现。
在做题前，我们需要先大概明白二分插入法的基本思想和步骤，其基本思想是(设 R[low，…，high]是当前的插入区间)：
(1)将要插入的数取出放在X中；
(2)确定区间的中点位置：mid=[(low+high)/2]；
(3)确定插入位置，将待插入的k值与R[mid].key比较，具体方法如下：
·若R[mid].key＞k，则由排序后表的有序性可知R[mid,…，n].key均大于k，因此，插入区间是左子表R[low,…，high]，其中high=mid-1。
·若R[mid].keyk，则要插入的k必在mid的右子表R[mid+1，…，high]中，其中 low=mid+1。
(4)在上面的过程中，low逐步增加，而high逐步减少，直到highlow，则找到插入位置为low，然后循环移动位置low后面的元素，再插入数值。
(5)重复上述过程，直到所有数都被插入。
有了上面的分析，我们再来看程序伪代码，第(1)空处在准备阶段，准备阶段要完成的任务是给变量赋初值，high←i-1将数组中的最后一个位置赋给了插入指针high，因为插入的范围是数组的整个范围，那么第(1)空应该用来将数组的第一个位置赋给插入指针low，因此答案为low←1。
第(2)空是找插入位置用的循环条件，根据我们上面的分析，要直到highlow时，才能确定插入的位置；而在low=high时，循环一直执行，结合程序的内容，知道此空答案为low=high。
第(3)空很明显是用来确定区间的中间位置，但mid有可能为小数，在程序中我们用取整的方法来去掉小数部分，因此，此空答案为mid-int((low+high)/2)。
第(4)空是条件X.keyR[mid].key不成立的情况下执行的语句，如果条件为假，则说明要插入的数大于中间位置的数，应该在其右区间里进行插入，根据分析知道，这时左指针low应该改变，这个空就是用来实现这个功能的，因此，答案为low←mid+1。
第(5)空在后移的循环操作中，作为后移的循环判断条件，在找到插入位置后，进行插入前，我们需要一个空间来存放插入的值。从程序中不难看出，是将待插入位置后面的所有元素向后移动一位，而待插入位置存放在low中，因此，此空答案为i-1到 low。
阅读下列算法说明和流程图1，回答问题1至问题3。
[算法说明]
某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(占用)。客房是以房间(不是床位)为单位出租的。
本算法根据几个散客的要求预订一间空房。程序的输人为：人数M，房间等级要求R(R =0表示任意等级都可以)。程序的输出为：所有可供选择的房间号。
流程图1描述了该算法。
假设当前该旅馆各个房间的情况见表3。
当输入M=4，R=0时，该算法的输出是什么?
101,301 解析：当M=4，R=0表示客人数为4，对房间等级没有要求，根据流程图，依次判断各个房间是否满足要求，101有4张床且房间空闲，满足要求；102、202已被占用，排除，201床数为34，排除；301有6张床，且未被占用，满足条件，所以，输出结果为：101，301。
算法设计与分析(第2版)王红梅胡明习题答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，17071783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3输出m 3设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C+描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2022整除。 #include using namespace std; int main() double value=0; 图 七桥问题 for(int n=1;nvalue; for (int i = 2;i!=value;+i) while (value % i = 0 ) k+=i;有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来 第二趟：甲，丙过桥且甲回来 第一趟：甲，丁过桥 一共用时19小时 9欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动为什么 设最初两个数较大的为a, 较小的为b ，两个数的最大公约数为factor 。 则最终能出现的数包括: factor, factor*2, factor*3, ., factor*(a/factor)=a. 一共a/factor 个。 如果a/factor 是奇数，就选择先行动；否则就后行动。 习题2 1如果T 1(n )=O (f (n )，T 2(n )=O (g (n )，解答下列问题： （1）证明加法定理：T 1(n )T 2(n )=maxO (f (n ), O (g (n )； （2）证明乘法定理：T 1(n )T 2(n )=O (f (n )O (g (n )； （3）举例说明在什么情况下应用加法定理和乘法定理。 ,（1） （2） （3）比如在 for （f(n)） for(g(n) 中应该用乘法定理 如果在“讲两个数组合并成一个数组时”，应当用加法定理 2考虑下面的算法，回答下列问题：算法完成什么功能算法的基本语句是什么基本语句执行了多少次算法的时间复杂性是多少 （1） 完成的是1-n 的平方和 基本语句：s+=i*i ，执行了n 次 时间复杂度O （n ） （2） （2）完成的是n 的平方 （1）int Stery(int n) int S = 0; for (int i = 1; i -=1 )1(314 )(n n T n n T （2）? ?+=1)3(211)(n n n T n n T (1) int T(int n) if(n=1) return 4; else if(n1) return 3*T(n-1); (2) int T(int n) if(n=1) return 1; else if(n1) return 2*T(n/3)+n; 5. 求下列问题的平凡下界，并指出其下界是否紧密。 （1）求数组中的最大元素； （2）判断邻接矩阵表示的无向图是不是完全图； （3）确定数组中的元素是否都是惟一的； （4）生成一个具有n 个元素集合的所有子集 (1) (n) 紧密 (2) (n*n) (3) (logn+n )（先进行快排，然后进行比较查找） （1）for (i = 1; i =summax) summax=temp; x=x0;1.1.11.1.2变位词。给定两个单词，判断这两个单词是否是变位词。如果两个单词的字母完全相同，只是位置有所不同，则这两个单词称为变位词。例如，eat 和tea 是变位词。 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系。 2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，算法的时间复杂性可达到O (n )。 O(N)=2*O(N/2)+x O(N)+x=2*O(N/2)+2*x a*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 由此可知，时间复杂度可达到O(n); 3.分治策略一定导致递归吗如果是，请解释原因。如果不是，给出一个不包含递归的分治例子，并阐述这种分治和包含递归的分治的主要不同。 不一定导致递归。 如非递归的二叉树中序遍历。 这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。 4. 对于待排序序列(5, 3, 1, 9)，分别画出归并排序和快速排序的递归运行轨迹。 归并排序： 第一趟：（5,3）（1,9）； 第二趟：（3,5,1,9）； 第三趟：（1,3,5,9）； 快速排序： 第一趟：5（,3,1,9）；设计分治算法求一个数组中的最大元素，并分析时间性能。 设计分治算法，实现将数组An中所有元素循环左移k个位置, 要求时间复杂性为O(n)，空间复杂性为O(1)。例如，对abcdefgh循环左移3位得到defghabc。 设计递归算法生成n个元素的所有排列对象。 #include using namespace std; int data100; 设计分治算法求解一维空间上n个点的最近对问题。 参见4.4.1最近对问题的算法分析及算法实现 9. 在有序序列(r1, r2, , r n)中，存在序号i（1in），使得r i=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。 在
阅读以下说明和算法，完善算法并回答问题。
【说明】
假设以二维数组G[1..m，1..n)表示一幅图像各像素的颜色，则G[i，j]表示区域中点(i，j)处的颜色，颜色值为0～k的整数。
下面的算法将指定点(i0，j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0，j0)同色的上、下、左、右可连通的点组成同色邻接区域。
例如，一幅8×9像素的图像如图2-1所示。设用户指定点(3，5)，其颜色值为0，此时其上方(2，5)、下方(4，5)、右方(3，6)邻接点的颜色值都为0，因此这些点属于点(3，5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点(见图2-1中的阴影部分)。将上述同色区域的颜色替换为颜色值7所得的新图像如图2-2所示。
【算法】
输入：矩阵G，点的坐标(i0，j0)，新颜色值newcolor。
输出：点(i0，j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。
算法步骤(为规范算法，规定该算法只在第七步后结束)如下。
第一步：若点(i0，j0)的颜色值与新颜色值newcolor相同，则(1)；
第二步：点(i0，j0)的颜色值→oldcolon创建栈S，并将点坐标(i0，j0)入栈；
第三步；若(2)，则转第七步；
第四步；栈顶元素出栈→(x,y)，并(3)；
第五步；1)若点(x，y-1)在图像中且G[x，y-1]等于oldcolor，则(x,y-1)入栈S；
2)若点(x，y+1)在图像中且GIx，y+1]等于oldeolor，则(x，y+1)入栈S；
3)若点(x-1，y)在图像中且G[x-1，y)等于oldcolor，则(x-1，y)入栈S；
4)若点(x+1，y)在图像中且G[x+1，y)等于oldcolor，则(x+1，y)入栈S；
第六步：转(4)；
第七步：算法结束。
【问题】
是否可以将算法中的栈换成队列?回答；(5) 。
(1)转第七步 (2)栈S空，或等价的文字描述 (3)G[x,y]←newcolor，或G[x,y]=newcolor，或等价的文字描述 (4)第三步 (5)可以 解析：本题考查栈结构在算法中的应用。
栈或(和)队列常在某些应用中用来临时存储需要处理的元素，因此，其基本应用方式为：首先令一个(或多个)元素入栈(队列)，然后在栈(队列)非空的情况下，栈顶(队头)元素出栈(队列)并进行处理，然后令与该栈顶(队头)元素相关的其他元素入栈(队列)，再从判栈(队列)空开始重复以上过程。
根据题目说明部分的描述，所有与点(i0，j0)同色的上、下、左、右可连通的点组成同色邻接区域。要置换一个同色邻接区域中所有点的颜色，可先将所有需要改变颜色的点的坐标记录下来，然后逐个地改变其颜色值；也可采取找出一个点、处理一个点的方式进行颜色置换。题中给出的算法属于后一种情况。
显然，算法中需要一个存储空间，用于临时存储需要置换颜色的点的坐标，使每个需要处理的元素都进、出该存储区域一次，算法中的栈起的就是这个作用。实际上，对区域中各点的颜色置换的顺序是无关紧要的，因此，将算法中的栈换成队列不会影响算法的输出。
在本题中，若新的颜色值与同色区域中的原颜色相同，则无需置换。因此空 (1)处应填入“转第七步”。算法第二步先记下点(i0，j0)所在区域的原颜色，并令点(i0，j0)入栈，之后就是基于栈非空的操作了，因此空(2)处应填入“栈S为空”。第三步令栈顶元素出栈并修改对应点的颜色值，空(3)处应填入“修改(x，y)处的颜色值为newcolor"。算法中必然有一步能使算法步骤循环处理，因此第六步中的空(4)处应填入“第三步”。
阅读以下说明和算法，完善算法并回答问题，将解答写在对应栏内。
[说明]
假设以二维数组G[1..m,1..n]表示一幅图像各像素的颜色，则G[i,j]表示区域中点(i,j]处的颜色，颜色值为0到k的整数。
下面的算法将指定点(i0,j0)所在的同色邻接区域的颜色置换为给定的颜色值。约定所有与点(i0,j0)同色的上、下、左、右可连通的点组成同色邻接区域。
例如，一幅8×9像素的图像如图1-1所示。设用户指定点(3,5)，其颜色值为0，此时其上方(2,5)、下方(4,5)、右方(3,6)邻接点的颜色值都为0，因此这些点属于点(3,5)所在的同色邻接区域，再从上、下、左、右四个方向进行扩展，可得出该同色邻接区域的其他点(见图1-1中的阴影部分)。将上述同色区域的颜色替换为颜色值7所得的新图像如图1-2所示。
[算法]
输入：矩阵G，点的坐标(i0,j0)，新颜色值newcolor。
输出：点(i0,j0)所在同色邻接区域的颜色置换为newcolor之后的矩阵G。
算法步骤(为规范算法，规定该算法只在第七步后结束)：
第一步：若点(i0,j0)的颜色值与新颜色值newcolor相同，则(1)；
第二步：点(i0,j0)的颜色值→oldcolor；创建栈S，并将点坐标(i0,j0)入栈；
第三步：若(2)，则转第七步；
第四步：栈顶元素出栈→(x,y)，并(3)；
第五步：
1) 若点(x,y-1)在图像中且G[x,y-1]等于oldcolor,则(x,y-1)入栈S；
2) 若点(x,y+1)在图像中且G[x,y+1]等于oldcolor,则(x,y+1)入栈S；
3) 若点(x-1,y)在图像中且G[x-1,y]等于oldcolor,则(x-1,y)入栈S；
4) 若点(x+1,y)在图像中且G[x+1,y)等于oldcolor,则(x+1,y)入栈S：
第六步：转(4)；
第七步：算法结束。
[问题]
是否可以将算法中的栈换成队列?回答：(5)。
(1)转第七步;(2)栈为空;(3)newcolor→G[x,y];(4)转第三步;(5)可以
回路问题
Euler回路(DFS)
定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点）
Hamilton回路
定义：经过图的每个顶点仅一次的回路。
一笔画
充要条件：图连通且奇点个数为0个或2个。
阅读以下说明和流程图，回答问题1-2，将解答填入对应的解答栏内。
[说明]
下面的流程图采用欧几里得算法，实现了计算两正整数最大公约数的功能。给定正整数m和 n，假定m大于等于n，算法的主要步骤为：
(1)以n除m并令r为所得的余数；
(2)若r等于0，算法结束；n即为所求；
(3)将n和r分别赋给m和n，返回步骤(1)。
[流程图]
[问题1] 将流程图中的(1)～(4)处补充完整。
[问题2] 若输入的m和n分别为27和21，则A中循环体被执行的次数是(5)。
[问题1] (1) n＞m或nm或其它等效形式 (2) m←t (3) n←r (4) m%n [问题2] (5) 1 解析：(1)～(2)当n的值大于(等于)m时，应交换两者的值，再使用欧几里得算法；
(3)～(4)略；
(5)m，n和r在执行循环A前后的值分别为：
假设该商务交流中心当前各个房间的情况如表2-14所示。
当输入M=3，R=0时，该算法的输出是(1)。
当输入M=2，R=1时，该算法的输出是(2)。
(1)1101 1202 1302 (2)1201 解析：当输入M=3，R=0时，表示客人的人数为3，对房间的等级没有要求，因此，只要房间的床铺足够且房间未被占用即可满足要求。换言之，在表2-14中NBED列中的值大于等于3，STATUS列中的值为0即可满足条件，因此输出的结果为：110112021302。
当输入M=2，R=1时，表示客人的人数为2，要求房间的等级为1级，因此，在房间的床铺足够且房间未被占用时，还要求房间的等级为1级才可满足要求。换言之，表2-14中RANK列中的值等于1，NBED列中的值大于等于2，STATUS列中的值为0即可满足条件，因此，输出的结果为：1201。