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

算法设计与分析基础习题1.15..证明等式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//输出:实根或者无解信息If a≠0D←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. 这个断言是正确的。

软件工程复习题一、单选题1、软件开发的结构化设计(SD)方法,全面指导模块划分的最重要原则应该是( c )A模块高内聚B模块低耦合C模块独立性D程序模块化2、软件工程方法的提出起源于软件危机,而其目的应该是最终解决软件的什么问题?( D )A产生危机B质量保证C开发效率D生产工程化3、软件工程开发的可行性研究是决定软件项目是否继续开发的关键,而可行性研究的结论主要相关于( A)A软件系统目标B软件的性能C软件的功能D软件的质量4、软件需求分析一般应确定的是用户对软件的( D)A.功能需求B.非功能需求C.性能需求D.功能需求和非功能需求5、软件测试是满足软件的功能和性能要求,保证软件正确性的措施,一般软件测试计划的制订应始于软件开发的哪个阶段? ( D)A.需求分析B.软件设计C.程序编码D.软件计划6、软件工程方法是在实践中不断发展的方法,而早期的软件工程方法主要是指( B )A.原型化方法B.结构化方法C.面向对象方法.D.功能分解法7、数据流图描述数据在软件中流动和被处理变换的过程,它是以图示的方法来表示,即.( A )A.软件模型B.软件功能C.软件结构D.软件加工8、软件工程学涉及到软件开发技术和工程管理两方面的内容,下述内容中哪一个不属于开发技术的范畴?（D）A.软件开发方法B.软件开发工具C.软件工程环境D.软件工程经济9、软件文档是软件工程实施中的重要成份,它不仅是软件开发的各阶段的重要依据,而且也影响软件的（）A.可理解性B.可维护性C.可扩展性D.可靠性10、从( )语言开始,软件摆脱了对硬件的依赖。

A.第一代B.第二代C.第三代D.第四代11、在下面列出的基本成分中,哪个不是实体关系图的基本成分? ( )A.实体B.数据存储C.关系D属性12、结构化程序设计主要强调程序的（C）A.效率B.速度C.可读性D.大小13、在软件工程中根据程序的功能说明,而不关心程序内部逻辑的测试方法为( A)A.黑盒法B.白盒法C.灰盒法D.综合法14、软件开发的结构化分析方法,常用的描述软件功能需求的工具有( C)A业务流程图,数据字典 B.软件流程图,模块说明C.数据流图,数据字典D.系统流程图,程序编码15、结构化程序设计思想的核心是要求程序只由顺序、循环和( A)三种结构组成。

2021现代科技学院《软件技术基础》练习题+答案《软件技术基础》练习题太原理工大学现代科技学院20211第一章算法一、选择题1.算法的复杂度包括【】。

a、时间复杂度b、空间复杂度c、时间及空间复杂度d、以上都不对2.若x在长度为n的无序线性顺序表的概率为50%，则在该表搜寻x的平均值搜寻次数（平均值性态分析）为【】。

a、(n*3+1)/4b、(n-1)/2c、(n+1)/2d、(n+1)*n/23.若x在长度为n的无序线性顺序表的概率为50%，则在该表搜寻x的最坏情况分析为【】。

a、n/2b、(n-1)/2c、(n+1)/2d、n4.未知基本运算继续执行次数与n的关系，则以下哪个时间复杂度最小：【】。

a.f(n)=1b.f(n)=2n-1c.f(n)=10000n+10000d.f(n)=n2-100005.算法分析的目的是【】。

a．找到数据结构的合理性b．研究算法中的输入和输出的关系c．分析算法的效率以求改进d．分析算法的易懂性和文档性二、填空题1.常用算法包括_________、_________、_________、_________、_________和回溯法。

2.算法的基本特征有_________、_________、有穷性、输入和输出。

3.下列程序段的时间复杂度是____。

