算法设计第六章答案

算法设计与分析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 )的关系。

题目：下列叙述中正确的是_________________。

选项A：以上三种说法都不对
选项B：设计算法时只需要考虑结果的可靠性
选项C：算法就是程序
选项D：设计算法时只需要考虑数据结构的设计
答案：以上三种说法都不对
题目：当一个算法输入不合法的数据时，应当能够作适当处理，不致于引起严重后果，这属于算法的( ) 。

选项A：可读性
选项B：高效性
选项C：正确性
选项D：健壮性
答案：健壮性
题目：下列叙述中正确的是_________________。

选项A：以上三种说法都不对
选项B：一个算法的时间复杂度大，则其空间复杂度必定小
选项C：一个算法的空间复杂度大，则其时间复杂度也必定大
选项D：一个算法的空间复杂度大，则其时间复杂度必定小
答案：以上三种说法都不对
题目：一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（）。

选项A：可行性
选项B：有穷性
选项C：有零个或多个输入
选项D：有零个或多个输出
答案：有零个或多个输出
题目：下面叙述正确的是（）。

选项A：数据的逻辑结构与存储结构是一一对应的
选项B：算法的效率只与问题的规模有关，而与数据的存储结构无关
选项C：算法的时间复杂度与空间复杂度一定相关
选项D：算法的时间复杂度是指执行算法所需要的计算工作量
答案：算法的时间复杂度是指执行算法所需要的计算工作量
题目：根据问题条件估计答案的范围，在此范围内对所有可能情况逐一验证，直到全部情况均通过验证为止。

这种算法是（）。

选项A：递归法
选项B：回溯法
选项C：穷举法
选项D：分治法。

算法设计与分析智慧树知到课后章节答案2023年下山东交通学院山东交通学院第一章测试1.解决一个问题通常有多种方法。

若说一个算法“有效”是指( )A:这个算法能在一定的时间和空间资源限制内将问题解决B:这个算法能在人的反应时间内将问题解决C:这个算法比其他已知算法都更快地将问题解决D:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）答案:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）2.农夫带着狼、羊、白菜从河的左岸到河的右岸，农夫每次只能带一样东西过河，而且，没有农夫看管，狼会吃羊，羊会吃白菜。

请问农夫能不能过去？（）A:不一定B:不能过去 C:能过去答案:能过去3.下述（）不是是算法的描述方式。

A:自然语言 B:E-R图 C:程序设计语言 D:伪代码答案:E-R图4.有一个国家只有6元和7元两种纸币，如果你是央行行长，你会设置（）为自动取款机的取款最低限额。

A:40 B:29 C:30 D:42答案:305.算法是一系列解决问题的明确指令。

（）A:对 B:错答案:对6.程序=数据结构+算法（）A:对 B:错答案:对7.同一个问题可以用不同的算法解决，同一个算法也可以解决不同的问题。

（）A:错 B:对答案:对8.算法中的每一条指令不需有确切的含义，对于相同的输入不一定得到相同的输出。

( )A:错 B:对答案:错9.可以用同样的方法证明算法的正确性与错误性 ( )A:错 B:对答案:错10.求解2个数的最大公约数至少有3种方法。

( )A:对 B:错答案:错11.没有好的算法，就编不出好的程序。

（）A:对 B:错答案:对12.算法与程序没有关系。

( )A:错 B:对答案:错13.我将来不进行软件开发，所以学习算法没什么用。

( )A:错 B:对答案:错14.gcd(m,n)=gcd(n,m m od n)并不是对每一对正整数(m,n)都成立。

第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。

本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。

第六章动态规划法• P137 2 ,3, 4•2.解答:cost[i]表示从顶点i 到终点n-1 的最短路径，path[i]表示从顶点i 到终点n-1 的路径上顶点i 的下一个顶点。

cost[i]=min{cij+cost[j]}3 有5 个物品，其重量分别是{3, 2, 1, 4,5}，价值分别为{25, 20, 15, 40, 50}，背包的容量为6。

V[i][j]表示把前i 个物品装入容量为j 的背包中获得的最大价值。

最优解为（0，0，1，0，1）最优值为65. 4.序列A =(x, z , y , z , z , y,x )，B =(z , x , y , y , z , x , z )，建立两个(m+1)×(n+1)的二 维表L 和表S ，分别存放搜索过程中得到的子序列的长度和状态。

