2022年2022年计算机二级公共基础知识考点 .pdf

《2022年2022年计算机二级公共基础知识考点 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机二级公共基础知识考点 .pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机二级公共基础知识考点第1章 数据结构与算法考点 1：算法的基本概念所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确结果，则称这个问题是算法可解的。算法不等于程序，也不等于计算方法。1 算法的基本特征（1）可行性（effectiveness）：针对实际问题而设计的算法，执行后能够得到满意的结果。（2）确定性（definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。（3）有穷性（finiteness）：算法必须的有限时间内做完，即算法必须能在执行有限个步骤之后终止。（4）拥

2、有足够的情报：要使算法有效必须为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的；当提供的情报不够时，算法可能无效。综上所述，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的，此顺序将在有限的次数后终止。2算法的基本要素（1）算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。基本的运算和操作有以下4列类：算术运算（包括加、减、乘、除等）；逻辑运算（包括“与”、“或”、“非”等运算）；关系运算（包括“大于”、“小于”、“等于”、“不等于”等）；数据传输（包括赋值、输入、输出等操作）。（2）算法的控

3、制结构：一个算法的功能不仅仅取决非于所选用的操作，而且还与各操作间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的的框架，它不仅决定了算法中各操作的执行顺序，也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程、N-S 结构化流程图和算法描述评议等。一个算法一般都以用顺序、选择和循环3种基本控制结核组合而成。3算法设计的基本方法计算机算法不同于人工处理的方法，工程上常用的算法有列举法和归纳法。在实际应用时，各种方法之间往往存在着一定的联系。（1）列举法。列举法的的思想是根据提出的问题，列举所有可能的情况并用问题中给定的条件检测哪些是需要

4、的，哪些是不需要的。列举法常用于解决“是否存在”或“有多少名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 25 页 -种可能”等类型的问题。（2）归纳法。归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。（3）递推。递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。对于数值型的递推算

5、法必须要注意数值计算的稳定性问题。（4）递归。人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来的分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与间接递归两种。（5）减半递推技术。实际问题的复杂程度往往与问题的规模有着密切的联系，因此利用分治法解决这类实际问题是有效的。工程上常用的分治法是减半递推技术。所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。（6）回溯法。

6、在工程上有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换其他路线再逐步试探。考点 2：算法复杂度1 算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。同一个算法使用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的

7、规模（通常用整数n表示），它是问题的规模函数。即：算法的工作量=f(n)分析算法的工作量通过采用以下两种方法来分析。（1）平均性态（Average Behavior）：所谓平均性态分析，是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。（2）最坏情况复杂性（Worst-case Complexity）：所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。2 算法的空间复杂度算法的空间复杂度是指执行算法所需要的内在空间一个算法所占用的存储空间包括：算法程序所占的空间；输入的初始数据所占的存储空间；算法执行过程中所要的额外空间其中额外空间包括算法程序执行过程中的工作单

8、元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以减少不必要的额外空间。1 2数据结构的基本概念名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 25 页 -考点 1：什么是数据结构1 数据结构研究的主要内容数据结构作为计算机的一门学科，主要研究和讨论以下3个方面的问题：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的 存储结构；（3）对各种数据结构进行的运

9、算。2 研究数据结构的目的研究数据结构的主要目的是为了提高数据处理的效率。提高数据处理的效率主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。3 数据结构的定义数据结构是指相互有关联的数据元素的集合。数据元素之间的关系可以用前后件关系（或直接前驱与直接后继关系）来描述。一个数据结构应包含以下两方面作息：（1）表示数据元素的信息：（2）表示各数据元素之间的前后件关系。考点 2：数据的逻辑结构和数据的存储结构1 数据的逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构只抽象地

10、反映数据元素之间的逻辑关系，即数据元素之间的前后件关系，而不管它在计算机中的存储表示形式。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是 D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构B可以表示为：B=（D，R）2 数据的存储结构数据的存储结构是数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。一个数据结构中的各数据元素在计算机存储空间的位置与逻辑关系有可能不同。一种数据结构可根据需要采用不同的存储结构。常用的存储结构有顺序、链接和索引等存储方式。采用不同的存储结构，其数据处理的效率是不同的。考点 3：数据结构的图形表示一个数据结构除了用二

