二级公共基础

《二级公共基础》由会员分享，可在线阅读，更多相关《二级公共基础（115页珍藏版）》请在金锄头文库上搜索。

1、二级公共基础知识二级公共基础知识第一章第一章 数据结构基础数据结构基础内容提要内容提要 n算法算法: :算法的基本概念、算法复杂度算法的基本概念、算法复杂度n数据结构的基本概念：什么是数据结构、数据结构的基本概念：什么是数据结构、 数据结构的图数据结构的图形表示、形表示、 线性结构与非线性结构线性结构与非线性结构n线性表及其顺序存储结构：线性表的基本概念、线性表及其顺序存储结构：线性表的基本概念、 顺序存顺序存储结构、插入运算、删除运算储结构、插入运算、删除运算n栈和队列：栈及其基本运算、队列及其基本运算栈和队列：栈及其基本运算、队列及其基本运算n线性链表：基本概念、基本运算、循环链表及其基本

2、运算线性链表：基本概念、基本运算、循环链表及其基本运算n树与二叉树：树的基本概念、二叉树及其基本性质、树与二叉树：树的基本概念、二叉树及其基本性质、 二二叉树的存储结构、二叉树的遍历叉树的存储结构、二叉树的遍历n查找技术：查找技术： 顺序查找、二分法查找顺序查找、二分法查找n排序技术：交换类排序法、排序技术：交换类排序法、 插入类排序法、选择类排序插入类排序法、选择类排序法法21.1 1.1 算法算法1.1.1 1.1.1 算法的基本概念算法的基本概念n算法是解题方案的准确而完整的描述，它不等于程序，也算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。不等计算方法。n1 1算法的

3、基本特征算法的基本特征n可行性(effectiveness)n确定性(definiteness)n有穷性(finiteness)n拥有足够的情报n2 2算法的基本要素算法的基本要素n算法中对数据的运算和操作n算术运算:包括加、减、乘、除等）n逻辑运算:包括“与”、“或”、“非”等运算）n关系运算:包括“大于”、“小于”、“等于”、“不等于”等）n数据传输:包括赋值、输入、输出等操作n算法的控制结构41.1.1 1.1.1 算法的基本概念算法的基本概念n3 3算法设计的基本方法算法设计的基本方法n列举法n归纳法n递推n递归n减半递推技术n回溯法51.1.2 1.1.2 算法复杂度算法复杂度n算法

