第一部分数据结构与算法.ppt

《第一部分数据结构与算法.ppt》由会员分享，可在线阅读，更多相关《第一部分数据结构与算法.ppt（62页珍藏版）》请在三一办公上搜索。

1、公共基础知识考试方式1 笔试：90分钟，满分100分，其中含公共基础知识部分的30分。公共基础知识的考试方式为笔试，所有语言程序设计的笔试部分合为一张试卷，公共基础知识部分占全卷的30分。公共基础知识有l0道选择题和5道填空题。2 上机操作：90分钟上，满分100分。上机题目类型要求：（1）基本操作。（2）简单应用。（3）综合应用。,基本要求 新大纲的二级基础知识分为四部分数据结构与算法程序设计基础软件工程基础数据库设计基础,数据结构与算法 本章的知识用于提高程序的效率以及对较复杂的问题进行求解。本章内容在计算机专业基础课中也属于比较难的一门，学习本章的内容必须进行理解，死记硬背是无效的。本章

2、重点的考核点主要在二叉树，同时这也是本章的难点，考核形式主要为二叉树的遍历问题（如给图求遍历序列、给前序、中序遍历求后序遍历等）、二叉树的结点问题（如给出一些条件然后求叶子结点个数）；还有排序和查找考试中也经常会涉及到，排序主要以计算时间复杂度的形式考核，查找主要以计算最佳/最坏比较次数的方式考核。其余的知识点主要以概念的形式考察，考生需要仔细看书并理解。,程序设计基础与软件工程基础 这两章以概述的形式简介了规范化开发软件的方法。与数据结构不同，这两章内容主要是记忆性的知识点。程序设计基础的内容与大纲改革前添加了面向对象程序设计的内容，考生可以对本章进行几次细读后了解即可；软件工程基础这章主要

3、考核内容为结构化分析及结构化设计方法（即SA及SD，约占50%），信息量较大，其次是软件测试（约占20%），考生需要将相关的概念及规则背诵，在以后有机会进行程序开发时这些知识可以得到深刻理解。,数据库设计基础 数据库是当前软件处理的信息核心，目前大部分软件都是基于数据库的，因此学习一下数据库知识对程序开发也是很有帮助的。本章主要的考核点是关系模型、关系代数及数据库系统的基本概念，其余的知识点了解即可，其中数据库的设计和管理可以结合着软件工程来看，考生会发现这两者有很多相似之处。除了关系代数会考一些简单的计算问题外，其余的都是以概念题的形式考核，考生需要仔细的阅读。,05年4 月:10/2(选择

4、/填空)05年9月:6/606年4月:8/206年9月:6/407年4月:6/407年9月:8/408年4月:6/408年9月:6/409年3月:6/409年9月:6/410年3月:8/210年9月:8/2,数据结构与算法,近几年出题情况,考点1：算法考点2：数据结构考点3：线性表及其顺序存储结构考点4：栈和队列考点5：线性链表考点6：树与二叉树考点7：查找技术考点8：排序技术,数据结构与算法,1算法的基本概念 算法是指对解题方案的准确而完整的描述。2、算法的基本特征 可行性 确定性 有穷性（即算法必须能在执行有限个步骤之后终止）拥有足够的情报 算法是一组严谨地定义运算顺序的规则,并且每一个规

5、则都是有效的,而且是明确的,此顺序将在有限的次数下终止。,数据结构与算法考点1：算法,3、算法设计基本方法 一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成 列举法：解决“是否存在”或“有多少种可能”等类型问题 归纳法 递推 递归：分为直接递归和间接递归 减半递推技术 回溯法,数据结构与算法考点1：算法,4算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度两种。算法时间复杂度：指算法在执行过程中所需基本运算的执行次数，即指执行算法所需要的计算工作量。度量一个算法的工作量，与计算机、程序设计语言以及程序编制者无关、与算法实现过程中的许多细节无关，只 与问题的规模有关。)算法的空间复

6、杂度：指执行这个算法所需要的内存空间。,数据结构与算法考点1：算法,填空题 1、问题处理方案的正确而完整的描述称为_ 2、算法的复杂度主要包括_复杂度和空间复杂度选择题 1、下面叙述正确的是算法的执行效率与数据的存储结构无关算法的空间复杂度是指算法程序中指令（或语句）的条数算法的有穷性是指算法必须能在执行有限个步骤之后终止以上三种描述都不对。,数据结构与算法考点1：算法,1、研究内容：主要研究数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构；(2)在对数据进行处理时,各数据元素在计算机中的存储关系，即数据的存储结构;,数据