11、元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点：为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）。一个数据结构中的结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。考点 4：线性结构

12、与非线性结构如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，线性结构又称为线性表。例如，线性表、栈、队列和线性链表都是线性结构。如果一个数据结构不是线性结构，称之为非线性结构。例如树、二叉树和图都是非线性结构。线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构，否

13、则属于非线性结构。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 25 页 -1 3线性表及其顺序存储结构考点 1：线性表的基本概念线性表是由 n(n 0)个数据元素 1，2,，n组成有限序列，表中的每一个数据元素，除了第一个外有且只有一个前件，除了最后一个外有且只有一个后件，即线性表或是一个空表，或可以表示为（1，2，,，i,n）其中 1（i=1，2，,，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。在非空表中的每个数据元素都有一个确定位置，如 1是第一个元素，n是最后一个数据元素，i是第 i个数据元素，称i为数据元素i在线性表中的位序。非空线性表有如下一些结构特征

14、：有且只有一个根结点1，它无前件；有且只有一个终端结点n，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0 时，称为空表。考点 2：线性表的顺序存储结构线性表的顺序存储结构指的是用一组地址连续的存储单元依次存放线性表中的数据元素。线性表的顺序存储结构具备如下两个基本特征：线性表中的所有元素所占的存储空间是连续的；线性表中各数据元在存储空间中是按逻辑顺序依次存放的。假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为ADR（a1），每个数据元 素 占 k 个 字 节，则 线 性 表 中 第 i个

15、元 素 在 计 算 机 存 储 空 间 的存 储 地 址 为 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的顺序表中进行一次插入操作时所需进

16、行“移动”元素个数的期望值（即平均移动个数），则：其中，P1是在第 i个元素之前插入一个元素的概率，n是在第i个元素之前插入一个元素时所需移动的元素个数。由于可能插入的位置i=1，2，3，,，n+1共n+1 个，假设在每个位置上进行插入的机会均等，则：由此，在上述等概率假设的情况下，考点 4：顺序表的删除运算线性表的删除运算是指将表的第个结点删去，使长度为n的线性表（a1，,，ai1，ai，ai+1，,an）变成长度为 n的线性表（a1，,，ai1，ai+1，,an）。对顺序表而言，需要改变从第 i+1 个元素起到第 n个元素的存储位置，即从第 i+1到第 n个元素往前移动一个位置，共需移动

17、n个元素。令Edl（n）表示在长度为n的顺序表中进行一次删除操作时所需要进行“移动”元素个数的期望值（即平均移动个数），则其中，是删除第 i个元素的概率，n是删除第i个元素时所需移动元素的个数。同样假设在n个可能进行删除的位置i=1，2，,，n，机会均等，则由此，在上述等概率的假设下由此可见，在以顺序方式存储的线性表中插入或删除一个数据元素，平均约需移动表中一半元素。这个数目在线性表的长度较大时是很可观的。这个缺陷完全是由于顺序存储要求线性表的元素依次存放造成的。因此，顺序存储表仅适用于不常进行插入或删除操作、表中元素相对稳定的线性表。1 4 栈和队列考点 1：栈及其基本运算名师资料总结-精品

18、资料欢迎下载-名师精心整理-第 4 页，共 25 页 -1栈的定义栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称做“栈顶（top）”，不允许插入和删除的另一端称做“栈底（bottom）”。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的。因此，栈又称为先进后出（FILO，First In Last Out）或后进先出（LIFO，Last In First Out）的线性表。2.栈的顺序存储及其运算在程序设计语言中，用一维数组S（1：m）作为栈的顺序存储空间，其中 m为栈的最大容量。S(bottom)通常为栈底元素（栈非空情况下），S（to

