软考教材分享程序员考试考点分析与真题详解(第4版)

程序员程序员考试考点分析与真题详解（第4版）第1章数据结构与算法数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为S=（D,R）。其中，D是数据结构中的数据的非空有限集合，R是定义在D上的关系的非空有限集合。在数据结构中，结点与结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称为数据的存储结构。数据结构按逻辑结构不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形结构和图结构，而树形结构又可分为树结构和二叉树结构。按照考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点。1.常用数据结构数组（一维数组、二维数组、静态数组、动态数组）、线性表、链表（单向链表、双向链表、环形链表）、队列、栈、树（二叉树、查找树）和图（邻接矩阵、邻接表）等的定义、存储和操作。2.常用算法（1）排序算法、查找算法、数值计算算法、字符串处理算法、递归算法、最小生成树、拓扑排序和单源点最短路径求解算法、图的相关算法。（2）算法与数据结构的关系、算法效率、算法设计、算法描述（流程图、伪代码、决策表）、算法的复杂性。1.1算法设计概述程序员算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下5个重要的特征。（1）有穷性：一个算法（对任何合法的输入值）必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。（3）输入：一个算法有零个或多个输入，以确定运算对象的初始情况。所谓零个输入是指算法本身定出了初始条件。这些输入取自于某个特定对象的集合。（4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。（5）可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。算法设计要求正确性、可读性、健壮性、高效率与低存储量需求。效率指的是算法执行的时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。算法的复杂性是算法效率的度量，是算法运行所需要的计算机资源的量，是评价算法优劣的重要依据。可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。当将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素。（1）硬件的速度。例如，使用486还是使用586.（2）书写程序的语言。实现语言的级别越高，其执行效率就越低。程序员（3）编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。（4）问题的规模。例如，求100以内的素数与求1000以内的素数其执行时间必然是不同的。显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述的各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。1.时间复杂度一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该操作重复执行的次数作为算法的时间度量。在一般情况下，算法中原操作重复执行的次数是规模n的某个函数T（n）。许多时候要精确地计算T（n）是困难的，我们引入渐近时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。定义（大Ο记号）：如果存在两个正常数c和n0,对于所有的n,当n≥n0时有：f（n）≤cg（n）则有：f（n）=Ο（g（n））也就是说，随着n的增大，f（n）渐近的不大于g（n）。例如，一个程序的实际执行程序员时间为T（n）=2n3+n2+5,则T（n）=Ο（n3）。T（n）和n3的值随n的增大渐近地靠拢。使用大Ο记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。通常用Ο（1）表示常数计算时间。常见的渐近时间复杂度有：Ο（1）Ο（log2n）Ο（n）Ο（nlog2n）Ο（n2）Ο（n3）Ο（2n）2.空间复杂度一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分。（1）固定部分：这部分空间与所处理数据的大小和个数无关。主要包括程序代码、常量、简单变量和定长成分的结构变量所占的空间。（2）可变部分：这部分空间大小与算法在某次执行中处理特定数据的大小和规模有关。例如，100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。算法由数据结构来体现，所以看一个程序首先要搞懂程序实现中所使用的数据结构，如解决装箱问题就使用链表这种数据结构。数据结构是算法的基础，数据结构支持算法，如果数据结构是递归的，算法也可以用递归来实现，如二叉树的遍历。经常采用的算法有迭代法、递推法、递归法、穷举法、贪婪法、分治法和回溯法等，根据考试大纲的要求，对程序员级别的考试，需要考生掌握递归法。1.2线性表线性表是最简单和最常用的一种数据结构，线性表是由相同类型的结点组成的有限序程序员列。一个由n个结点a0,a1,…，an-1组成的线性表可记为（a0,a1,…，an-1）。线性表的结点个数为线性表的长度，长度为0的线性表称为空表。对于非空线性表，a0是线性表的第一个结点，an-1是线性表的最后一个结点。线性表的结点构成一个序列，对序列中两相邻结点ai和ai+1,称ai是ai+1的前驱结点，ai+1是ai的后继结点。其中a0没有前驱结点，an-1没有后继结点。线性表中结点之间的关系可由结点在线性表中的位置所确定，通常用（ai,ai+1）（0≤i≤n–2）表示两个结点之间的先后关系。例如，如果两个线性表有相同的数据结点，但它们的结点在线性表中出现的顺序不同，则它们是两个不同的线性表。线性表的结点可由若干个成分组成，其中能唯一标识该结点的成分称为关键字，或简称键。为了讨论方便，往往只考虑结点的关键字，而忽略其他成分。1.线性表的基本运算线性表包含的结点个数可以动态地增加或减少，可以在任何位置上插入或删除结点。线性表常用的运算可分成几类，每类有若干种运算，如下所示。1）查找运算在线性表中查找具有给定键值的结点。2）插入运算在线性表的第i（0≤i≤n–1）个结点的前面或后面插入一个新结点。3）删除运算删除线性表的第i（0≤i≤n–1）个结点。4）其他运算统计线性表中结点的个数；程序员输出线性表各结点的值；复制线性表；线性表分拆；线性表合并；线性表排序；按某种规则整理线性表。2.线性表的存储线性表常用的存储方式有顺序存储和链接存储。1）顺序存储顺序存储是最简单的存储方式，通常用一个数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中，即线性表的第i个结点存储在数组的第i（0≤i≤n–1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。顺序存储线性表的最大优点就是能随机存取线性表中的任何一个结点。缺点主要有两个：一是数组的大小通常是固定的，不利于任意增加或减少线性表的结点个数；二是插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。2）链接存储链接存储是用链表存储线性表（链表），最简单的是用单向链表，即从链表的第一个结点开始，将线性表的结点依次存储在链表的各结点中。链表的每个结点不但要存储线性表结点的信息，还要用一个域存储其后继结点的指针。单向链表通过链接指针来体现线性表中结点的先后次序关系。链表存储线性表的优点是线性表的每个结点的实际存储位置是任意的，这给线性表的插程序员入和删除操作带来方便，只要改变链表有关结点的后继指针就能完成插入或删除的操作，不需移动任何表元。链表存储方式的缺点主要有两个：一是每个结点增加了一个后继指针成分，要花费更多的存储空间；二是不方便随机访问线性表的任一结点。3.线性表上的查找线性表上的查找运算是指在线性表中找某个键值的结点。根据线性表中的存储形式和线性表本身的性质差异，有多种查找算法，例如顺序查找、二分法查找、分块查找、散列查找等。其中二分法查找需要线性表是一个有序序列。4.在线性表中插入新结点1）顺序存储设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i（0≤i≤n）个位置上。完成插入主要有以下步骤。检查插入要求的有关参数的合理性；把原来的第n–1个结点至第i个结点依次往后移一个数组元素的位置；把新结点放在第i个位置上；修改线性表的结点个数。在具有n个结点的线性表上插入新结点，其时间主要花费在移动结点的循环上。若插入任一位置的概率相等，则在顺序存储线性表中插入一个新结点，平均移动次数为n/2.2）链接存储在链接存储线性表中插入一个键值为x的新结点，分以下4种情况。在某指针p所指结点之后插入；插在首结点之前，使待插入结点成为新的首结点；程序员接在线性表的末尾；在有序链表中插入，使新的线性表仍然有序。5.删除线性表的结点1）顺序存储在有n个结点的线性表中，删除第i（0≤i≤n–1）个结点。删除时应将第i+1个表元至第n–1个结点依次向前移一个数组元素的位置，共移动n–i–1个结点。完成删除主要有以下几个步骤。检查删除要求的有关参数的合理性；把原来第i+1个表元至第n–1个结点依次向前移一个数组元素的位置；修改线性表表元个数。在具有n个结点的线性表上删除结点，其时间主要花费在移动表元的循环上。若删除任一表元的概率相等，则在顺序存储线性表中删除一个结点，平均移动次数为n/2.2）链接存储对于链表上删除指定值结点的删除运算，需考虑几种情况：一是链表为空链表，不执行删除操作；二是要删除的结点恰为链表的首结点，应将链表头指针改为指向原首结点的后继结点；其他情况，先要在链表中寻找要删除的结点，从链表首结点开始顺序寻找。若找到，执行删除操作，若直至链表末尾没有指定值的结点，则不执行删除操作。完成删除由以下几个步骤组成。如链表为空链表，则不执行删除操作；若链表的首结点的值为指定值，更改链表的头指针为原首结点的后继结点；在链表中找指定值的结点；程序员将找到的结点删除。1.2.1栈栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端称为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征。1.顺序存储可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量top指出栈顶结点在数组中的下标。2.链接存储栈也可以用链表实现，用链表实现的栈称为链接栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top,top为NULL的链表是空栈。1.2.2队