全国计算机等级考试二级公共基础知识总结
- 格式:doc
- 大小:128.00 KB
- 文档页数:22
全国计算机等级考试二级公共基础知识总结
-
第一章数据结构与算法
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 6.一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、7。索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。 8.数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式,与所使用的计算机密切相关 9.根据数据结构中各数据元素之间前后件关系的复杂度,一般将数据结构分为 10.在数据结构的图形表示中,对于数据集合中的每一个数据元素用中间标有元 11.插入和删除是对数据结构的两种基本运算。除此之外,对数据结构的运算还有查找、分类、合并、分解、复制和修改等。 12.在数据结构中,用一组地址连续的存储单元依次存储数据元素的方式是线性结构。 13 1.3 线性表及其顺序存储结构 1 2.线性表是由n个数据元素组成的一个有限序列。删除一个元素,平均移动的元素的个数为(n-1+n-2+......+0)/n=(n-1)/2;插入一个元素,平均移动元素个 数为(n+n-1+n-2+......+1)/n=(n+1)/2 3 4.线性表可以是空表。 5.非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 6.线性表的顺序存储结构具有以下两个基本特点: 7.ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。 例:一个矢量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是108 数据元素的存储位置均取决于第一个数据元素的存储位置,即:。 ADR(ai)=ADR(a1)+(i-1)k 第5个元素的地址:ADR(a5)=100+(5-1)X2=108 8.在线性表的顺序存储结构下,可以对线性表进行各种处理。主要的运算有: 线性表的合并、线性表的复制、线性表的逆转等 9 合适的,因为顺序存储的结构比较简单。 10.采用顺序存储的线性表,顺序存储结构必须占用一片连续的存储单元,当对其进行插入和删除操作时需要移动大量的元素,优点是存储密度大,由于数组的存储方式是采用顺序存储的,即占用连续的存储空间,所以可以用数组的下标直接存取。 11.查找第i-1个结点和第i个结点,在顺序表中查找的时间复杂度为O(1)速度最快。由于链表结构在空间存储上的不连续性,在查找某个结点时,需要从当前结点开始向前或者向后逐个比较查找,浪费时间,查找结果的时间复杂度均为O(n), 12.链接存储不是占用一片连续的存储空间,所以便于进行插入和删除操作。13.线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素,还包括指针,每一个指针指向一个与本结点有逻辑关系的结点,此类存储方式属于顺序存储。 1.4 栈和队列 1.栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。 2FILO LIFO top表示栈顶位置,用bottom表示栈底。 3.当一个栈ST (最多元素为MaxSize)时,ST->top= -1是判断顺序栈为空的条件。ST->top=MaxSize-1是判断顺序栈为满的条件。 4.栈的基本运算:(12 (3 本运算有:入栈,出栈(删除栈顶元素),初始化、置空、判断栈是否为空或满、提取栈顶元素等,对栈的操作都是在栈顶进行的。 5 元素。 6 7.队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front指针指向队头。