公共基础知识-算法篇.doc

1、下列叙述中正确的是（ ）答案：D 2011-9A)算法是程序B)设计算法时只需要考虑数据结构的设计C)设计算法时只需要考虑结果的可靠性D)以上三种说法都不对算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算方法，程序可以作为算法的一种描述。 （算法也可以用流程图、专门的描述语言、自然语言来描述。 ） 2、算法的基本要素 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 (1) 算法中对数据的运算和操作： 算术运算；逻辑运算； 关系运算； 数据传输 （2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环 3 种基本控制结构组合而成。 3、算法设计的基本方法 （1）列举法：列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 （2）归纳法：归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。 （3）递推：递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。 （4）递归 ：为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与间接递归两种。 （5）减半递推技术：所谓“减半” ，是指将问题的规模减半，而问题的性质不变；所谓“递推” ，是指重复“减半”的过程。 （6）回溯法：在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试” 。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。 5、算法的有穷性是指（ ）答案：A 2008-3A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的 D）算法只能被有限的用户使用1、算法的基本特征： （1）可行性，针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报，要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 （2）算法的时间复杂是指() 答案：D 2010-3A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数4. 算法的空间复杂度是指（ ）。答案 A 2009-9A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量C.算法程序中的语句或指令条数 D.算法在执行过程中所需要的临时工作单元数1、算法的时间复杂度 算法的时间复杂度，是指执行算法所需要的计算工作量。 （不直接衡量时间） 算法的工作量用算法所执行的基本运算次数来度量，只依赖于问题的规模，它是问题的规模函数。 2、算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。包括算法程序占用的空间、输入数据所占用的空间及算法执行过程中所需要的额外空间。 10、下列选项中属于面向对象设计方法主要特征是（ ）答案：A 2011-9A)继承 B)自顶向下C)模块化D)逐步求精结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。 结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。 面向对象的主要特征：封装性、继承性、多态性。5. 结构化程序所要求的基本结构不包括（ ）答案：B 2011-3A. 顺序结构B. GOTO跳转C. 选择（分支）结构D. 重复（循环）结构解析：结构化程序设计的三种基本控制结构为:顺序结构、选择结构和重复结构。（6）面向对象方法中，继承是指_。答案：D 2010-9A）一组对象所具有的相似性质 B）一个对象具有另一个对象的性质C）各对象之间的共同性质 D）类之间共享属性和操作的机制面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 1. 对象 ：通常把对象的操作也称为方法或服务。 属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。属性值应该指的是纯粹的数据值，而不能指对象。 操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。 对象具有如下特征：标识惟一性、分类性、多态性、封装性、模块独立性。 2. 类和实例 ：类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。 3. 消息 ：消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。 一个消息由三部分组成：接收消息的对象的名称、消息标识符（消息名）和零个或多个参数。 4. 继承 ：广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。 继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。 5. 多态性 ：对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。6. 下列选项中不属于结构化程序设计原则的是（ ）。答案 A 2009-9A.可封装 B.自顶向下 C.模块化 D.逐步求精结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。 (4)下列排序方法中,最坏情况下比较次数最少的是（ ）答案：D 2009-3A)冒泡排序 B)简单选择排序 C)直接插入排序 D)堆排序（1）冒泡排序法：在最坏的情况下，需要比较次数为n(n-1)/2。 （2）快速排序法：在最坏情况下时间复杂性：n(n-1)/2，最好情况为 nlog2n。（3）简单插入排序法，最坏情况下，比较次数为n（n-1）/2，最好情况下（已经从小到大有序），比较次数为 n-1。（4）希尔排序法，最坏情况需要O(n1.5)次比较。 （5）简单选择排序法，最坏情况需要n(n-1)/2次比较； （6）堆排序法，最坏情况需要O(nlog2n)次比较。 相比以上几种（除希尔排序法外），堆排序法的时间复杂度最小。（7）在面向对象方法中，不属于“对象”基本特点的是（ ）。答案：A 2008-9A）一致性B）分类性C）多态性D）标识唯一性对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。即对象是属性和方法的封装体。 对象的属性即对象所包含的信息。对象的操作描述了对象执行的功能，操作也称为方法或服务。 对象的基本特点： （1）标识惟一性；指对象可由其内在本质来区分。 （2）分类性；指可以将具有相同属性和操作的对象抽象成类。 （3）多态性；指同一操作可以是不同对象的思维。 （4）封装性；从外部只能看到对象的外部特征。在面向对象方法中，信息隐蔽是通过对象的封装性来实现的。 （5）模块独立性好。(3)符合结构化原则的三种基本