知识点大纲全国计算机等级考试数据结构和算法

-让每个人公平地提升自我全国计算机等级考试二级office〕第一章. 算法与数据构造考点1：算法概念算法算法：指解题方案准确而完整的描述。2：算法的四个根本特征〔算法步骤有明确定义、有穷性、拥有足够情报3：算法的时间简单度和空间简单度时间简单度：执行算法所需的工作量。算法执行的根本次数是问题规模的函数，固定规模下还与输入有关。〔〕数据构造〔反映数据元素之间关系的数据元素集合，即带有构造的数据元素的集合，构造指数据元素之间的前后件〔前驱、后继〕关系。目的是提高数据处理的效率〔速度/空间〕线性表线性表面方个三的究研构结据数线性构造栈数据的规律构造队列〔循环队列〕树形构造非线性构造图形构造数据的存储构造〔物理构造〕挨次存储链式存储数据的运算检索、排序、插入、删除、修改等是反映数据元素之间规律关系的数据构造。可以表示成：B=〔D，R〕BDRB=〔D，R；D=〔春，夏，秋，冬；B={〔春，夏，〔夏，秋〔秋，冬〕}数据构造的图形表示：数据元素：用中间标有元素值的方框表示，称为结点。根结点；没有后件的结点称为终端结点〔叶子结点〕d1d3d7d6d2d1d3d7d6d2d4d5={d1,d2,d3,d4,〔d1,d3〕,〔d1,d7〕,〔d2,d4〕,〔d3,d6〕,〔d4,d5〕}4：数据的存储构造数据的存储构造：指数据的规律构造在计 算机储存空间的存放形式。既储存数据元素的信息,还有元素的前后件关系信息。数据的规律关系与数据的存储构造不肯定一样。数据构造一般可以表示成多种存储构造，常6--让每个人公平地提升自我算都在线性表的一端进展，而另一端是封闭的，不进展任何操作。在栈中，允许插入4草莓算都在线性表的一端进展，而另一端是封闭的，不进展任何操作。在栈中，允许插入4草莓或删除操作的一端称为栈顶，另一端称为栈底。原则是：先进后出〔或后进先出。3西瓜栈具有记忆功能。2桔子1.栈底指针bottom〔指向最底部〕1苹果栈顶指针top〔始终指向最顶部〕 Top空即top=0〔不能退栈，否则下溢错误〕 bottom入栈〔元素苹果、桔子、西瓜、草莓依次入栈，top指针上移〕 栈空栈满〔top04草莓入出6.出栈〔草莓、西瓜、桔子、苹果依次出栈进展退栈操作，top〕3西瓜考点8：队列 Rear队列：允许在一端进展插入，另一端进展删除的线性表。先进先出〔或后进后出〕rear：插入一端称队尾，rear指向队尾元素且始终指向最终入队元素。 Front排头指针front：出队一端称为排头〔队头，用front指向排头元素的前一个位置。 考点9：循环队列 Rear队列的挨次储存构造一般承受循环队列的形式。循环队列初始状态为空，即rear=front=m〔队头、队尾指针同时指向同一个元素。 Front/ Rear入队运算：初始状态下，F和R都指向1，随着ABC元素的入队，R依次上移，2143215桔子CBADRearFRC，R1，使之构成循环。4C出队运算：在初始状态下RF都在1，一个元素退出，F上移一格R不变。上移一格，第一个元素A就会退出，被赋值给其它元素如a,Rear/ FrontRear/ Front321E6YFront/ Rear考点5：线性构造和非线性构造〔规律构造而言〕线性构造〔线代表：有且只有一个根结点，它无前件；有且只有一个终端〔叶子〕结点，无后件；春夏秋冬n春夏秋冬常见的线性构造有线性表、栈、队列〔循环队列。线性表是最简洁、常见数据构造。可用挨次存储构造、链式存储构造。挨次储存构造特点：线性表中全部元素存储空间连续，按规律挨次依次存放。非线性构造：一个数据构造不是线性构造，称为非线性构造〔树、图。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元素之前进展，需要移动一半的元素；最坏状况下需移动全部元素】例：线性表的删除运算删除线性表中的第一个元素〔29，过程如下：1、29；2、18；3、56 1、；2、18；3、56 1、18；2、；3、56 1、18；2、56元素时，在平均状况下，需要移动一半的元素。因此，在线性表挨次存储状况下，要删除一个数据，效率很低】7：栈栈：是限定在一端进展插入和删除的线性表，其特别性表达在它的插入和删除运FBb，以此类推。队尾指针始终不变指向1，rear指向位置才是队尾。E、F直到队满。此时，RearFront即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 18〔原指向〕X取得一个结点，设该结点号为p，其数据域为b.使结点p指向包含X的结点。 转 向即结点p的指针域为原结点q的指针域〔X的存储地址〕 p3〕使结点p指针域改为p，即指向元素b,完成插入。 b 18挨次表和链表的优缺点比较链表易于扩张并可动态安排规律关系；存储密度比挨次表低考点11：树与二叉树树〔tree：非线性构造，具有明显的层次构造FCKFCKADGB根结点〔F：没有前件的结点称为根节点，一个树只有一个。子节点：在树构造中，每一个结点可以有多个后件，这些后件都称为子节点。叶子结点：没有后件的结点，称为叶子结点。结点的度：〔叶子结点度为0〕F度为3树的度：在树构造中，全部结点中最大的度称为树的度。结点F 3树的深度：树的最大层次称为树的深度。4 〔树〕〔图框内是以C为根结点的子树。Value〔值〕Degree〔度〕Link1Value〔值〕Degree〔度〕Link1……Linkn对于一个树来讲首先要保存这个结点表示的值，然后说明结点的度〔即后件个数件进展依次说明，这是对于树当中每个结点必需存在的存储形式。二叉树特点：分别称为该结点的左子树和右子树。12341234567891011121314156--让每个人公平地提升自我66考点11-13：二叉树的性质1、2、3性质1：二叉树的第i层上至多有2i-1〔i≥1〕个结点。123456789101234567891010性质3：在任意二叉树中，度为0结点〔叶子结点〕比度为2结点多一个。121234567891011121314152的 结点有18个，则叶子 结点有 个。〔19。如上图所示， 二叉树第4层有=8〔1424-1=15〔2。10移到右侧也不算完全二叉树，必需保持左侧相对完整。FCEAFCEADGBHP左指针域和右指针域。BT二叉树存储结点构造：Lchild Value RchildL〔L〔i〕V〔i〕R〔i〕指向左子结点的指针域 数据域 结点的指针域考点14：二叉树的遍历二叉树的遍历：不重复的访问二叉树中的全部结点。【总原则：先左后右】前序遍历〔DLR：根左-右 以右图为例，访问挨次为：FCADBEGHP中序遍历〔LDR：左-根-右 以右图为例，遍历挨次为ACBDFEHGP后序遍历〔LRD：左-右-根ABDCHPGEF〔注：所谓的前中后遍历是依据访问根的挨次打算的；遍历左右子树时，仍承受以上原则〕宝宝定理：对于完全二叉树而言叶子结点个数=非叶子结点个数=n/2假设它的结点个数为奇数m，则该二叉树中：2346732264123467322641查找结果：1.查找成功：找到；2.查找不成功：没找到15：挨次查找挨次查找的根本思想：需元素为止。否则就是查找不成功，表中无要找元素。平均要与表中一半以上元素进展比较，最坏状况下需要比较全部元素n次。以下两种状况下只能承受挨次查找：假设线性表是无序表，则只能承受挨次查找。16：二分法查找思想：先确定待查找记录所在范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必需在具有挨次存储构造的有序表中进展。特点：比挨次查找方法效率更高。最坏状况下，需要比较log2二分法举例：在以下图长度为11的线性表中查找22过程

