全国计算机等级考试二级公共基础知识总结
第一章数据结构与算法
1.1 算法
1．算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。，
2．确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；
3．算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
4
的设计方法。
5．算法时间复杂度是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
6．算法时间复杂度取决于问题的规模和待处理的数据的初态。
7．如果算法P调用另一个算法Q，而算法Q又调用算法P，
8．工程上常用的分治法是减半递推技术
9
10．如果查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。也就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均的情况下需要检查数组中一半的元素。如果已知需要查找的x有一半机会在数组中，此时q=1/2。则A(n)=[(n+1)/4]+n/2=3n/4。x不在数组中时，A(n)=n。.
11．下面程序段的时间复杂度是
for(int i=0;i
for(int j=1;j<=m;j++)
A[i][j]=0;
语句的频度指的是该语句重复执行的次数，一个算法中所有语句的频度之和构成了该算法的运行时间。本例中语句:A[i][j]=0;的频度是n*m，所以该程序段的时间复杂度是：O(m*n).
12
13．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程较慢。
14
1.2 数据结构的基本基本概念
1．数据结构研究的三个方面：；数据运算。
2
．逻辑结构是数据元素间关系的描述，与所用的计算机无关
3．数据的逻辑关系是指数据元素的关联。
4．数据的不可分割的基本单位是数据项。
5