19、p）为栈顶元素。Top=0 时表示栈空，top=m 时表示栈满。（1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加1（即 top 加1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作，这种情况称为栈“上溢”错误。（2）退栈运算：退栈是指取出栈顶元素并赋予一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）赋予一个指定的变量，然后将栈顶指针减1（即 top 减1）。当栈顶指针为0时，说明栈空，不可进行退栈操作，这种情况称为栈的“下溢”错误。（3）读栈顶元素：读栈顶元素是指将栈顶元素赋予一个指定的变量。这

20、个运算不删除栈顶元素，只是将它赋予一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。考点 2：队列及其基本运算队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。在表中，允许插入的一端称做“队尾（rear）”，允许删除的另一端称做“队头（front）”。队列的修改是依“先进先出”的原则进行的，因此队列又称先进先出（FIFO,First In First Out）表或后进后出（LILO,Last In Last Out）线性表。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。入队运算只涉及队尾指针rear 的变化，而

21、退队运算只涉及到队头指针front 的变化。考点 3：循环队列及其基本运算在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear 指向的位置之间所有元素均为队列中的元素。循环队列的初始状态为空，即rear=front=m。当循环队列满时有rear=front，而当循环队列空时也有rear=front，即在循环队列中当rear=

22、front 时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志 s，s=0 表示队列空，s=1 表示队列非空。循环队列主要有两种基本运算：入队运算与退队运算。（1）入队运算。入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针进一（即rear=rear+1），并当 rear=m+1 时，设置 rear=1；然后将新元素插入到队尾指针指向的位置。当循环队列非空（s=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。（2）退队运算。退队运算是指在循环队列的队头位置退出一个元素并赋

23、予指定的变量。首先将队头指针进一（即front=front+1），并当 front=m+1 时，设置 front=1；然后将排头指针指向的元素赋予指定的变量。当循环队列为空（s=0）时，不能进行退队运算，这种情况称为“下溢”。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 25 页 -1 5 线性链表考点 1：线性链表的基本概念1线性表顺序存储的缺点（1）插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。（2）线性表的顺序存储结构下，线性表的存储空间不便于扩充。当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新

24、的元素时就会发生“上溢”错误。（3）线性表的顺序存储结构不便于对存储空间的动态分配。2链式存储在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。在链式存储方式中，存储空间可以是连续的，也可以是不连续的，各个数据结点的存储顺序与数据元素之间的逻辑结构可以不一致，数据结构的逻辑结构由指针域来确定。3 线性链式线性表的链式存储结构称为线性链表。在线性链表中，每个结点包括数据域data 和指针域 next 两个部分；其中，域是数据域用来存放结点的值：指针域（亦称链域）用来存放结点的

25、后件的地址（或位置）。在定义的链表中，若只含有一个指针域用来存放下一个元素地址，称这样的链表为单链表或线性链表。在线性链表中，用一个专门的指针head指向线性链表中的第一个数据元素的结点。线性表中最后一个元素没有后件，因此线性链表中最后一个结点的指针为空（用NULL 或0表示）表示链表终止。在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针，指向其前件结点：另一个称为右指针，指向其后件结点。这种链表称为双向链表。4 栈的链式存储结构链栈栈是线性表，也可采用链式存储结构，由于线只在栈顶做插入和删除操作，因此链栈中不需要头结点，但要注意链栈中指针的方向是从栈顶指向栈底的，这正好和单

26、链表是相反。链栈没有上溢的限制。5.队列链式存储结构链队列链列是队列的的链式存储结构，从结构图可见，链队列和单链表一样，也附加一个头结点，链表中的指针方向也和线性表一致。链队列中设有两个指针，其一为“队尾指针（Q.rear）”，指向链队列中的队尾元素结点；其二为“队头指针（Q.front）”，指向链表的头结点，这表明真正的队头元素并非在“队头指针”所指的结点中，而在队头指针所指结点的“后继”结点中。“空队列”中只含一个其指针域为空的头结点，并且头、尾指针都指向头结点而不为空。考点 2：线性链表的基本运算线性链表的运算主要有以下几个方面：在线性链表中包含指定元素的结点之前插入一个新元素；在线性链