z , x , y , y , z,x , z )path[i]= 使 cij+cost[j] 最小的 j i 012345678 9 10 11 12 13 14 15 Cost[i] 18 13 16 13 10 9 12 7 6875943Path[i]145778911 11 11 13 14 14 15 15 0得到最短路径 0->1->4->7->11->14->15 , 长度为 18(a)长度矩阵L(b)状态矩阵S 。

第七章贪心算法2.背包问题:有7 个物品，背包容量W=15。

将给定物品按单位重量价值从大到小排序，结果如下：个物品，物品重量存放在数组w[n]中，价值存放在数组放在数组x[n]中。

按算法7.6——背包问题1．改变数组w 和v 的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；2．将数组x[n]初始化为0；//初始化解向量3．i=1;4．循环直到( w[i]>C )4.1 x[i]=1; //将第i个物品放入背包4.2 C=C-w[i];4.3 i++;5. x[i]=C/w[i];得出,该背包问题的求解过程为:: x[1]=1;c=15-1=14 v=6 x[2]=1; c=14-2=12V=6+10=10 x[3]=1; c=12-4=8V=16+18=34 x[4]=1; c=8-5=3V=34+15=49 x[5]=1; c=3-1=2 V=49+3=52x[6]=2/3 ; c=0; V=52+5*2/3=156/3 最优值为156/3 最优解为(1,1,1,1,1,2/3,0)) (x[i]按排序后物品的顺序构造)5.可以将该问题抽象为图的着色问题,活动抽象为顶点,不相容的活动用边相连(也可以将该问题理解为最大相容子集问题,重复查找剩余活动的最大相容子集,子集个数为所求).具体参见算法7.3 算法7.3——图着色问题1．color[1]=1; //顶点1着颜色12．for (i=2; i<=n; i++) //其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++; //取下一个颜色4.2for (i=2; i<=n; i++) //用颜色k 为尽量多的顶点着色4.2.1 若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2 若图中与顶点i邻接的顶点着色与顶点i着颜色k 不冲突，则color[i]=k;5．输出k;第八章回溯法4.搜索空间(a) 一个无向图(b) 回溯法搜索空间最优解为（1，2，1，2，3）5.0-1 背包问题n∑w i x i≤c 1• 可行性约束函数：i =1• 上界函数：nr =∑Vi5 = 3A B *CD8 ** * 131 =12 =23 = 14 = 2 34215课后答案网（）i=k+1 1第九章分支限界法5，解：应用贪心法求得近似解：(1,4,2,3)，其路径代价为：3+5+7+6=21，这可以作为该问题的上界。

第 6 章图课后习题讲解1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

参考答案第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）由于顶层设计和底层实现局部化，在设计中出现的差错也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、删、改也都是局部的，因而也都容易进行。

《程序设计基础》第六章自测一、选择题（共10道，每道6分）题目1正确获得6.00分中的6.00分标记题目题干下列叙述中正确的是_________________。

选择一项：A. 设计算法时只需要考虑结果的可靠性B. 算法就是程序C. 设计算法时只需要考虑数据结构的设计D. 以上三种说法都不对恭喜你答对了反馈正确答案是：以上三种说法都不对题目2正确获得6.00分中的6.00分标记题目题干当一个算法输入不合法的数据时，应当能够作适当处理，不致于引起严重后果，这属于算法的( ) 。

选择一项：A. 可读性B. 正确性C. 高效性D. 健壮性恭喜你答对了反馈正确答案是：健壮性题目3正确获得6.00分中的6.00分标记题目题干下列叙述中正确的是_________________。

选择一项：A. 一个算法的时间复杂度大，则其空间复杂度必定小B. 一个算法的空间复杂度大，则其时间复杂度也必定大C. 一个算法的空间复杂度大，则其时间复杂度必定小D. 以上三种说法都不对恭喜你答对了反馈正确答案是：以上三种说法都不对题目4正确获得6.00分中的6.00分标记题目题干一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（）。

选择一项：A. 有零个或多个输出恭喜你答对了B. 有零个或多个输入C. 有穷性D. 可行性反馈正确答案是：有零个或多个输出题目5正确获得6.00分中的6.00分标记题目题干下面叙述正确的是（）。

选择一项：A. 数据的逻辑结构与存储结构是一一对应的B. 算法的时间复杂度是指执行算法所需要的计算工作量恭喜你答对了C. 算法的时间复杂度与空间复杂度一定相关D. 算法的效率只与问题的规模有关，而与数据的存储结构无关反馈正确答案是：算法的时间复杂度是指执行算法所需要的计算工作量题目6正确获得6.00分中的6.00分标记题目题干根据问题条件估计答案的范围，在此范围内对所有可能情况逐一验证，直到全部情况均通过验证为止。

