国家计算机二级考试第一章

1二级公共基础知识第一章数据结构基础2内容提要算法:算法的基本概念、算法复杂度数据结构的基本概念：什么是数据结构、数据结构的图形表示、线性结构与非线性结构线性表及其顺序存储结构：线性表的基本概念、顺序存储结构、插入运算、删除运算栈和队列：栈及其基本运算、队列及其基本运算线性链表：基本概念、基本运算、循环链表及其基本运算树与二叉树：树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树的遍历查找技术：顺序查找、二分法查找排序技术：交换类排序法、插入类排序法、选择类排序法31.1算法41.1.1算法的基本概念算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。1．算法的基本特征可行性(effectiveness)确定性(definiteness)有穷性(finiteness)拥有足够的情报2．算法的基本要素算法中对数据的运算和操作算术运算:包括加、减、乘、除等）逻辑运算:包括“与”、“或”、“非”等运算）关系运算:包括“大于”、“小于”、“等于”、“不等于”等）数据传输:包括赋值、输入、输出等操作算法的控制结构:顺序、选择、循环51.1.1算法的基本概念3．算法设计的基本方法列举法归纳法递推递归减半递推技术回溯法61.1.1算法的基本概念4．算法设计的设计要求正确性可读性健壮性效率和低存储量需求71.1.2算法复杂度算法复杂度：时间复杂度、空间复杂度1．算法的时间复杂度执行算法所需要的计算工作量与下列因素有关：书写算法的程序设计语言编译产生的机器语言，代码质量机器执行指令的速度问题的规模81.1.2算法复杂度问题的规模函数算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应增加。常见算法复杂度：O(1)：常数阶O(n)：作线性阶O(n2)：平方阶O(n3)：立方阶O(logn)：对数阶O(2n)：指数阶91.1.2算法复杂度n×n矩阵相乘算法：时间复杂度为O(n3)。101.1.2算法复杂度分析算法的工作量两种方法：平均性态最坏情况复杂性111.1.2算法复杂度2．算法的空间复杂度算法执行过程中所需的最大存储空间存储量包括以下三部分算法程序所占的空间输入的初始数据所占的存储空间算法执行过程中所要的额外空间算法空间复杂度可定义为：S(n)=O(f(n))原地工作(inplace)的算法：记作O(1)压缩存储技术121.2数据结构的基本概念131.2.1什么是数据结构1．数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2．研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间141.2.1什么是数据结构1．数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2．研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间151.2.1什么是数据结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面161.2.1什么是数据结构3．数据结构的定义相互有关联的数据元素的集合数据元素之间的关系可以用前后件关系来描述一个数据结构应包含以下两方面信息：表示数据元素的信息表示各数据元素之间的前后件关系171.2.1什么是数据结构4．数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关两个要素：数据元素的集合，通常记为D；前后件关系，通常记为R一个数据结构B可以表示为：B=（D，R）181.2.1什么是数据结构5．数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构：顺序链式索引一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同191.2.2数据结构的图形表示数据结点：用方框表示根结点、终端结点前后件关系：用有向线段表示基本运算：插入运算删除运算查找、分类、合并、分解、复制、修改、……201.2.3线性结构与非线性结构空的数据结构：一个数据元素都没有线性结构如果一个非空数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。常见的线性结构有：线性表、栈与队列、线性链表非线性结构如果一个数据结构不是线性结构常见的非线性结构有：树、二叉树、图211.3线性表及其顺序存储结构221.3.1线性表的基本概念线性表：由n(n≥0)个相同类型数据元素构成的有限序列：n定义为线性表的表长；n=0时的线性表被称为空表。称i为在线性表中的位序。例如：英文大写字母表（A，B，C，D，E，F，…X，Y，Z）同一花色的13张扑克牌(2,3,4,5,6,7,8,9,10,J,Q,K,A)231.3.1线性表的基本概念线性表的结构特征数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；对于一个非空线性表，有且只有一个根结点a1，它无前件，有且只有一个终端结点an，它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的存储结构顺序存储链式存储241.3.2线性表的顺序存储结构两个基本特点：线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。存储示意图251.3.3顺序表的插入运算261.3.4顺序表的删除运算27顺序表的插入和删除分析插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑281.4栈和队列291.4.1栈及其基本运算1．栈的定义栈（stack）：一种只允许在表的一端进行插入或删除操作的特殊的线性表栈顶(top)：允许进行插入与删除操作的一端栈底(bottom)：不允许插入与删除操作的另一端先进后出（FILO）或后进先出(LIFO)的线性表301.4.1栈及其基本运算2．栈的顺序存储及其运算top=0：栈空top=m：栈满栈的基本运算入栈运算退栈运算读栈顶元素311.4.2队列及其基本运算1．队列的定义限定只能在表的一端进行插入和在另一端进行删除操作的线性表队尾(rear)：允许插入的一端队头(front)：允许删除的另一端先进先出（FIFO）表或后进后出（LILO）线性表基本操作入队运算：往队列的队尾插入一个元素，队尾指针rear的变化退队运算：从队列的排头删除一个元素，队头指针front的变化321.4.2队列及其基本运算2．循环队列及其运算队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用入队运算：队尾指针加1，并当rear=m+1时置rear=1出队运算：队头指针加1，并当front=m+1时置front=1331.5线性链表341.5.1线性链表的基本概念1．线性表顺序存储的缺点插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。线性表的顺序存储结构下，线性表的存储空间不便于扩充。线性表的顺序存储结构不便于对存储空间的动态分配。351.5.1线性链表的基本概念2．线性链表线性表的链式存储结构物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的每个结点由两部分组成：数据域和指针域361.5.1线性链表的基本概念双向链表：每个结点设置两个指针左指针：指向其前件结点右指针：指向其后件结点371.5.2线性链表的基本运算插入删除合并分解逆转复制排序查找381.5.2线性链表的基本运算1．在线性链表中查找指定元素链表不是随机存取结构从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止2．线性链表的插入391.5.2线性链表的基本运算3．线性链表的删除与顺序存储相比，链表的优点有：插入和删除元素时，不需要移动数据元素，只需要修改指针即可401.5.3栈和队列的链式存储结构1．栈的链式存储结构——链栈411.5.3栈和队列的链式存储结构2．队列链式存储结构——链队列421.5.4循环链表及其基本运算循环链表特点：在链表中增加了一个表头结点最后一个结点的指针域指向表头结点，构成了一个环状链循环链表优点：从任一结点出发来访问表中其他所有结点空表与非空表的运算的统一431.6树与二叉树1．树的定义树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m≥0)个互不相交的子集T1，T2，T3，…，Tm，其中每个子集又是一棵树，并称其为子树。44ABCDEFGHIJKL(b)一般的树451.6树与二叉树2．树中的基本概念父结点与树的根：每个结点最多只允许有一个前件，称为该结点的父结点。没有前件的结点中有一个，称为树的根结点。子结点与叶子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。结点的度和树的度：一个结点所拥有后件个数称为该结点的度。一棵树中各个结点度数的最大值叫做这棵树的度。层和树的深度：树结构是一种层次结构，根结点为第一层，根的子结点为第二层，其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度。461.6.1树的基本概念树的特点（1）树中只有根结点没有前件；（2）除根外，其余结点都有且仅一个前件；（3）树的结点，可以有零个或多个后件；（4）除根外的其他结点，都存在唯一条从根到该结点的路径；（5）树是一种分支结构（除根的结点外）每个元素都有且仅有一个直接前件，有且仅有零个或多个直接后件。树的存储用多重链表来表示471.6.2二叉树及其基本性质1．二叉树的定义一个二叉树是n个结点的有限集合（n≥0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。481.6.2二叉树及其基本性质2．二叉树的性质性质1

