二级公共基础知识教程

《二级公共基础知识教程》由会员分享，可在线阅读，更多相关《二级公共基础知识教程（56页珍藏版）》请在金锄头文库上搜索。

1、公共基础知识公共基础知识第一章第一章 数据结构与算法数据结构与算法一、学习目标与要求1了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度； 2掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利用图形的方 式表示数据结构； 3了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的线性表的基 本运算； 4了解栈和队列的基本概念，并掌握它们的基本运算； 5了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循环链表的基 本概念和基本操作； 6理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存储结构和遍 历技术； 7掌握查找技术，学会利用顺序查找和二分

2、查找在数列中查找指定的数据； 8学会利用相关的排序技术实现无序数列的排序操作。二、内容要点（一）算法（一）算法1 1算法的基本概念算法的基本概念算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且 每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。1 1）算法的基本特征）算法的基本特征（1）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的， 因此，它总是受到计算工具的限制，使执行产生偏差。 如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数 的影响而使小数丢失，因此，在算法设计时，应该考

3、虑到这一点。 （2）确定性 算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义 性。 例如，一个实际的问题，小宝和萍萍共有 12 个苹果，小宝比萍萍多 4 个，请问小宝和萍萍各有几个苹果？这个问题，我们可以立一个方程来求解，要求 x 和 y 412 yxyx的值，公式是正确的，但如何让计算能够进行计算，我们的算法不能把公式直接输进去， 而应该设计出解题的步骤和过程。 即设计的算法是计算工具所能够正常解决问题的过程。 （3）有穷性 算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够 正常结束。 例如，在数学中的无穷级数，在计算机中只能求有限项，即计

4、算的过程是有穷的。 （4）拥有足够的情报 算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的 输出结果，提供准确的初始条件和数据，才能使算法正确执行。2 2）算法的基本要素）算法的基本要素一是数据对象的运算和操作，二是算法的控制结构。 （1）算法中对数据的运算和操作 算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指 令序列。即算法是计算机所能够处理的操作所组成的指令序列。 （2）算法的控制结构 算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺序有关。 在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：顺序 结构、选择

5、结构和循环结构。 在算法描述是，有相关的工具对这三种结构进行描述，常用的描述工具有：流程图、 N-S 结构图和算法描述语言等。3 3）算法设计的基本方法）算法设计的基本方法为用计算机解决实际问题而设计的算法，即是计算机算法。 通常的算法设计有如下几种： （1）列举法 列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的 条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在”或 “有哪些可能”等问题。 例如，我国古代的趣味数学题：“百钱买百鸡” 、 “鸡兔同笼”等，均可采用列举法进 行解决。 使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理

6、化、完备化、系 统化，从中找出规律。 （2）归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。 归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况 进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。 （3）递推 递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其 中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，递推关系式通常是归纳的结果。 例如，裴波那契数列，是采用递推的方法解决问题的。 （4）递归 在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐

7、层分解，最后归 结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是当 解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是 递归的方法。 递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归 调用；如果一个算法 A 调用另一个算法 B，而算法 B 又调用算法 A，则此种递归称为间接递 归调用。 （5）减半递推技术 减半递推即将问题的规模减半，然后，重复相同的递推操作。 例如，一元二次方程的求解。 （6）回溯法 有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限 的列举。对于这类问题，只能采用试探的

8、方法，通过对问题的分析，找出解决问题的线索， 然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退， 换别的路线进行试探。这种方法，即称为回溯法。 如人工智能中的机器人下棋。2 2算法复杂度算法复杂度算法的复杂度包括时间复杂度和空间复杂度。1 1）时间复杂度）时间复杂度即实现该算法需要的计算工作量。算法的工作量用算法所执行的基本运算次数来计算。同一个问题规模下，如果算法执行所需要的基本次数取决于某一特定输入时，可以用 以下两种方法来分析算法的工作量： 算法工作量=f(n) （1）平均性态 用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 设 x 是某个可