7、结构与算法考点2：数据结构,2、数据结构概念：数据结构是指相互有关联的数据元素的集合。理解（前件、后件）数据元素具有广泛的含义，一般来说,现实世界中客观存在的一切个体都可以是数据元素。例如,描述一年四季的季节名春、夏、秋、冬可以作为季节的数据元素;表示家庭成员的各成员名父亲、儿子、女儿可以作为家庭成员的数据元素。,数据结构与算法考点2：数据结构,具有相同特征的数据元素集合中,各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中通常把数据元素之间这种固有的关系简单地用前后件关系来描述。例如，在考虑一年4个季节的顺序关系时，“春”是“夏”的前件,而“夏

8、”是“春”的后件等。,数据结构与算法考点2：数据结构,3、数据的逻辑结构 数据的逻辑结构,是指反映数据元素之间逻辑关系的数据结构。,数据结构与算法考点2：数据结构,数据的逻辑结构有两个要素:一是数据元素的集合,通常记为 D;二是D上的关系,它反映了 D 中各数据元素之间的前后件关系,通常记为 R,即一个数据结构可以表示成：B=(D,R)其中 B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系,一般用二元组来表示。例如,一年四季的数据结构可以表示成:B=(D,R)D=春，夏，秋，冬 R=(春，夏),(夏，秋),(秋，冬),数据结构与算法考点2：数据结构,4 数据的存储结构 数据的逻辑结

9、构在计算机存储空间的存放形式称为数据的存储结构。（也称数据的物理结构）数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，一种数据的逻辑结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等存储结构。而采取不同的存储结构数据处理时效率不同，选择合适的存储结构是很重要的。,数据结构与算法考点2：数据结构,数据结构的图形表示 一个数据结构除了用二元关系表示外,还可以直观地用图形表示。在数据结构的图形表示中,对于数据集合 D 中的每一个数据元素用中间标有元素值的方框表示,称为结点。对于关系 R中的每一个二元组,用一条有向线段从前件结点指向后件结点。,数据结构与算法考点2：数据结构

10、,例如,一年四季的数据结构可以用如下图所示的图形来表示。反映家庭成员间辈分关系的数据结构可以用如下图所示的图形表示:在数据结构中,没有前件的结点称为根结点;没有后件的结点称为叶子结点.,数据结构与算法考点2：数据结构,5线性结构与非线性结构 数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足两个条件:有且只有一个根结点.每一个结点最多有一个前件,也最多有一个后件.则称该数据结构为线性结构。也称为线性表。注意：在一个线性结构中插入或删除任何一个结点后还应是线性结构。如数据结构不是线性结构,则称为非线性结构。,数据结构与算法考点2：数据结构,填空题：数据的逻辑结构在计算机存储空

11、间中的存放形式称为数据的_。选择题1、以下关于数据的逻辑结构的叙述中，哪一条是不正确的？数据的逻辑结构是数据间关系的描述数据的逻辑结构抽象地反映数据元素间的逻辑关系数据逻辑结构具体的反映数据在计算机中的存储方式数据的逻辑分为线性结构和非线性结构,数据结构与算法考点2：数据结构,2、数据的存储结构是指_.A、存储在外存中的数据B、数据所占的存储空间C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示,数据结构与算法考点2：数据结构,1线性表的基本概念：线性表是一种线性结构。非空线性表有如下一些结构特征:有且只有一个根结点a1,它无前件;有且只有一个终端结点an,它无后件;除根结点与

12、终端结点外，其他所有结点有且只有一个前件,也有且只有一个后件。,数据结构与算法考点3：线性表及其顺序存储结构,线性表由一组数据元素构成。例如,一维数组int a10=1,2,3,4,5,6,7,8,9,10是一个长度为10的线性表，其中的每一个元素就是一个数据元素。又如一年中的4个季节(春,夏,秋,冬)是一个长度为4的线性表，其中的每一个季节名就是一个数据元素。线性表是由 n(n=O)个数据元素a1,a2,an 组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。线性表中的元素ai(i=1,2,n)通常称其为线性表中的一个结点。,数据结构

13、与算法考点3：线性表及其顺序存储结构,2线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点:线性表中所有元素所占的存储空间是连续的;线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中,如果线性表中各数据元素所占的存储空间(字节数)相等,第1个数据元素的存储地址为 ADR(a1),每一个数据元素占k 个字节,则线性表中第 i 个元素ai存储地址为:ADR(ai)=ADR(a1)+(i-1)*k,数据结构与算法考点3：线性表及其顺序存储结构,1栈及其基本运算1）什么是栈 栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在