在二叉树的第k层上，最多有个结点。性质2

深度为m的二叉树最多有个结点。性质3

在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。即：其中，n0表示度数为0的结点数，n2表示度数为2的结点数。性质4

具有n个结点的二叉树的深度至少为，其中表示取的整数部分。491.6.2二叉树及其基本性质3．满二叉树和完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。501.6.2二叉树及其基本性质性质5具有n个结点的完全二叉树深度为。性质6设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k=1，2，…，n）的结点有以下结论：①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点的编号为INT(k/2)。②若2k≤n，则编号为k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。③若2k+1≤n，则编号为k的右子结点编号为2k+1；否则该结点无右子结点。511.6.3二叉树的存储结构普通二叉树采用链式存储结构存储结点由两部分组成：数据域与指针域两个指针域：左指针域右指针域满二叉树与完全二叉树采用顺序存储结构521.6.4二叉树的遍历二叉树的遍历：不重复地访问二叉树中的所有结点1．前序遍历（DLR）首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。2．中序遍历（LDR）首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树3．后序遍历（LRD）首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。531.6.4二叉树的遍历前序遍历：A、B、D、G、C、E、F中序遍历：D、G、B、A、E、C、F后序遍历：G、D、B、E、F、C、AP16-33图54ABCDEF551.7查找技术561.7查找技术查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找结果：查找成功：找到查找不成功：没找到平均查找长度：查找过程中关键字和给定值比较的平均次数571.7.1顺序查找基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。平均要与表中一半以上元素进行比较，最坏情况下需要比较n次。下列两种情况下只能采用顺序查找：如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。581.7.2二分法查找思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。查找过程：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。591.7.2二分法查找例：查找元素22过程：601.8排序技术611.8.1交换类排序法基本思想两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。方法冒泡排序快速排序621.冒泡排序基本思想对存放原始数据的数组，按从后往前的方向进行多次扫描，当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。性能分析假设线性表的长度n，则在最坏情况下，需要的比较次数为n(n-1)/2。631.冒泡排序642．快速排序基本思想任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序的平均时间复杂度为O(nlog2n)。652．快速排序P66-5:快速排序法初始顺序:661351768126576923

一次交换:231351768126576966二次交换:23135166

8126576976三次交换:23135157

8126666976四次交换:23135157

66

2681

6976五次交换:23135157

26

6681

697666671.8.2插入类排序法基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。方法:简单插入排序希尔排序681．简单插入排序法基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。在最坏的情况下，需要n(n-1)/2次比较