二级ACCESS笔试之数据结构基础

1、二级公共基础知识二级公共基础知识 第一章第一章 数据结构基础数据结构基础 内容提要内容提要 n1.1.算法的基本概念算法的基本概念; ;算法复杂度的概念和意义算法复杂度的概念和意义( (时间复杂度时间复杂度 与空间复杂度与空间复杂度) )。 n2.2.数据结构的定义数据结构的定义; ;数据的逻辑结构与存储结构数据的逻辑结构与存储结构; ;数据结构数据结构 的图形表示的图形表示; ;线性结构与非线性结构的概念。线性结构与非线性结构的概念。 n3.3.线性表的定义线性表的定义; ;线性表的顺序存储结构及其插入与删除线性表的顺序存储结构及其插入与删除 运算。运算。 n4.4.栈和队列的定义栈和队列的

2、定义; ;栈和队列的顺序存储结构及其基本运栈和队列的顺序存储结构及其基本运 算。算。 n5.5.线性单链表、双向链表与循环链表的结构及其基本运算。线性单链表、双向链表与循环链表的结构及其基本运算。 n6.6.树的基本概念树的基本概念; ;二叉树的定义及其存储结构二叉树的定义及其存储结构; ;二叉树的前二叉树的前 序、中序和后序遍历。序、中序和后序遍历。 n7.7.顺序查找与二分法查找算法顺序查找与二分法查找算法; ;基本排序算法基本排序算法( (交换类排序，交换类排序， 选择类排序，插入类排序选择类排序，插入类排序) )。 1.1 1.1 算法算法 1.1.1 1.1.1 算法的基本概念算法的

3、基本概念 n算法是解题方案的准确而完整的描述，它不等于程序，也算法是解题方案的准确而完整的描述，它不等于程序，也 不等计算方法。不等计算方法。 n1 1算法的基本特征算法的基本特征 n可行性(effectiveness) n确定性(definiteness) n有穷性(finiteness) n拥有足够的情报 n2 2算法的基本要素算法的基本要素 n算法中对数据的运算和操作 n算术运算:包括加、减、乘、除等） n逻辑运算:包括“与”、“或”、“非”等运算） n关系运算:包括“大于”、“小于”、“等于”、“不等于”等） n数据传输:包括赋值、输入、输出等操作 n算法的控制结构 1.1.1 1.1

4、.1 算法的基本概念算法的基本概念 n3 3算法设计的基本方法算法设计的基本方法 n列举法:列举所有可能的情况 n归纳法：特殊-一般关系 n递推：从初始条件逐次推出中间结果和最后结果 n递归：逐层分解，大问题变小问题 n减半递推技术:重复减半 n回溯法 1.1.2 1.1.2 算法复杂度算法复杂度 n算法复杂度：时间复杂度、空间复杂度算法复杂度：时间复杂度、空间复杂度 n1 1算法的时间复杂度算法的时间复杂度 n执行算法所需要的计算工作量，即所执行的基 本运算次数。 n与下列因素无关： n书写算法的程序设计语言 n编译产生的机器语言，代码质量 n机器执行指令的速度 n与问题的规模有关 1.1.