14、线性表的一端进行，即这种线性表的一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许进行插入与删除元素。例如，子弹夹就是一种栈的结构。,数据结构与算法考点4：栈和队列,栈是一种特殊的线性表，一端是封闭的，不允许进行插入和删除，另一端是开口的，允许插入与删除元素。按照“先进后出“或”后进先出“的原则结构数据，栈具有记忆功能。往栈中插入一个元素称为入栈运算，从栈中删除一个元素称为退栈运算。,数据结构与算法考点4：栈和队列,栈是限定在一端进行插入与删除的线性表，允许进行插入与删除的一端成为栈顶（top）,而不允许进行插入与删除的一端成为栈底（bottom）。栈顶的元素总是最后被插入的元素，也

15、是最先被删除的元素；栈底的元素总是最先被插入的元素，也是最后被删除的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆功能.2）栈运算 往栈中插入一个元素称为入栈运算，从栈中删除一个元素称为退栈运算。,数据结构与算法考点4：栈和队列,2队列及其基本运算 队列是指允许在一端进行插入,而在另一端进行删除的线性表。是“先进先出”或“后进后出”的原则。允许插入的一端称为队尾,允许删除的一端称为排头(也称为队头).在队列这种数据结构中,最先插入的元素将最先能够被删除,反之,最后插入的元素将最后才能被删除。因此,队列又称为先进先出 或后进后出的线性表,它体现了先来先服务的原则。往队列的

16、队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。,数据结构与算法考点4：栈和队列,3.循环队列及其运算 循环队列就是将队列存储空间的最后一个位置绕到第1个位置,形成逻辑上的环状空间，供队列循环使用。,数据结构与算法考点4：栈和队列,1线性链表的基本概念 线性表的链式存储结构称为线性链表。在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。,数据结构与算法考点5：线性链表,线性链表：为了适应线性表的链式存储结构,计算机存储空间被划分为一个一个的小块，每一小块占若干字节,通常称这些小块为存储结点。为了存储线性表中的每一个

17、元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域;另一部分用于存放下一个数据元素的存储序号(即存储结点的地址),即指向后件结点，称为指针域,数据结构与算法考点5：线性链表,在线性链表中，用一个专门的指针 HEAD 指向线性链表中第1 个数据元素的结点(即存放线性表中第 1 个数据元素的存储结点的序号)。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空(用 NULL 或 O 表示),表示链表终止。线性链表的逻辑结构如下图所示。,数据结构与算法考点5：线性链表,2

18、线性链表及其基本运算（1）线性链表的插入（2）线性链表的删除（3）线性链表的查找线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点p，并赋值。然后找到待插入位置的前一个结点的指针q。先将p指向q的后件，然后将p挂接在q结点后面。,数据结构与算法考点5：线性链表,线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到待删除元素的前一个结点p，用另一个指针q保存p的后续结点，然后把q结点的后续链挂接在p的后面。最后归还q结点所分配的栈空间。线性链表的查

19、找过程是从头指针指向的结点开始向后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为搜索值x为止。,数据结构与算法考点5：线性链表,1树的基本概念,数据结构与算法考点6：树与二叉树,树是一种简单的非线性结构，在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。没有后件的结点称为叶子结点。,2、树的一些常用术语。结点：结点由数据元素和构造数据元素之间关系的指针组成。例如，图中有22个结点。结点的度：结点所拥有的子树的个数称为该结点的度。例如，在上图中，结点R的度为4，结点K的度为2，结点M的度为0。树的度：树中所有结点中的最大度称为该树的度。例如，上图R

20、的度等于4是该树中所有结点的度的最大值，所以该树的度为4。,数据结构与算法考点6：树与二叉树,叶子结点：没有后件的结点称为叶子结点，叶子结点也称做终端结点。结点C、E、M、F、G等均为叶子结点。结点的层次：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，这样其他结点的层次就是它的前件的层次加1。树的深度：树中所有结点的层次的最大值称为该树的深度。上图中树的深度等于5。,数据结构与算法考点6：树与二叉树,子树：在树中，以某结点的一个子结点为根构成的树称为该点的一棵子树。如结点R有4棵子树。叶子结点没有子树。森林:m(m0)棵树的集合称为森林。自然界中树和森林的概念差

