笔试数据结构与算法.ppt

第1章基本数据结构与算法,主讲：曾庆尚 烟台大学文经学院电子系,二级ACCESS数据库基础知识,本章的重要性,2007年4月-2010年9月共8次计算机等级考试 涉及到本章内容的题目有40题，平均每次接近10分，因此本章还是很重要的。 本章在考试中只涉及笔试题目，上机不考。,二级ACCESS数据访问页,关键考点,顺序存储与链式存储的基本概念 栈、队列的基本概念与基本操作 循环队列元素个数的计算 算法时间、空间复杂度的概念 几种查找与排序的比较次数 二叉树的遍历 二叉树结点个数的计算,基本数据结构与算法,本章主要内容,算法 数据结构 数据结构研究的主要内容 基本概念和术语 数据结构类型 线性结构和非线性结构 顺序存储与链式存储 线性表 栈和队列 线性链表 树与二叉树 查找和排序 图,基本数据结构与算法,1.1 算法,算法的基本概念 算法：解题方案的准确而完整的描述。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。 基本特性 可行性：根据实际问题设计的算法，执行得到满意结果 确定性：每一步骤必须有明确定义，不允许有多义性。 有穷性：算法必须能在有限的时间内做完。 拥有足够的情报：输入和输出，方可执行。,基本数据结构与算法,1.1 算法,算法的基本要素 1.算法中对数据的运算和操作 算术运算：、等 逻辑运算：、=、=、!=等 关系运算：and、or、not等 数据传输：w、r等 2.算法的控制结构 算法中各操作之间的执行顺序 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等 算法可以用顺序、选择、循环三种基本机构组合而成。,基本数据结构与算法,1.1 算法,算法设计基本方法 （1）列举法：根据问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 （2）归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。 （3）递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。 （4）递归：将问题逐层分解的过程。 （5）减半递推技术： “减半”，是指将问题规模减半，而问题性质不变； “递推”，是指重复“减半”过程。 （6）回溯法：分析问题，找出一个解决总线索，然后沿着这个线索逐步试探。,基本数据结构与算法,1.1 算法,算法的复杂度：时间复杂度、空间复杂度 （P5） 算法的时间复杂度 算法时间复杂度是指执行算法所需要的计算工作量。 工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f(n) 算法空间复杂度 算法空间复杂度是指执行这个算法所需要的内存空间。 存储空间包括：算法程序所占的空间、 输入数据所占的空间、算法执行过程中所需要的额外空间。,基本数据结构与算法,3.2.1 数据结构研究的主要内容,当今计算机应用的特点 所处理的数据量大且具有一定的关系； 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。 应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的学生信息。,基本数据结构与算法,特点 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系. 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。,数据结构研究的主要内容,基本数据结构与算法,应用举例2制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些则不需要;而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：,数据结构研究的主要内容,基本数据结构与算法,数据结构研究的主要内容,特点 课程的先后关系用图结构描述； 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。,基本数据结构与算法,数据结构主要研究以下三个方面的问题(P7) 数据的逻辑结构：数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系） 数据的存储结构：各数据元素在计算机中的存储关系 对各种数据结构进行的运算 主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。,数据结构研究的主要内容,基本数据结构与算法,数据结构是一门研究数据组织、存储和运算的一般方法的学科。是相互有关联的数据元素的集合。,1.2 数据结构的基本概念,基本数据结构与算法,能输入到计算机中 并能被计算机程序处理的 符号的集合。,整数(1,2)、实数(1.1,1.2) 字符串(Beijing)、 图形、声音。,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,1.2 数据结构的基本概念,基本数据结构与算法,计算机管理图书问题 图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。 如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,1.2 数据结构的基本概念,基本数据结构与算法,最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,1.2 数据结构的基本概念,基本数据结构与算法,如何将0,1,2,3,4,5,6,7,8,9这10个数存放在 计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。 从大到小排列：9,8,7,6,5,4,3,2,1,0 输出偶数：0,2,4,6,8,1,3,5,7,9,数据元素在 计算机中的表示,数据结构是一门研究数据组织、存储和运算的一般方法的学科。,1.2 数据结构的基本概念,基本数据结构与算法,对数据结构中的节点进行操作处理 (插入、删除、修改、查找、排序),数据结构是一门研究数据组织、存储和运算的一般方法的学科。,1.2 数据结构的基本概念,基本数据结构与算法,数据元素(Data Element) 数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元素可由若干数据项(Data Item)组成。数据项是数据的最小单位。,数据元素亦称节点或记录。,1.2 数据结构的基本概念,基本数据结构与算法,数据结构可描述为 Group=（D，R）,有限个数据元素的集合,有限个节点间关系的集合,1.2 数据结构的基本概念,基本数据结构与算法,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构类型,基本数据结构与算法,线性结构和非线性结构,线性结构条件 （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 （3）首节点无前件，尾节点无后件。 非线性结构：不满足线性结构条件的数据结构 注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。,基本数据结构与算法,线性结构和非线性结构,树形结构,基本数据结构与算法,树形结构 结点间具有分层次的连接关系,线性结构和非线性结构,树形结构,基本数据结构与算法,线性结构和非线性结构,图形结构：节点间的连接任意,基本数据结构与算法,顺序存储与链式存储,顺序存储 常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 三个弱点 插入或删除操作时，需移动大量元数。 长度变化较大时，需按最大空间分配。 表的容量难以扩充,基本数据结构与算法,每个节点都由两部分组成：数据域和指针域。 数据域：存放元素本身的数据， 指针域：存放指针，体现数据元素之间的逻辑联系,顺序存储与链式存储,链接存储结构特点 比顺序存储结构的存储密度小 (每个节点都由数据域和指针愈组成)。 逻辑上相邻的节点物理上不必相邻。 插入、删除灵活(不必移动节点，仅改变节点中的指针)。,链接存储结构,基本数据结构与算法,顺序存储与链式存储,链式存储的地址映射表,基本数据结构与算法,1.3 线性表,线性表的基本概念 （P15） 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 非空线性表的结构特征 有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件； 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。,基本数据结构与算法,在线性表上常用的运算有 初始化、求长度、取元素、修改、插入、删除、检索、排序。 线性表的插入操作 （P17） 在线性表L中第i个数据元素之前插入数据元素e 检查插入要求的有关参数的合理性 把原来第n个数据元素至第i个元素（共n-i+1)依次后移一个数组元素的位置。 把新数据元素放在第i个位置上 修正线性表的数据元素个数。 线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：n/2,1.3 线性表,基本数据结构与算法,线性表的插入操作（时间复杂度O(n)）,1.3 线性表,基本数据结构与算法,线性表的删除操作（时间复杂度O(n)）（P18）,1.3 线性表,基本数据结构与算法,1.4 栈和队列（P19）,栈和队列是两种运算时要受到某些特殊限制的线性表，故也称为限定性的数据结构。 栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。 设栈s=（a1，a2，,ai，an） 其中a1是栈底元素， an是栈顶元素。 栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。 栈底（bottom):不允许插入和删除的一端。,基本数据结构与算法,队列的主要运算 设置一个空队列； 插入一个新的队尾（rear）元素，称为进队； 删除队头（front）元素，称为出队； 读取队头元素；,a1 , a2 , a3 , a4 , an-1 , an,队头,队尾,1.4 栈和队列,队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。,基本数据结构与算法,1.4 栈和队列,队列的主要运算 队空时，令rear=front=0; 元素个数rear-front 当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置,基本数据结构与算法,循环队列元素个数=(rear-front+n) mod n,a1 , a2 , a3 , a4 , an-1 , an,队头,队尾,1.4 栈和队列,循环队列：首尾相接的队列，逻辑上形成一个环状。,基本数据结构与算法,1.5 线性链表（P24）,线性表顺序存储结构的特点 简单、方便，要求数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题 在做插入或删除元素的操作时，会产生大量的数据元素移动； 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； 线性表的容量难以扩充。,基本数据结构与算法,将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。 数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。 线性链表分为：单链表、双链表、循环链表,1.5 线性链表,基本数据结构与算法,单链表：每个结点只有一个指针域，由该指针只能找到其后件结点。,1.5 线性链表,基本数据结构与算法,1.5 线性链表,线性链表的计算 在指定节点前插入一个元素(不必移动节点，仅改变节点中的指针，且不会出现“上溢”现象) 删除指定节点(不必移动节点，仅改变节点中的指针) 合并两个线性链表 逆转线性链表 复制线性链表 线性链表排序 线性链表查找,基本数据结构与算法,P,P,单链表的插入运算：在节点a之后插入一新节点,S,1.5 线性链表,基本数据结构与算法,L,p,单链表的删除运算：删除节点ai,1.5 线性链表,基本数据结构与算法,循环链表: 首尾相接的链表 （P30） 循环链表是表中最后一个结点的指针非空，而是指向头结点，使链表构成环状。 特点： 2、增加了头结点，使得任何时候循环链表中至少有一个结点。 1、从表中任一结点出发均可找到表中其他结点，提高查找效率。,1.5 线性链表,基本数据结构与算法,双向链表：在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。,1.5 线性链表,基本数据结构与算法,1.5 线性链表,线性链表的特点 插入、删除节点方便(不必移动节点，仅改变节点中的指针) 只能顺序存取（查找只能从头指针开始），不能随即存取。 适应于数据的动态变化,基本数据结构与算法,树的定义：由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。,现实世界中，能用树的结构表示：学校的行政关系、书的层次结构、人类的家族血缘关系等。,1.6 树与二叉树,基本数据结构与算法,树的基本概念： 结点（Node）：树中的元素 结点的度（Degree）：结点拥有的子树数。 结点的层次：从根结点开始算起，根为第一层。 叶子（Leaf）：度为零的结点，也称端结点。 孩子（Child）：结点子树的根称为该结点的孩子结点。 兄弟（Sibling）：同一双亲的孩子。 双亲（Parent）：孩子结点的上层结点，称为其的双亲。 深度（Depth)： 树中结点的最大层次数。 森林（Forest）：M棵互不相交的树的集合。,1.6 树与二叉树（P31）,基本数据结构与算法,二叉树（Binary Tree）的定义(P34),二叉树的五种基本形态,因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的理论。,1.6 树与二叉树,二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。,基本数据结构与算法,满二叉树 （P35）,特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。,1.6 树与二叉树,基本数据结构与算法,完全二叉树 （P35）,特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。,1.6 树与二叉树,基本数据结构与算法,A、二叉树的第i层上至多有2k-1（k 1）个结点。 B、深度为h的二叉树中至多含有2m-1个结点。 C、若在任意一棵二叉树中，有n0个叶子结点（度为0），有n2个度为2的结点，则：n0=n2+1 D、具有n个结点的完全二叉树的深度为log2n+1，其中 log2n表示log2n 的整数部分。,二叉树的基本性质（P34）,1.6 树与二叉树,第三层 (i=3)，有23-1=4个节点 深度h=4，共有24-1=15个节点 n0=8,n2=7,n0=n2+1 15个节点，深度=log215+1=4,基本数据结构与算法,E、设完全二叉树共有n个结点，如从根结点开始，按层序（每一层从左到右）用自然数1,2,n给结点进行编号，则对于编号为k（k=1,2,n）的结点有以下结论： 若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点的编号为INT(k/2)。 若2kn，则结点k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。 若2k+1n，则结点k的右子结点编号为2k+1；否则该结点无右子结点。,二叉树的基本性质,1.6 树与二叉树,例如结点6，其父结点为3，左子结点为12，左子结点为13,基本数据结构与算法,1.6 树与二叉树,二叉树的存储结构 (P36) 顺序存储结构 链式存储结构 顺序存储结构 （不需掌握） 用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。 用数组存储时，若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。 顺序存储二叉树必须按完全二叉树的形式存储，将造成存储的浪费。,基本数据结构与算法,二叉树的顺序存储结构（不需掌握）,T16,2h-1=,24-1 = 15,1.6 树与二叉树,基本数据结构与算法,1.6 树与二叉树,二叉树链式存储结构（不需掌握） 在顺序存储结构中，对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：,A,B,基本数据结构与算法,1.6 树与二叉树,二叉树的链接存储结构（不需掌握）,基本数据结构与算法,二叉树的遍历（P38） 遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。 按先左后右的原则，一般使用三种遍历： 前序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。 后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。,1.6 树与二叉树,基本数据结构与算法,遍历算法,先序遍历：D L R 中序遍历：L D R 后序遍历：L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,1.6 树与二叉树,基本数据结构与算法,查找：在一个给定的数据结构中，根据给定的条件找到满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 平均查找长度：查找过程中比较的次数 查找的结果 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。,1.7 查找技术（P39）,基本数据结构与算法,顺序查找（线性查找） 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方法。 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度=(n+1)/2。 时间复杂度O(n) 在下面两种情况下只能采取顺序查找： 线性表为无序表（元素排列是无序的）； 即使是有序线性表，但采用的是链式存储结构。,1.7 查找技术（P39）,基本数据结构与算法,折半查找（二分法查找）,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 若中间项的值等于x,则说明已查到。 若x小于中间项的值，则在线性表的前半部分查找； 若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。,1.7 查找技术（P39）,折半查找（二分法查找）算法,假设查找表存放在数组a的a1an中，且升序，查找关键字值为k。折半查找的主要步骤为： （1）置初始查找范围：low=1，high=n; （2）求查找范围中间项：mid=(low+high)/2 （3）将指定的关键字值k与中间项amid.key比较。 若相等，查找成功，找到的数据元素为此时mid 指向的位置； 若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1; 若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1; （4）重复步骤（2）、（3）直到查找成功或查找范围空（lowhigh），即查找失败为止。 （5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。,查找23和79的过程如下图：9元素,mid=(low+high)/2不进位取整,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),基本数据结构与算法,排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。 排序过程的组成步骤 1、首先比较两个关键字的大小； 2、然后将记录从一个位置移动到另一个位置。,1.8 排序技术（P40）,基本数据结构与算法,交换排序的特点在于交换，有冒泡和快速排序两种。 冒泡排序（起泡排序） 思想：小的浮起，大的沉底。从左端开始比较。 第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上； 依次类推，则完成排序。 正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2) 排序n个记录的文件最多需要n-1趟冒泡排序。,1.8.1 交换类排序法（P40）,基本数据结构与算法,第 六 趟 排 序 后,第 五 趟 排 序 后,第 四 趟 排 序 后,第 三 趟 排 序 后,第 二 趟 排 序 后,第 一 趟 排 序 后,初 始 关 键 字,1.8.1 交换类排序法示例,基本数据结构与算法,该算法适合于n 较小的情况，时间复杂度为O(n2).,待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序： 15 27 36 42 53 69 直接插入排序示例,对于有n个数据元素的待排序列，插入操作要进行n-1次,1.8.2 直接插入排序（P42）,从数组的第2号元素开始，顺序取出后续元素，并将该元素插入到其左端已排好序数组的适当位置。需比较n(n-1)/2次,基本数据结构与算法,例：有6个记录，前5 个已排序的基础上，对第6个记录排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 ,(highlow ，查找结束，插入位置为low 或high+1 ),( 4236 ),( 4253 ),折半插入排序,折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置 。待排序元素越多，改进效果越明显。,思想：首先从1n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。 时间复杂度为O(n2)，最坏情况下需要比较 n(n-1)/2次 适用于待排序元素较少的情况。,1.8.3 简单选择排序（P44）,初态,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3 9 8 6,1 3 9 8 6,1 3 9 8 6,基本数据结构与算法,各种排序法比较,二级ACCESS查询,过关练习,【2010.9】(1) 下列叙述中正确的是【 】 A) 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B) 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C) 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D) 上述三种说法都不对 【2010.9】(2)下列叙述中正确的是【 】A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D）上述三种说法都不对,二级ACCESS查询,过关练习,【2010.9】(3)一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素)的顺序为【 】。 【2010.9】(4)在长度为n的线性表中，寻找最大项至少需要比较【 】次。 【2010.9】(5)一棵二叉树有10个度为1的结点，7个度为2的结点，则该二义树共有【 】个结点。,1DCBA2345,1,25,二级ACCESS查询,过关练习,【2010.3】(6)下列叙述中正确的是【 】 A)对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n B)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2) C)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n) D)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n log2n) 【2010.3】(7)算法的时间复杂度是指【 】 A)算法的执行时间 B)算法所处理的数据量 C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数,二级ACCESS查询,过关练习,【2010.3】(8)一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为【 】。 【2010.3】(9)设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有【 】 个元素。 【2010.3】(10)设二叉树如下： 对该二叉树进行后序遍 历的结果为【 】 。,A,B,C,D,E,F,5,4,3,2,1,15,EDBGHFCA,二级ACCESS查询,过关练习,【2009.9】(11) 下列数据结构中，属于非线性结构的是【 】 A）循环队列 B）带链队列 C）二叉树 D）带链栈 【2009.9】(12)下列数据结果中，能够按照“先进后出”原则存取数据的是【 】 A）循环队列B）栈C）队列D）二叉树 【2009.9】(13) 对于循环队列，下列叙述中正确的是【 】 ）队头指针是固定不变的 ）队头指针一定大于队尾指针 ）队头指针一定小于队尾指针 ）队头指针可以大于队尾指针，也可以小于队尾指针,二级ACCESS查询,过关练习,【2009.9】（14）算法的空间复杂度是指【 】 ）算法在执行过程中所需要的计算机存储空间 ）算法所处理的数据量 ）算法程序中的语句或指令条数 ）算法在执行过程中所需要的临时工作单元数【2009.9】（15）某二叉树由5个度为2的结点以及3 个度为1的结点，则该二叉树中共有 【 】 个结点。,14,二级ACCESS查询,过关练习,【2009.3】(16)下面叙述中正确的是【 】 A）栈是“先进先出”的线性表 B）队列是“先进后出”的线性表 C）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 【2009.3】(17)支持子程序调用的数据结构是【 】 A）栈 B）树 C）队列 D）二叉树,二级ACCESS查询,过关练习,【2009.3】(18)某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【 C 】 A）10 B） 8 C）6 D）4 【2009.3】(19)下列排序方法中，最坏情况下比较次数最少的是【 D 】 A）冒泡排序 B）简单选择排序 C）直接插入排序 D）堆排序 【2009.3】（20）假如用一个长度为50的数组（数组元 素的下标从0到49）作为栈的存储空间，栈底指针 bottom指向栈底元素，栈顶指针top指向栈顶元素， 如果bottom=49,top=30（数组下标），则栈中具有【 】个元素。,19,谢谢大家,