9、能输入中的某个特定输入，p(x)是 x 出现的概率，t(x)是算法在输入为 x 时所执行的基本运算次数，则算法的平均性态定义为： nDxxtxpnA)()()(Dn表示当规模为 n 时，算法执行时所有可能输入的集合。 （2）最坏情况复杂度 指在规模为 n 时，算法所执行的基本运算的最大次数。它定义为： )(max)(xtnW nDx例如，在具有 n 个元素的数列中搜索一个数 x。平均性态：nqqnnqinqtpnAniinii)1 (2) 1()1 ()(111 即该数在数列中任何位置出现的数列是相同的，也有可能不存在，存在的概率为 q。 如果有一半的机会存在，则概率 q 为 1/2，平均性态

10、：nnn nA43)211 (221) 1( )( 如果查找的元素一定在数列中，则每个数存在的概率即为 1，则平均性态为：221)(nnnA最坏情况分析：即要查找的元素 X 在数列的最后或不在数列中，显然，它的最坏情况复杂度为：nnitnWi11 |max)(2 2）算法的空间复杂度）算法的空间复杂度指要执行该算法所需要的内存空间。算法所占用的内存空间包括算法程序所占的空间、 输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，如执行过程中工 作单元以及某种数据结构所需要的附加存储空间等。（二）数据结构的基本概念（二）数据结构的基本概念1 1概念概念数据结构是指相互有关联的数据元素

11、的集合。它包括以下两个方面： 表示数据元素的信息 表示各数据之间的前后件关系1 1）数据的逻辑结构）数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构。 数据的逻辑结构有两个要素： 数据元素的集合，记作 D 数据之间的前后件关系，记作 R 则数据结构 B=（D，R）2 2）数据的存储结构）数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理 结构。 即数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的前后件关系 的信息。 通常的数据存储结构有顺序、链接、索引等存储结构。2 2数据结构的图形表示数据结构的图形表示数据结构的图形表示有两个元素：

12、中间标有元素值的方框表示数据元素，称为数据结点 用有向线段表示数据元素之间的前后件关系，即有向线段从前件结点指向后件结 点 注意：在结构图中，没有前件的结点称为根结点，没有后件的结点称为终端结点，也 称叶子结点。3 3线性结构与非线性结构线性结构与非线性结构如果一个数据元素都没有，该数据结构称为空数据结构；在空数据结构中插入一个新 的元素后数据结构变为非空数据结构；将数据结构中的所有元素均删除，则该数据结构变 成空数据结构。 如果一个非空的数据结构满足如下条件，则该数据结构为线性结构： 有且只有一个根结点 每一个结点最多只有一个前件，也最多只有一个后件 线性结构又称线性表。 注意：在线性结构表

13、中插入或删除元素，该线性表仍然应满足线性结构。 如果一个数据结构不满足线性结构，则称为非线性结构。（三）线性表及其顺序存储结构（三）线性表及其顺序存储结构1 1基本概念基本概念线性表是最常用的数据结构，它由一组数据元素组成。 注意：这里的数据元素是一个广义的数据元素，并不仅仅是指一个数据。如，矩阵、 学生记录表等。 非空线性表的结构特征： 有且只有一个根结点，它无前件 有且只有一个终端结点，它无后件 除根结点和终端结点之外，所有的结点有且只有一个前件和一个后件。线性表中 结点的个数称为结点的长度 n。当 n=0 时，称为空表。2 2顺序存储结构顺序存储结构顺序存储结构的特点： 线性表中所有的元

14、素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 通常，顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由 该元素在线性表中的位置序号唯一确定。 线性表的顺序存储结构下的基本运算： 在指定位置插入一个元素删除线性表中的指定元素 查找某个或某些特定的元素 线性表的排序 按要求将一个线性表拆分为多个线性表 将多个线性表合并为一个线性表 复制线性表 逆转一个线性表3 3线性表的基本操作线性表的基本操作1 1）顺序表的插入运算）顺序表的插入运算在顺序存储结构的线性表中插入一个元素。 注意：找到插入位置后，将插入位置开始的所有元素从最后一个元素开始顺序后移

15、。 另外，在定义线性表时，一定要定义足够的空间，否则，将不允许插入元素。2 2）顺序表的删除运算）顺序表的删除运算在顺序在存储结构的线性表中删除一个元素。 注意：找到删除的数据元素后，从该元素位置开始，将后面的元素一一向前移动，在 移动完成后，线性表的长度减 1（四）栈和队列（四）栈和队列1 1栈及其基本运算栈及其基本运算1 1）栈）栈栈是一种特殊的线性表，它是限定在一端进行插入和删除的线性表。它的插入和删除 只能在表的一端进行，而另一端是封闭的，不允许进行插入和删除操作。 在栈中，允许插入和删除操作一端称为栈顶，不允许插入和删除操作的一端则称为栈 底。栈顶的元素总是最后被插入的元素，也是最先

16、被删除的元素。它遵循的原则是：先进 后出或后进先出。 堆栈指针总是指向栈顶元素的。2 2）栈的顺序存储及其运算）栈的顺序存储及其运算在栈的顺序存储空间 S（1：m）中，S（bottom）通常为栈底元素，S（top）为栈顶元 素。Top=0 表示栈空；top=m 表示栈满。 1）入栈运算 即在栈的顶部插入一个新元素。操作方式是：将栈顶指针加 1，再将元素插入至指针 所指的位置。 2）退栈运算 退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是：先将栈顶元素赋给 指定的变量，再将栈顶指针减 1。 3）读栈顶元素 将栈顶元素赋给某一指定变量，但栈顶指针不变。2 2队列及其基本运算队列及其基本运算1 1）队列）队列队列即是允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为 队尾，通常用一个尾指针指向队尾；允许删除的一端称为队首，通常用一个队首指针指向 排队元素的前一个位置。 队列遵循