(完整版)太原理工大学软件学院算法设计与分析复习题目及答案

《计算机算法设计与分析》试卷 考试时间120分钟2002年-2003年第二学期学号 姓名 成绩一、阐述题1． 请说明算法的五个基本特性，并进行简要的分析(5分) 答：算法的五个基本特性如下：① 确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。

② 能行性 一个算法是能行的是指算法中有待实现的运算都是基本的运算，每种运算至少在原理上能由人用纸和笔在有限时间内完成。

③ 输入 一个算法有0个或多个输人，这些输人是在算法开始之前给出的量，它取自特定的对象集合。

④ 输出 一个算法产生一个或多个输出，这些输出是同输人有某种特定关系的量。

⑤ 有穷性 一个算法总是在执行了有穷步的运算之后能够终止，且每一步都可在有穷时间内完成。

这里的有穷的概念不是纯数学的，而是在实际上是合理的，可以接受的。

凡是算法，都必须满足以上五条特性。

只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。

2． 若森林非空，请按照森林和树相互递归的定义，阐述森林的两种遍历的方法。

(10分) 答：森林是由m(m ≥0)棵互不相交的树构成的集合。

对树中的每一个结点而言，其子树的集合即为森林。

所以，森林和树是可以相互递归定义的。

对于一个非空的森林F=(T 1，T 2，…，T m )，因为至少存在一棵树，不妨假设为T 1，则森林F 可以分解成T 1和由T 2，…，T m 构成的森林。

于是，可得到森林的两种遍历算法。

① 先序遍历森林若森林非空，则可按下述规则遍历这个森林： （1） 访问树中第一棵树的根结点；（2） 先序遍历第一棵中根结点的所有子树构成的森林； （3） 先序遍历除去第一棵树外剩下的树构成的森林。

② 中序遍历森林若森林非空，则可按下述规则遍历这个森林：（1） 中序遍历第一棵中根结点的所有子树构成的森林； （2） 访问树中第一棵树的根结点；（3） 中序遍历除去第一棵树外剩下的树构成的森林。

《计算机算法设计与分析》习题及答案一．选择题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。

4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort 的算法。

它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max ，然后将该元素同未排序序列中的最后一个元素交换。

这时，max 元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max 已经不在未排序序列之中了。

重复上述过程直到完成整个序列的排序。

(a) 写出Maxsort 算法。

其中待排序序列为E ，含有n 个元素，脚标为范围为0,,1n -。

void Maxsort(Element[] E) { int maxID = 0;for (int i=E.length; i>1; i--) { for (int j=0; j<i; j++) {if (E[j] > E[maxID]) maxID = k; }E[i] <--> E[maxID]; } }最坏情况同平均情况是相同的都是11(1)()2n i n n C n i -=-==∑。

几遍浏览序列实现。

排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。

也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位起泡排序的最坏情况为逆序输入，比较次数为11(1)()2n i n n C n i -=-==∑。

(b) 最好情况为已排序，需要(n-1)次比较。

