(公共基础知识基本数据结构与算法).ppt

1、全国计算机等级考试二级,公共基础知识 基本数据结构与算法,公共基础知识 基本要求1. 掌握算法的基本概念。2. 掌握基本数据结构及其操作。3. 掌握基本排序和查找算法。4. 掌握逐步求精的结构化程序设计方法。5. 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6. 掌握数据的基本知识，了解关系数据库的设计 一、数据结构与算法 二、程序设计基础 三、软件工程基础 四、数据库设计基础,数据结构与算法,1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3. 线性表的

2、定义；线性表的顺序存储结构及其插入与删除运算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,一.算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。就是指解题方案的准确而完备的描述。 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。2.算法的基本要

3、素：算法中对数据的运算和操作 、算法的控制结构。3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求,在计算机中，算法是指_。A. 查询方法B. 加工方法C. 解题方案的准确而完整的描述D. 排序方法,C,二.算法的复杂度1.算法的时间复杂度：指执行算法所需要的计算工作量2.算法的空间复杂度：执行这个算法所需要的内存空间 算法的复杂度的表示 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n) 表示随问题规模n的增大，算法执行时间的增长率和f(n)的增

4、长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 空间复杂度：算法所需存储空间的量度。记作：S(n)=O(f(n),算法的时间复杂度是指_。A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数 下面叙述正确的是_。A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对,(C),(C),算法的空间复杂度是指_。A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要

5、的存储空间 算法一般都可以用哪几种控制结构组合而成_。A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环 算法的复杂度主要包括_复杂度和空间复杂度。,(D),(D),答：时间,三.数据结构的定义 数据结构：相互之间存在一种或多种特定关系的数据元素的集合 1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。2.数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构，又称存储结构。常用的存储结构有顺序、链接、索引等存储结构。,数据的逻辑结构在计算机存储空间中的存放形式称

6、为数据的_。,答：存储结构,数据的存储结构是指_。A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据,(B),四.数据结构的图形表示：在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。 （1）集合：松散的关系。 （2）线性结构:一对一 （3）树形结构:一对多 （4）图状结构:多对多,五.线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构。线性结构：非空数据结构满

7、足：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。 非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。常见的线性结构：线性表、栈、队列 常见的非线性结构：树、图 注意：链表也属于线性表，所以也是线性结构,六.线性表的定义线性表是n 个元素构成的有限序列（A1，A2，A3）。表中的每一个数据元素，除了第一个以外，有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表是一个空表，或可以表示为（a1,a2,an）, 其中ai(I=1,2,n)是属于数据对象的元素，通常也称其为线性表中的一个结点。非空线性表有如下一些特征：（1）有且只有一个根结点a1,它无前件；（2）有

8、且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。,七.线性表的顺序存储结构线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具备如下两个基本特征：1.线性表中的所有元素所占的存储空间是连续的；2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。即线性表逻辑上相邻、物理也相邻，则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。,顺序存储方法是把逻辑上相邻的结点存储在物理位置_的存储单元中。,答：相邻,假设线性表

9、的每个元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系:LOC(ai+1)=LOC(ai)+KLOC(ai)=LOC(a1)+(i-1)*K 其中，LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。因为在顺序存储结构中，每个数据元素地址可以通过公式计算得到，所以线性表的顺序存储结构是随机存取的存储结构。在线性表的顺序存储结构下，可以对线性表做以下运算：插入、删除、查找、排序、分解、合并、复制、逆转,八.顺序表的插入运

10、算线性表的插入运算是指在表的第I个位置上，插入一个新结点x，使长度为n的线性表（a1,a2 aian）变成长度为n+1的线性表(a1,a2x,aian).该算法的时间主要花费在循环的结点后移语句上，执行次数是n-I+1。当I=n+1,最好情况，时间复杂度o(1) 当I=1, 最坏情况，时间复杂度o(n)算法的平均时间复杂度为o(n),九.顺序表的删除运算线性表的删除运算是指在表的第I个位置上，删除一个新结点x，使长度为n的线性表（a1,a2 aian）变成长度为n-1的线性表(a1,a2ai-1,ai+1an).当I=n,时间复杂度o(1),当I=1,时间复杂度o(n) ,平均时间复杂度为o(

11、n),顺序表的插入运算过程,十.栈的存储结构及其基本运算1.什么是栈？ 栈实际上也是一个线性表，只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶（TOP），另一端为栈底（BOTTOM）。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。假设栈S=（a1,a2,a3,an），则a1 称为栈底元素，an称为栈顶元素。栈中元素按a1,a2,a3an的次序进栈，退栈的第一个元素应该是栈顶元素。即后进先出。 注意： 栈是限定仅在表尾进行插入或删除操作的线性表。栈的

12、表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。栈又称后进先出（LIFO，last in first out）的线性表。,2.栈的顺序存储及其运算用S（1：M）作为栈的顺序存储空间。M为栈的最大容量。栈的基本运算有三种：入栈、退栈与读栈顶元素。入栈运算：在栈顶位置插入一个新元素。首先将栈顶指针进一（TOP+1），然后将新元素插入到栈顶指针指向的位置。退栈运算：指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素赋给一个指定的变量，然后将栈顶指针退一（TOP-1）读栈顶元素：将栈顶元素赋给一个指定的变量。栈顶指针不会改变。,例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：,栈顶top,栈底

13、bottom,下列关于栈的叙述中正确的是_。 A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。A. ABCEDB. DBCEAC. CDABED. DCBEA 解题分析： A、B、C、D的出栈顺序一定是DCBA,E在其中任何位置都可以,(D),(D),十一.队列的存储结构及其基本运算1.什么是队列队列是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做队头，允许插入的一端叫做队尾。队列的修改是先进先出。往队尾插入一个元素成为入队运算。从

14、对头删除一个元素称为退队运算。 注意： 队列：限定仅在表的一端进行插入，在另一端进行删除操作的线性表。是一种先进先出（FIFO，first in first out）的线性表。允许插入的的一端叫队尾，允许删除的一端则称为队头。,下图是队列的示意图： a1a2an,出队,入队,队头,队尾,由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素

15、的下一位置。 0 1 2 3,Front rear,Front rear,(a)队列初始为空（b）A,B,C入队,front rear front rear,（c) a出队 (d) b,c出队，队为空 和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。,下列关于队列的叙述中正确的是_。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线

