计算机导论 第五章测验题答案

1、第五章测验题答案1.计算机程序设计语言的分类：(1)机器语言：由机器指令构成的语言称机器语言，即用二进制编码组成。(如：onioioi)特点：费时费事；难懂容易错；只能在一种型号计算机上运行；可以直接在计算机上运行。(2)汇编语言：用容易记忆的符号来代替机器指令中操作码和地址码的一种 语言。(如:ADD代表“+” SUB代表 MOV代表“传递”)优点：程序直观容易阅读；编程工作量相对小。缺点：只能在一种型号机器上运行；不能直接在计算机上运行。(3)高级程序设计语言：高级程序设计语言是一种面向过程或者面向对象的 语言，不面向机器，用一些符号或者数字对求解的问题或者现实世界进行描 述。特点： 直观

2、、易写、易读、工作量小；不依赖于具体的机器；便于程序交流；不可直接在计算机上运行，经编译程序编译成机器语言后方可运行。.算法(Algorithm)是对特定问题求解步骤准确而完整的描述，它的表现 形式是计算机指令的有序系列，执行这些指令就可解决特定问题。一个好的算 法应当具有以下5个重要特性。(1)有限性：算法在执行有限步之后必须终止，且每一步都应在有限的时间 内完成；(2)确定性：算法的每一步必须要有确切的含义，不能存在二义性；(3)可行性：算法的每一步都是可执行的，可以通过有限次操作来完成其功 能；(4)输入：一个算法具有。个或多个输入；(5)输出：一个算法具有1个或多个输出。.常用算法的描

3、述方法有：自然语言法、流程图法、N-S流程图法、伪代 码法等。(1)自然语言:就是采用人们日常使用的语言，来描述解决问题的方法和步 骤；这种描述方法通俗易懂，即使是不熟悉计算机语言的用户也很容易理解程 序。(2)流程图:流程图是以特定的图形符号加上说明来表示算法，通常是用一 些图框来表示各种操作。(3)N-S图是在流程图的基础上完全去掉流程线，并将全部算法写在一个矩 形框内，且框内还可以包含其他框的表示形式。N-S图包括顺序、选择和循环3 种基本结构，如下列图所示：当条件为真时循环体循环结构(4)伪代码:伪代码是介于自然语言和计算机语言之间的文字和符号.伪代码 通常采用自然语言、数学公式和符号

4、来描述算法的操作步骤，同时采用计算机 高级语言的控制结构来描述算法步骤的执行顺序。在程序开发期间，伪代码经 常用于“规划” 一个程序，然后再转换成某种高级语言程序。.计算机技术所涉及的算法比拟多，常用的算法有枚举法、递推法、递归 法、贪心算法、分治法、回溯法等.(1)枚举法，或称为穷举法，其基本思路是：对于要解决的问题，列举出它 所有可能的情况，逐个判断哪些是符合问题所要求的条件，从而得到问题的 解；(2)递推法:是按照一定的规律来计算序列中的某个项，通常是通过计算前 面的一些项来得出序列中指定项的值；(3)递归法:程序直接或间接自己调用自己的方法简称为递归，它通常是把 一个大型的、复杂的问题

5、层层转化为一个个与原问题相似的、规模较小的问题 来进行求解；(4)贪心算法:贪心算法采用自顶向下，以迭代的方式做出相继的贪心选 择，每做一次贪心选择就将所求解问题简化为一个规模更小的子问题，通过每 一步贪心选择，就可得到问题的一个最优解。贪心算法的每一步都能获得局部 最优解，但由此产生的全局解有时不一定是最优解，所以贪婪法不能回溯。(5)分治法：分治法是把一个复杂的问题分解成两个或更多个相同或相似的 子问题，再把子问题分解成更小的子问题，直到最后的子问题可以进行简单的 直接求解，合并所有子问题的解就可得到原问题的解。(6)回溯法：回溯法的基本思想是，在包含问题所有解的解空间树中，按照 深度优先搜索的策略，从根结点出发深度搜索解空间树；当搜索到某一结点 时，要先判断该结点是否包含问题的解，如果包含就从该结点出发继续搜索下 去，否那么就逐层向其祖先结点