● 算法是问题求解过程的精确描述, 它为解决某一特定类型的问题规定了一个运算过程。以下关于算法的叙述中,错误的是(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,回答问题1至问题3。
[算法说明]
某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(占用)。客房是以房间(不是床位)为单位出租的。
本算法根据几个散客的要求预订一间空房。程序的输人为:人数M,房间等级要求R(R =0表示任意等级都可以)。程序的输出为:所有可供选择的房间号。
流程图1描述了该算法。
假设当前该旅馆各个房间的情况见表3。
当输入M=4,R=0时,该算法的输出是什么?
算法设计与分析(第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) 。
阅读以下说明和算法,完善算法并回答问题,将解答写在对应栏内。
[说明]
假设以二维数组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)。
回路问题
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)。
假设该商务交流中心当前各个房间的情况如表2-14所示。
当输入M=3,R=0时,该算法的输出是(1)。
当输入M=2,R=1时,该算法的输出是(2)。