27、表中删除包含指定元素的结点；将两线性链表按要求合并成一个线性表；将一个线性链表按要求进行分解；逆转线性链表；复制线性链表；线性链表的排序；线性链表的查找。1在线性链表中查找指定元素在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个结点。在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺着链域next 逐个结点往下搜索，直到搜索到名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 25 页 -第i个结点为止，因此链表不是随机存取结构。2线性链

28、表的插入线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。在链表中“插入”一个元素x时，使元素之间的关系改变为和。当用指针后继元素时，实现这种关系的改变就很容易了，只要修改相应指针即可。因为新的元素插入在线性表的第i个元素之前，使得ai+1 不再是 ai 的后继，而是新的元素x的后继，因此需要修改元素x和元素ai所在结点指针。线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结点的指针即可，从而提高了插入的效率。同时，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。3线性链表的删除线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。和

29、插入类类似，由于删除元素 ai改变了元素之间的关系，使ai+1 不再是 ai的后继，而是 ai-1的后继，因此需要修改ai-1 元素所在结点的指针。与在单链表中删除元素操作的算法基本思想和插入相同，也是首先找到第i-1个结点，然后修改相应指针。从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在结点的前一个结点的指针域即可。考点 3：循环链表及其基本运算在线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。循环链表具有以下两个特点：（1）在循环链表中