5、2 1.1.2 算法复杂度算法复杂度 n问题的规模函数问题的规模函数 算法的工作量=f(n) n算法中基本操作重复执行的频率算法中基本操作重复执行的频率T(n)T(n)，是问题规，是问题规 模模n n的某个函数的某个函数f(n)f(n)，记作：，记作： T(n)=O(f(n) n记号“O”读作“大O”。表示随问题规模n的增加，算法 执行时间的增长率和f(n)相应增加。 n常见算法复杂度：常见算法复杂度： nO(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶 nO(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶 1.1.2 1.1.2 算法复杂度算法复杂度 nn nn n矩阵相

6、乘算法：矩阵相乘算法： n时间复杂度为时间复杂度为O(nO(n3 3) )。 1.1.2 1.1.2 算法复杂度算法复杂度 n分析算法的工作量两种方法：分析算法的工作量两种方法： n平均性态 n最坏情况复杂性 1.1.2 1.1.2 算法复杂度算法复杂度 n2算法的空间复杂度 n算法执行过程中所需的内存空间 n存储量包括以下三部分 n算法程序所占的空间 n输入的初始数据所占的存储空间 n算法执行过程中所要的额外空间 n算法空间复杂度可定义为： S(n)=O(f(n) n原地工作(in place)的算法：记作O(1) n压缩存储技术 1.2 1.2 数据结构的基本概念数据结构的基本概念 1.2

7、.1 1.2.1 什么是数据结构什么是数据结构 n1 1数据结构研究的主要内容数据结构研究的主要内容 n数据的逻辑结构：反映数据之间的逻辑关系的结构。 n数据的存储结构：逻辑结构在计算机的存储形式。 n对各种数据结构进行的运算 n2 2研究数据结构目的研究数据结构目的 n提高数据处理的速度 n尽量节省在数据处理过程中所占用的计算机存 储空间 1.2.1 1.2.1 什么是数据结构什么是数据结构 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面 1.

8、2.1 1.2.1 什么是数据结构什么是数据结构 n3数据结构的定义 n相互有关联的数据元素的集合 n数据元素之间的关系可以用前后件关系来描述 n一个数据结构应包含以下两方面信息： n表示数据元素的信息 n表示各数据元素之间的前后件关系（即逻辑关系） 1.2.1 1.2.1 什么是数据结构什么是数据结构 n4 4数据的逻辑结构数据的逻辑结构 n对数据元素之间的逻辑关系的描述 n只抽象地反映数据元素之间的逻辑关系，与计 算机中的存储无关 n两个要素： n数据元素的集合，通常记为D； n前后件关系，通常记为R n一个数据结构B可以表示为： B=B=（D D，R R） 1.2.1 1.2.1 什么是

9、数据结构什么是数据结构 n5 5数据的存储结构数据的存储结构 n数据的逻辑结构在计算机存储空间中的存放形 式 n常用的存储结构： n顺序 n链式 n索引 n一种数据结构可根据需要采用不同的存储结构。 采用不同的存储结构，其数据处理的效率是不 同 1.2.2 1.2.2 数据结构的图形表示数据结构的图形表示 n数据结点：用方框表示数据结点：用方框表示 n根结点（没有前件）、终端结点（没有后件）、内部 结点 n前后件关系：用有向线段表示前后件关系：用有向线段表示 n基本运算：基本运算： n插入、 删除运算 n查找、分类、合并、分解、复制、修改、 1.2.3 1.2.3 线性结构与非线性结构线性结构

10、与非线性结构 n空的数据结构：空的数据结构：一个数据元素都没有。线性结构和 非线性结构都可以是空的数据结构。 n线性结构线性结构 n如果一个非空数据结构满足下列两个条件： n有且只有一个根结点； n每一个结点最多有一个前件，也最多有一个后件。 n常见的线性结构有：线性表、栈与队列、线性链表 n非线性结构非线性结构 n如果一个数据结构不是线性结构 n常见的非线性结构有：树、二叉树、图 1.3 1.3 线性表及其顺序存储结构线性表及其顺序存储结构 1.3.1 1.3.1 线性表的基本概念线性表的基本概念 n线性表：由线性表：由n n(n0)(n0)个个相同类型数据元素相同类型数据元素构成的有构成的

11、有 限序列：限序列： nn n定义为线性表的表长；定义为线性表的表长；n n=0 =0 时的线性表被称为空时的线性表被称为空 表。称表。称i i为在线性表中的位序。为在线性表中的位序。 n例如：例如： n英文大写字母表 （A，B，C，D，E，F，X，Y，Z） n同一花色的13张扑克牌 n(2,3,4,5,6,7,8,9,10,J,Q,K,A) ),( 21ni aaaa 1.3.1 1.3.1 线性表的基本概念线性表的基本概念 n线性表的结构特征线性表的结构特征 n数据元素在表中的位置由序号决定，数据元素 之间的相对位置是线性的； n对于一个非空线性表，有且只有一个根结点a1， 它无前件，有且

12、只有一个终端结点an，它无后 件，除根结点与终端结点外，其他所有结点有 且只有一个前件，也有且只有一个后件。 n线性表的存储结构线性表的存储结构 n顺序存储 n链式存储 1.3.2 1.3.2 线性表的顺序存储结构线性表的顺序存储结构 n两个基本特点：两个基本特点： n线性表中所有元素所占的存储空间是连续的。 n线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 n存储示意图存储示意图 kiaLocaLoc i *) 1()()( 1 1.3.3 1.3.3 顺序表的插入运算顺序表的插入运算 1.3.4 1.3.4 顺序表的删除运算顺序表的删除运算 顺序表的插入和删除分析顺序表的插入和删除

13、分析 n插入算法的分析插入算法的分析 n假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位 置上插入元素的可能性均等，则平均移动元素的个数为： n删除算法的分析删除算法的分析 n在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元 素的个数为： n分析结论分析结论 n顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大 约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插 入或删除操作时，这一点需要值得考虑 n i idl n inp n E 1 2 1 )( 1 1 1 2 ) 1( 1 1 n i iis n inp n E 1.4 1.4 栈

14、和队列栈和队列 1.4.1 1.4.1 栈及其基本运算栈及其基本运算 n1 1栈的定义栈的定义 n栈（stack）：一种只允许在表的一端进行插入或删除 操作的特殊的线性表 n栈顶(top) ：允许进行插入与删除操作的一端 n栈底(bottom)：不允许插入与删除操作的另一端 n先进后出（FILO）或后进先出(LIFO)的线性表 1.4.1 1.4.1 栈及其基本运算栈及其基本运算 n2栈的顺序存储及其运算 ntop=0：栈空 top=m：栈满 n栈的基本运算 n入栈运算 n退栈运算 n读栈顶元素 1.4.2 1.4.2 队列及其基本运算队列及其基本运算 n1 1队列的定义队列的定义 n限定只能

15、在表的一端进行插入和在另一端进行删除操作的线性表 n队尾(rear)：允许插入的一端，指向插入的最后一个元素 n队头(front)：允许删除的另一端，指向队头元素的前一个位置 n先进先出（FIFO）表或后进后出（LILO）线性表 n基本操作 n入队运算：往队列的队尾插入一个元素，队尾指针rear的变化。“上 溢” n退队运算：从队列的排头删除一个元素，队头指针front的变化 1.4.2 1.4.2 队列及其基本运算队列及其基本运算 n2 2循环队列及其运算循环队列及其运算 n队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环 状空间，供队列循环使用 n入队运算 ：队尾指针加1，并当re

16、ar=m+1时置rear=1 n出队运算：队头指针加1，并当front=m+1时置front=1。“下溢” 1.5 1.5 线性链表线性链表 1.5.1 1.5.1 线性链表的基本概念线性链表的基本概念 n1 1线性表顺序存储的缺点线性表顺序存储的缺点 n插入或删除的运算效率很低。在顺序存储的线 性表中，插入或删除数据元素时需要移动大量 的数据元素。 n线性表的顺序存储结构下，线性表的存储空间 不便于扩充。 n线性表的顺序存储结构不便于对存储空间的动 态分配。 1.5.1 1.5.1 线性链表的基本概念线性链表的基本概念 n2 2线性链表线性链表 n线性表的链式存储结构 n物理存储单元上非连续

17、、非顺序的存储结构， 数据元素的逻辑顺序是通过链表中的指针链接 来实现的 n每个结点由两部分组成：数据域和指针域 n数据域：存储数据的值数据域：存储数据的值 n指针域：存放下一个元素的存储序号（即指针域：存放下一个元素的存储序号（即 存储点的地址）存储点的地址） n用专门的一个指针用专门的一个指针headhead指向线性表的一个指向线性表的一个 元素的结点，最后一个元素没有后件，指元素的结点，最后一个元素没有后件，指 针域为空（针域为空（NULLNULL），表示链表终止。），表示链表终止。 nHead=NULLHead=NULL时为空表。时为空表。 1.5.1 1.5.1 线性链表的基本概念线

18、性链表的基本概念 n双向链表：每个结点设置两个指针双向链表：每个结点设置两个指针 n左指针：指向其前件结点 n右指针：指向其后件结点 1.5.2 1.5.2 线性链表的基本运算线性链表的基本运算 n插入插入 n删除删除 n合并合并 n分解分解 n逆转逆转 n复制复制 n排序排序 n查找查找 1.5.2 1.5.2 线性链表的基本运算线性链表的基本运算 n1 1在线性链表中查找指定元素在线性链表中查找指定元素 n链表不是随机存取结构 n从链表的头指针出发，顺着链域next逐个结点 往下搜索，直至搜索到第i个结点为止 n2 2线性链表的插入线性链表的插入 1.5.2 1.5.2 线性链表的基本运算

19、线性链表的基本运算 n3 3线性链表的删除线性链表的删除 n与顺序存储相比，链表的优点有：与顺序存储相比，链表的优点有： n插入和删除元素时，不需要移动数据元素，只 需要修改指针即可 1.5.3 1.5.3 栈和队列的链式存储结构栈和队列的链式存储结构 n1栈的链式存储结构链栈 1.5.3 1.5.3 栈和队列的链式存储结构栈和队列的链式存储结构 n2队列链式存储结构链队列 1.5.4 1.5.4 循环链表及其基本运算循环链表及其基本运算 n循环链表特点：循环链表特点： n在链表中增加了一个表头结点 n最后一个结点的指针域指向表头结点，构成了一个环 状链 n循环链表优点：循环链表优点： n从任

20、一结点出发来访问表中其他所有结点 n空表与非空表的运算的统一 1.6 1.6 树与二叉树树与二叉树 n1树的定义 n树(Tree)是n(n0)个结点的有限集T，T为空时称为空 树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点； （2）其余的结点可分为m(m0)个互不相交的子集T1，T2， T3，Tm，其中每个子集又是一棵树，并称其为子树。 1.6 1.6 树与二叉树树与二叉树 n2 2树中的基本概念树中的基本概念 n父结点与树的根：每个结点最多只允许有一个前件， 称为该结点的父结点。没有前件的结点中有一个，称 为树的根结点。 n子结点与叶子结点：在树结构中，每一个

21、结点可以有 多个后件，它们都称为该结点的子结点。没有后件的 结点称为叶子结点。 n结点的度和树的度：一个结点所拥有直接后件个数称 为该结点的度。一棵树中各个结点度数的最大值叫做 这棵树的度。 n层和树的深度：树结构是一种层次结构，根结点为第 一层，根的子结点为第二层，其余各结点的层数逐层 由上而下计算。一棵树中结点的最大层数叫做此树的 深度。 1.6.1 1.6.1 树的基本概念树的基本概念 n树的特点树的特点 n（1）树中只有根结点没有前件； n（2）除根外，其余结点都有且仅一个前件； n（3）树的结点，可以有零个或多个后件； n（4）除根外的其他结点，都存在唯一条从根到该结点 的路径； n

22、（5）树是一种分支结构（除根的结点外）每个元素都 有且仅有一个直接前件，有且仅有零个或多个直接后 件。 n树的存储树的存储 n用多重链表来表示 1.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质 n1 1二叉树的定义二叉树的定义 n一个二叉树是n个结点的有限集合（n0），此集合或者是空集 （n=0），或者是由一个根结点及两棵互不相交的、分别称为左 子树和右子树的二叉树组成，并且左右子树都是二叉树。 n特点： n非空二叉树只有一个根结点； n每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 1.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质 n2 2二叉树的性质二

23、叉树的性质 n性质性质1 在二叉树的第k层上，最多有 个结点。 n性质性质2 深度为m的二叉树最多有个 结点。 n性质性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总 比度为2的结点多一个。即： 其中，n0表示度数为0的结点数，n2表示度数为2的结点数。 n性质性质4 具有n个结点的二叉树的深度至少为 ， 其中 表示取 的整数部分。 )1(2 1 k k 12 m 1 20 nn 1log2n log2nn 2 log 1.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质 n3满二叉树和完全二叉树 n满二叉树：除最后一层外，每一层上的所有结 点都有两个子结点。 n完全二叉树：

24、除最后一层外，每一层上的结点 数均达到最大值；在最后一层上只缺少右边的 若干结点。 1.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质 n性质性质5 5 具有具有n n个结点的完全二叉树深度为个结点的完全二叉树深度为 。 n性质性质6 6 设完全二叉树共有设完全二叉树共有n n个结点，如果从根结点开始，个结点，如果从根结点开始， 按层序（每一层从左到右）用自然数按层序（每一层从左到右）用自然数1 1，2 2，n n给结点给结点 进行编号，则对于进行编号，则对于编号为编号为k k（k k=1=1，2 2，n n）的结点有以）的结点有以 下结论：下结论： 若k=1，则该结点为根结点，它没

25、有父结点；若k1，则该结点的 父结点的编号为INT(k/2)。 若2kn，则编号为k的左子结点编号为2k；否则该结点无左子结 点（显然也没有右子结点）。 若2k+1n，则编号为k的右子结点编号为2k+1；否则该结点无右 子结点。 补充：度为1的结点个数要么为0个，要么为1个。 1log2n 1.6.3 1.6.3 二叉树的存储结构二叉树的存储结构 n普通二叉树普通二叉树 n采用链式存储结构 n存储结点由两部分组成：数据域与指针域 n两个指针域： n左指针域 n右指针域 n满二叉树与完全二叉树满二叉树与完全二叉树 n采用顺序存储结构 1.6.4 1.6.4 二叉树的遍历二叉树的遍历 n二叉树的遍

26、历：不重复地访问二叉树中的所有结点二叉树的遍历：不重复地访问二叉树中的所有结点 n1 1前序遍历（前序遍历（DLRDLR） n首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在 遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍 历右子树。 n2 2中序遍历（中序遍历（LDRLDR） n首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在 遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后 遍历右子树 n3 3后序遍历（后序遍历（LRDLRD） n首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在 遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后 访问根结点

27、。 1.6.4 1.6.4 二叉树的遍历二叉树的遍历 n前序遍历：前序遍历： nA、B、D、G、C、E、F n中序遍历：中序遍历： nD、G、B、A、E、C、F n后序遍历：后序遍历： nG、D、B、E、F、C、A 1.7 1.7 查找技术查找技术 1.7 1.7 查找技术查找技术 n查找（查找（SearchingSearching）：根据给定的某个值，）：根据给定的某个值， 在查找表中确定一个其关键字等于给定值在查找表中确定一个其关键字等于给定值 的数据元素。的数据元素。 n查找结果：查找结果： n查找成功：找到 n查找不成功：没找到 n平均查找长度：查找过程中关键字和给定平均查找长度：查找

28、过程中关键字和给定 值比较的平均次数值比较的平均次数 1.7.1 1.7.1 顺序查找顺序查找 n基本思想：基本思想： n从表中的第一个元素开始，将给定的值与表中逐个元 素的关键字进行比较，直到两者相符，查到所要找的 元素为止。否则就是表中没有要找的元素，查找不成 功。 n平均要与表中一半以上元素进行比较，最坏情况平均要与表中一半以上元素进行比较，最坏情况 下需要比较下需要比较n n次。次。 n下列两种情况下只能采用顺序查找：下列两种情况下只能采用顺序查找： n如果线性表是无序表（即表中的元素是无序的），则 不管是顺序存储结构还是链式存储结构，都只能用顺 序查找。 n即使是有序线性表，如果采用

29、链式存储结构，也只能 用顺序查找。 1.7.2 1.7.2 二分法查找二分法查找 n思想：先确定待查找记录所在的范围，然后逐步 缩小范围，直到找到或确认找不到该记录为止。 n前提：必须在具有顺序存储结构的有序表中进行。 n查找过程： 1）若中间项的值等于）若中间项的值等于x,则说明已查到。则说明已查到。 2）若）若x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找； 3）若）若x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。 n特点：比顺序查找方法效率高。最坏的情况下， 需要比较 log2n次。 1.7.2 1.7.2 二

30、分法查找二分法查找 n例：查找元素例：查找元素2222过程：过程： 1.8 1.8 排序技术排序技术 1.8.1 1.8.1 交换类排序法交换类排序法 n基本思想基本思想 n两两比较待排序记录的关键字，发现两个记录 的次序相反时即进行交换，直到没有反序的记 录为止。 n方法方法 n冒泡排序 n快速排序 1.1.冒泡排序冒泡排序 n基本思想基本思想 n对存放原始数据的数组，按从后往前的方向进 行多次扫描，当发现相邻两个数据的次序与排 序要求的“递增次序”不符合时，即将这两个 数据进行互换。这样，较小的数据就会逐单元 向前移动，好象气泡向上浮起一样。 n性能分析性能分析 n假设线性表的长度n，则在

31、最坏情况下，需要 的比较次数为n(n-1)/2。 2 2快速排序快速排序 n基本思想基本思想 n任取待排序序列中的某个元素作为基准（一般 取第一个元素），通过一趟排序，将待排元素 分为左右两个子序列，左子序列元素的排序码 均小于或等于基准元素的排序码，右子序列的 排序码则大于基准元素的排序码，然后分别对 两个子序列继续进行排序，直至整个序列有序。 n快速排序的平均时间复杂度为快速排序的平均时间复杂度为O(nlogO(nlog2 2n)n)。 2 2快速排序快速排序 1.8.2 1.8.2 插入类排序法插入类排序法 n基本思想：基本思想： n每次将一个待排序的记录，按其关键字大小插 入到前面已经

32、排好序的子序列中的适当位置， 直到全部记录插入完成为止。 n方法方法: : n简单插入排序 n希尔排序 1 1简单插入排序法简单插入排序法 n基本思想：基本思想： n把n个待排序的元素看成为一个有序表和一个 无序表，开始时有序表中只包含一个元素，无 序表中包含有n-1个元素，排序过程中每次从无 序表中取出第一个元素，把它的排序码依次与 有序表元素的排序码进行比较，将它插入到有 序表中的适当位置，使之成为新的有序表。 n在最坏的情况下，需要在最坏的情况下，需要n(n-1)/2n(n-1)/2次比较。次比较。 2 2希尔排序希尔排序 n基本思想基本思想 n先将整个待排元素序列分割成若干个子序列（由

33、相隔 某个增量h的元素组成的）分别进行直接插入排序，待 整个序列中的元素基本有序（增量足够小）时，再对 全体元素进行一次直接插入排序。因为直接插入排序 在元素基本有序的情况下（接近最好情况），效率是 很高的。 n增量序列一般取 ，其中n为待排序 序列的长度 n在最坏情况下，希尔排序的时间复杂度为在最坏情况下，希尔排序的时间复杂度为 )log, 2 , 1(2/ 2 nknh k i )( 5 . 1 nO 1.8.3 1.8.3 选择类排序法选择类排序法 n基本思想：基本思想： n每一趟从待排序的记录中选出关键字最小的记 录，顺序放在已排好序的子序列的最后，直到 全部记录排序完毕。 n方法：方

34、法： n简单选择排序 n堆排序 1 1简单选择排序法简单选择排序法 n基本思想：基本思想： n扫描整个线性表，从中选出最小的元素，将它 交换到表的最前面；然后对剩下的子表采用同 样的方法，直到子表空为止。 n最坏情况下，需要比较最坏情况下，需要比较n(n-1)/2n(n-1)/2次。次。 2 2堆排序法堆排序法 n堆的定义堆的定义 具有n个元素的序列，当且仅当满足 或 时称之为堆。称为大根堆；称为小根堆 。 12 2 ii ii hh hh 12 2 ii ii hh hh 2 2堆排序法堆排序法 n建堆建堆 n在建堆的过程中，总是将根结点值与左、右子树的根结点值进行 比较，若不满足堆的条件，

35、则将左、右子树根结点值中的大者与 根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。 n堆排序堆排序 n（1）首先将一个无序序列建成堆。 n（2）然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换 (最大项应该在序列的最后)。不考虑已经换到最后的那个元素， 只考虑前n-1个元素构成的子序列，将该子序列调整为堆。 n反复做步骤（2），直到剩下的子序列空为止。 n在最坏情况下，堆排序法需要比较的次数为在最坏情况下，堆排序法需要比较的次数为O(nlogO(nlog2 2n)n)。 各种排序法比较各种排序法比较 典型考题分析典型考题分析 n【例例1-11-1】问题处理方案的正确而完整的描问

36、题处理方案的正确而完整的描 述称为述称为 。（。（20052005年年4 4月）月） n答案答案 算法算法 n【例例1-21-2】算法复杂度主要包括时间复杂度算法复杂度主要包括时间复杂度 和和 复杂度。（复杂度。（20052005年年9 9月）月） n答案答案 空间空间 n【例例1-31-3】算法的时间复杂度是指算法的时间复杂度是指_。 A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 n答案答案C C n【例例1-41-4】算法的空间复杂度是指算法的空间复杂度是指_。 A）算法程序的长度 B）算法程序中的指令条数 C）算法程序

37、所占的存储空间 D）算法执行过程中所需要的存储空间 n答案答案D D n【例例1-51-5】下列叙述中正确的是下列叙述中正确的是 。 （20062006年年9 9月）月） A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间可复杂度必定小 D）上述三种说法都不对 n答案答案 D D n【例例1-61-6】下列叙述中正确的是下列叙述中正确的是 。 （20052005年年9 9月）月） A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属 于非线性结构 C）一个逻辑数据结构可以有多种

38、存储结构，且 各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且 各种存储结构影响数据处理的效率 n答案答案 D D n【例例1-71-7】数据结构分为逻辑结构和存储结数据结构分为逻辑结构和存储结 构，循环队列属于构，循环队列属于 结构。（结构。（20052005年年9 9 月）月） n答案答案 逻辑逻辑 n【例例1-81-8】数据结构分为线性结构和非线性数据结构分为线性结构和非线性 结构，带链的队列属于结构，带链的队列属于 。（。（20062006年年 9 9月）月） n答案答案 线性结构线性结构 n【例例1-91-9】下列叙述中正确的是下列叙述中正确的是_。 （2

39、0062006年年4 4月）月） A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 n答案答案 A A n【例例1-101-10】某线性表采用顺序存储结构，某线性表采用顺序存储结构， 每个元素占每个元素占4 4个存储单元，首地址为个存储单元，首地址为200200， 则第则第1212个元素的存储地址为个元素的存储地址为 。 A）248 B）247 C）246 D）244 n答案答案 D D n【例例1-111-11】在长度为在长度为n n的顺序表的第的顺序表的第i i （11i in n+1+1）个位置上插入一个元素，元）个

40、位置上插入一个元素，元 素的移动次数为素的移动次数为 。 A）n-i+1 B）n-i C）i D）i-1 n答案答案 A A n【例例1-121-12】在一个长度为在一个长度为n n的顺序表中，删的顺序表中，删 除第除第i i（11i in n）个元素时，需要移动的）个元素时，需要移动的 元素个数为元素个数为 。 A）n-i+1 B）n-i C）i D）i-1 n答案答案 B B n【例例1-131-13】以下描述的中，不是线性表的以下描述的中，不是线性表的 顺序存储结构的特征的是顺序存储结构的特征的是 。 A）不便于插入和删除 B）需要连续的存储空间 C）可随机访问 D）需另外开辟空间来保存

41、元素之间的关系 n答案答案 D D n【例例1-141-14】下列关于栈的描述中错误的是下列关于栈的描述中错误的是 _。（。（20052005年年4 4月）月） A）栈是先进后出的线性表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底 指针 n答案答案 B B n【例例1-151-15】栈和队列的共同点是栈和队列的共同点是_。 A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 n答案答案 C C n【例例1-161-16】栈的输入序列为栈的输入序列为1 1，2 2，3 3， n n-1-1，n n，输出序列的第，输出序列的

42、第1 1个元素为个元素为n n，则第，则第 个输出元素为个输出元素为_。 A）n-i+1 B）n-1 C）i D）哪个元素无所谓 n答案答案 A A n【例例1-171-17】一个队列的入队序列是一个队列的入队序列是1 1、2 2、 3 3、4 4，则队列的输出序列是，则队列的输出序列是 。 A）4、3、2、1 B）1、2、3、4 C）1、4、3、2 D）3、2、4、1 n答案答案 B B n【例例1-181-18】队列是限定只能在表的一端进队列是限定只能在表的一端进 行插入和在另一端进行删除操作的线性表。行插入和在另一端进行删除操作的线性表。 允许插入的一端称作允许插入的一端称作_。 n答案

43、答案 队尾队尾 n【例例1-191-19】下列对于线性链表的描述中正下列对于线性链表的描述中正 确的是确的是 。（。（20052005年年4 4月）月） A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且各前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 n答案答案 A A n【例例1-201-20】下列叙述中，错误的是下列叙述中，错误的是 。 A）线性表是由n个数据元素组成的一个有限序列 B）线性表是一种线性结构。 C）线性表的所有结点有且只有一个前件和一个 后件 D）

44、线性表可以是空表。 n答案答案 C C n【例例1-211-21】下列描述的不是链表的优点是下列描述的不是链表的优点是 _。 A）逻辑上相邻的结点物理上不必邻接 B）插入、删除运算操作方便，不必移动结点 C）所需存储空间比线性表节省 D）无需事先估计存储空间的大小 n答案答案 C C n【例例1-221-22】某线性表最常用的运算是插入某线性表最常用的运算是插入 和删除，插入运算是指在表尾插入一个新和删除，插入运算是指在表尾插入一个新 元素。删除运算是指删除表头第一个元素，元素。删除运算是指删除表头第一个元素， 那么采用那么采用 存储方式最节省运算时间。存储方式最节省运算时间。 A）仅有尾指针

45、的单向循环链表 B）仅有头指针的单向循环链表 C）单向链表 D）顺序存储 n答案答案 A A n【例例1-231-23】一棵二叉树第六层（根结点为一棵二叉树第六层（根结点为 第一层）的结点数最多为第一层）的结点数最多为 个。个。 （20052005年年9 9月）月） n答案答案 3232 n【例例1-241-24】深度为深度为5 5的二叉树至多有的二叉树至多有 _个结点。个结点。 A）16 B）32 C）31 D）10 n答案答案 C C n【例例1-251-25】设树设树T T的度为的度为4 4，其中度为，其中度为1 1，2 2， 3 3，4 4的结点个数分别为的结点个数分别为4 4，2 2

46、，1 1，1 1。则。则T T中中 的叶子结点为的叶子结点为_。 A）8 B）7 C）6 D）5 n答案答案 A A n【例例1-261-26】某二叉树中度为某二叉树中度为2 2的结点有的结点有1818个，个， 则该二叉树中有则该二叉树中有 个叶子结点。个叶子结点。 （20052005年年4 4月）月） n答案答案 1919 n【例例1-271-27】具有具有8888个结点的二叉树，其深个结点的二叉树，其深 度至少为度至少为_。 n答案答案 7 7 n【例例1-281-28】在深度为在深度为7 7的满二叉树中，叶子的满二叉树中，叶子 结点的个数为（结点的个数为（20062006年年4 4月）月

47、） A）32 B）31 C）64 D）63 n答案答案 C C n【例例1-291-29】设一棵完全二叉树共有设一棵完全二叉树共有700700个结点，个结点， 则在该二叉树中有则在该二叉树中有_个叶子结点。个叶子结点。 n答案答案 350350 n【例例1-301-30】对如图对如图1-301-30所示的二叉树，进所示的二叉树，进 行后序遍历的结果为行后序遍历的结果为 。（。（20062006年年4 4 月）月） A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA n答案答案 D D n【例例1-311-31】假设一棵二叉树的后序遍历序假设一棵二叉树的后序遍历序 列为列为DGJHEBIFCADGJHEBIFCA，中序遍历序列为，中序遍历序列为 DBGEHJACIFDBGEHJACIF，则其前序遍历序列为，则其前序遍历序列为 。 n答案：答案：ABDEGHJCFIABDEGHJCFI n【例例1-321-32】对长度为对长度为n n的线性表进行顺序查的线性表进行顺序查 找，在最坏情况下所需要的比较次数为找，在最坏情况下所需要的比较次数为 _。（。（20052005年年4 4月）月） A）log2n B）n/2 C）n D）n+l n答案答案 C C n【例例1-331-33】下列数据结构中，能用二分法下列数据结构中，能用