for(i=1；i<=n；i++)a[i，i]=0；4.下列程序段的时间复杂度是____s=0；for(i=1；i<=2n；i++)for(j=1；j<=n；j++)s=s+b[i][j]；sum=s；5.以下程序段的时间复杂度就是____i=1；2while(i<=n)i=i*2；6.在下面的程序段中，s=s+p；语句的执行次数为_________，p=p×j语句的执行次数为_________，该程序段的时间复杂度为________。

inti=0,s=0,p=1;while(++i<=n){for(j=1;j<=i;j++)p=p×j;s=s+p;}7.常用时间复杂度的量级存有：常数阶o(_________)、对数阶o(_________)、线性阶o(_________)、平方阶o(_________)和指数阶o(_________)。

第一章软件测试概述1.对软件缺陷有什么真实的体验？当登录某网站购物完毕并退出后，忽然想查查购物时付账的总金额，于是按了浏览器左上角的“退回”按钮，就又回到了退出前的网页。

该软件缺陷所属类别与软件产品说明书的要求有关。

2.以客户为导向来讨论软件测试的理念和作用判断软件是否存在缺陷的基本依据是软件的用户需求，软件功能特性就是为了满足用户需求，不能满足用户需求的功能是有缺陷的。

所以软件测试要服从用户需求，以用户需求为依据，来对产品进行检验。

软件测试的作用是尽可能多的发现软件中的错误。

3.给软件测试下定义，它的内容是什么？软件测试是由“验证”和“有效性确认”活动构成的整体：“验证”是检验软件是否已正确地实现了产品规格书所定义的系统功能和特性；“有效性确认”是确认所开发的软件是否满足用户真正需求的活动。

4.软件开发和软件测试是一种对立的关系吗？为什么？软件测试和软件开发并行的活动，使软件测试和软件开发相互协作、相互补充，构成有机的软件开发整体。

第二章需求和设计评审1.需求评审和设计评审可以同时进行吗？为什么？不能，需求评审一定要“从用户的角度”出发，基于用户需求，一切围绕用户需求进行评审，而设计评审一般依据设计技术的评审标准和非功能性质量特性的设计评审要求，采用分层评审和整体评审相结合的方法，经过整体评审到分层评审，再从分层评审到整体评审的过程，既能确保评审的深度，又能确保评审的一致性。

2.需求评审和设计评审有什么不同？从测试的观点看，产品需求评审是对需求的验证，属于静态测试，也是做好软件测试和理解设计等的基础性工作。

设计评审时，先从系统架构，整体功能结构上开始审查系统的非功能特性是否得到完美实现，然后深入到功能组件，操作逻辑和用户界面设计等各个方面的细节审查，力求发现任何不合理的设计以及设计缺陷，尽早地设计上的问题得到纠正。

3.在需求评审过程中，最有效的方法是什么？在需求形成的过程中，最好采用分阶段评审方法进行多次评审，而不是在需求最终形成后进行一次评审，分阶段评审可以将原本需要进行的大规模评审拆分成各个小规模的评审，降低了需求分析返工的风险，提高了评审的质量。

软考算法题库及答案详解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. 题目：编写一个算法，实现归并排序。

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

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

太原理工复试题《软件工程》题库及答案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 ）级别的信息共享。

Java习题答案_太原理⼯⼤学软件⼯程（2）太原理⼯⼤学·Java语⾔程序设计(2)第5章习题解答1.使⽤抽象和封装有哪些好处？答：抽象是⼈们解决问题的基本⼿段，程序设计过程中需要对问题领域进⾏分析、设计中得出的抽象概念，然后封装成⼀些类。

封装也称为信息隐藏，是指利⽤抽象数据类型将数据和基于数据的操作封装在⼀起，使其构成⼀个不可分割的独⽴实体，数据被保护在抽象数据类型的内部，尽可能地隐藏内部的细节，只保留⼀些对外接⼝使之与外部发⽣联系。

