算法设计与分析C++语言描述(陈慧南版)课后答案
第一章
15P
1-3. 最大公约数为1。快1414倍。
主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环）
若考虑其他语句，则没有这么多，可能就601倍。 第二章
32P
2-8.（1）画线语句的执行次数为log n ???
?。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为
111
(1)(2)16
j
n
i
i j k n n n ===++=
∑∑∑。3
()n O 。
（3）画线语句的执行次数为
。O 。
（4）当n 为奇数时画线语句的执行次数为
(1)(3)
4
n n ++， 当n 为偶数时画线语句的执行次数为 2(2)4
n +。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 ≤-+≤，所以2
2
582()n n n -+=Θ。
2-11. (1) 当3n ≥时，3
log log n n n <<，所以()20log 21f n n n n =+<，3
()log 2g n n n n =+>。可
选 21
2
c =
，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。
（2） 当 4n ≥ 时，2log log n n n <<，所以 22
()/log f n n n n =<，22()log g n n n n =≥。
可选 1c =，04n =。对于 0n n ≥，2()()f n n cg n <≤，即 ()(())f n g n =O 。
（3）因为 log log(log )()(log )
n
n f n n n ==，()/log log 2n g n n n n ==。当 4n ≥ 时，log(log )
()n f n n n =≥，
()log 2n g n n n =<。所以，可选 1c =，04n =，对于0n n ≥，()()f n cg n ≥，即 ()(())f n g n =Ω。 第二章 2-17. 证明：设
2i n =，则 log i n =。
()22log 2n T n T n n ????=+ ???????
2222log 2log 222
n n
n T n n ????
????=+??+?? ? ?????????
??
()2222log log22log 2n T n n n n ??
??=+-+ ?
?
?????
22222log 22n T n n n ??
??=+?- ??
?????
2322222log 22log 2222n n n T n n n ??????=+??+?-?? ??
?????
?? ()3322log log422log 22n T n n n n n ??
??=+-+?- ??
?????
33232log 242n T n n n n ??
??=+?-- ?
??????
=
()22log 2421
2k k n T kn n n n n k ??
??=+----- ??
?????
()()()1
2221log 2422i T i n n n n n i -=+----
--
()()()1
242log log 121i n n n i i n -=?+---- ()
2222log 2log log 3log 2n n n n n n n n =+---+ 2
log log n n n n =+ 当
2n ≥ 时，()22log T n n n ≤。所以，()()2log T n n n =O 。
第五章
5-4. SolutionType DandC1(int left,int right) {
while(!Small(left,right)&&left { int m=Divide(left,right); if(x else if(x>P[m]) left=m+1; else return S(P) } } 5-7. template int SortableList if (left<=right) { int m=(right+left)/3; if (x } return -1; } 第五章 9． 4 2 6 3517 01234567 -10 证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为log n ????，至多为log 1n +????。在 不成功搜索的情况下，关键字之间的比较次数至少为log 1n +????，至多为log 2n +????。所以，算法的最好、最坏情况的时间复杂度为()log n Θ。 假定查找表中任何一个元素的概率是相等的，为1 n ，那么， 不成功搜索的平均时间复杂度为 ()()log 1 u E A n n n = =Θ+， 成功搜索的平均时间复杂度为()()21log s I n E n n E A n n n n n +-+===-=Θ。 其中，I 是二叉判定树的内路径长度，E 是外路径长度，并且2E I n =+。 11. 12.（1）证明：当0n =或1n =或2n =时，程序显然正确。 当n=right-left+1>2时，程序执行下面的语句： int k=(right-left+1)/3; StoogeSort(left,right-k); StoogeSort(left+k,right); StoogeSort(left,right-k); ①首次递归StoogeSort(left,right-k);时，序列的前2/3的子序列有序。 ②当递归执行StoogeSort(left+k,right);时，使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。 ③再次执行StoogeSort(left,right-k);使序列的前2/3有序。 经过三次递归，最终使序列有序。 所以，这一排序算法是正确的。 （2）最坏情况发生在序列按递减次序排列。 ()()010T =T =，()21T =，()2313n n ?? T =T + ???。 设322i n ?? = ??? ，则log 1log31n i -=-。 ()2431331139n n n ??????T =T +=T ++ ? ????????? 49319n ?? =T ++ ???= 122333313i i i i n --????=T +++ ++?? ??????? ()31 322 i i -=T + ()31322 i = - log 1 log31312222n n --=??- log3 log31 3n -≤? log3log31 n -??=O ? ? ?? 冒泡排序最坏时间复杂度为() 2n O ，队排序最坏时间复杂度为()log n n O ，快速排序最坏时间复杂度为 ()log n n O 。所以，该算法不如冒泡排序，堆排序，快速排序。 13. template if(m+n int mid,left=0,right=n-1,cnt=0,j=0,r=0; for(int i=0;i { mid=(left+right)/2; if(a[mid] else if(a[mid]>b[i]) right=mid; else {cnt=mid; break;} }while(left if(a[left] else cnt=left-1; if(k>cnt) { if(cnt>0) { for(j=0;j { temp[j]=a[r]; r++; } left=cnt; k-=cnt; } else { temp[j]=b[i]; left=0; k--; } } else { for(j=0;j } left=cnt; k-=cnt; return temp[k-1]; } } } } 第六章 1.由题可得：012345601234561051576183,,,,,,,,,,,,2357141p p p p p p p w w w w w w w ???? = ? ??? ??， 所以，最优解为()01234562 ,,,,,,,1,,1,0,1,1,13 x x x x x x x ??= ??? ， 最大收益为21 +?++++=。 10515618355 33 8. 第六章 6-9. 普里姆算法。 因为图G是一个无向连通图。 所以n-1<=m<=n (n-1)/2; O(n)<=m<=O(n2); 克鲁斯卡尔对边数较少的带权图有较高的效率，而()() 1.992 =O≈O，此图边数较多，接近完全图， m n n 故选用普里姆算法。 6-10. T仍是新图的最小代价生成树。 证明：假设T不是新图的最小代价生成树，T’是新图的最小代价生成树，那么cost(T’) 是原图的最小代价生成树矛盾。所以假设不成立。证毕。 第七章 1. Bcost(1,0)=0; Bcost(2,1)=c(1,1)+Bcost(1.0)=5 Bcost(2,2)=c(1,2)+Bcost(1,0)=2 Bcost(3,3)=min{c(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)}=min{6+2,3+5}=8 Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7 Bcost(3,5)=min{c(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)}=min{3+5,8+2}=8 Bcost(4,6)=min{c(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)}=min{1+8,6+7,6+8}=9 Bcost(4,7)=min{c(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)}=min{4+8,2+7,6+8}=9 Bcost(5,8)=min{c(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)}=min{7+9,3+9}=12 2.向后递推的计算过程如上题所示 向前递推过程如下： cost(5,8)=0 cost(4,6)=7,cost(4,7)=3 cost(3,3)=min{1+cost(4,6),4+cost(4,7)}=7, cost(3,4)=min{6+cost(4,6),2+cost(4,7)}=5 cost(3,5)=min{6+cost(4,6),2+cost(4,7)}=5 cost(2,1)=min{3+cost(3,3),3+cost(3,5)}=8 cost(2,2)=min{6+cost(3,3),8+cost(3,5),5+cost(3,4)}=10 cost(1,0)=min{5+cost(2,1),2+cost(2,2)}=12 所以，d(4,6)=d(4,7)=8, d(3,3)=d(3,4)=d(3,5)=7, d(2,1)=5, d(2,2)=4, d(1,0)=2 从s 到t 的最短路径为 (0, d(1,0)=2, d(2,2)=4, d(3,4)=7, d(4,7)=8),路径长为12。 第七章 9. char A[8]={‘0’,’x’,’z’,’y’,’z’,’z’,’y’,’x’ } B[8]={‘0’,’z’,’x’,’y’,’y’,’z’,’x’,’z’} ???????????? ??????????????44 332210 4333211043322110333221102222211022211110111111000000000 0 ???????????? ??????????????21 222120 2221122012122210131222102221122013122210313331200000000 (a) c[i][j] （b ）s[i][j] 所以，最长公共字串为 (x,y,z,z)。 第七章 11. void LCS::CLCS ( int i , int j ) { if ( i = = 0 || j = = 0) return; if (c[i][j] = = c[i-1][j-1]+1) { CLCS ( i-1,j-1); Cout< else if ( c[i-1][j]>=c[i][j-1]) CLCS (i-1,j); else CLCS (i,j-1); } 12. int LCS::LCSLength() { for ( int i =1; i<=m; i++) c[i][0]=0; for (i =1; i<=n; i++) c[0][i]=0; for (i =1; i<=m; i++) for (int j =1; j<=n; j++) if (x[i]= =y[j]) c[i][j]=c[i-1][j-1]+1; else if (c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j]; else c[i][j]=c[i][j-1]; return c[m][n]; } 15. )}0,0{(1 =-S , )}2,10{(01=S , )}2,10(),0,0{(0=S , )}7,25(),5,15{(1 1=S , )}7,25(),5,15(),2,10(),0,0{(1=S , )}15,31(),13,21(),10,16(),8,6{(21=S , )}15,31(),13,21(),10,16(),8,6(),0,0{(2=S )}16,40(),14,30(),11,25(),9,15(),1,9{(31=S , )}15,31(),14,30(),13,21(),10,16(),9,15(),8,6(),0,0{(3=S 8-1． 状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。 显示约束：用于规定每个xi取值的约束条件称为显示约束 隐式约束：用于判定一个候选解是否为可行解的条件 问题状态：在状态空间树中的每个节点称为一个问题状态 解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态 答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。 活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点 扩展结点：算法从x出发，访问x的摸个后继结点y，则x被称为扩展结点 约束函数：一个约束函数是关于部分向量的函数Bk(x0,x1.....xk),它被定义为：如果可以判定Y的子树上不含任何答案状态，则Bk(x0,x1.....xk)为false,否则为true. 剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态节点数，他们统称为剪枝函数 8-2 bool place(int k,int ,I,int*x) { For(int j=0,j If((x[j]==i)||(abs(x[j]-j)==abs(j-k))) Return false; Return true; } Void nqueens(int k,int n,int *x) { For(int i=0;i If(place(k,I,x)) { X[k]=I; If(k= =n-1 { For(i=0;i Return; } Else nqueens(k+1,n,x) } } Void nqueens(int n,int *x) { Nqueens(0,n,x); } 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 第0章习题 1. 将下列十进制数分别转化为二进制数、八进制数和十六进制数： （1）128 （2）511 （3）1024 （4）65535 （5）1048575 答： （1）10000000、200、80 （2）111111111、777、1FF （3）10000000000、2000、400 （4）1111111111111111、177777、FFFF （5）11111111111111111111、3777777、FFFFF 2. 将下列二进制数转化为十进制数和十六进制数： （1）1100110101B （2）101101.1011B 答： （1）821、335 （2）45.6875、2D.B 3. 写出下列数的原码、反码、补码：15、-20、-27/32 答： （1）00001111、00000000、00001111 （2）10010100、11101011、11101100 （3）1.1101100、1.0010011、1.0010100 4. 16位无符号定点整数的数值表示范围为多少？8位补码的表示范围是多少？16位补码的表示范围是多少？ 答： 0～65535、-128～127、-32768～32767 5．1968年Dijkstra提出结构化程序设计的思想的原因是什么？简要回答结构化程序设计的经典定义。 答： 结构化程序设计概念的提出主要是源于程序结构的层次性与模块化使得构造出来的软件具有良好的可理解性和可维护性，随着软件规模的扩大与复杂性的提高，程序的可维护性成为程序设计者们关注的重要问题之一。 如果一个程序的代码块仅仅通过顺序、选择和循环这3种基本控制结构进行连接，并且每个代码块只有一个入口和一个出口，则称这个程序是结构化的。 6．C程序在内存中存储在哪儿？计算机的内存空间是如何分区的？分区存放不同类型的数据的目的是什么？ 答： 1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。 源代码： #include E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include c语言课后习题答案 第二章习题 2.什么叫做结构化算法？为什么要提倡结构化算法？ 答：结构化算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转,流程的转移只存在于一个基本的结构范围内。一个非结构化的算法可以用一个等价的结构化算法代替,其功能不变。 跟结构化算法比较起来,非结构化算法有以下缺点： 流程不受限制的随意转来转去,使流程图豪无规律使人在阅读的时候难以理解算法的逻辑.难以阅读,也难以修改，从而使算法的可靠性和可维护性难以保证。 4. 第三章习题 １．#include float p,p1,r=0.09; scanf("%u",&n); p=pow(1+r,n); p1=(p-1)*100; printf("%5.2f%%\n",p1); } 运行结果：输入，回车，见结果： ２．#include 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 第1章程序设计和C语言1 1.1什么是计算机程序1 1.2什么是计算机语言1 1.3C语言的发展及其特点3 1.4最简单的C语言程序5 1.4.1最简单的C语言程序举例6 1.4.2C语言程序的结构10 1.5运行C程序的步骤与方法12 1.6程序设计的任务14 1-5 #include 2.5结构化程序设计方法34 习题36 第章最简单的C程序设计——顺序程序设计37 3.1顺序程序设计举例37 3.2数据的表现形式及其运算39 3.2.1常量和变量39 3.2.2数据类型42 3.2.3整型数据44 3.2.4字符型数据47 3.2.5浮点型数据49 3.2.6怎样确定常量的类型51 3.2.7运算符和表达式52 3.3C语句57 3.3.1C语句的作用和分类57 3.3.2最基本的语句——赋值语句59 3.4数据的输入输出65 3.4.1输入输出举例65 3.4.2有关数据输入输出的概念67 3.4.3用printf函数输出数据68 3.4.4用scanf函数输入数据75 3.4.5字符数据的输入输出78 习题82 3-1 #include P 15 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while循环体做了10次，程序1-3的while循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 2-8.（1）画线语句的执行次数为。。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为。。 （3）画线语句的执行次数为。。 （4）当n为奇数时画线语句的执行次数为， 当n为偶数时画线语句的执行次数为。。 2-10.（1）当时，，所以，可选，。对于，，所以，。 （2）当时，，所以，可选，。对于，，所以，。 （3）由（1）、（2）可知，取，，，当时，有，所以。 2-11. (1) 当时，，所以，。可选，。对于，，即。注意：是f(n)和g(n)的关系。 （2）当时，，所以，。可选，。对于，，即。 （3）因为，。当时，，。所以，可选，，对于，，即。 第二章 2-17. 证明：设，则。 当时，。所以，。 第五章 5-4. SolutionType DandC1(int left,int right) { while(!Small(left,right)&&left 3-5-1正确 大写字母转化成小写或者小写变大写 #include #include 习题一 一、简答题 1．顺序结构、选择（分支）结构和循环结构。 2． （1） （2） 3．编辑、编译、连接和运行 二、填空题 1． Ctrl+F9；Alt+F5；F2。 2． main(主) 3． main(主) 4． 任意 5． /* */ 不 6． ； 7．。 程序： include studio.h main{} /* this program prints the number of weeks in a year. /* ( int s s:=52; print(There are s weeks in a year"); 正确的为： #include 习题二 一、选择题 1、C 2、B，D，F，G 3、C 4、A 5、C 6、B 二、填空题 1、声明；使用。 2、整型、浮点型（实型）、字符型。 3、hat_1，cat1，all, Dollar, piece_f, SIN, _ , FALSE. 4、'A'(字符)，005（整型），3e0（整型），'\\'(字符)，'\05'(字符)， 1.2e+5（整型），0xf12（整型）。 5、（1）6+(4+5)*(4+5)/(2+3) （2）sin(a+b)*ain(a+b)/ (4*2)/(3*2)+2 三、读程题 1.若x为float型，其原值为5,a=2,b=4.7。写出下列表达式运算后x的值。 （1）x=(int)(b-a)%3*a/4-a （2）x=(x=b+1)+(int)(b)%10/2.0 （3）x+=x （4）x-=x （5）x*=x+x （6）x/=x+x （7）x+=x-=x*=x （8）x%=x （9）x=3*4,5*6 答案：（1）-1,（2）7.7,（3）10,（4）0,（5）50,（6）0.5,（7）0,（8）非法,（9）12。 2.写出下面程序的运行结果。 #include 《算法分析与设计》期末复习题 一、选择题 1.应用Johnson法则的流水作业调度采用的算法是（D） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B） " ; | A. void hanoi(int n, int A, int C, int B) 《 { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); ] move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } } 3. 动态规划算法的基本要素为（C ） A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O 表示（B ）， 记号Ω表示（A ）， 记号Θ表示（D ）。 … A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A ） A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ?=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f (n)O(g(n))g(n)O(f (n))=?= D. void hanoi(int n, int C, int A, int B) { if (n > 0) { | hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } 作业A： 一、单项选择题 1、如果要把常量327存入变量a中，a不能定义的类型是哪一个?() A）int B）char C）long D）float 2、若x 为unsigned int 型变量，则执行下列语句后x值为（） x = 65535； printf(“%d\n”,x); A）65535 B）1 C）无定值D）-1 3、有以下程序 main（） ｛int a=1，b=2，m=0，n=0，k;k=（n=b>a）||（m=a 第3章 三、编程题 1． 编写程序，输入一个非负数，输出以此数为半径的圆周长以及面积。 #include "stdio.h" #define PI 3.1415 void main() { float r,area,circumference; scanf("%f",&r); area=PI*r*r; circumference=2*r*PI; printf("area=%6.2f\ncircumference=%6.2f\n",area,circumference); } 2． 编写程序，输出下面结果，注意，双引号也要输出： “I'm a student!” #include 第4章 三、编程题 1．输入一个整数，判断这个整数是奇数还是偶数（提示：整数的奇偶性可以利用取余运算符%判定）。#include 第1章程序设计和C语言1 什么是计算机程序1 什么是计算机语言1 语言的发展及其特点3 最简单的C语言程序5 最简单的C语言程序举例6 语言程序的结构10 运行C程序的步骤与方法12 程序设计的任务14 1-5 #include <> int main ( ) { printf ("**************************\n\n"); printf(" Very Good!\n\n"); printf ("**************************\n"); return 0; } 1-6#include <> int main() {int a,b,c,max; printf("please input a,b,c:\n"); scanf("%d,%d,%d",&a,&b,&c); max=a; if (max 数据类型42 整型数据44 字符型数据47 浮点型数据49 怎样确定常量的类型51 运算符和表达式52 语句57 语句的作用和分类57 最基本的语句——赋值语句59 数据的输入输出65 输入输出举例65 有关数据输入输出的概念67 用printf函数输出数据68 用scanf函数输入数据75 字符数据的输入输出78 习题82 3-1 #include <> #include <> int main() {float p,r,n; r=; n=10; p=pow(1+r,n); printf("p=%f\n",p); return 0; 《算法分析与设计》期末复习题 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi 塔问题的移动规则。由此设计出解Hanoi 塔问题的递归算法正确的为：（B ） Hanoi 塔 A. void hanoi(int n, int A, int C, int B) { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } 3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O表示（B），记号Ω表示（A），记号Θ表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f(n)O(g(n))g(n)O(f(n)) =?= 6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 一、已知下列递推式： C(n) = 1 若n =1 = 2C （n/2） + n – 1 若n ≥ 2 请由定理1 导出C(n)的非递归表达式并指出其渐进复杂性。 定理1：设a,c 为非负整数，b,d,x 为非负常数，并对于某个非负整数k, 令n=c k , 则以下递推式 f(n) =d 若 n=1 =af(n/c)+bn x 若 n>=2 的解是 f(n)= bn x log c n + dn x 若 a=c x f(n)= x x x a x x n c a bc n c a bc d c ???? ??--???? ??-+log 若 a ≠c x 解：令F(n) = C(n) – 1 则 F(n) = 0 n=1 F(n) = 2C(n/2) + n – 2 n>=2 = 2[F(n/2) + 1] + n – 2 = 2F(n/2) + n 利用定理1，其中： d=0,a=2,c=2,b=1,x=1,并且a=c x 所以 F(n) = nlog 2n 所以 C(n) = F(n) + 1 = nlog 2n + 1 C(n)的渐进复杂性是O(nlog 2n) 二、由于Prim 算法和Kruskal 算法设计思路的不同，导致了其对不同问题实例的效率对比关系的不同。请简要论述： 1、如何将两种算法集成，以适应问题的不同实例输入； 2、你如何评价这一集成的意义？ 答： 1、Prim 算法基于顶点进行搜索，所以适合顶点少边多的情况。 Kruskal 从边集合中进行搜索，所以适合边少的情况。 根据输入的图中的顶点和边的情况，边少的选用kruskal 算法，顶点少的选用prim 算法 2、没有一个算法是万能的，没有一个算法是对所有情况都适合的。这一集成体现了针对具体问题选用最适合的方法，即具体问题具体分析的哲学思想。 三、分析以下生成排列算法的正确性和时间效率： HeapPermute (n ) //实现生成排列的Heap 算法 合并排序1： #include 2.2 #include double x,y; printf("Inputa,b,c:"); scanf("%f,%f,%f",&a,&b,&c); x=(-b+sqrt(b*b-4*a*c))/(2*a); y=(-b-sqrt(b*b-4*a*c))/(2*a); printf("x=%f,y=%f\n",x,y); } 4.1(1) #include《计算机算法设计与分析》习题及答案
算法设计与分析课程设计(完整版)
C语言课后习题答案(最终)
OpenJudge算法设计与分析习题解答
最新c语言课后习题答案汇总
算法设计与分析复习题目及答案
《C语言程序设计》课后习题答案(第四版)谭浩强
算法设计与分析c语言描述课后答案
C语言课后作业答案
C语言课后答案
《算法设计与分析》考试题目及答案
C语言课后练习及答案
C语言课后答案最新版本
《C语言程序设计》课后习题答案(第四版)谭浩强
算法设计与分析考试题目及复习资料
北航计算机研究生课程 算法设计与分析 HomeWork_1
计算机算法设计与分析课程设计常规题目的(C及C++)代码集
C语言程序设计课后答案
相关文档
- 算法设计与分析复习题目及答案
- 算法设计与分析C语言描述陈慧南版课后答案
- OpenJudge算法设计与分析习题解答
- 算法设计与分析复习要点
- 算法设计与分析考试题目及复习资料
- 算法设计与分析期末考试复习题
- 算法设计与分析C 语言描述(陈慧南版)课后答案
- 算法设计与分析C语言描述(陈慧南版)课后答案
- 算法设计与分析
- 计算机算法设计与分析课程设计常规题目的(C及C++)代码集
- 《算法设计与分析》实验指导
- 《算法设计与分析》试题(C)卷
- 算法设计与分析课程设计(完整版)
- 《算法设计与分析》考试题目与答案
- 最新算法设计与分析C 语言描述(陈慧南版)课后答案讲解学习
- 算法设计与分析c语言描述(陈慧南版)课后答案
- 算法设计与分析C 语言描述(陈慧南版)课后答案
- 计算机算法设计与分析习题和答案解析
- 算法设计与分析c语言描述课后答案
- 北航计算机研究生课程 算法设计与分析 HomeWork_1