4.3： (a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k 时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k 个元素进行比较，当k元素大于k-1元素时，它为k个元素中最大的，命题成立；当k元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。

太原理工复试题《软件工程》题库及答案1.开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称做(C)A.软件工程B.软件周期C.软件危机D.软件产生2.研究开发所需要的成本和资源是属于可行性研究中的（B ）研究的一方面。

A.技术可行性B.经济可行性C.社会可行性D.法律可行性3.IDEF0图不反映出系统（ B ）A.系统做什么B.系统功能如何实现C.系统由谁来做D.系统实现的约束条件4.模块的内聚性最高的是（ D ）A.逻辑内聚B.时间内聚C.偶然内聚D.功能内聚5.在SD方法中全面指导模块划分的最重要的原则是（ D ）A.程序模块化B.模块高内聚C.模块低耦合D.模块独立性6.软件详细设计主要采用的方法是（ D ）A.模块设计B.结构化设计C.PDL语言D.结构化程序设计7.下列关于JSP方法不正确的说法是（ D ）A.JSP方法主要用于规模不大的数据处理系统B.JSP方法不明确的划分软件概要设计和详细设计的两个阶段C.JSP方法适用于输入数据和输出数据之间有对应关系的问题求解D.JSP方法根据输入、输出的数据结构，按一定的规则映射成软件的体系结构。

因此它只适用于详细设计阶段8.不适合作为科学工程计算的语言是（ D ）A. PascalB. CC. FortranD. Prolog9.黑盒测试在设计测试用例时，主要需要研究（ A ）A.需求规格说明与概要设计说明B.详细设计说明C.项目开发计划D.概要设计说明与详细设计说明10.若有一个计算类型的程序，它的输入量只有一个X，其范围是［-1.0，1.0］，现从输入的角度考虑一组测试用例：-1.001，-1.0，1.0，1.001。

设计这组测试用例的方法是（ C ）A.条件覆盖法B.等价分类法C.边界值分析法D.错误推测法11.下列属于维护阶段的文档是（ C ）A.软件规格说明B.用户操作手册C.软件问题报告D.软件测试分析报告12.快速原型模型的主要特点之一是（ D ）A.开发完毕才见到产品B.及早提供全部完整的软件产品C.开发完毕后才见到工作软件D.及早提供工作软件13.因计算机硬件和软件环境的变化而做出的修改软件的过程称为（ B ）A.较正性维护B.适应性维护C.完善性维D.预防性维护14.类库这种机制是（ D ）级别的信息共享。

一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。

2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。

3.某一问题可用动态规划算法求解的显著特征是____________________________________。

4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。

6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。

7.以深度优先方式系统搜索问题解的算法称为_____________。

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。

9.动态规划算法的两个基本要素是___________和___________。

10.二分搜索算法是利用_______________实现的算法。

二、综合题（50分）1.写出设计动态规划算法的主要步骤。

2.流水作业调度问题的johnson算法的思想。

3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。

4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。

2022年太原理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A.单链表B.双向链表C.单循环链表D.顺序表4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列叙述中，不符合m阶B树定义要求的是（）。

5..证明等式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//输出:实根或者无解信息D←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. 这个断言是正确的。

太原理工大学软件工程
太原理工大学软件工程专业是一个广泛涉及计算机科学和软件开发的学科领域。

这个专业旨在培养学生掌握软件工程的基本理论和实践技能，使他们能够设计、开发和维护高质量的软件系统。

该专业的课程设置包括计算机编程、数据结构、算法设计、计算机网络、数据库系统、软件测试和质量保证等多个方面的内容。

学生将学习掌握各种编程语言和开发工具，通过实际项目实践培养解决实际问题的能力。

在学习过程中，学生将参与到各种软件开发项目中，包括个人项目和团队项目。

通过项目实践，他们将学习如何进行软件需求分析、系统设计、编码实现、测试和上线部署等工作。

此外，太原理工大学软件工程专业还注重培养学生的沟通和团队合作能力。

学生将通过课程中的小组讨论、项目团队合作等形式，培养自己的团队协作和领导能力。

毕业后，软件工程专业的学生可以在各种软件开发和IT服务行业就业。

他们可以成为软件工程师、系统分析员、软件架构师、项目经理等职位。

他们也可以选择继续深造，攻读硕士或博士学位，从事科研或教学工作。

总之，太原理工大学软件工程专业是一个培养软件开发和工程化能力的学科，为学生提供了丰富的知识和实践机会，为他们未来的职业发展奠定坚实的基础。

一、选择题2．软件测试中白盒法是通过分析程序的（ B ）来设计测试用例的。

A）应用范围B）内部逻辑C）功能D）输入数据3．黑盒法是根据程序的（ C ）来设计测试用例的。

A）应用范围B）内部逻辑C）功能D）输入数据5．与设计测试用例无关的文档是（ A ）。

A）项目开发计划B）需求规格说明书C）设计说明书D）源程序6．测试的关键问题是（ B ）。

A）如何组织软件评审B）如何选择测试用例C）如何验证程序的正确性D）如何采用综合策略7．软件测试用例主要由输入数据和（ C ）两部分组成。

A）测试计划B）测试规则C）预期输出结果D）以往测试记录分析10．在黑盒测试中，着重检查输入条件组合的方法是（ D ）。

A）等价类划分法B）边界值分析法C）错误推测法D）因果图法11．单元测试主要针对模块的几个基本特征进行测试，该阶段不能完成的测试是（ A ）。

A）系统功能B）局部数据结构C）重要的执行路径D）错误处理12．软件测试过程中的集成测试主要是为了发现（ B ）阶段的错误。

A）需求分析B）概要设计C）详细设计D）编码14．集成测试时，能较早发现高层模块接口错误的测试方法为（ A ）。

A）自顶向下渐增式测试B）自底向上渐增式测试C）非渐增式测试D）系统测试15．确认测试以（ A ）文档作为测试的基础。

A）需求规格说明书B）设计说明书C）源程序D）开发计划16．使用白盒测试方法时，确定测试数据应根据（ A ）和指定的覆盖标准。

A）程序内部逻辑B）程序的复杂度C）使用说明书D）程序的功能18．结构化程序设计的一种基本方法是（ D ）A）筛选法B）递归法C）归纳法D）逐步求精法20．程序三种基本结构的共同特点是（ D ）A）不能嵌套使用B）只能用来写简单程序C）已经用硬件实现D）只有一个入口和一个出口22．覆盖准则最强的是( D )。

A）语句覆盖B）判定覆盖C）条件覆盖D）路径覆盖23．发现错误能力最弱的是( A )。

A）语句覆盖B）判定覆盖C）条件覆盖D）路径覆盖24．实际的逻辑覆盖测试中，一般以( C )为主设计测试用例。

算法分析与设计重点课后习题答案习题13．设计算法求数组中相差最小的两个元素（称为最接近数）的差。

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

//采用分治法//对数组先进行快速排序//在依次比较相邻的差#includeusing namespace std;int partions(int b[],int low,int high){int prvotkey=b[low];b[0]=b[low];while (low<high)< p="">{while (low<high&&b[high]>=prvotkey)</high&&b[high]>--high;b[low]=b[high];while (low<high&&b[low]<=prvotkey)< p="">++low;b[high]=b[low];}b[low]=b[0];return low;}void qsort(int l[],int low,int high){int prvotloc;if(low<high)< p="">{prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high }}void quicksort(int l[],int n){qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个}int main(){int a[11]={0,2,32,43,23,45,36,57,14,27,39};int value=0;//将最小差的值赋值给valuefor (int b=1;b<11;b++)cout<<a[b]<<' ';<="" p="">cout<<endl;< p="">quicksort(a,11);for(int i=0;i!=9;++i){if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}cout<<value<<endl;< p="">return 0;}4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。

软考算法题库及答案详解1. 题目：给定一个整数数组，找出其中的最大值。

答案：使用线性搜索算法遍历数组中的每个元素，记录并更新最大值。

2. 题目：实现一个函数，判断一个链表是否为回文结构。

答案：首先将链表复制到数组中，然后使用双指针方法从两端向中间遍历，判断是否相等。

3. 题目：编写一个算法，计算两个字符串的最长公共子序列长度。

答案：使用动态规划方法，创建一个二维数组dp，其中dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列长度。

遍历两个字符串，更新dp数组。

4. 题目：给定一个无序数组，找出其中第k大的元素。

答案：使用快速选择算法，通过随机选择一个元素作为基准，将数组分为两部分，一部分包含比基准小的元素，另一部分包含比基准大的元素。

根据k的值确定是否继续在左部分或右部分进行快速选择。

5. 题目：实现一个算法，将一个字符串反转。

答案：使用双指针方法，一个指针从字符串的开始位置，另一个指针从字符串的结束位置，逐个交换两个指针所指的字符。

6. 题目：给定一个整数n，打印所有可能的n位二进制数。

答案：使用回溯算法，从最低位开始，依次尝试0和1，直到达到n位。

7. 题目：编写一个函数，实现二分查找。

答案：首先确定数组是有序的，然后设置两个指针low和high分别指向数组的开始和结束。

计算中间位置mid，比较中间元素与目标值，如果相等则返回mid，如果目标值小于中间元素，则在左半部分继续查找，否则在右半部分继续查找。

8. 题目：给定一个二维矩阵，找出其中的最大值。

答案：遍历矩阵的每一行，记录每行的最大值，然后从这些行的最大值中找出整个矩阵的最大值。

9. 题目：实现一个算法，将一个栈转换为队列。

答案：使用两个栈，将原栈的所有元素依次压入第一个栈，然后依次将第一个栈的元素压入第二个栈，这样第二个栈就实现了队列的先进先出特性。

10. 题目：编写一个算法，实现归并排序。

答案：将数组分成两部分，直到每部分只有一个元素，然后递归地合并这些元素，直到整个数组被排序。

算法设计和分析（第二版）习题答案（第三章）2010年06月15日星期二下午 03:51算法设计和分析（第二版）主编：吕国英习题答案第三章：1.#include<stdlib.h>#include<stdio.h>int main(int argc,char **argv){int n;int i,j,k;int *buf;printf("请输入n的数值:");scanf("%d",&n);buf=(int *)malloc(n*sizeof(int)); for(i=0;i<n;i++){buf[i]=2;}for(i=n-2;i>=0;i--)for(j=i;j>=0;j--){buf[j]+=2;}}for(k=0;k<=n-2;k++){if(buf[k]>=10){buf[k+1]+=buf[k]/10;buf[k]%=10;}}for(i=n-1;i>=0;i--)printf("%d",buf[i]); printf("\n");return 0;}2.#include<stdio.h>int main(int argc,char **argv)int buf[6][6];int i,j;printf("任意输入6个数字:");for(i=0;i<6;i++)scanf("%d",&buf[0][i]);for(i=0;i<5;i++){for(j=0;j<5;j++){buf[i+1][j+1]=buf[i][j];}buf[i+1][0]=buf[i][j];}for(i=0;i<6;i++){for(j=0;j<6;j++)printf("%d ",buf[i][j]);printf("\n");}return 0;}#include<stdio.h>#define N 7int main(int argc,char **argv) {int buf[N][N];int i,j,k,m,n;int a=0,b=N-1;int count=1;for(i=0;i<(N/2)+(N%2);i++) {for(j=a;j<=b;j++){buf[a][j]=count++;}for(k=a+1;k<=b;k++){buf[k][b]=count++;}for(m=b-1;m>=a;m--){buf[b][m]=count++;}for(n=b-1;n>a;n--){buf[n][a]=count++;}a++;b--;}for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%5d",buf[i][j]);printf("\n");}return 0;}4.#include<stdio.h>#define N 5int main(int argc,char **argv) {int buf[N][N];int i,j,k;int count=1;int n=0;for(i=0;i<N;i++){for(k=0,j=n;j>=0;j--,k++) buf[j][k]=count++;n++;}for(i=0;i<N;i++){for(j=0;j<N-i;j++)printf("%5d",buf[i][j]);printf("\n");}return 0;}5.#include<stdio.h>#define N 5int main(int argc,char **argv) {int buf[N][N];int i,j;int a=0,b=N-1;int count=1;for(i=0;i<N/2+N%2;i++){for(j=a;j<=b;j++)buf[a][j]=count;for(j=a+1;j<=b;j++)buf[j][b]=count;for(j=b-1;j>=a;j--)buf[b][j]=count;for(j=b-1;j>a;j--)buf[j][a]=count;count++;a++;b--;}for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%5d",buf[i][j]);printf("\n");}return 0;}6.#include<stdio.h>#include<stdlib.h>typedef struct s_node s_list;typedef s_list *link;struct s_node{char ch;int flag;link next;};link top;void push(char ch,int flag){link newnode;newnode=(link)malloc(sizeof(s_list)); newnode->ch=ch;newnode->flag=flag;newnode->next=NULL;if(top==NULL){top=newnode;}else{newnode->next=top;top=newnode;}}int pop(){int flag;link stack;if(top!=NULL){stack=top;top=top->next;flag=stack->flag;free(stack);}return flag;}int op(char ch){switch(ch){case '+':return 1;break;case '-':return 2;break;case '*':return 3;break;case '/':return 4;break;default:return 5;}}void nirnava(char *buf,int count)//count个数，buf数组{int bool=1;int min;int j;int i;int k;int flag;for(i=0;i<count;i++){if(buf[i]=='(')push(buf[i],i);if(buf[i]==')'){flag=pop();if(flag!=0){if((buf[flag-1]=='(')&&(buf[i+1]==')')) {buf[flag]='!';buf[i]='!';}min=op(buf[flag]);for(j=flag+1;j<i;j++) {if(buf[j]=='(') {push(buf[j],j);bool=0;continue;}elseif(buf[j]==')'){pop();bool=1;continue;}if(bool==1){if(min>op(buf[j]))min=op(buf[j]); }if(i<count-1){if((buf[i+1]=='+')||(buf[i+1]=='-')) {if(flag==0){buf[i]='!';buf[flag]='!';}elseif(op(buf[flag-1])<=min){buf[i]='!';buf[flag]='!';}}elseif((buf[i+1]=='*')||(buf[i+1]=='/')){if(flag==0){buf[i]='!';buf[flag]='!';}elseif((min>=op(buf[i+1])&&op(buf[flag-1])<=min)) {buf[i]='!';buf[flag]='!';}}}elseif(i==count-1){if(flag==0){buf[i]='!';buf[flag]='!';}elseif(op(buf[flag-1])<=min){buf[i]='!';buf[flag]='!';}}}}for(k=0;k<count;k++){if(buf[k]!='!') printf("%c",buf[k]);}printf("\n");}int main(void){char buf[255];int i;for(i=0;i<255;i++){scanf("%c",&buf[i]);if(buf[i]=='\n') break;}buf[i]='\0';nirnava(buf,i);return 0;}7.#include<stdio.h>#include<stdlib.h>int ack(int m,int n);int count=0;int main(int argc,char **argv) {int m,n;scanf("%d%d",&m,&n);printf("%d\n",ack(m,n));printf("%d\n",count);return 0;}int ack(int m,int n){count++;if(m==0)return n+1;elseif(n==0)return ack(m-1,1);elsereturn ack(m-1,ack(m,n-1));}8.#include<stdio.h>char buf[1024];int is_huiwen(int a,int count){if(a==count/2){return 1;}elseif(buf[a]==buf[count-a-1])return (is_huiwen(a-1,count))&&1;else{return 0;}}int main(void){int count;int i;for(i=0;i<1024;i++){scanf("%c",&buf[i]);if(buf[i]=='\n') break;}count=i;i--;printf("%d",is_huiwen(i,count)); return 0;}9.#include<stdio.h>char buf[100];int pos(int a,int b){if(b-a==1)return 1;elseif(b-a==0)return 1;elsereturn pos(a,b-1)+pos(a,b-2); }int main(void){int a,b;scanf("%d%d",&a,&b);printf("%d",pos(a,b));return 0;}10.#include<stdio.h>#define MAX 1024int buf[MAX];int main(void){int m,n;int i;scanf("%d%d",&m,&n);for(i=0;i<MAX;i++)buf[i]=0;i=0;while(buf[i%m]==0){buf[i%m]=1;i+=n;}for(i=0;i<m;i++){if(buf[i]==0) printf("%d ",i);}return 0;}11.#include<stdio.h>int main(void){int temp,temp1;int count=0;int n;int i;scanf("%d",&n);for(i=1;i<=n;i++){temp=i%10;if(temp==5)count++;elseif(temp==0){temp1=i;while((temp1%10)==0){temp1=temp1/10;count++;}}}printf("%d",count);return 0;}12.#include<stdio.h>int main(void){int count=0;int buf[53];int i,n;for(i=1;i<53;i++){buf[i]=1;}for(n=2;;n++){for(i=n;i<53;i+=n) {buf[i]=1-buf[i];count++;if(count>=104)break;}if(count>=104)}for(i=1;i<53;i++){if(buf[i]==1)printf("%d ",i);}printf("\n");return 0;}13.#include<stdio.h>int main(void){int a,b,c,d,e;for(a=1;a<=5;a++)for(b=1;b<=5;b++)if(a!=b)for(c=1;c<=5;c++)if(c!=a&&c!=b)for(d=1;d<=5;d++)if(d!=a&&d!=b&&d!=c)e=15-a-b-c-d;if(e!=a&&e!=b&&e!=c&&e!=d)if(((b==3)+(c==5)==1)&&((d==2)+(e==4)==1)&&((b==1) +(e==4)==1)&&((c==1)+(b==2)==1)&&((d==2)+(a==3)==1))printf("a=%d,b=%d,c=%d,d=%d,e=%d",a,b,c,d,e);}return 0;}14.#include<stdio.h>int main(void){int buf[3];int i;int mul;int temp;for(i=10;i<=31;i++){mul=i*i;temp=mul;buf[0]=temp%10;temp=temp/10;buf[1]=temp%10;temp=temp/10;buf[2]=temp;if((buf[0]==buf[1])||(buf[0]==buf[2])||(buf[1]==bu f[2])){printf("%d^2=%d\n",i,mul);}}return 0;}15.#include<stdio.h>int main(void){int a,b,c;for(a=1;a<=3;a++)for(b=1;b<=3;b++)if(a!=b){c=6-a-b;if(c!=a&&c!=b)if((a!=1)&&((c!=1)&&(c!=3))==1)printf("a=%d,b=%d,c=%d",a,b,c); }return 0;}16.#include<stdio.h>int main(void){int k;int n;scanf("%d",&n);k=(n%4==0)+(n%7==0)*2+(n%9==0)*4;switch(k){case 7:printf("all");break;case 6:printf("7 and 9");break;case 5:printf("4 and 9");break;case 4:printf("9");break;case 3:printf("4 and 7");break;case 2:printf("7");break;case 1:printf("4");break;case 0:printf("none");break;}return 0;}17.#include<stdio.h>int main(void){int a,b,c,d;printf("please think of a number between 1 and 100.\n"); printf("your number divided by 3 has a remainder of "); scanf("%d",&a);printf("your number divided by 4 has a remainder of "); scanf("%d",&b);printf("your number divided by 7 has a remainder of "); scanf("%d",&c);printf("let me think a moment...\n");d=36*c+28*a+21*b;while(d>84)d=d-84;printf("your number was %d\n",d);return 0;}18.#include<stdio.h>int main(void){int buf[10];int i,j;int mul;int temp1,temp2;int bool;for(i=5000;i<=9999;i++){bool=0;for(j=0;j<10;j++) buf[j]=0;temp1=i;while(temp1>0) {if((++buf[temp1%10])>1){bool=1;break;}temp1/=10;}if(bool==1) continue;mul=i*2;temp2=mul;while(temp2>0){if((++buf[temp2%10])>1){bool=1;break;}temp2/=10;}if(bool==1)continue;printf("2*%d=%d\n",i,mul);}return 0;}19.#include<stdio.h>#include<stdlib.h>int ppow(int a,int b){int mul=1;int i;for(i=0;i<b;i++){mul=a*mul;}return mul;}int main(void){int t;char buf[10];int i,j,k;int sum=0;for(i=0;i<10;i++){scanf("%c",&buf[i]);if(buf[i]=='\n') break;}buf[i]='\0';for(j=0;j<i;j++){if((buf[j]>='0')&&(buf[j]<='9')) buf[j]=buf[j]-48;elseif((buf[j]>='A')&&(buf[j]<='F'))buf[j]=buf[j]-55;elseexit(1);}k=0;for(j=i-1;j>=0;j--){t=ppow(16,k);sum=sum+t*(int)buf[j];k++;}printf("%d\n",sum);return 0;}20.#include<stdio.h>int main(void){int a;int b;int c;int i;int buf[10];for(a=10;a<=99;a++){for(i=0;i<10;i++)buf[i]=0;if((++buf[a%10]>1)||(++buf[a/10%10]>1)) continue;for(b=100;b<=999;b++){for(i=0;i<10;i++){if((i!=a%10)&&i!=a/10%10)buf[i]=0;}if((++buf[b%10]>1)||(++buf[b/10%10]>1)||(++buf[b/100%10] >1))continue;c=a*b;if(c<10000&&c>999){if((++buf[c%10]>1)||(++buf[c/10%10]>1)||(++buf[c /100%10]>1)||(++buf[c/1000%10]>1))continue;elseprintf("%d*%d=%d\n",a,b,c);}}}return 0;}21.#include<stdio.h>int main(void){int a;int b;int i;int t;int buf[10];int bool;for(a=317;a<1000;a++){bool=0;for(i=0;i<10;i++)buf[i]=0;if((++buf[a%10]>1)||(++buf[a/10%10]>1)||(++buf[a/1 00%10]>1))continue;b=a*a;t=b;for(i=0;i<6;i++){if(++buf[t%10]>1){bool=1;break;}t=t/10;}if(bool==1)continue;printf("%d^2=%d\n",a,b);}return 0;}22.#include<stdio.h>int main(void){int buf[100];int i;int n;int max;int temp;for(i=1;i<100;i++){scanf("%d",&buf[i]);if(buf[i]==0)break;}n=i;max=buf[1]+buf[2]+buf[3]+buf[4];for(i=2;i%10!=1;i++){temp=buf[i%10]+buf[(i+1)%10]+buf[(i+2)%10]+buf[(i+ 3)%10];if(temp>max)max=temp;}printf("max=%d\n",max);return 0;}23.#include<stdio.h>void nirnava(int n){if(n<10)printf("%d ",n);else{nirnava(n/10);printf("%d ",n%10);}}int main(void){int count=0;int n;int i;int t;scanf("%d",&n);t=n;while(t>0){printf("%d ",t%10);t=t/10;count++;}printf("\n");nirnava(n);printf("\n%d位数\n",count);}24.#include<stdio.h>int main(void){int buf[4]={2,3,5,7};int i,j,k,temp,m;int bool;int mul;for(i=0;i<4;i++)for(j=0;j<4;j++)for(k=0;k<4;k++)for(m=0;m<4;m++){bool=0;mul=(buf[i]+buf[j]*10+buf[k]*100)*buf[m];if(mul<1000)continue;temp=mul;while(temp>0){if((temp%10==2)||(temp%10==3)||(temp%10==5)||(temp%10==7 )){}else{bool=1;break;}temp/=10;}if(bool==0){printf("%d%d%d * %d= %d\n",buf[k],buf[j],buf[i],buf[m],mul);}}return 0;}25.#include<stdio.h>int main(void){int buf[4]={2,3,5,7};int i,j,k,m,n;int bool;int mul,mul1,mul2;int temp,temp1,temp2;for(i=0;i<4;i++)for(j=0;j<4;j++)for(k=0;k<4;k++)for(m=0;m<4;m++)for(n=0;n<4;n++){bool=0;mul=(buf[i]+buf[j]*10+buf[k]*100)*(buf[m]+buf[n] *10);mul1=(buf[i]+buf[j]*10+buf[k]*100)*buf[m];mul2=(mul-mul1)/10;if((mul<10000)||(mul1<1000)||(mul2<1000)) continue;temp=mul;temp1=mul1;temp2=mul2;while(temp>0){if((temp%10==2)||(temp%10==3)||(temp%10==5)||(temp%10= =7)){}else{bool=1;break;}temp/=10;}if(bool==0){while(temp1>0){if((temp1%10==2)||(temp1%10==3)||(temp1%10==5) ||(temp1%10==7)){}else{bool=1;break;}temp1/=10;}}if(bool==0)while(temp2>0){if((temp2%10==2)||(temp2%10==3)||(temp2%10==5)||(t emp2%10==7)){}else{bool=1;break;}temp2/=10;}if(bool==0){printf("第一行 : %d%d%d\n第二行 : %d%d\n第三行 : %d\n 第四行 : %d\n第五行 : %d\n\n\n\n\n",buf[i],buf[j],buf[k],buf[m],buf[n],mul1,mu l2,mul);}}return 0;}26.#include<stdio.h>//从a到b是不是循环节int is_xunhuan(int *buf,int a,int b) {int i;if(a==b){for(i=1;i<10;i++){if(buf[a]==buf[a+i]){}elsereturn 0;}}elsefor(i=a;i<=b;i++){if(buf[i]==buf[i+b-a+1]){}else{return 0;}return 1;}int main(void){int buf[1024];int yushu;int m,n;int i,j,k;scanf("%d%d",&m,&n); yushu=m;buf[0]=0;i=1;while(yushu!=0){yushu=yushu*10;buf[i]=yushu/n;yushu=yushu%n;i++;if(i==1024) break;if(i<1024){printf("有限小数\n");printf("%d.",buf[0]);for(j=1;j<i;j++)printf("%d",buf[j]);printf("\n");}else{printf("循环小数\n");for(i=1;i<100;i++)for(j=i;j<200;j++){if(is_xunhuan(buf,i,j)){printf("%d.",buf[0]);if(i>1){for(k=1;k<i;k++)printf("%d",buf[k]);printf("(");for(k=i;k<=j;k++)printf("%d",buf[k]);printf(")");printf("\n");return 0;}}}return 0;}27.#include<stdio.h>int main(void){int n;char eng[12][10]={"一月","二月","三月","四月","五月","六月","七月","八月","九月","十月","十一月","十二月"};scanf("%d",&n);printf("%s\n",eng[n-1]);return 0;}算法设计和分析（第二版）主编：吕国英习题答案第四章1.#include<stdio.h>int main(void){int buf[100];int n;int i,j,k;scanf("%d",&n);for(i=0;i<n;i++)buf[i]=2;for(i=0;i<n-1;i++){for(j=0;j<n-i-1;j++) {buf[j]+=2;}}for(j=0;j<n;j++){if(buf[j]>=10){buf[j+1]+=buf[j]/10;buf[j]=buf[j]%10;}}for(i=n-1;i>=0;i--)printf("%d",buf[i]); printf("\n");return 0;}2.#include<stdio.h>int main(void){int n=2;int i;for(i=1;i<=9;i++){n=(n+2)*2;}printf("%d\n",n);return 0;}3.#include<stdio.h>int main(void){int a=54;int n;int m;printf("计算机先拿3张牌\n");a=a-3;while(a>=0){printf("还剩%d张牌\n",a);printf("你拿几张？请输入：");scanf("%d",&n);if(n>4||n<1||n>a){printf("错误！重新拿牌\n");continue;}a=a-n;printf("还剩%d张牌\n",a);if(a==0)break;m=5-n;printf("计算机拿%d\n",m);a=a-m;}return 0;}4.#include<stdio.h>int d;int a1,a2;int fun(int n);int main(void){int n;printf("n=?,d=?,a1=?,a2=?");scanf("%d%d%d%d\n",&n,&d,&a1,&a2); printf("%d\n",fun(n));return 0;}int fun(int n){if(n==1)return a1;if(n==2)return a2;return fun(n-2)-(fun(n-1)-d)*2;}5.#include<stdio.h>char chess[8][8];int is_safe(int row,int col);int queen(int row,int col,int n); int main(void){int i,j;for(i=0;i<8;i++)for(j=0;j<8;j++)chess[i][j]='X';queen(0,0,0);for(i=0;i<8;i++){for(j=0;j<8;j++)printf("%c ",chess[i][j]);printf("\n");}return 0;}int is_safe(int row,int col){int i,j;for(i=0;i<8;i++){if(chess[row][i]=='Q') return 0;。