第三章习题答案1.掌握算法必须要掌握的五个特性：a)有穷性。

算法执行步骤的次数有限，能在有限时间内完成。

b)确切性。

每一步操作的执行步骤、执行结果确定，不能有二义性。

c)有效性。

算法中的每一步操作都是可执行的，即算法的每一步都能通过手工或机器在有限时间内完成。

d)必须有零个或多个输入。

e)必须有一个或多个输出。

2.算法是指令的有限序列，是求解问题显式的一步一步进行的过程。

为程序编写提供依据。

程序是用C语言单词将算法表达出来的过程。

算法是程序的灵魂。

3.数据类型总体分为三类：a)对象类型。

对象类型的基本类型又分为整型、浮点型、字符型。

b)函数类型。

c)不完全类型。

4.整型可分为：a)有符号整数。

它又包括 short int、int、long int、long long int。

b)无符号整数。

它又包括unsigned short int、unsigned int、unsigned longint、unsigned long long int。

不同数据类型数据的值域范围不同。

5.合法的标识符有：scanf、x、x1、_y 、_y2x、printf、main合法标识符由英文字母、数字、下划线组成，且第一个字符只能是英文字母或下划线。

关键词不能成为合法标识符。

6.略7.8.变量名：x 数据对象：3存储地址：&x 存储单元:8(在VS2005中)9.0x13B1：十六进制int型字面值；3e3：十进制 int型字面值；‘d’：字符型字面值；“my university”：字符串型字面值；99：十进制int型字面值；023：八进制int型字面值；1.3e-4：double型浮点型字面值；33U：十进制unsigned int型字面值；034L：八进制long int型字面值；0x34UL：十六进制unsigned long int型字面值；30.23L：十进制long double型字面值；30.23F：十进制float型字面值；10.\?：？\’：’\”：”\\：\\233：表示八进制int型整数233\x2f：表示十六进制int型整数 2f。

算法设计与分析智慧树知到课后章节答案2023年下天津大学天津大学第一章测试1.下列关于效率的说法正确的是（）。

答案:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法;效率是一个性能要求，其目标应该在需求分析时给出;效率主要指处理机时间和存储器容量两个方面2.算法的时间复杂度取决于（）。

答案:待处理数据的初态;问题的规模3.计算机算法指的是（）。

答案:解决问题的有限运算序列4.归并排序法的时间复杂度和空间复杂度分别是（）。

答案:O(nlog2n);O(n)5.将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。

（）答案:错6.用渐进表示法分析算法复杂度的增长趋势。

（）答案:对7.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

（）答案:对8.某算法所需时间由以下方程表示，求出该算法时间复杂度（）。

答案:O(nlog2n)9.下列代码的时间复杂度是（）。

答案:O(log2N)10.下列算法为在数组A[0,...,n-1]中找出最大值和最小值的元素，其平均比较次数为（）。

答案:3n/2-3/2第二章测试1.可用Master方法求解的递归方程的形式为（）。

答案:T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.2.答案:对3.假定，, 递归方程的解是. ( )答案:对4.假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。

针对该问题的任何算法需要的时间复杂度的下限必为。

( )答案:错5.使用Master方法求解递归方程的解为（）.答案:6.考虑包含n个二维坐标点的集合S，其中n为偶数，且所有坐标点中的均不相同。

一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。

若给定集合S，则可在时间内找到这条分界线L。

( )答案:对7.答案:8.从n个数中找出前k个最小的元素并对所选择的前k个最小的元素进行排序。

习题11. 图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707 —1783) 提出并解决了该问题。

七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。

请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点输出：相同的点1，一次步行2，经过七座桥，且每次只经历过一次3，回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。

另一类是只有二个奇点的图形。

2 •在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法=m-n2.循环直到r=0m=nn=rr=m-n3输出m3 •设计算法求数组中相差最小的两个元素（称为最接近数）的差。

要求分别给出伪代码和C++描述。

编写程序，求n至少为多大时，n个"1”组成的整数能被2013整除。

#in clude<iostream> using n amespace std;int mai n(){double value=0;for(int n=1;n<=10000 ;++n){ value=value*10+1;if(value%2013==0){cout<<"n 至少为:"<<n<<endl; break;}}计算n值的问题能精确求解吗编写程序，求解满足给定精度要求的n值#include <iostream> using namespace std;int main (){double a,b;double arctan(double x); 圣经上说：神6 天创造天地万有，第7 日安歇。

为什么是6 天呢任何一个自然数的因数中都有1 和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。