n次。n712712182240566679848894LowLow1〔a〕初始状态mid2345678910high11712182240566679848894Low12mid34high5〔b〕第一次比较后67891011712182240566679848894Lowmid high〔c〕其次次比较后交换类快速排序简洁插入两个子序列表中。插入排序素，将它交换到表的最前面。一个元素交换，再调整为堆O(nlogn)2O〔nlogn〕2O〔n〕2n(n-1)/2O〔n2〕插入类排序O〔n2〕希尔排序时间效率与选取增量有关O〔〕简洁选择n(n-1)/2O〔n〕2O〔n〕2选择类排序堆排序O(nlogn)2O〔nlogn〕O〔nlogn〕2 2挨次存储构造交换类快速排序简洁插入两个子序列表中。插入排序素，将它交换到表的最前面。一个元素交换，再调整为堆O(nlogn)2O〔nlogn〕2O〔n〕2n(n-1)/2O〔n2〕插入类排序O〔n2〕希尔排序时间效率与选取增量有关O〔〕简洁选择n(n-1)/2O〔n〕2O〔n〕2选择类排序堆排序O(nlogn)2O〔nlogn〕O〔nlogn〕2 2类别排序方法根本思想时间简单度平均时间最坏状况冒泡排序相邻元素比较，不满足条件时交换n(n-1)/2O〔n2〕时间O〔n2〕排序，是指将一个无序序列整理成按值非递减挨次排列的有序序列的过程。之间的比较和交换，不断的消退逆序，直到全部数据元素有序为止。对〔4,1,6,5,2,3〕6466562636〔1,4,5,2,3,6。614523，先比较结果为〔12，4，5，3，6。其次遍的排序方法同上，不再赘述。割，直到全部元素全部选取完毕，此时线性表即排序完毕。快速排序的具体做法：设置两个指针，lowhigh，它们的初值分别指向线性表的第一个元素k素和最终一个元素，首先从high所指向的位置向前扫描，找到第一个小于k元素的元素，并与k元kklowhigh序法。简洁插入排序法：是把n个待排序的元素看成一个有序表和一个无序表，开头时有序表只包含一个元素，而无序表包含剩余的n-1n，无序表为空时排序完成。此排序方法的效率与冒泡排序