16、性表D. 队列是先进后出的线性表,(C),2.循环队列及其运算在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，从队头指针front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素均为队列中的元素。,克服上述假上溢现象的方法 是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指

17、针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0,在实际使用循环队列时，为了能区分队满还是队列空，通常需要增加一个标志S：队列空，则S=0，rear=front=m 队列满，则S=1，rear=front=m循环队列主要有两种基本运算：入队运算和退队运算入队运算指在循环队列的队尾加入一个新元素，首先rear=rear+1,当rear=m+1时，置rear=1,然后将新元素插入到队尾指针指向的位置。当S=1，rear=front,说明队列已满，不能进行入队运算，称为“上溢”。退队运算指在循环队列的队头位置退出一个元素并赋给指定的变

18、量。首先front=front+1,并当front=m+1时，置front=1,然后将对头指针指向的元素赋给指定的变量。当循环队列为空S=0，不能进行退队运算，这种情况成为“下溢”。,十二.线性单链表的存储结构: 以链式结构存储的线性表称之为线性链表。缺点是不容易找到直接前趋。 头指针只相当于结点的指针域，头结点即整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放线性表的长度等附加信息，也可以不存储任何信息。,十三.线性链表的基本运算 1.线性链表的插入 2.线性链表的删除,用链表表示线性表的优点是_。A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间

19、较顺序存储少D. 便于随机存取,(A),十四.双向链表的存储结构：在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。,十五.循环链表的存储结构及其基本运算是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任一结点出发均可找到表中其他结点。,在 中，只要指出表中任何一个结点的位置，就可以从它出发依次访问到表中其他所有结点。 A线性单链表 B双向链表 C线性链表 D循环链表 这里的关键词是“依次”，线性单链表不能找到前面的节点。这题有2个答案。,（B，D）,十六.树 一、树的定义：树是n(n=0)个结点的有限集。在任意一棵非

