计算机二级公共基础知识

公共基础知识——基本数据结构与算法二级ACCESS—数据库基础知识本章的重要性经统计本章在理论考试中占10%左右即4个左右的选择题。本章在考试中只涉及笔试题目，上机不考。二级ACCESS—数据访问页关键考点顺序存储与链式存储的基本概念栈、队列的基本概念与基本操作循环队列元素个数的计算算法时间、空间复杂度的概念几种查找与排序的比较次数二叉树的遍历二叉树结点个数的计算基本数据结构与算法1.1算法算法的基本概念٭算法：解题方案的准确而完整的描述。٭算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。٭基本特性(P1)▪可行性：根据实际问题设计的算法，执行得到满意结果▪确定性：每一步骤必须有明确定义，不允许有多义性。▪有穷性：算法必须能在有限的时间内做完。▪拥有足够的情报：输入和输出，方可执行。基本数据结构与算法1.1算法算法的复杂度：时间复杂度、空间复杂度算法的时间复杂度▪算法时间复杂度是指执行算法所需要的计算工作量。▪工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)٭算法空间复杂度▪算法空间复杂度是指执行这个算法所需要的内存空间。▪存储空间包括：①算法程序所占的空间、②输入数据所占的空间、③算法执行过程中所需要的额外空间。。基本数据结构与算法数据结构主要研究以下三个方面的问题٭数据的逻辑结构：数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系）٭数据的存储结构：各数据元素在计算机中的存储关系٭对各种数据结构进行的运算主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。数据结构研究的主要内容基本数据结构与算法数据元素(DataElement)数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元素可由若干数据项(DataItem)组成。数据项是数据的最小单位。数据元素亦称节点或记录。1.2数据结构的基本概念基本数据结构与算法1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构类型基本数据结构与算法线性结构和非线性结构线性结构条件٭（1）有且只有一个根结点；٭（2）每一个结点最多有一个前件，也最多有一个后件。٭（3）首节点无前件，尾节点无后件。非线性结构：不满足线性结构条件的数据结构注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号基本数据结构与算法线性结构和非线性结构全校学生档案管理的树形结构的组织方式非线性结构树形结构基本数据结构与算法Lo+（n-1)*m元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m每个元素所占用的存储单元个数顺序存储与链式存储顺序存储٭常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。三个弱点٭插入或删除操作时，需移动大量元数。٭长度变化较大时，需按最大空间分配。٭表的容量难以扩充基本数据结构与算法每个节点都由两部分组成：数据域和指针域。数据域：存放元素本身的数据，指针域：存放指针，体现数据元素之间的逻辑联系顺序存储与链式存储1536元素21400元素11346元素3∧元素4head1345链接存储结构特点٭比顺序存储结构的存储密度小(每个节点都由数据域和指针愈组成)。٭逻辑上相邻的节点物理上不必相邻。٭插入、删除灵活(不必移动节点，仅改变节点中的指针)。链接存储结构基本数据结构与算法1346元素31536…….……..…….1536元素21400…….……..…….∧元素413461400元素11345指针存储内容存储地址1536元素21400元素11346元素3∧元素4head1345顺序存储与链式存储链式存储的地址映射表基本数据结构与算法1.3线性表线性表的基本概念线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。非空线性表的结构特征٭有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；٭除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。Lo+（n-1)*m元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m基本数据结构与算法在线性表上常用的运算有初始化、求长度、取元素、修改、插入、删除、检索、排序。线性表的插入操作在线性表L中第i个数据元素之前插入数据元素e٭检查插入要求的有关参数的合理性٭把原来第n个数据元素至第i个元素（共n-i+1)依次后移一个数组元素的位置。٭把新数据元素放在第i个位置上٭修正线性表的数据元素个数。٭线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：n/21.3线性表基本数据结构与算法线性表的插入操作（时间复杂度O(n)）插入前插入xlastMaxsize-1aia1a0ai-1ai+1an-1a0a1ai-1aian-1lastMaxsize-1后移后ai＋1a0a1ai-1ai+1ai+1anxlastMaxsize-1插入后ai+21.3线性表基本数据结构与算法线性表的删除操作（时间复杂度O(n)）1.3线性表a0a1ai-1aiai+1an-1删除lastmaxsize删除前a0a1ai-1ai+2an-1lastmaxsize删除后ai+1基本数据结构与算法1.4栈和队列栈和队列是两种运算时要受到某些特殊限制的线性表，故也称为限定性的数据结构。栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。٭设栈s=（a1，a2，…,ai，…，an）٭其中a1是栈底元素，an是栈顶元素。٭栈顶（top)：允许插入和删除的一端；٭约定top始终指向新数据元素将存放的位置。٭栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底基本数据结构与算法队列的主要运算٭设置一个空队列；٭插入一个新的队尾（rear）元素，称为进队；٭删除队头（front）元素，称为出队；٭读取队头元素；a1,a2,a3,a4,…………an-1,an队头队尾1.4栈和队列队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。基本数据结构与算法3210(a)rear=front=0(队空）e3e4(c)(c)e1,e2出队，e4入队rear=4fronte1e2e3(b)rearfront(b)e1,e2,e3入队1.4栈和队列队列的主要运算٭队空时，令rear=front=0;元素个数＝rear-front٭当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置基本数据结构与算法循环队列元素个数=(rear-front+n)modna1,a2,a3,a4,…………an-1,an队头队尾1.4栈和队列循环队列：首尾相接的队列，逻辑上形成一个环状。基本数据结构与算法1.5线性链表线性表顺序存储结构的特点简单、方便，要求数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题٭在做插入或删除元素的操作时，会产生大量的数据元素移动；٭对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；٭线性表的容量难以扩充。基本数据结构与算法将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。线性链表分为：单链表、双链表、循环链表1.5线性链表a1a2∧ana3L…..带头结点的单链表基本数据结构与算法单链表：每个结点只有一个指针域，由该指针只能找到其后件结点。1.5线性链表基本数据结构与算法babaxPP单链表的插入运算：在节点a之后插入一新节点S1.5线性链表基本数据结构与算法ai-1a1aiai+1Lp单链表的删除运算：删除节点ai1.5线性链表a1qq基本数据结构与算法1.5线性链表线性链表的特点٭插入、删除节点方便(不必移动节点，仅改变节点中的指针)٭只能顺序存取（查找只能从头指针开始），不能随即存取。٭适应于数据的动态变化基本数据结构与算法树的定义：由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。ACGT2DHIT3JMBELKT1F现实世界中，能用树的结构表示：学校的行政关系、书的层次结构、人类的家族血缘关系等。1.6树与二叉树基本数据结构与算法树的基本概念：结点（Node）：树中的元素结点的度（Degree）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第一层。叶子（Leaf）：度为零的结点，也称端结点。孩子（Child）：结点子树的根称为该结点的孩子结点。兄弟（Sibling）：同一双亲的孩子。双亲（Parent）：孩子结点的上层结点，称为其的双亲。深度（Depth)：树中结点的最大层次数。森林（Forest）：M棵互不相交的树的集合。ACGT2DHIT3JMBELKT1F1.6树与二叉树基本数据结构与算法二叉树（BinaryTree）的定义二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的理论。1.6树与二叉树二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。基本数据结构与算法满二叉树423167891011121314155特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。1.6树与二叉树基本数据结构与算法423167891011125非完全二叉树完全二叉树423167891011125完全二叉树特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。1.6树与二叉树基本数据结构与算法A、二叉树的第k层上至多有2k-1（k1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点（度为0），有n2个度为2的结点，则：n0=n2+1D、具有n个结点的完全二叉树的深度为[log2n]+1，其中[log2n]表示log2n的整数部分。二叉树的基本性质4231678910111213141551.6树与二叉树第三层(i=3)，有23-1=4个节点深度h=4，共有24-1=15个节点n0=8,n2=7,n0=n2+115个节点，深度=[log215]+1=4基本数据结构与算法二叉树的遍历遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍历：前序遍历(DLR):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(LDR):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。1.6树与二叉树基本数据结构与算法遍历算法先序遍历：DLR中序遍历：LDR后序遍历：LRDADBCT1T2T3DLRADLRDLRBDCDLR以先序遍历DLR为例演示