系统的其他部分只有通过包裹在数据外⾯的被授权的操作来与这个抽象数据类型交流与交互。

也就是说，⽤户⽆需知道对象内部⽅法的实现细节，但可以根据对象提供的外部接⼝(对象名和参数)访问该对象。

把对象中相同或相似地地⽅抽象出来，从特殊到⼀半，从具体到抽象的过程，对象经过抽象得到类，类的实例化成了对象。

也可以⾼度抽象成接⼝，让不完全相同，但包含相同点的对象实现此接⼝，也就是利⽤多态实现。

把相同点抽象出来，抽象成此类或接⼝的⽅法、属性、字段等，封装就是隐藏某个对象的与其基本特性没有很⼤关系的所有详细信息的过程，就是将需要让其他类知道的暴露出来，不需要让其他类了解的全部隐藏起来，封装可以阻⽌对不需要信息的访问，我们可以使⽤访问指定符实现封装，也可以使⽤⽅法实现封装，可以将隐藏的信息作为参数或者属性值、字段指传给公共的接⼝或⽅法，以实现隐藏起来的信息和公开信息的交互。

封装的⽬的就是为了实现“⾼内聚，低耦合”。

⾼内聚就是类的内部数据操作细节⾃⼰完成，不允许外部⼲涉，就是这个类只完成⾃⼰的功能，不需要外部参与；低耦合，就是仅暴露很少的⽅法给外部使⽤。

2.构造⽅法的作⽤是什么？它与⼀般的成员⽅法在使⽤和定义⽅⾯有什么区别？答：构造⽅法⽤于⽣成⼀个对象实例，并对对象实例中的成员变量初始化。

当⽤new创建⼀个类的新的对象时，构造⽅法⽴即执⾏。

构造⽅法名字必须与类名相同。

3.Overload和Override的区别?答：⽅法重载（overloading）与⽅法覆盖（overriding）是实现多态性的基本⼿段，但两者的机制不同。

算法分析与设计基础习题答案[第1版]习题1.15..证明等式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,r6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m 的一对数字 ,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//输出:实根或者无解信息If a≠0D←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*aelse 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=(intn/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<=nb.删除有序数组的第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(nb.α>0时,Θ(αg(n= Θ(g(n解:a. 这个断言是正确的。

一、填空题（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树定义要求的是（）。

太原理工大学·Java语言程序设计第1章习题解答1．Java语言有那些特点？答：Java语言的特点包括：平台无关性、面向对象、简单性、安全性、分布式、健壮性、解释型、多线程。

2．为什么说Java是结构中立的，具有跨平台特性？答：无论哪种编程语言编写的程序最终都需要操作系统和处理器来完成程序的运行，平台无关性是指软件的运行不因操作系统、处理器的变化导致程序无法运行或出现运行错误。

以C++程序为例，C++编译器针对源程序所在平台进行编译、连接，然后生成机器指令，这样就无法保证C++编译器产生的可执行文件在所有平台上都被正确执行。

如果更换了平台，可能需要修改源程序，并针对新的平台重新编译源程序。

相反，Java源代码不会针对一个特定平台进行编译，而是生成一种字节码中间文件（class 文件），这种文件是平台无关且体系结构中立的。

也就是说，无论一个Java程序是在Windows、Solaris、Linux还是其他具有Java编译器的操作系统下编译，作为编译结果的字节码文件都是相同的，都可以在任何具有Java虚拟机（JVM）的计算机上运行。

JVM能够识别这些字节码文件，JVM将字节码文件进行转换，使之能够在不同平台上运行。

任何操作系统只要安装了JVM，就可以解释并执行这种与体系结构无关的字节码文件，实现了跨平台。

跨平台特性保证了Java的可移植性，任何Java源程序都可以移植到其他平台上。

除此之外，Java的数据类型与机器无关，原始数据类型存储方式是固定的，避开了移植时可能产生的问题。

