知识点大纲全国计算机等级考试-数据结构和算法
全国计算机等级考试二级office
二级公共基础知识部分（10分*10题） 第一章. 算法与数据结构 考点1：算法概念 算法
算法：指解题方案准确而完整的描述。
算法不等于程序，也不是计算方法。程序编制通常不优于算法设计。 考点2：算法的四个基本特征
可行性、确定性（算法步骤有明确定义）、有穷性、拥有足够情报 考点3：算法的时间复杂度和空间复杂度 1. 时间复杂度：执行算法所需的工作量。
算法执行的基本次数是问题规模的函数，固定规模下还与输入有关。
2. 空间复杂度：算法执行需要的存储空间（算法程序、输入初始数据、某种数据结构所需空间） 数据结构
（反映数据元素之间关系的数据元素集合，即带有结构的数据元素的集合，结构指数据元素之间的前后件（前驱、后继）关系）。目的是提高数据处理的效率（速度/空间）
线性表数据结构研究的三个方面线性结构数据的逻辑结构栈队列（循环队列）树形结构非线性结构图形结构数据的存储结构（物理结构）顺序存储链式存储检索、排序、插入、删除、修改等数据的运算
数据的逻辑结构：是反映数据元素之间逻辑关系的数据结构。 可以表示成：B=（D，R）
B表示数据结构；D表示数据元素集合；R表示数据元素之间的前后件关系 【例：一年四季的数据结构可以表示成B=（D，R）；D=（春，夏，秋，冬）；B={（春，夏），（夏，秋），（秋，冬）}】 数据结构的图形表示：
数据元素：用中间标有元素值的方框表示，称为结点。
逻辑关系：用有向线段从前件指向后件。没有前件的结点称为根结点；没有后件的结点称为终端结点（叶子结点） B=（D，R） d1d2D={di|1≤i≤7}
d7={d1,d2,d3,d4,d5.d6.d7} d3d4R={（d1,d3）,（d1,d7）,（d2,d4）,（d3,d6）,
d5d6（d4,d5）}
考点4：数据的存储结构
数据的存储结构：指数据的逻辑结构在计算机储存空间的存放形式。既储存数据元素的信息,还有元素的前后件关系信息。
数据的逻辑关系与数据的存储结构不一定相同。数据结构一般可以表示成多种存储结构，常见的存储结构有顺序、链接、索引等。采用不同的存储结构，其数据处理效率不同。
考点5：线性结构和非线性结构（逻辑结构而言） 线性结构（线代表）：
有且只有一个根结点，它无前件；
有且只有一个终端（叶子）结点，无后件；
除根结点和终端结点外，其他所有结点有且只有一个前件和一个后件。
线性表中结点个数n称为线性表的长度；n=0表示空表。 春夏秋冬常见的线性结构有线性表、栈、队列（循环队列）。
线性表是最简单、常见数据结构。可用顺序存储结构、链式存储结构。
顺序储存结构特点：线性表中所有元素存储空间连续，按逻辑顺序依次存放。 非线性结构：一个数据结构不是线性结构，称为非线性结构（树、图）。 空的数据结构可能是线性结构，也可能是非线性结构。 考点6：顺序表的插入运算
例：在第二个元素（18）之前插入一个元素87，过程如下：
1、29；2、18；3、56；4、63 1、29；2、18；3、56；4、 ；5、63 1、29；2、18；3、 ； 4、56；5、63 1、29；2、；3、18 ；4、56；5、63 1、29；2、87；3、18 ；4、56；5、63 【在平均情况下，插入运算在第i个（1≤i≤n）元素之前进行，需要移动一半的元素；最坏情况下需移动所有元素】
例：线性表的删除运算 删除线性表中的第一个元素（29），过程如下：
1、29；2、18；3、56 1、 ；2、18；3、56 1、18；2、 ；3、56 1、18；2、56
【在一般情况下，要删除第i个（1≤i≤n）元素时，在平均情况下，需要移动一半的元素。因此，在线性表顺序存储情况下，要删除一个数据，效率很低】 考点7：栈
栈：是限定在一端进行插入和删除的线性表，其特殊性体现在它的插入和删除运算都在线性表的一端进行，而另一端是封闭的，不进行任何操作。在栈中，允许插入或删除操作的一4•草莓端称为栈顶，另一端称为栈底。原则是：先进后出（或后进先出）。栈具有记忆功能。 3•西瓜1. 栈底指针 bottom（指向最底部）
Top 2•桔子2. 栈顶指针 top（始终指向最顶部）
1•苹果3. 栈空 即top=0（不能退栈，否则 下溢错误） bottom 栈空 04. 入栈（元素苹果、桔子、西瓜、草莓依次入栈，top指针上移）
入出 5. 栈满 （top指针指向顶部元素草莓栈满，栈满再入栈则出现溢出错误 6. 出栈（草莓、西瓜、桔子、苹果依次出栈进行退栈操作，top依次下移） 4•草莓Rear 考点8：队列
队列：允许在一端进行插入，另一端进行删除的线性表。先进先出（或后进后出） 3•西瓜2•桔子1. 尾指针 rear：
插入一端称队尾，rear指向队尾元素且始终指向最后入队元素。 1Fron2. 排头指针 front： t 4•C出队一端称为排头（队头），用front指向排头元素的前一个位置。 Rear 考点9：循环队列 3•BRear 队列的顺序储存结构一般采用循环队列的形式。循环队列初始状态为空，即2•ARear rear=front=m（队头、队尾指针同时指向同一个元素）。
FrontRear 1入队运算：初始状态下，F和R都指向1，随着ABC元素的入队，R依次上移， / F不变。当R指向最后一个元素C之后，R最终回到指向1，使之构成循环。 •D5出队运算：在初始状态下RF都在1，一个元素退出，F上移一格 R不变。 4•CFronRear如：当F上移一格，第一个元素A就会退出，被赋值给其它元素如a, 3/ Reart Fron队头指针F继续上移一格，B退出赋值给b，以此类推。 2•E/ t 队尾指针始终不变指向1，rear指向位置才是队尾。 1•YFrontRear 此时，队尾可以继续进行入队操作,元素E、F可以继续入队 / 直到队满。此时，Rear和Front同时指向3.F时队满。
即rear=front=m。因此，仅凭rear=front=m，不能确定对空或者队满。
因此，我们定义标记S。S=0 表示队列空；S=1 表示队列非空（不一定是满）
因此，我们可以得到：队列为空条件为s=0，rear=front；队列满条件为s=1，rear=front。 队列满，不能进行入队操作，否则“上溢”；队列空不能进行退队操作，否则“下溢”。 考点10：线性链表
线性链表是线性表的链式存储结构。
线性链表中每一个存储结点分为两部分：数据域（用于存储数据元素的值）；指针域（用于存放下一个数据元素的存储序号（及存储结点的地址），也就是指向后件结点类似于一个指针） 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。 q 18 例：在线性链表的结点X之前插入一个新元素b,过程如下： a （原指向）X
1) 取得一个结点，设该结点号为p，其数据域为b. 2) 使结点p指向包含X的结点。 转 向 即结点p的指针域为原结点q的指针域（X的存储地址） p 3）使结点p指针域改为p，即指向元素b,完成插入。 顺序表和链表的优缺点比较
类 型 优 点 缺 点 b 在进行插入或删除运算时，不需要移需要指针域来表示数据元素之间的 链 表 动元素只需改变指针；链表存储空间逻辑关系；存储密度比顺序表低 易于扩张并可动态分配 考点11：树与二叉树 树（tree）：非线性结构，具有明显的层次结构
父结点：在树结构中，每一个结点只有一个前件，这个前件称为父结点。 F 根结点（F）：没有前件的结点称为根节点，一个树只有一个。
CK 子节点：在树结构中，每一个结点可以有多个后件，这些后件都称为子节点。
ADG 叶子结点：没有后件的结点，称为叶子结点。
结点的度：一个结点拥有的后件个数称该结点的度。（叶子结点度为0）F度为3 B 树的度：在树结构中，所有结点中最大的度称为树的度。结点F 3
树的深度：树的最大层次称为树的深度。 4 （树） 子树：以某结点的一个子结点为根构成的树称为该结点的子树（图框内是以C为根结点的子树）。
树的存储结构：树在计算机中用多重链表示。多重链表中的每个结点描述了树中对应结点的信息，
每个结点中的链域（即指针域）个数随树中结点的度而定 Value（值） Degree（度） Link 1 …… Link n 对于一个树来讲首先要保存这个结点表示的值，然后说明结点的度（即后件个数），再对每个后件进行依次说明，这是对于树当中每个结点必须存在的存储形式。 二叉树特点：
非空二叉树只有一个根结点；每一个结点最多有两颗子树，且分别称为该结点的左子树和右子树。 在二叉树中，每一个结点的度最大为2，所有子树均为二叉树。 考点11-13：二叉树的性质1、2、3 1性质1：二叉树的第i层上至多有2（i≥1）个结点。 性质2：深度为h的二叉树中至多含有2-1个结点。
性质3：在任意二叉树中，度为0结点（叶子结点）比度为2结
h
410i-1
251112613143715
点多一个。
例：某二叉树中度为2的结点有18个，则叶子结点有 个。（19）。如上图所示，二叉树第4层有4-142=8个结点（性质1）；深度为4的该二叉树最多有2-1=15个结点（性质2）。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结
点。
1如下图，如果把10移到右侧也不算完全二叉树，必须保持左侧相对完整。 23 1满二叉树：出最后一456723层叶子结点外，每一
456710层上所有结点都有两10101112131415个子结点。在满二叉
树中，每一层的结点数都达到最大值。 F二叉树通常采用链式存储结构，每个存储结点由两部分组成：数据域和指针域。
CE其中指针域有两个：左指针域和右指针域。BT指针称为二叉链表的头指针，用
ADG于指向根结点。
B二叉树存储结PHL（i）V（i）R（i）点结构：
Lchild Value Rchild
i
指向左子结点的指针域 数据域 指向左子结点的指针域 考点14：二叉树的遍历
二叉树的遍历：不重复的访问二叉树中的所有结点。 【总原则：先左后右】 前序遍历（DLR）：根-左-右 以右图为例，访问顺序为：FCADBEGHP 中序遍历（LDR）：左-根-右 以右图为例，遍历顺序为：ACBDFEHGP 后序遍历（LRD）：左-右-根 以右图为例，遍历顺序为：ABDCHPGEF
（注：所谓的前中后遍历是根据访问根的顺序决定的；遍历左右子树时，仍采用以上原则） 宝宝定理：对于完全二叉树而言
➢ 如果它的结点个数为偶数n，则该二叉树中：
叶子结点个数=非叶子结点个数=n/2
➢ 如果它的结点个数为奇数m，则该二叉树中：
叶子结点个数=非叶子结点个数+1=（m+1）/2（即叶子结点个数比非叶子结点个数多一个） 查找技术：根据给定值，在查找表中确定一个其关键字等于给定值的数据元素。
234673221
查找结果：1.查找成功：找到；2.查找不成功：没找到
平均查找长度：查找过程中关键字和给定值进行比较的平均次数。 考点15：顺序查找
➢ 顺序查找的基本思想：
从表中的第一个元素开始，将给定值与表中逐个元素的关键字进行比较，直到两者相符，查到所需元素为止。否则就是查找不成功，表中无要找元素。
➢ 平均要与表中一半以上元素进行比较，最坏情况下需要比较全部元素n次。
➢ 以下两种情况下只能采用顺序查找：
1. 如果线性表是无序表，则只能采用顺序查找。
2. 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 考点16：二分法查找
➢ 思想：先确定待查找记录所在范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 ➢ 前提：必须在具有顺序存储结构的有序表中进行。
➢ 特点：比顺序查找方法效率更高。最坏情况下，需要比较log2 n次。n指线性表长度 二分法举例：在下图长度为11的线性表中查找22过程
1 2 3 4 5 6 7 8 9 10 11
7121822405666798484
Low （a）初始状态 mid high 1 2 3 4 5 6 7 8 9 10 11 7121822405666798484
Low mid high （b）第一次比较后 1 2 3 4 5 6 7 8 9 10 11 7121822405666798484
Low mid high （c）第二次比较后 如上图所示：在上述顺序存储结构的有序表中，low指针指向最小元素7，high指针指向最大元素94，mid指针指向中间元素56。用中间元素56跟目标元素22比可知22一定在56左侧。（a）如此，我们把high指针移到56左侧的最大位置40，low指针不动，mid指针重新设定为小数据表的中间位置，即元素18所在位置，再用18与22进行比较可知22在18右侧。（b）如此，我们将low指针移到18右侧的最小结点22处，high指针不动。此时Mid指针指向中间偏左位置指向22，在进行比较，找到。
考点17：排序技术及最坏情况下的比较次数（必考内容P15） 类 别 排序方法 基本思想 时间复杂度 平均时间 最坏情况时间 2冒泡排序 相邻元素比较，不满足条件时交换 n(n-1)/2 O（n） O（n2） 交换类 选择基准元素，通过交换，划分成快速排序 O(nlog2n) O（nlog2n） O（n2） 两个子序列 待排序元素看成一个有序比表和无简单插入序表，将无序表中元素插入到有序n(n-1)/2 O（n2） O（n2） 排序 表中。 插入类 分割成若干个子序列分别进行直接希尔排序 时间效率与选取增量有关 O（n1.5） 插入排序 简单选择扫描整个线性表，从中选出最小元n(n-1)/2 O（n2） O（n2） 排序 素，将它交换到表的最前面。 选择类 选择堆，然后将堆顶元素与堆中最堆排序 O(nlog2n) O（nlog2n） O（nlog2n） 后一个元素交换，再调整为堆 排序，是指将一个无序序列整理成按值非递减顺序排列的有序序列的过程。 交换类排序法：指借助数据元素的交换来进行排序的一种方法，主包括冒泡排序法和快速排序法。 ➢ 冒泡排序法：最简单的一种交换类排序方法，在数据元素的序列中，对于某个元素，如果其后存
在一个元素小于它，则称之为存在一个逆序。冒泡排序的基本思想，就是通过两两相邻数据元素之间的比较和交换，不断的消除逆序，直到所有数据元素有序为止。
举例来说：对（4,1,6,5,2,3）这样一个6个元素组成的线性表排序。
第一遍从前往后扫描，首先比较4和1，前元素大于后元素，这是一个逆序，两者交换。交换后，接下来是4和6比较，不交换。6和5比较，交换。6和2比较，交换。6和3比较，交换。最大元素6到达尾部，第一遍从前往后扫描的最后结果为（1,4,5,2,3,6）。
第一遍从后往前扫描，由于数据元素6已经排好序，因此排序范围为（1，4，5，2，3），先比较3和2,不交换。比较2和5,交换。比较2和4，交换。比较2和1，不交换。此时排序范围内，（1，4，5，2，3）的最小元素1到达表头，达到了他在有序表中的应有位置。第一遍从后往前扫描的最后结果为（1，2，4，5，3，6）。第二遍的排序方法同上，不再赘述。
➢ 快速排序法：是冒泡排序法的一种改进，其基本思路如下：在线性表中逐个选取元素对表进行分
割，直到所有元素全部选取完毕，此时线性表即排序结束。
快速排序的具体做法：设置两个指针，low和high，它们的初值分别指向线性表的第一个元素 k元素和最后一个元素，首先从high所指向的位置向前扫描，找到第一个小于k元素的元素，并与k元素互相交换，然后从low所指位置向后扫描，找到第一个大于k元素的数据元素，并与k元素交换，重复这两个步骤，直到low等于high为止，此时线性表排好序。
插入排序法：将无序序列中的各元素依次插入到有序的线性表中。包括简单插入排序法和希尔排
序法。
➢ 简单插入排序法：是把n个待排序的元素看成一个有序表和一个无序表，开始时有序表只包含一
个元素，而无序表包含剩余的n-1个元素，每次取无序表中第一个元素插入到有序表中的正确位置，使之成为增加了一个元素的新的有序表，插入元素时插入位置及其后的记录依次向后移动，最后当有序表的长度为n，无序表为空时排序完成。此排序方法的效率与冒泡排序法相同。 ➢ 希尔排序法：希尔排序也是一种插入类排序，但希尔排序比简单插入排序更有效率。希尔排序的
基本思想是：将整个无序序列分割成若干个小的子序列，并分别进行插入排序。其分割方法如下：将相隔某个增量h的元素构成一个子序列，在排序过程中逐次减少这个增量，直到h减到1，进行一次插入排序，排序即可完成。希尔排序的效率与选取的增量序列有关。 选择类排序法： ➢ 简单选择排序法：从所有n个待排序的数据元素中选取最小的元素，将该元素与第一个元素交换，
再从剩下的n-1个元素中，选取出最小的元素与第2个元素交换，重复操作，直到所有元素有序。 ➢ 堆排序法：属于选择类排序法。所谓堆，即若有n个元素的序列，将元素按顺序组成一棵完全二
叉树，所有结点的值大于或等于左右子结点的值，我们称之为大根堆；当所有结点的值小于或等于左右子节点的值时，称为小根堆。排序方法如下（以大根堆为例）：首先将一个无序序列建成堆。然后将根结点与其左右子树的根结点进行比较，将左右子树中＞根结点元素与根结点交换。其次再分别比较交换后的左右子树根结点值与其底下左右子树的值。如此通过不断的比较，大值上移交换完成排序。
{其他补充知识：1.算法的两个基本要素：对数据对象的运算（算术运算、逻辑运算、关系运算、数据传输；加减乘除、与或非、＞＜=、输入输出）和操作、算法的控制结构（顺序、选择、循环结构）；2.算法设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法等。3.带链的栈：栈也是线性表，可以采用链式存储结构。栈具有记忆功能。4.带链的队列：队列也是线性表，也可以采用链式存储结构。}
——后续内容持续更新中哦。。。。。。