20、空树中： (1)有且仅有一个特定的称为根的结点； (2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,.Tm,其中每一个集合本身又是一棵树,并且称为根的子树.,二、树的基本概念： 树的结点包含一个数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度。 度为0的结点称为叶子或终端结点。 度不为0的结点称为非终端结点或分支结点。 树的度是树内各结点的度的最大值。 结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。,同一个双亲的孩子之间互称兄弟。 结点的祖先是从根到该结点所经分支上的所有结点。 以某结点为根的子树中的任一结点都称为该结点的子孙。 结点的层次从根

21、开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度，或高度。 如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。,森林是m(m=0)棵互不相交的树的集合。,十七.二叉树的定义 二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。 一棵深度为k且有2k-1个结点的二叉树称为满二叉树，如图(a)，按图示给每个结点编号，如果有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应

22、时，称之为完全二叉树。 注意： 满二叉树：除最后一层以外，每一层上的所有结点都有两个子结点。在满二叉树的第K层上有2K-1个结点，且深度为M的满二叉树有2M-1个结点完全二叉树：除最后一层以外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有N个结点的完全二叉树的深度为log2n+1完全二叉树总结点数为N，N为奇数，则叶子结点数为（N+1）/2 若N为偶数，则叶子结点数为N/2。（即N/2向上取整）,性质：在二叉树的第i层上至多有2i-1次方个结点(i=1)。 性质：深度为k的二叉树至多有2k-1个结点(k=1)。 性质：对任何一棵二叉树T，如果其终端结点数为n0,度为2的

23、结点数为n2,则n0=n2+1。 性质：具有n个结点的完全二叉树的深度为|log2n|+1 性质：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1=1,则双亲PARENT(i)是结点i/2(2)如果2in,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i(3)如果2i+1n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1,1、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。 A.349 B. 350 C. 255 D. 351 2、在一棵二叉树上第5层的结点数最多是_。A. 8 B. 16 C. 32 D. 1

24、5 3、在深度为5的满二叉树中，叶子结点的个数为 4、以下数据结构中不属于线性数据结构的是_。A. 队列 B. 线性表 C. 二叉树 D. 栈 5、树是结点的集合，它的根结点数目是（ ） 6、具有3个结点的二叉树有（ ）种形态,(B),(B),(16),（C）,有且只有1,（5）,二叉树的存储结构 二叉树通常采用链式存储结构,十八.遍历二叉树的三种方法： 先序： 1、访问根结点 2、先序访问左子树 3、先序访问右子树 中序 1、中序访问左子树 2、中序访问根结点 3、中序访问右子树 后序 1、后序访问左子树 2、后序访问右子树 3、访问根结点,先序遍历结果：1,2,4,5,6,7,3 中序遍历

25、结果：4,2,6,5,7,1,3 后序遍历结果：4,6,7,5,2,3,1,1、设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（13）分析 2、已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba）分析3、已知一棵二叉树前序遍历和中序遍历分别为ABDGCFK和DGBAFCK，则该二叉树的后序遍历为（B）分析 A、ACFKBDG B、GDBFKCA C、KCFAGDB D、ABCDFKG 4、若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca）,十九

26、.顺序查找与二分查找 顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。平均查找长度：3(n+1)/4 在两种情况下只能用顺序查找： 1、线性表（顺序或链式）为无序表 2、链式存储结构的有序表 二分查找（折半查找）只适用于顺序存储的有序表（从小到大）。对于长度为N的有序线性表，在最坏情况下，二分查找只需要比较log2N次，而顺序查找要比较N次。 先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。,对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。A.

27、N+1B. NC. (N+1)/2D. N/2,(B),二分查找查找过程,二十.排序 排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。 直接插入排序:是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。排序过程：38,49,65,97,76,13,27,49,.,二十.交换类排序法冒泡排序与快速排序法属于交换类的排序方法冒泡排序法 假设线性表的长度为N，则在最坏的情况下，冒跑排序需要经过N/2遍的从前往后的扫描和N/2遍的从后往前的扫描，需要的比较次数为N（N-1）/2,（1）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将

28、两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。 然后进行第二趟起泡排序，对前n-1个记录进行同样操作。.直到在某趟排序过程中没有进行过交换记录的操作为止。,在最坏情况下，冒泡排序的时间复杂度为_。,答：n(n-1)/2或n*(n-1)/2或O(n(n-1)/2)或O(n*(n-1)/2),（2）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。,二十一.选择类排序法 1.简单选择排序法 2.堆排序 二十二.插入类排序法 1.

29、简单插入排序法2.希尔排序 交换类排序 冒泡排序：最坏n(n-1)/2 ；最简单的交换排序。在待排序的元素序列基本有序的前提下，效率最高。快速排序：最坏n(n-1)/2； 最好O(Nlog2 N) 插入排序 简单插入排序：最坏n(n-1)/2 ；每个元素距其最终位置不远时适用。 希尔排序：最坏O(n1.5) 选择排序 简单选择排序：最坏n(n-1)/2 堆排序：最坏O(nlog2n) ，适用于较大规模的线性表。,希尔排序法属于哪一种类型的排序法_。A. 交换类排序法B. 插入类排序法C. 选择类排序法D. 建堆排序法 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是_。A. 堆排序B. 直接插入排序C. 快速排序D. 直接选择排序,(B),(B),1.栈和队列的共同特点是（ ） 2.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（e2,e4,e3,e1 ，这只是其中一种，请大家分别列出剩下的几种出栈序列）选择题选择答案为 A. e3,e1,e2,e4 B.e4,e2,e3,e1 C. e4,e1,e3,e2 D.e3,e4,e2,e1