21、别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树由根结点和m个子树组成，若把树中的根结点删除，则树就变成了包含m棵树的森林。当然，根据定义，一棵树也可以称做森林。,数据结构与算法考点6：树与二叉树,3二叉树特点1）什么是二叉树 二叉树是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结构很相似，并且，树结构的所有术语都可以用到二叉树这种数据结构上。,数据结构与算法考点6：树与二叉树,二叉树两个特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。由以上特点可以看出，在二叉树中，每一个结点的度最大为 2,即所有子树(

22、左子树或右子树)也均为二叉树。而树结构中的每一个结点的度可以是任意的。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。,数据结构与算法考点6：树与二叉树,4、二叉树的基本性质二叉树具有以下几个性质。性质 1:在二叉树的第 k 层上，最多有 2k-1(k=1)个结点。性质 2:深度为 m 的二叉树最多有 2m-1 个结点。深度为 m 的二叉树是指二叉树共有 m 层。根据性质 1,只要将第 1 层到第 m 层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即:20+21+2m-l=2m-1,数据结构

23、与算法考点6：树与二叉树,性质 3:在任意一棵二叉树中，度为 O 的结点(即叶子结点)总是比度为 2 的结点多1个。性质 4：具有 n 个结点的二叉树，其深度至少为 log2n+1,其中 log2n 表示取log2n的整数部分。,数据结构与算法考点6：树与二叉树,5、满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。1)满二叉树所谓满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。这就是说,在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有 2k-1 个结 点，且深度为 m 的满二叉树有 2m-1 个结点。,数据结构与算法考点6：树与二叉树,2)完全二

24、叉树 所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为 m,且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 m 的满二叉树中编号从 1 到 n 的结点一一对应时，称之为完全二叉树。由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。,数据结构与算法考点6：树与二叉树,完全二叉树两个性质：性质 5：具有 n 个结点的完全二叉树的深度为 log2n+1。性质 6：设完全二叉树共有 n 个结点。如果从根结点开始，按

25、层序(每一层从左到右)用自然 1,2,n 给结点进行编号，则对于编号为 k（k=1,2,，n)的结点有以下 结论:若是k=1,则该结点为根结点，它没有父结点;若k1,则该结点的父结点编号为INT(k/2)若2k=n,则编号为 k 的结点的左子结点编号为 2k,否则该结点无左子结点 若 2k+1=n,则编号为k的结点的右子结点编号为 2k+1;否则该结点无右子结点。,数据结构与算法考点6：树与二叉树,4二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。由于二叉树是一种非线性结构，因此，对二叉树的遍历要比遍历线性表复杂得多。在遍历二叉树的过程中，当访问到某个结点时，再往下访问可能有两个

26、分支，那么先访问哪一个分支呢?对于二叉树来说，需要访问根结点、左子树上的所有结点、右子树上的所有结点，在这三者中，究竟先访问哪一个?也就是说，遍历二叉树的方法实际上是要确定访问各结点的顺序，以便不重不漏地访问到二叉树中的所有结点。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为 3 种:前序遍历、中序遍历、后序遍历。,数据结构与算法考点6：树与二叉树,（1）前序遍历(根左右)所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树;并且，在遍历左右子树时，仍然先访问根结点

27、，然后，遍历左子树，最后遍历右子树。（2）中序遍历(左根右)中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树;并且，在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树;（3）后序遍历(左右根)首先遍历左子树，然后遍历右子树，最后访问根结点。,数据结构与算法考点6：树与二叉树,查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。所谓查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。1顺序查找顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其

28、基本方法如下:从线性表的第 1 个元素开始，依次将线性表中的元素与被查元素进行比较，若相等，则表示找到(即查找成功);若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素(即查找失败)。,数据结构与算法考点7：查找技术,2二分查找二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)。设有序线性表的长度为 n,被查元素为 z,则二查找的方法如下。将 Z 与线性表的中间项进行比较:若中间项的值等于z，则说明查到，查找结束;若 Z 小于中间项的值，则在线性表的前半部分(即中间项以前的部分)以相同的方法进行

29、查找;若 Z 大于中间项的值，则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找。在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。,数据结构与算法考点7：查找技术,排序也是数据处理的重要内容。所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法冒泡排序：最坏情况下需要比较n(n-1)/2快速排序：在数据基本有序的情况下，不利于发挥其长处。最坏情况下需要比较n(n-1)/2简单插入排序法：最坏情况下需要比较n(n-1)/2希尔排序法：最坏情况下需要比较O（n1.5）简单选

