公共基础知识-算法篇

《公共基础知识-算法篇》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、下列叙述中正确的是（）答案：D2011-9A)算法是程序B)设计算法时只需要考虑数据结构的设计C)设计算法时只需要考虑结果的可靠性D)以上三种说法都不对算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算方法，程序可以作为算法的一种描述。（算法也可以用流程图、专门的描述语言、自然语言来描述。）2、算法的基本要素算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。(1)算法中对数据的运算和操作：①算术运算；②逻辑运算；③关系运算；④数据传输（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流

2、程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。3、算法设计的基本方法（1）列举法：列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。（2）归纳法：归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。（3）递推：递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（4）递归：为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解

3、，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与间接递归两种。（5）减半递推技术：所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。（6）回溯法：在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。5、算法的有穷性是指（）答案：A2

4、008-3A）算法程序的运行时间是有限的　　　B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的　　　D）算法只能被有限的用户使用1、算法的基本特征：（1）可行性，针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报，要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。（2）算法的时间复

5、杂是指(    )答案：D2010-3A)算法的执行时间                B)算法所处理的数据量C)算法程序中的语句或指令条数    D)算法在执行过程中所需要的基本运算次数4.算法的空间复杂度是指（）。答案A2009-9A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数1、算法的时间复杂度算法的时间复杂度，是指执行算法所需要的计算工作量。（不直接衡量时间）算法的工作量用算法所执行的基本运算次数来度量，只依赖于问题的规模，它是问题的规模函数。2、算法的空间复杂

6、度算法的空间复杂度是指执行这个算法所需要的内存空间。包括算法程序占用的空间、输入数据所占用的空间及算法执行过程中所需要的额外空间。10、下列选项中属于面向对象设计方法主要特征是（）答案：A2011-9A)继承B)自顶向下C)模块化D)逐步求精结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。面向对象的主要特征：封装性、继承性、多态性。5.结构化程序所要求的基本结构不包括（）答案：B2011-3A.顺序结构B.GOTO跳转C.选择（分支）结构D.重复（循环）结构解析：

7、结构化程序设计的三种基本控制结构为:顺序结构、选择结构和重复结构。（6）面向对象方法中，继承是指______。答案：D2010-9A）一组对象所具有的相似性质　　B）一个对象具有另一个对象的性质C）各对象之间的共同性质　　D）类之间共享属性和操作的机制面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。1.对象：通常把对象的操作也称为方法或服务。属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。属性值应该指的是纯粹的数据值，而不能指对象。操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。对象具有如下

8、特征：标识惟一性、分类性、多态性、封装性、模块独立性