全国计算机等级考试二级公共基础知识总结第一章数据结构与算法11算法1．算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。，2．确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；3．算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。4．归纳法：通过观察一些简单而特殊的情况，最后总结出一般性的结论的算法的设计方法。5．算法时间复杂度是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。6．算法时间复杂度取决于问题的规模和待处理的数据的初态。7．如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用8．工程上常用的分治法是减半递推技术9．算法空间复杂度是指执行这个算法所需要的内存空间。10．如果查找的x一定在数组中，此时q1，则A
12。也就是说，在这种情况下，用顺序搜索法在长度为
的一维数组中查找值为x的元素，在平均的情况下需要检查数组中一半的元素。如果已知需要查找的x有一半机会在数组中，此时q12。则A
14
23
4。x不在数组中时，A
。11．下面程序段的时间复杂度是fori
ti0i
ifori
tj1jmjAij0语句的频度指的是该语句重复执行的次数，一个算法中所有语句的频度之和构成了该算法的运行时间。本例中语句Aij0的频度是
m，所以该程序段的时间复杂度是：Om
12．算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。13．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程较慢。14．算法复杂度：算法时间复杂度和算法空间复杂度。12数据结构的基本基本概念1．数据结构研究的三个方面：数据的逻辑结构；数据的存储结构（物理结构）；数据运算。2．逻辑结构是数据元素间关系的描述，与所用的计算机无关3．数据的逻辑关系是指数据元素的关联。4．数据的不可分割的基本单位是数据项。
f5．数据结构是指相互有关联的数据元素的集合。6．一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、7。索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。8．数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式，与所使用的计算机密切相关9．根据数据结构中各数据元素之间前后件关系的复杂度，一般将数据结构分为r