30、增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中所有结点的指针构成了一个环状链。在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这点。由于在循环链表中设置了一个表头结点，因此在任何情况下，循环链表中至少有一个结点存在，从而使空表的运算统一。1 6 树与二叉树考点 1：树的基本概念1树的定义树（Tree）是 n(n 0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一

31、个特定的称为根（Root）的结点；（2）其余的结点可分为m(m0)个互不相交的子集T1，T2，T3,，Tm，其中每个子集又是一棵树，并称其为子树。由此可见，树是递归结构，在树的定义中又用到了树的概念。例如，一个公司组织结构可以用一棵树来表示；树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的“双亲”，结点的后继结点称为该结点的“子女”或“孩子”，同一结点的“子女”之间互称“兄弟”。2树中的基本概念（1）结点的度：树中每个结点具有的子树数或者后继结点数称为结点的度（Degree）。度数为 0的结点，即没有子树的的结点

32、叫做端结点或叶子结点。一棵树中各个子结点度数的最大值叫做这棵树的度。（2）孩子结点及双亲结点：一个结点的子树的根或者后继结点称为该结点的孩子结点，反名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 25 页 -之，该结点则称为其后继结点的双亲结点。（3）兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。（4）子孙结点和祖先结点：一个结点的子树中所有结点均称为之该结点的子孙结点。反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。（5）树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二层，其余各结点的层数逐层由

33、上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。（6）森林：n棵树的集合叫做森林。3树的特点从逻辑结构看，树有如下特点：树中只有根结点没有前件；除根外，其余结点都有且仅有一个前件；树的结点可以有零个或多个后件；除根外我其他结点，都存在惟一一条从根到该结点的路径；树是一种分支结构（除根结点外）每个元素都有且仅有一个直接前件，有且仅有零个或多个直接后件。4树的应用在计算机中，可以用树结构来表示自述表达式。用树来表示算术表达式的原则是：（1）表达式中的每一个运算符在树中对应一个结点，称为运算符结点；（2）运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）；（3）运算对

34、象中的单变量均为叶子结点。5树的存储树在计算机中通常用多重链表来表示。多重链表中每个结点描述树中对应结点信息，而每个结点中的链域（即指针）个数随树中该结点的度而定。由于树中每个结点的度一般不相同，为简化算法和节约存储空间，可以用二叉树来表示树。考点 2：二叉树及其基本性质1二叉树的定义一棵二叉树是 n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个要结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。二叉树具有两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树不是树的特殊情况它们是两个完全不同的

35、概念二叉树中每个结点最多有两棵子树，也就是说二叉树每个结点度小于等于2，而普通树中不限制结点的度数；二叉树是一个有序树，左、右子树不能颠倒，这是与普通树最主要的区别。2满二叉树和完全二叉树（1）满二叉树：满二叉树指这样的一种二叉树：除最后一层外，每一层上的所有结点都有有个子结点，从满二叉树中每一层上的结点数都达到最大，即在满二叉的第k层上有 2k-1个结点，否则就不是满二叉树。深度为m的满二叉树有 2m-1 个结点。（2）完全二叉树。完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。更确切地说，如果一棵具有n个结点的深度为 k的二叉树，它

36、的每一个结点都与深度为k的满二叉树中编号为1n的结点一一对应，这棵二叉树称为完全二叉树。满二叉树也是完全二叉树，反之完全二叉树不一定是满二叉树。3二叉树的性质性质 1：在二叉树的第k层上，最多有 2k-1(k 1)个结点。性质 2：深度为 m的二叉树最多有2m-1 个结点。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 25 页 -性质 3：在任意一棵二叉树中，度数为 0的结点（即叶子结点）总比度为 2的结点多一个。即：n0=n2+1 其中，n0表示二叉树中度数为0的结点数，n2表示二叉树中度数为2的结点数。性质 4：具有 n个结点的二叉树的深度至少为log2n+1，其中 log

37、2n 表示 log2n 的整数部分。性质 5：具有 n个结点的完全二叉树深度为log2n+1。性质 6：设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2,，n给结点进行编号，则对于编号为 k(k=1,2,n)的结点有以下结论。若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点的编号为INT（k/2）。若2kn，则编号为 k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。若2k+1 n,则编号为 k的右子结点编号为2k+1；否则该结点无右子结点。考点 3：二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各

38、元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件（两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。对于满二叉树与完全二叉树来说，根据完全二叉树的性质6，可以按层序进行顺序存储，这样，不仅节省存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对一般二叉树不适用。考点 4：二叉树的遍历1前序遍历（DLR）前序遍历是指在访问根结点、遍历左子树与遍历右子树这3者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，

39、在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历二叉树的过程是一个递归过程。前序遍历描述如下。若二叉树为空，则执行空操作；否则，访问根结点，前序遍历左子树，前序遍历右子树。2中序遍历（LDR）中序遍历是指在访问根结点、遍历左子树与遍历右子树这3者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历二叉树的过程也是一个递归过程。中序遍历描述如下。若二叉树为空，则执行空操作；否则，中序遍历左子树，访问根结点，中序遍历右子树。3后序遍历（LRD）后序遍历是指在访问根结点、遍历左子树与遍历右

40、子树这3者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历二叉树的过程也是一个递归过程。后序遍历描述如下。若二叉树为空，则执行空操作；否则，后序遍历左子树，后序遍历右子树，访问根结点。1 7 查找技术考点 1：顺序查找顺序查找是一种最基本和最简单的查找方法。它是思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相等，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。但是下列两种情况下只能采用顺序查找：名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 2

41、5 页 -（1）如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储，都只能用顺序查找；（2）即使是有序线性表，如果采用链式存储结构，也只用顺序查找。考点 2：二分法查找二分法查找 只适用于顺序存储的线性表，且表中元素必须按关键字有序（升序或降序均可）排列。这里假设表中元素为升序排列。设有序线性表长度为n，被查找元素为x，则二分法查找的方法如下：（1）将 x与线性表的中间项比较；（2）若 x的值与中间项的值相等，则说明查到，查找结束；（3）若 x小于中间项的值，则在线性表的前半部分以相同的方法查找；（4）若 x大于中间项的值，则在线性表的后半部分以相同的方法查找。对于长

42、度为 n的有序线性表，在最坏的情况下，二分法查找只需要比较log2n 次，而顺序查找需要比较n次。18 排序技术考点 1：交换类排序法交换排序的基本思想是：两两比较待排序记录的关键字，发现两记录的次序相反时即进行交换，直到没有反序的记录为止。冒泡排序和快速排序都属于交换类的排序方法。1冒泡排序冒泡排序基本思想是对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟（pass）。当发现相邻两数据的次序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好像气泡向上浮起一样；假设线性表的长度n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫

43、描和n/2 从后往前的扫描，需要比较次数为n(n-1)/2.2快速排序快速排序基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。通过一次划分，将一个区间以基准值分成两个子区间，左子

44、区间的值小于等于基准值，右子区间的值大于基准值。对剩下的子区间重复此划分步骤，则可以得到快速排序的结果。考点 2：插入类排序法插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。常用两种插入排序方法是简单插入排序和希尔排序。1简单插入排序法所谓插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。简单插入排序法的基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，

45、将它插入到有序表中的适当位置，使之成为新的有序表。在简单插入排序法中，每一次比较后最多移掉一个逆名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 25 页 -序，因此，这种排序方法的效率与冒泡排序法相同。在最坏的情况下，简单插入排序需要n(n-1)/2 次比较。2希尔排序希尔排序法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个增量 h的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。直接插入排序是在元素基本有序的情况下（接近最好情况），故效率是很高的。增量序列一般取hi=n/2k(k=1,2,log

46、2n，n为待排序序列长度。希尔排序的效率与所选取增量序列有关。在最坏情况下希尔排序的时间复杂度为 O(n1.5)。考点 3：选择类排序法选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有简单选择排序和堆排序。1简单选择排序法简单选择排序法思想是：扫描整个线性表，从中先出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍，每遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素，与子表中的第一个元素进行交换。最坏情况下简单选择排序

47、法需要比较n(n-1)/2次。2堆排序法（1）堆的定义。具有 n个元素的序列（h1,h2,hn），当且仅当满足(1)hi h2i(2)hi h2i hih2i+1 hih2i+1(i=1,2,3,n/2)时称之为堆。若将此排序码按顺序组成一棵完全二叉树，则（1）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值），（2）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值）。（2）建堆。在调整建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。（3）堆排序。堆排序的方法为：

48、首先将一个无序序列建成堆。然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将孩子序列调整为堆。反复做步骤，直到剩下的子序列空为止。在最坏情况下，堆排序法需要比较的次数为O(nlon2n)。第2章 程序设计基础2 1 程序设计方法与风格考点 1：程序设计方法分类程序设计是一门技术，需要相应的理论、技术、方法和工具来支持，程序设计主要经历了结构化设计和面向对象的程序设计阶段。考点 2：良好的编程序风格程序设计的风格主要强调程序的简单、清晰和可理解性。“清晰第一，效率第二”已成为当今主导的程序设计风格。

49、要形成良好的程序风格，需注意以下几点:1源程序的文档化（1）符号名的命名：符号名的命名应具有一定实际含义，以便理解程序功能。（2）正确的程序注释：注释一般为序言性注释和功能性注释。序言性注释常名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 25 页 -位于程序开头部分，它包括程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期及修改日期等。功能性注释一般嵌在源程序体之中，用于描述其后的语句或程序的主要功能。（3）视觉组织：在程序中利用空格、空行、缩进等技巧使程序层次清晰。2数据说明的方法数据说明的方法有：数据说明的次序规范化；说明语句中变

50、量安排有序化；使用注释来说明复杂数据的结构。3语句的结构为使程序更简单易懂，语句构造应该简单直接，应注意如下几点：在一行内只写一条语句；程序编写应优先考虑清晰性；程序编写要做到清晰第一，效率第二；在保证程序正确的基础上再要求提高效率；避免使用临时变量前使程序的可读性下降；避免不必要的转移；尽量使用使用库函数；避免采用复杂的条件语句；尽量减少使用“否定”条件语句；数据结构要有利于程序的简化；11要模块化，使模块功能尽可能单一化；12利用信息隐蔽，确保每一个模块的独立性；13从数据出发去构造程序；14不要修补不好的程序，要重新编写。5 输入输出输入输出方式和风格应尽可能方便用户的使用，应考虑如下原