30、择排序法：最坏情况下需要比较n(n-1)/2堆排序：可以用完全二叉权表示堆的结构，最坏情况下需要比较O（nlog2n）,数据结构与算法考点8：排序技术,练习题一、选择题1算法的时间复杂度是指A)执行算法程序所需要的时间 B)算法程序的长度C 算法执行所需要的基本运算次数 D)算法程序中的指令条数2算法的空间复杂度是指A)算法程序的长度 B)算法程序中的指令条数C)算法程序所占的存储空间 D)算法执行过程中所需要的存储空间3下列叙述中正确的是A)线性表是线性结构 B)栈和队列是非线性结构C)线性链表是非线性结构 D)二叉树是线性结构,CDA,4数据的存储结构是指A)数据所占的存储空间量 B)数据

31、在计算机中的存放形式C)数据在计算机中的顺序存储方式 D)存储在外存中的数据5长度为10的顺序表的首地址是从1023开始的,顺序表中每个元素的长度为2，在第 4个元素前面插入一个元素和删除第7个元素后,顺序表的总长度还是不变。问在执行插入和删除操作前,顺序表中第5个元素在执行插入和删除操作后的顺序表中的存储地址是A)1028 B)1029 C)1031 D)1033,BD,6下列关于线性表的两种存储结构叙述正确的是:A)存储相同数目的元素线性链表比顺序表要节省存储空间B)对无序表的查找,顺序表和线性链表的效率是一样的C)顺序表适用于插入、删除等更新操作频繁的场合D)线性链表适用于查询操作比较频

32、繁的场合7下列关于栈的叙述中不正确的是A)在栈中只能在同一端插入、删除数据 B)在栈中只能在一端插入数据，在另一端删除数据C)栈是先进后出的线性表 D)栈是后进先出的线性表,BB,8在线性链表的插入算法中,若要把结点q插在结点p后面,下列操作正确的是A)使结点p指向结点q,再使结点q指向结点p的后件结点B)使结点q指向p的后件结点,再使结点p指向结点qC)使结点q指向结点p,再使结点p指向结点q的后进结点D)使结点p指向q的后件结点,再使结点q指向结点p9下列叙述中错误的是:A)循环链表中,通过表中的任何一个结点可以访问到表中其他所有的结点 B)对线性链表插入和删除效率比顺序表的效率高C)线性

33、链表与顺序表相比,它容易实现动态增长D)在线性链表中查找一个元素要比在顺序表中查找一个元素快,BD,10.下面排序算法中,平均排序速度最快的是 A)冒泡排序法B)选择排序法 C)交换排序法 D)堆排序法O（n2）O（n2）O（n2）O(nlog2n)11.设栈和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，并且一个元素出栈后即进入队列Q，若出队的顺序为b,d,c,f,e,a，则栈S的容量至少应该为：A)3 B)4 C)5 D)613在下列数据结构中，不是线性结构的是：A)线性链表 B)带链的栈 C)循环链表 D)二叉树,DAD,14在下列数据结构中按先进后出原则组织数据的是A)

34、循环队列 B)栈 C)循环链表 D)顺序表15下列数据结构中具有记忆功能的是A)队列 B)循环队列 C)栈 D)顺序表,BC,16设有下列二叉树：对此二叉树前序遍历的结果是：,A)ZBTYCPXA B)ATBZXCYP C)ZBTACYXP D)ATBZXCPY,B,二、填空题1假如刚开始时栈为空,依次有A,B,C,D四个元素入栈,此时找底指针指向元素,栈顶指针值为(假设每个元素的长度为1)。执行四次出栈操作后把E,F,G压入栈,问此时栈底指针指向元素,此时栈的长度为。,1)A 2)4 3)E 4)3,2一个容量为8的循环队列,当它的队首和队尾指针相等时(front=rear)时队列中有()个有效数据。3.请写出用二分查找法在有序顺序表(1,2,3,4,6,8,9,11)中查找3的比较序列()。4 请写出用冒泡排序法对序列(5,1,7,3,1,6,9,3,2,7,6)从前往后进行第一遍扫描后的中间结果()。,1)08 2)4.2.3 3)1531672769,5.数据结构分为逻辑结构与存储结构，线性链表属于()。6在一个容量为25的循环队列中，若头指针front=16，尾指针rear=9，则该循环队列中共有()个元素。7在长度为n的线性表中查找一个表中不存在的元素，需要的比较次数为()。,1)存储 2)18 3)n,