例如，在任何机器上，Java的整型都是32位的，而C++中整型的存储依赖于目标计算机。

另外Java的字符串采用标准的Unicode格式保存，也保证了Java的可移植性。

3．简述Java的3种主要平台，这些适合开发那种应用？答：Java的开发平台（JDK）是开发人员用来构建Java应用程序的软件包，它包括：Java 虚拟机（JVM）、Java编译器（javac）、Java归档（jar）实用程序、Java文档（javadoc）实用程序等。

算法分析与设计重点课后习题答案习题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、什么是算法？算法是指解决特定问题的一系列明确步骤，它具有确定性、可行性、有穷性、输入和输出等特性。

例如，计算两个数的最大公约数的欧几里得算法，就是通过反复用较小数去除较大数，然后将余数作为新的较小数，直到余数为 0，此时的除数就是最大公约数。

2、算法的复杂度包括哪些？它们的含义是什么？算法的复杂度主要包括时间复杂度和空间复杂度。

时间复杂度是指算法执行所需要的时间量，通常用大 O 记号来表示。

例如，一个算法的时间复杂度为 O(n)，表示其执行时间与输入规模 n成正比。

空间复杂度则是算法在运行过程中所需要的额外存储空间的大小。

比如说，一个算法需要创建一个大小为 n 的数组来存储数据，那么其空间复杂度就是 O(n)。

二、分治法1、分治法的基本思想是什么？分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题结构相同。

然后分别求解这些子问题，最后将子问题的解合并得到原问题的解。

2、请举例说明分治法的应用。

例如归并排序算法。

将一个未排序的数组分成两半，对每一半分别进行排序，然后将排好序的两部分合并起来。

其时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

三、动态规划1、动态规划的基本步骤有哪些？动态规划的基本步骤包括：（1）定义问题的状态。

（2）找出状态转移方程。

（3）确定初始状态。

（4）计算最终的解。

2、解释最长公共子序列问题，并给出其动态规划解法。

最长公共子序列问题是指找出两个序列的最长公共子序列的长度。

假设我们有两个序列 X 和 Y，用 dpij 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。

状态转移方程为：如果 Xi 1 ＝＝ Yj 1，则 dpij ＝ dpi 1j 1 ＋ 1否则 dpij ＝ max(dpi 1j, dpij 1)四、贪心算法1、贪心算法的特点是什么？贪心算法在每一步都做出当前看起来最优的选择，希望通过这种局部最优选择达到全局最优解。

《算法设计与分析》考试题⽬及答案解析《算法分析与设计》期末复习题⼀、选择题1.应⽤Johnson法则的流⽔作业调度采⽤的算法是（D）A. 贪⼼算法B. 分⽀限界法C.分治法D. 动态规划算法2.Hanoi塔问题如下图所⽰。

现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。

移动圆盘时遵守Hanoi塔问题的移动规则。

由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔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．最优⼦结构性质与重叠⼦问题性质D. 预排序与递归调⽤7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。

A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分⽀限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。

A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。

A.B.C.D.10. 回溯法的效率不依赖于以下哪⼀个因素？（C ）A.产⽣x[k]的时间；B.满⾜显约束的x[k]值的个数；C.问题的解空间的形式；D.计算上界函数bound的时间；E.满⾜约束函数和上界函数约束的所有x[k]的个数。

《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。

2.程序：程序是算法用某种程序设计语言的具体实现。

二、简答题：1.算法需要满足哪些性质？简述之。

答：算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入。

（2）输出：算法产生至少一个量作为输出。

（3）确定性：组成算法的每条指令清晰、无歧义。

（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

答：将递归算法转化为非递归算法的方法主要有：（1）采用一个用户定义的栈来模拟系统的递归调用工作栈。

该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

（2）用递推来实现递归函数。

（3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]<a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。

答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n 的关系。

（1）设比较一次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。