4、复杂度：时间复杂度、空间复杂度算法复杂度：时间复杂度、空间复杂度n1 1算法的时间复杂度算法的时间复杂度n执行算法所需要的计算工作量n与下列因素有关：n书写算法的程序设计语言n编译产生的机器语言，代码质量n机器执行指令的速度n问题的规模61.1.2 1.1.2 算法复杂度算法复杂度n问题的规模函数问题的规模函数算法的工作量=f(n)n算法中基本操作重复执行的频率算法中基本操作重复执行的频率T(nT(n) )，是问题规，是问题规模模n n的某个函数的某个函数f(nf(n) )，记作：，记作：T(n)=O(f(n)n记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应

5、增加。n常见算法复杂度：常见算法复杂度：nO(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶nO(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶71.1.2 1.1.2 算法复杂度算法复杂度nnnnn矩阵相乘算法：矩阵相乘算法：n时间复杂度为时间复杂度为O(nO(n3 3) )。81.1.2 1.1.2 算法复杂度算法复杂度n分析算法的工作量两种方法：分析算法的工作量两种方法：n平均性态n最坏情况复杂性91.1.2 1.1.2 算法复杂度算法复杂度n2算法的空间复杂度n算法执行过程中所需的最大存储空间n存储量包括以下三部分n算法程序所占的空间n输入的初始数据所占的存储空间n算

6、法执行过程中所要的额外空间n算法空间复杂度可定义为：S(n)=O(f(n)n原地工作(in place)的算法：记作O(1)n压缩存储技术101.2 1.2 数据结构的基本概念数据结构的基本概念1.2.1 1.2.1 什么是数据结构什么是数据结构n1 1数据结构研究的主要内容数据结构研究的主要内容n数据的逻辑结构n数据的存储结构n对各种数据结构进行的运算n2 2研究数据结构目的研究数据结构目的n提高数据处理的速度n尽量节省在数据处理过程中所占用的计算机存储空间121.2.1 1.2.1 什么是数据结构什么是数据结构n1 1数据结构研究的主要内容数据结构研究的主要内容n数据的逻辑结构n数据的存储

7、结构n对各种数据结构进行的运算n2 2研究数据结构目的研究数据结构目的n提高数据处理的速度n尽量节省在数据处理过程中所占用的计算机存储空间131.2.1 1.2.1 什么是数据结构什么是数据结构 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个方面 141.2.1 1.2.1 什么是数据结构什么是数据结构n3数据结构的定义n相互有关联的数据元素的集合n数据元素之间的关系可以用前后件关系来描述n一个数据结构应包含以下两方面信息：n表示数据元素的信息 n表示各数据元素

8、之间的前后件关系151.2.1 1.2.1 什么是数据结构什么是数据结构n4 4数据的逻辑结构数据的逻辑结构n对数据元素之间的逻辑关系的描述n只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关n两个要素：n数据元素的集合，通常记为D；n前后件关系，通常记为Rn一个数据结构B可以表示为：B=B=（D D，R R）161.2.1 1.2.1 什么是数据结构什么是数据结构n5 5数据的存储结构数据的存储结构n数据的逻辑结构在计算机存储空间中的存放形式n常用的存储结构：n顺序n链式n索引n一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同171.2.2 1.2.

9、2 数据结构的图形表示数据结构的图形表示n数据结点：用方框表示数据结点：用方框表示n根结点、终端结点n前后件关系：用有向线段表示前后件关系：用有向线段表示n基本运算：基本运算：n插入运算n删除运算n查找、分类、合并、分解、复制、修改、181.2.3 1.2.3 线性结构与非线性结构线性结构与非线性结构n空的数据结构：一个数据元素都没有空的数据结构：一个数据元素都没有n线性结构线性结构n如果一个非空数据结构满足下列两个条件：n有且只有一个根结点；n每一个结点最多有一个前件，也最多有一个后件。n常见的线性结构有：线性表、栈与队列、线性链表n非线性结构非线性结构n如果一个数据结构不是线性结构n常见的

10、非线性结构有：树、二叉树、图191.3 1.3 线性表及其顺序存储结构线性表及其顺序存储结构1.3.1 1.3.1 线性表的基本概念线性表的基本概念n线性表：由线性表：由n n(n0)(n0)个相同类型数据元素构成的有个相同类型数据元素构成的有限序列：限序列：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)211.3.1 1.3.1

11、线性表的基本概念线性表的基本概念n线性表的结构特征线性表的结构特征n数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；n对于一个非空线性表，有且只有一个根结点a1，它无前件，有且只有一个终端结点an，它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。n线性表的存储结构线性表的存储结构n顺序存储n链式存储221.3.2 1.3.2 线性表的顺序存储结构线性表的顺序存储结构n两个基本特点：两个基本特点：n线性表中所有元素所占的存储空间是连续的。n线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。n存储示意图存储示意图231.3.3 1.3.3 顺序

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

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

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

15、 线性链表线性链表1.5.1 1.5.1 线性链表的基本概念线性链表的基本概念n1 1线性表顺序存储的缺点线性表顺序存储的缺点n插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。n线性表的顺序存储结构下，线性表的存储空间不便于扩充。n线性表的顺序存储结构不便于对存储空间的动态分配。331.5.1 1.5.1 线性链表的基本概念线性链表的基本概念n2 2线性链表线性链表n线性表的链式存储结构n物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的n每个结点由两部分组成：数据域和指针域341.5.1 1.5.1 线性链表的

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

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

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

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

20、个或多个直接后件。n树的存储树的存储n用多重链表来表示441.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质n1 1二叉树的定义二叉树的定义n一个二叉树是n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。n特点：n非空二叉树只有一个根结点；n每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。451.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质n2 2二叉树的性质二叉树的性质n性质性质1 在二叉树的第k层上，最多有 个结点。n性质性质2 深度为m的二叉树最多有个

21、结点。n性质性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。即： 其中，n0表示度数为0的结点数，n2表示度数为2的结点数。n性质性质4 具有n个结点的二叉树的深度至少为 ，其中 表示取 的整数部分。461.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质n3满二叉树和完全二叉树n满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。n完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。471.6.2 1.6.2 二叉树及其基本性质二叉树及其基本性质n性质性质5 5 具有具有n n个结点的完全二叉树深度为个结点的

22、完全二叉树深度为 。n性质性质6 6 设完全二叉树共有设完全二叉树共有n n个结点，如果从根结点开始，个结点，如果从根结点开始，按层序（每一层从左到右）用自然数按层序（每一层从左到右）用自然数1 1，2 2，n n给结点给结点进行编号，则对于编号为进行编号，则对于编号为k k（k k=1=1，2 2，n n）的结点有以）的结点有以下结论：下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点的编号为INT(k/2)。若2kn，则编号为k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。若2k+1n，则编号为k的右子结点编号为2k+1；否则该结点无右子结点。4

23、81.6.3 1.6.3 二叉树的存储结构二叉树的存储结构n普通二叉树普通二叉树n采用链式存储结构n存储结点由两部分组成：数据域与指针域n两个指针域：n左指针域n右指针域n满二叉树与完全二叉树满二叉树与完全二叉树n采用顺序存储结构491.6.4 1.6.4 二叉树的遍历二叉树的遍历n二叉树的遍历：不重复地访问二叉树中的所有结点二叉树的遍历：不重复地访问二叉树中的所有结点 n1 1前序遍历（前序遍历（DLRDLR）n首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。n2 2中序遍历（中序遍历（LDRLDR）n首先遍历左子树，

24、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树n3 3后序遍历（后序遍历（LRDLRD）n首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。501.6.4 1.6.4 二叉树的遍历二叉树的遍历n前序遍历：前序遍历：nA、B、D、G、C、E、Fn中序遍历：中序遍历：nD、G、B、A、E、C、F n后序遍历：后序遍历：nG、D、B、E、F、C、A 511.7 1.7 查找技术查找技术1.7 1.7 查找技术查找技术n查找（查找（SearchingSearching）

25、：根据给定的某个值，）：根据给定的某个值，在查找表中确定一个其关键字等于给定值在查找表中确定一个其关键字等于给定值的数据元素。的数据元素。n查找结果：查找结果：n查找成功：找到n查找不成功：没找到n平均查找长度：查找过程中关键字和给定平均查找长度：查找过程中关键字和给定值比较的平均次数值比较的平均次数531.7.1 1.7.1 顺序查找顺序查找n基本思想：基本思想：n从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。n平均要与表中一半以上元素进行比较，最坏情况平均要与表中一半以上元素进行比较，最坏情况下

26、需要比较下需要比较n n次。次。n下列两种情况下只能采用顺序查找：下列两种情况下只能采用顺序查找：n如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。n即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。541.7.2 1.7.2 二分法查找二分法查找n思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。n前提：必须在具有顺序存储结构的有序表中进行。n查找过程：1）若中间项的值等于）若中间项的值等于x,则说明已查到。则说明已查到。2）若）若x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性

27、表的前半部分查找；3）若）若x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。n特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。551.7.2 1.7.2 二分法查找二分法查找n例：查找元素例：查找元素2222过程：过程： 561.8 1.8 排序技术排序技术1.8.1 1.8.1 交换类排序法交换类排序法n基本思想基本思想n两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。n方法方法n冒泡排序n快速排序581.1.冒泡排序冒泡排序 n基本思想基本思想n对存放原始数据的数组，按从后往前的方向进行多次扫描

28、，当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。n性能分析性能分析n假设线性表的长度n，则在最坏情况下，需要的比较次数为n(n-1)/2。591.1.冒泡排序冒泡排序 602 2快速排序快速排序n基本思想基本思想n任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。n快速排序的平均时间复杂度为快速排序的平均时间复杂

29、度为O(nlogO(nlog2 2n)n)。612 2快速排序快速排序621.8.2 1.8.2 插入类排序法插入类排序法n基本思想：基本思想：n每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。n方法方法: :n简单插入排序n希尔排序631 1简单插入排序法简单插入排序法n基本思想：基本思想：n把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。n在

30、最坏的情况下，需要在最坏的情况下，需要n(n-1)/2n(n-1)/2次比较。次比较。641 1简单插入排序法简单插入排序法652 2希尔排序希尔排序n基本思想基本思想n先将整个待排元素序列分割成若干个子序列（由相隔某个增量h的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。n增量序列一般取 ，其中n为待排序序列的长度n在最坏情况下，希尔排序的时间复杂度为在最坏情况下，希尔排序的时间复杂度为 662 2希尔排序希尔排序671.8.3 1.8.3 选择类排序法选择

31、类排序法n基本思想：基本思想：n每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕。n方法：方法：n简单选择排序n堆排序681 1简单选择排序法简单选择排序法 n基本思想：基本思想：n扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。n最坏情况下，需要比较最坏情况下，需要比较n(n-1)/2n(n-1)/2次。次。691 1简单选择排序法简单选择排序法 702 2堆排序法堆排序法n堆的定义堆的定义具有n个元素的序列，当且仅当满足 或 时称之为堆。称为大根堆；称为小根堆 。712 2堆排序法堆排

32、序法n建堆建堆n在建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。n堆排序堆排序n（1）首先将一个无序序列建成堆。n（2）然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。n反复做步骤（2），直到剩下的子序列空为止。n在最坏情况下，堆排序法需要比较的次数为在最坏情况下，堆排序法需要比较的次数为O(nlogO(nlog2 2n)n)。72各种排序法比较各种排序法比

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

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

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

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

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

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

39、出元素为个输出元素为_。A）n-i+1B）n-1C）iD）哪个元素无所谓n答案答案 A A90n【例例1-171-17】一个队列的入队序列是一个队列的入队序列是1 1、2 2、3 3、4 4，则队列的输出序列是，则队列的输出序列是 。A）4、3、2、1B）1、2、3、4C）1、4、3、2D）3、2、4、1n答案答案 A A91n【例例1-181-18】队列是限定只能在表的一端进队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。行插入和在另一端进行删除操作的线性表。允许插入的一端称作允许插入的一端称作_。n答案答案 队尾队尾92n【例例1-191-19】下列对于线性链表的描述中正下

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

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

42、231-23】一棵二叉树第六层（根结点为一棵二叉树第六层（根结点为第一层）的结点数最多为第一层）的结点数最多为 个。个。（20052005年年9 9月）月）n答案答案 323297n【例例1-241-24】深度为深度为5 5的二叉树至多有的二叉树至多有_个结点。个结点。A）16B）32C）31D）10n答案答案 C C98n【例例1-251-25】设树设树T T的度为的度为4 4，其中度为，其中度为1 1，2 2，3 3，4 4的结点个数分别为的结点个数分别为4 4，2 2，1 1，1 1。则。则T T中的叶子结点为中的叶子结点为_。A）8B）7C）6D）5n答案答案 A A99n【例例1-2

43、61-26】某二叉树中度为某二叉树中度为2 2的结点有的结点有1818个，个，则该二叉树中有则该二叉树中有 个叶子结点。个叶子结点。（20052005年年4 4月）月）n答案答案 1919100n【例例1-271-27】具有具有8888个结点的二叉树，其深个结点的二叉树，其深度至少为度至少为_。n答案答案 7 7101n【例例1-281-28】在深度为在深度为7 7的满二叉树中，叶子的满二叉树中，叶子结点的个数为（结点的个数为（20062006年年4 4月）月）A）32B）31C）64D）63n答案答案 C C102n【例例1-291-29】设一棵完全二叉树共有设一棵完全二叉树共有700700

44、个结点，则个结点，则在该二叉树中有在该二叉树中有_个叶子结点。个叶子结点。n答案答案 350350103n【例例1-301-30】对如图对如图1-301-30所示的二叉树，进所示的二叉树，进行后序遍历的结果为行后序遍历的结果为 。（。（20062006年年4 4月）月）A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCAn答案答案 D D104n【例例1-311-31】假设一棵二叉树的后序遍历序假设一棵二叉树的后序遍历序列为列为DGJHEBIFCADGJHEBIFCA，中序遍历序列为，中序遍历序列为DBGEHJACIFDBGEHJACIF，则其前序遍历序列为，则其前序遍历序列为 。

45、n答案：答案：ABDEGHJCFIABDEGHJCFI105n【例例1-321-32】对长度为对长度为n n的线性表进行顺序查的线性表进行顺序查找，在最坏情况下所需要的比较次数为找，在最坏情况下所需要的比较次数为_。（。（20052005年年4 4月）月）A）log2nB）n/2C）nD）n+ln答案答案 C C106n【例例1-331-33】下列数据结构中，能用二分法下列数据结构中，能用二分法进行查找的是进行查找的是 。（。（20052005年年9 9月）月）A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序线性链表n答案答案 A A107n【例例1-341-34】已知一个有序表为（已

46、知一个有序表为（1313，1818，2424，3535，4747，5050，6262，8383，9090，115115，134134），当使用二分法查找值为），当使用二分法查找值为9090的元素时，的元素时，查找成功的比较次数为查找成功的比较次数为 。A）1B）2C）3D）9n答案答案 B B108n【例例1-351-35】对长度为对长度为1010的线性表进行冒泡的线性表进行冒泡排序，最坏情况下需要比较的次数为排序，最坏情况下需要比较的次数为 。（。（20062006年年4 4月）月）n答案答案 4545109n【例例1-361-36】在排序算法中，两两比较待排在排序算法中，两两比较待排序的记

47、录，当发现不满意顺序要求时，变序的记录，当发现不满意顺序要求时，变更它们的相对位置，这就是更它们的相对位置，这就是 排序。排序。A）希尔排序B）交换排序C）插入排序D）选择排序n答案答案 B B110n【例例1-371-37】设待排序关键码序列为（设待排序关键码序列为（3333，1818，9 9，2525，6767，8282，5353，9595，1212，7070），要按关键码值），要按关键码值递增的顺序排序，采取以第一个关键码为基准元递增的顺序排序，采取以第一个关键码为基准元素的快速排序法，第一趟排序完成后关键码素的快速排序法，第一趟排序完成后关键码3333被被放到了第放到了第_位置。位置。

48、 A）3B）5C）7D）9n答案答案 B B111n【例例1-381-38】对于给定的一组关键字（对于给定的一组关键字（1212，2 2，1616，3030，8 8，2828，4 4，1010，2020，6 6，1818），按照希尔排序），按照希尔排序（增量为（增量为 5 5 ）算法进行递增排序，第一趟排序后）算法进行递增排序，第一趟排序后得到的结果是得到的结果是 。n答案答案 1212，2 2，1010，2020，6 6，2828，4 4，1616，3030，8 8，1818112n【例例1-391-39】对数据元素序列（对数据元素序列（4949，7272，6868，1313，3838，50

49、50，9797，2727）进行排序，前三趟排序结束时）进行排序，前三趟排序结束时的结果依次为：第一趟：的结果依次为：第一趟：1313，7272，6868，4949，5050，9797，2727；第二趟：；第二趟：1313，2727，6868，4949，3838，5050，9797，7272；第三趟：；第三趟：1313，2727，3838，4949，6868，5050，9797，7272。该排序采用的方法是。该排序采用的方法是_。A）简单插入排序法B）冒泡排序法C）简单选择排序法D）快速排序法n答案答案 C C113n【例例1-401-40】以下各组序列中，属于堆的是以下各组序列中，属于堆的是_。A）19，34，26，97，56，75B）97，26，34，75，19，56C）19，56，26，97，34，75D）19，75，34，26，97，56n答案答案 A A114n【例例1-411-41】对于长度为对于长度为n n的线性表，在最坏的线性表，在最坏情况下，下列各排序法所对应的比较次数情况下，下列各排序法所对应的比较次数中正确的是中正确的是_。（。（20052005年年4 4月）月）A）冒泡排序为n/2B）冒泡排序为nC）快速排序为nD）快速排序为n(n-1)/2n答案答案 D D115