计算机二级公共基础知识考点
第1章 数据结构与算法 考点1：算法的基本概念
所谓算法是指解题方案的准确而完整的描述。
对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确结果，则称这个问题是算法
可解的。算法不等于程序，也不等于计算方法。 1 算法的基本特征
（1） 可行性（effectiveness）：针对实际问题而设计的算法，执行后能够得到满意的结果。 （2） 确定性（definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱
两可的解释和多义性。 （3） 有穷性（finiteness）：算法必须的有限时间内做完，即算法必须能在执行有限个步
骤之后终止。 （4） 拥有足够的情报：要使算法有效必须为算法提供足够的情报。当算法拥有足够的情
报时，此算法才是有效的；当提供的情报不够时，算法可能无效。 综上所述，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，
同时是明确的，此顺序将在有限的次数后终止。 2．算法的基本要素
（1）算法中对数据的运算和操作：
每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。
基本的运算和操作有以下4列类：①算术运算（包括加、减、乘、除等）；②逻辑运算（包括“与”、“或”、“非”等运算）；③关系运算（包括“大于”、“小于”、“等于”、“不等于”等）；④数据传输（包括赋值、输入、输出等操作）。 （2）算法的控制结构：一个算法的功能不仅仅取决非于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的的框架，它不仅决定了算法中各操作的执行顺序，也直接
反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程、N-S结构化流程图和算法描述评议等。一个算法一般都以用顺序、选择和循环3种基本控制结核组合而成。
3．算法设计的基本方法
计算机算法不同于人工处理的方法，工程上常用的算法有列举法和归纳法。 在实际应用时，各种方法之间往往存在着一定的联系。
（1） 列举法。 列举法的的思想是根据提出的问题，列举所有可能的情况并用问题中给定的条件检测哪些是需要的，哪些是不需要的。列举法常用于解决“是否存在”或“有多少种可能”等类型的问题。
（2） 归纳法。 归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
（3） 递推。 递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初 始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。
（4） 递归。 人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总 是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来的分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与间接递归两种。 （5） 减半递推技术。 实际问题的复杂程度往往与问题的规模有着密切的联系，因此利用分治法解决这类实际问题是有效的。工程上常用的分治法是减半递推技术。 所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。 （6） 回溯法。 在工程上有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换其他路线再逐步试探。 考点2：算法复杂度 1． 算法的时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。同一个算法使用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数n表示），它是问题的规模函数。即： 算法的工作量=f(n) 分析算法的工作量通过采用以下两种方法来分析。
（1） 平均性态（Average Behavior）：所谓平均性态分析，是指各种特定输入下 的基本运算次数的加权平均值来度量算法的工作量。
（2） 最坏情况复杂性（Worst-case Complexity）：所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。 2． 算法的空间复杂度
算法的空间复杂度是指执行算法所需要的内在空间一个算法所占用的存储空间包括：①算法程序所占的空间；②输入的初始数据所占的存储空间；③算法执行过程中所要的额外空间其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以减少不必要的额外空间。
1．2数据结构的基本概念 考点1：什么是数据结构
1． 数据结构研究的主要内容 数据结构作为计算机的一门学科，主要研究和讨论以下3个方面的问题： （1） 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2） 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3） 对各种数据结构进行的运算。
2． 研究数据结构的目的 研究数据结构的主要目的是为了提高数据处理的效率。提高数据处理的效率主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。
3． 数据结构的定义 数据结构是指相互有关联的数据元素的集合。数据元素之间的关系可以用前后件关系（或直接前驱与直接后继关系）来描述。一个数据结构应包含以下两方面作息： （1） 表示数据元素的信息： （2） 表示各数据元素之间的前后件关系。 考点2：数据的逻辑结构和数据的存储结构
1． 数据的逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，即数据元素之间的前后件关系，而不管它在计算机中的存储表示形式。 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构B可以表示为： B=（D，R） 2． 数据的存储结构 数据的存储结构是数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。一个数据结构中的各数据元素在计算机存储空间的位置与逻辑关系有可能不同。 一种数据结构可根据需要采用不同的存储结构。常用的存储结构有顺序、链接和索引等存储方式。采用不同的存储结构，其数据处理的效率是不同的。 考点3：数据结构的图形表示
一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点：为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。 在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）。 一个数据结构中的结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。 除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。 考点4：线性结构与非线性结构
如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。 如果一个非空数据结构满足下列两个条件： （1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，线性结构又称为线性表。例如，线性表、栈、队列和线性链表都是线性结构。 如果一个数据结构不是线性结构，称之为非线性结构。例如树、二叉树和图都是非线性结构。 线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构，否则属于非线性结构。 1．3线性表及其顺序存储结构
考点1：线性表的基本概念
线性表是由n(n≥0)个数据元素α1，α2?，αn组成有限序列，表中的每一个数据元素，除了第一个外有且只有一个前件，除了最后一个外有且只有一个后件，即线性表或是一个空表，或可以表示为 （α1，α2，?，αi,?αn） 其中α1（i=1，2，?，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。 在非空表中的每个数据元素都有一个确定位置，如α1是第一个元素，αn是最后一个数据元素，αi是第i个数据元素，称i为数据元素αi在线性表中的位序。 非空线性表有如下一些结构特征：①有且只有一个根结点α1，它无前件；②有且只有一个终端结点αn，它无后件；③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。
考点2：线性表的顺序存储结构
线性表的顺序存储结构指的是用一组地址连续的存储单元依次存放线性表中的数据元素。
线性表的顺序存储结构具备如下两个基本特征： ① 线性表中的所有元素所占的存储空间是连续的；
② 线性表中各数据元在存储空间中是按逻辑顺序依次存放的。
假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为ADR（a1），每个数据元素占k个字节，则线性表中第i个元素在计算机存储空间的存储地址为ADR(a1)= ADR(ai)+(i－1)k在线性表的顺序存储结构下可以对线性表做以下运算：插入、删除、查找、排序、分解、合并、复制和逆子转等。 考点3：顺序表的插入运算
线性表的插入运算是指在表的第 个位置元素之前，插入一个新结点x，使长度为n的线性表（a1，?，ai－1，ai，?an）变成长度为n+1的线性表（a1，?，ai－１，x,ai，?an）。对顺序表而言，需要改变是从第i个元素起到第n个元素的存储位置，即从第i个到第n个元素往后移动一个位置，共需移动n－ｉ＋１个元素。 令Ｅis（n）表示在长度为n的顺序表中进行一次插入操作时所需进行“移动”元素个数的期望值（即平均移动个数），则： 其中，P1是在第i个元素之前插入一个元素的概率，n－ｉ＋１是在第i个元素之前插入一个元素时所需移动的元素个数。由于可能插入的位置i=1，2，3，?，n+1共n+1个，假设在每个位置上进行插入的机会均等，则： 由此，在上述等概率假设的情况下， 考点4：顺序表的删除运算
线性表的删除运算是指将表的第 个结点删去，使长度为n的线性表（a1，?，ai－1，ai，ai+1，?an）变成长度为n－１的线性表（a1，?，ai－1，ai+1，?an）。对顺序表而言，需要改变从第i+1个元素起到第n个元素的存储位置，即从第i+1到第n个元素往前移动一个位置，共需移动n－ｉ个元素。 令Edl（n）表示在长度为n的顺序表中进行一次删除操作时所需要进行“移动”元素个数的期望值（即平均移动个数），则 其中， 是删除第i个元素的概率，n－ｉ是删除第i个元素时所需移动元素的个数。 同样假设在n个可能进行删除的位置i=1，2，?，n，机会均等，则 由此，在上述等概率的假设下 由此可见，在以顺序方式存储的线性表中插入或删除一个数据元素，平均约需移动表中一半元素。这个数目在线性表的长度较大时是很可观的。这个缺陷完全是由于顺序存储要求线性表的元素依次存放造成的。因此，顺序存储表仅适用于不常进行插入或删除操作、表中元素相对稳定的线性表。 1．4 栈和队列
