《二级公共基础知识(数据结构与算法).ppt》由会员分享，可在线阅读，更多相关《二级公共基础知识(数据结构与算法).ppt（109页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、全国计算机等级考试全国计算机等级考试二级公共基础知识二级公共基础知识考试形式1、公共基本知识部份只考选择题，没有操作题。2、公共基本知识占10分，共10道题，每题1分。注意事项注意事项公共基础知识部份的内容是属于计算机专业本科生的专业课，知识点特别散，而且有一定的难度。所以考生在学习的过程中，一定要克服畏难情绪，跟上老师的节奏。老师让记的，要记住。没做要求的，要学会放弃。放弃该放弃的，选择轻装上阵放弃该放弃的，选择轻装上阵一、数据结构与算法 1.算法的基本概念；算法复杂度的概念和意义（时间复杂度算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。与空间复杂度）。2.数据结构的定义
2、；数据的逻辑结构与存储结构；数据结构数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运线性表的定义；线性表的顺序存储结构及其插入与删除运算。算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中
3、序和后序遍历。序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，顺序查找与二分法查找算法；基本排序算法（交换类排序，插入类排序，选择类排序）。插入类排序，选择类排序）。1.1 算法1.1.1 算法算法(algorithm)基本概念基本概念它是指令的有限序列，其中每一条指令表示一个或多个操作。它是指令的有限序列，其中每一条指令表示一个或多个操作。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法算法计算机解题的过程实际上是在实施某种算法，这种算法称为计计算机解题的过程实际上
4、是在实施某种算法，这种算法称为计算机算法。算机算法。算法的基本特征算法的基本特征:(1)有穷性有穷性(2)确定性确定性(3)可行性可行性(4)拥有足够的情报拥有足够的情报（有零个或多个（有零个或多个输入，输入，有一个或多个有一个或多个输出输出）一个算法有零个或多个输入有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身定出了初始条件；一个算法有一个或多个输出有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；伪代码伪代码:S1:输入圆的半径输入圆的半径R;S2:求面积求面积 R2;S3:输出面积输出面积;例例1:已知圆的半径已知圆的半径,求圆的面积求圆的
5、面积.描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、N-S结构化流程结构化流程图、伪代码等。图、伪代码等。开始开始输入输入R RS=3.14 S=3.14*R*RR*R输出输出S S结束结束传统流程图传统流程图第8页n算法与计算机程序算法与计算机程序 算法算法是一组逻辑步骤是一组逻辑步骤 程序程序用计算机语言描述的算法用计算机语言描述的算法算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的
6、设计。设计。设计。设计。算法是程序设计的核心算法是程序设计的核心算法算法:S1:输入圆的半径输入圆的半径R;S2:求面积求面积R2;S3:输出面积输出面积;例题例题:已知圆的半径已知圆的半径,求圆的面积求圆的面积.程序程序#include#definePI3.14159intmain()floatr,s;doprintf(Pleaseinputr:);scanf(%f,&r);if(r0)printf(Error！n);while(r=0);s=PI*r*r;printf(Area=%fn,s);return0;1.1.2 算法的基本要素算法的基本要素 1、对数据对象的运算和操作、对数据对象的
7、运算和操作n算术运算算术运算n逻辑运算逻辑运算n关系运算关系运算n数据传输数据传输2、算法的控制结构、算法的控制结构n算法中各操作之间的执行顺序算法中各操作之间的执行顺序n一个算法一般可以用一个算法一般可以用顺序、选择、循环顺序、选择、循环3种基本结种基本结构组合而成。构组合而成。算术运算算术运算逻辑运算逻辑运算关系运算关系运算数据传输数据传输顺序、选择、顺序、选择、循环循环3种基种基本结构本结构#include#definePI3.14159intmain()floatR,S;doprintf(PleaseinputR:);scanf(%f,&R);if(R0)printf(Error！n)
8、;while(R=0);s=PI*R*R;printf(Area=%fn,S);return0;1.1.3 算法设计基本方法算法设计基本方法n列举法列举法n归纳法归纳法n递推递推n递归（以简洁的形式设计和描述算法）递归（以简洁的形式设计和描述算法）n减半递推技术减半递推技术n回溯法回溯法1.2 算法复杂度算法复杂度1.2.1 时间复杂度时间复杂度n是指执行算法所需要的计算工作量。是指执行算法所需要的计算工作量。n通常有事后统计法和通常有事后统计法和事前分析估算法事前分析估算法。算法的工作量用算法所执行的算法的工作量用算法所执行的基本运算基本运算次数来度量次数来度量.算法所执行的基本运算次数与算
9、法所执行的基本运算次数与问题的规模问题的规模n有关（即算有关（即算法所执行的基本次数是问题规模的函数）法所执行的基本次数是问题规模的函数）.执行算法所需要的计算工作量和执行算法所需要的计算工作量和f(n)同步增长，记为同步增长，记为:算法的工作量算法的工作量=f(n)时间复杂度时间复杂度=O(f(n)而对于一个固定的规模，算法所执行的基本次数还与特定的输入有关。例子例子4：for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：X增增1i=20i=31i=42i=nn-21+2+3+(n-2)=(n-1)(n-2)/2O
10、（）例子例子2：+x;O（1）例子例子3：for(i=1;i=n;+i)+x;O（n）时间复杂度：时间复杂度：O(n*n-3n+2)/2)基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：1X增增1基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：X增增1n1.2.2 算法的空间复杂度算法的空间复杂度n 一般是指执行这个算法所需要的内存空间一般是指执行这个算法所需要的内存空间n一个算法所占用的内存空间包括一个算法所占用的内存空间包括算法程序算法程序所占所占的空间、的空间、输入的初始数据输入的初始数据所占的存储空间以及所占的存储
11、空间以及算法在执行过程中所需要的额外空间这算法在执行过程中所需要的额外空间这3部分。部分。n 算法的时间复杂度是指算法的时间复杂度是指A)执行算法程序所需要的时间执行算法程序所需要的时间 B)算法程序的长度算法程序的长度C)算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数算法程序中的指令条数n算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、【1】和拥有足够的情报。和拥有足够的情报。n算法的空间复杂度是指算法的空间复杂度是指 A)算法程序的长度算法程序的长度 B)算法程序中的指令条数算法程序中的指令条数 C)算法程序所占的存储空间算法
12、程序所占的存储空间 D)执行过程中所需要的存储空间执行过程中所需要的存储空间n在计算机中，算法是指在计算机中，算法是指 A)加工方法加工方法B)解题方案的准确而完整的描述解题方案的准确而完整的描述 C)排序方法排序方法D)查询方法查询方法例题讲解例题讲解有穷性有穷性n算法分析的目的是算法分析的目的是 A)找出数据结构的合理性找出数据结构的合理性 B)找出算法中输入和输出之间的关系找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性分析算法的易懂性和可靠性 D)分析算法的效率以求改进分析算法的效率以求改进n算法的工作量大小和实现算法所需的存储单元多少分别称为算法算法的工作量大小和实现算法
13、所需的存储单元多少分别称为算法的的【1】。时间复杂度和空间复杂度时间复杂度和空间复杂度1.2 数据结构n数据结构的定义n数据的逻辑结构和存储结构n数据结构的图形表示n线性结构与非线性结构能输入到计算机中能输入到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合。符号的集合。整数整数(1,2)(1,2)、实数、实数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、图形、声音。图形、声音。1.2.2 基本概念和术语数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。计算机管理图书问题计算机管理
14、图书问题 在图书馆里有各种卡片：有按书名编排的、在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间既要考虑查询时间短，又要考虑节省空间数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。最简单的办法之一是建立一张表，最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如每一本书的信息在表中占一行，如 如何将如何将0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,
15、8,9这这1010个数存放在个数存放在计算机中能最快地达到你所需要的目的？计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同目的不同，最佳的存储方方法就不同。从大到小排列：从大到小排列：9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,0输出偶数：输出偶数：0,2,4,6,8,1,3,5,7,9 0,2,4,6,8,1,3,5,7,9 数据元素在数据元素在计算机中的表示计算机中的表示数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。对数据结构中的节点进行对数据结构中的节点进行操作处理操作处理(
16、插入、删除、修改、查找、排序插入、删除、修改、查找、排序)1数据的逻辑结构数据的逻辑结构2、数据的存储结构、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。A线性结构线性结构B非线性结构非线性结构A顺序存储顺序存储B链式存储链式存储线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面数据结构可描述为数据结构可描述为Group=（D，R）1.数据的逻辑结构数据的逻辑结构：是指反映数据元素之间逻辑关系是指反映数据元素之间逻辑关系的数据结构。它包括的数据结构。它包括数据元素的集合和数据元素之间数据元素的集
17、合和数据元素之间的前后关系两个因素。的前后关系两个因素。有限个数据元素的集合有限个数据元素的集合有限个数据元素有限个数据元素间关系的集合间关系的集合数据的逻辑结构数据的逻辑结构简称简称数据结构。数据结构。数据元素数据元素(Data Element)(Data Element)数据元素是数据的基本单位，即数据数据元素是数据的基本单位，即数据集合中的个体。集合中的个体。有时一个数据元素可由若干有时一个数据元素可由若干数据项数据项(Data Item)(Data Item)组成。数据项是数据的最小组成。数据项是数据的最小单位。单位。数据元素亦称数据元素亦称结点结点或或记录记录。线性线性树树图图常用数
18、据结构常用数据结构:A.线性结构线性结构(A,B,C,，X,Y,Z)例例:学生成绩表学生成绩表8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成绩成绩姓名姓名学号学号线性表线性表栈栈后进先出后进先出队列队列先进先出先进先出例例:英文字母表英文字母表数据结构数据结构S=(D,R)D=春春,夏夏,秋秋,冬冬R=,什么型的数据结构什么型的数据结构?用图形工具用图形工具线性结构线性结构数据元素：用中间标有元素值的方框表示，称为结点数据元素：用中间标有元素值的方框表示，称为结点逻辑关系：用有向线段从前件指向后
19、件（不引起误会逻辑关系：用有向线段从前件指向后件（不引起误会情况下，箭头可以省去）情况下，箭头可以省去）冬冬春春夏夏秋秋树形结构树形结构例例:家庭成员数据结构可表示成家庭成员数据结构可表示成例例:计算机文件管理系统也是典型的树形结构计算机文件管理系统也是典型的树形结构B非线性结构非线性结构父亲父亲儿子儿子女儿女儿没有前件的结点称为根结点；没有前件的结点称为根结点；没有后件的结点称为终端结点没有后件的结点称为终端结点（叶子结点）（叶子结点）1423例例:数据结构数据结构B(D,R)D=1,2,3,4R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)213例例:数据结构数据
20、结构C(D,R)D=1,2,3R=,图形结构图形结构元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(ai)=Lo+（i-1)*m1、顺序存储、顺序存储每个元素所占用每个元素所占用的存储单元个数的存储单元个数（3）存储结构）存储结构例：线性表例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang)顺序存储结构：顺序存储结构：存储地址存储地址数据数据7891011121314zhaoqiansunlizhouwuzhengwang7基地址基地址顺序存储结构，将逻辑上相
21、邻的顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存数据元素存储在物理上相邻的存储单元里储单元里,具有以下特点具有以下特点:1.随机存取。随机存取。2.作插入或删除操作时，需移动作插入或删除操作时，需移动大量元数。大量元数。3.长度变化较大时，需按最大空长度变化较大时，需按最大空间分配。间分配。4.表的容量难以扩充。表的容量难以扩充。2、链式存储、链式存储每个节点都由两部分组成：每个节点都由两部分组成：数据域数据域和和指针域指针域。数据域数据域存放元素本身的数据，存放元素本身的数据，指针域指针域存放指针。存放指针。数据元素之间逻辑上的联系由数据元素之间逻辑上的联系由指针来体现。指针来体
22、现。例：线性表例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang)链式存储结构：链式存储结构：存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针通常我们把链表画成用通常我们把链表画成用箭头箭头相链接的结点的序列，结点相链接的结点的序列，结点之间的箭头表示链域中的指针。之间的箭头表示链域中的指针。zhaoqiansunlizhouwuzhengwang/H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhen
23、gzhou指针指针43131null377192531头指针头指针1.比顺序存储结构多用空间比顺序存储结构多用空间(存储密度小存储密度小)(每个节点都由数据域和指针每个节点都由数据域和指针域域组成组成)。2.逻辑上相邻的节点物理上不必相邻。逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活插入、删除灵活(不必移动节点，只要改变节点中的指针不必移动节点，只要改变节点中的指针)。4.非随机存取。非随机存取。链接存储结构特点：链接存储结构特点：1数据的逻辑结构数据的逻辑结构2、数据的存储结构、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。
24、A线性结构线性结构B非线性结构非线性结构A顺序存储顺序存储B链式存储链式存储线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面(亦称物理结构亦称物理结构)n链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不必事先估计存储空间 B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度成正比所需空间与线性表长度成正比n数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1】。n数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是
25、数据的 A)存储结构存储结构B)物理结构物理结构 C)逻辑结构逻辑结构D)物理和存储结构物理和存储结构 n数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和【1】两大类。两大类。n数据的存储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据 例题讲解例题讲解存储结构存储结构 非线性结构非线性结构n顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。
26、的存储单元中。n数据处理的最小单位是数据处理的最小单位是 A)数据数据 B)数据元素数据元素 C)数据项数据项 D)数据结构数据结构n数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及 A)数据的存储结构数据的存储结构 B)计算方法计算方法 C)数据映象数据映象 D)逻辑存储逻辑存储n线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B)随机存取的存
27、储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 相邻相邻n根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成 A)动态结构和静态结构动态结构和静态结构 B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C)线性结构和非线性结构线性结构和非线性结构 D)内部结构和外部结构内部结构和外部结构 n数据结构包括数据的逻辑结构、数据的数据结构包
28、括数据的逻辑结构、数据的【2】以及对数据以及对数据的操作运算。的操作运算。n数据的基本单位是数据的基本单位是【5】。n下列叙述中，错误的是下列叙述中，错误的是 A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C)数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素1.3 线性表线性表1.3.1 线性表的概念线性表的概念线性表的定义：线性
29、表的定义：线性表线性表是是n个元素的有限序列，它们之间的关系可以排成一个元素的有限序列，它们之间的关系可以排成一 个线性序列：个线性序列：(a1，a2，ai，an)其中其中n称作表的称作表的长度长度，当，当n=0时，称作时，称作空表空表。线性表的特点：线性表的特点：1.线性表中所有元素的性质相同。线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继前驱和一个后继.第一个数据元素无前驱第一个数据元素无前驱,最后一个数据元素无后继。最后一个数据元素无后继。3.数据元素在表中的位置只取决于它自身
30、的序号。数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有：在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、查找、排序。初始化、求长度、取元素、修改、前插、删除、查找、排序。1.4 线性表的顺序存储结构及其插入与删除操作线性表的顺序存储结构及其插入与删除操作n特点：特点：1.线性表中数据元素类型一致，只有数线性表中数据元素类型一致，只有数据域，存储空间利用率高。据域，存储空间利用率高。2.所有元素所占的存储空间是连续的所有元素所占的存储空间是连续的 3.各数据元素在存储空间中是按逻辑顺各数据元素在存储空间中是按逻辑顺序依次存放的序依次存放的 4.做插入、删除时需
31、移动大量元素。做插入、删除时需移动大量元素。5.空间估计不明时，按最大空间分配。空间估计不明时，按最大空间分配。顺序存储结构：顺序存储结构：存储地址存储地址数据数据7891011121314zhaoqiansunlizhouwuzhengwang7基地址基地址元素元素a an n.元素元素a ai i.元素元素a a2 2元素元素a a1 1bb+mb+(i-1)*mb+(maxlen-1)*m存储地址存储地址内存状态内存状态Loc(元素元素i)=b+（i-1)*m顺序存储结构示意图顺序存储结构示意图(顺序表顺序表)：首地址首地址起始地址起始地址基地址基地址每个元素所占用每个元素所占用的存储单
32、元个数的存储单元个数1-1插入运算插入运算ai-1.a2a1alengthai+1aixai-1.a2a1alengthai+1ai X插入算法的分析插入算法的分析:假设线性表中含有假设线性表中含有n个数据元素，在进行插入操作个数据元素，在进行插入操作时，若假定在时，若假定在n+1个位置上插入元素的可能性均等，则个位置上插入元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为：1-2删除运算删除运算ai-1.a2a1alengthai+1aiai-1.a2a1alengthai+1删除算法的分析删除算法的分析:在进行删除操作时，若假定删除每个元素的可能性均等，则在进行删除操作时，若假
33、定删除每个元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为：总结总结:顺序存储结构表示的线性表，在做插入或删除操作时，平均需顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。常要对其做插入或删除操作时，这一点需要值得考虑。n链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不必事先估计存储空间 B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度
34、成正比所需空间与线性表长度成正比n顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。的存储单元中。n长度为长度为n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为素概率都相等时，插入一个元素所需移动元素的平均个数为【1】。n线性表若采用顺序存储结构时，要求内存中可用存储单元的线性表若采用顺序存储结构时，要求内存中可用存储单元的地址地址 A)必须是连续的必须是连续的 B)部分地址必须是连续的部分地址必须是连续的 C)一定是不连续的一定是不连续的
35、 D)连续不连续都可以连续不连续都可以例题讲解例题讲解相邻相邻n线性表线性表L=(a1,a2,a3,ai，an)，下列说法正确的是，下列说法正确的是 A)每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B)线性表中至少要有一个元素线性表中至少要有一个元素 C)表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D)除第一个元素和最后一个元素外，其余每个元素都有一个除第一个元素和最后一个元素外，其余每个元素都有一个 且只有一个直接前件和直接后件且只有一个直接前件和直接后件n线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储
36、结构和线性表的链式存储结构分别是 A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B)随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C)随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D)任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 n下列叙述中，错误的是下列叙述中，错误的是 A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C)数据的存储结构在计算机中所占的空间
37、不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 n根据数据结构中各数据元素之间前后件关系的复杂程根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成度，一般将数据结构分成 A)动态结构和静态结构动态结构和静态结构 B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C)线性结构和非线性结构线性结构和非线性结构 D)内部结构和外部结构内部结构和外部结构n当线性表采用顺序存储结构实现存储时，其主要特点当线性表采用顺序存储结构实现存储时，其主要特点是是【1】。随机存取随机存取1.5线性表的链式存储
38、结构及其插入与删除操作线性表的链式存储结构及其插入与删除操作zhaoqiansunlizhouwuzhengwang/H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针单链表单链表baPbaP1-1单链表的插入运算单链表的插入运算xS在在P所指向的结点之后插入新的结点所指向的结点之后插入新的结点1-2单链表单链表删除运算删除运算Laaian ai-1ai+1要求要求:删除结点删除结点ai。1-3.循环链表循环链表:首尾相接的链表。首尾相接的链表。将将最最后后一一个个结结点点的的空
39、空指指针针改改为为指指向向头头结结点点，从从任任一一结结点点出出发发均均可可找到其它结点。找到其它结点。a1a2ana3L.带头结点的单链表带头结点的单链表a1a2ana3L.循环单链表循环单链表特点特点:可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的所有结点.1-4双向链表双向链表在在每每个个结结点点中中设设置置两两个个指指针针，一一个个指指向向后后继继，一一个个指指向向前前驱驱。可可直直接接确确定定一一个个结结点点的的前前驱驱和和后后继继结点。可提高效率。结点。可提高效率。datanextbeforen链表不具有的特点是链表不具有的特点是A)不必事先估计存储空间不
40、必事先估计存储空间 B)可随机访问任一元素可随机访问任一元素C)插入删除不需要移动元素插入删除不需要移动元素D)所需空间与线性表长度成正比所需空间与线性表长度成正比n用链表表示线性表的优点是用链表表示线性表的优点是A)便于随机存取便于随机存取 B)花费的存储空间较顺序存储少花费的存储空间较顺序存储少C)便于插入和删除操作便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同数据元素的物理顺序与逻辑顺序相同n长度为长度为n的顺序存储线性表中的顺序存储线性表中,当在任何位置上插入一个元素概当在任何位置上插入一个元素概率都相等时率都相等时,插入一个元素所需移动元素的平均个数为插入一个元素所需移动元
41、素的平均个数为【1】。n在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是 A)方便运算的实现方便运算的实现 B)使单链表至少有一个结点使单链表至少有一个结点 C)标识表结点中首结点的位置标识表结点中首结点的位置 D)说明单链表是线性表的链式存储实现说明单链表是线性表的链式存储实现例题讲解例题讲解n非空的循环单链表非空的循环单链表head的尾结点的尾结点(由由p所指向所指向)，满足，满足 A)p-next=NULLB)p=NULL C)p-next=head D)p=head n循环链表的主要优点是循环链表的主要优点是 A)不再需要头指针了不再需要头指针了 B)从表中任一结点出发都能
42、访问到整个链表从表中任一结点出发都能访问到整个链表 C)在进行插入、删除运算时，能更好的保证链表不断开在进行插入、删除运算时，能更好的保证链表不断开 D)已知某个结点的位置后，能够容易的找到它的直接前件已知某个结点的位置后，能够容易的找到它的直接前件n当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为不能进行入队运算。这种情况称为【2】。n用链表表示线性表的突出优点是用链表表示线性表的突出优点是【1】。上溢上溢插入、删除灵活插入、删除灵活1.6 栈和队列栈和队列1.6.1 栈和队列的定义栈和队列的定
43、义 栈和队列栈和队列是两种特殊的线性表，它们是运算时是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为要受到某些限制的线性表，故也称为限定性的数据限定性的数据结构结构。1.栈栈栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。栈顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,an)后进先出后进先出（LIFO）2.栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a2 a1 a1 a2 top 用顺序存储结构表示的栈用顺序存储结构表示的栈:顺
44、序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量一般用一维数组表示，设置一个简单变量top指示栈顶位置，指示栈顶位置，称称为为栈顶指针栈顶指针，它始终指向待插入元素的位置。它始终指向待插入元素的位置。基本运算：基本运算：压（进）栈：压（进）栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：空桟：topbase非空桟：非空桟：top始终在桟顶元素的后一个位置始终在桟顶元素的后一个位置桟的元素个数：
45、桟的元素个数：top-base上溢上溢下溢下溢3.队列队列定义：一种特殊的线性结构，限定只能在表的一端进行插入，在定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表表的另一端进行删除的线性表。此种结构称为。此种结构称为先进先出（先进先出（FIFO）表表。a1,a2,a3,a4,an-1,an队队列列示示意意图图队队头头队队尾尾 e3 e4 (c)(c)e1,e2出队，出队，e4入队入队 队队满满rear=3front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队4.队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3210
46、 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终始终指向队尾元素的位置指向队尾元素的位置rear-front循环队列循环队列基本思想：基本思想：把队列设想为一个循环的表，臆想把队列设想为一个循环的表，臆想elem0接接在在elemmaxsize-1之后之后.frontrearMaxsize-101 e3 e4 rear=3front0012345frontABCDEFrear上溢上溢0012345frontrea
47、r下溢下溢front=rear队满队满front=rear队空队空n栈和队列的共同特点是栈和队列的共同特点是 A)都是先进先出都是先进先出 B)都是先进后出都是先进后出 C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D)没有共同点没有共同点n如果进栈序列为如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是，则可能的出栈序列是 A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2D)任意顺序任意顺序n一些重要的程序语言一些重要的程序语言(如如C语言和语言和Pascal语言语言)允许过允许过程的递归调用。而实现递归调用中的存储分配通常用程的递归调
48、用。而实现递归调用中的存储分配通常用 A)栈栈B)堆堆 C)数组数组 D)链表链表例题讲解例题讲解n栈底至栈顶依次存放元素栈底至栈顶依次存放元素A、B、C、D，在第五个元素，在第五个元素E入栈前，入栈前，栈中元素可以出栈，则出栈序列可能是栈中元素可以出栈，则出栈序列可能是 A)ABCED B)DCBEA C)DBCEA D)CDABE n栈通常采用的两种存储结构是栈通常采用的两种存储结构是 A)线性存储结构和链表存储结构线性存储结构和链表存储结构 B)散列方式和索引方式散列方式和索引方式 C)链表存储结构和数组链表存储结构和数组 D)线性存储结构和非线性存储结构线性存储结构和非线性存储结构n栈
49、和队列通常采用的存储结构是栈和队列通常采用的存储结构是【1】。n下列数据结构中，按先进后出原则组织数据的是下列数据结构中，按先进后出原则组织数据的是 A)线性链表线性链表 B)栈栈 C)循环链表循环链表 D)顺序表顺序表当循环队列非空且队尾指针等于队头指针时，说明循环队列已当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为满，不能进行入队运算。这种情况称为【2】。链表存储结构和数组链表存储结构和数组上溢上溢n由两个栈共享一个存储空间的好处是由两个栈共享一个存储空间的好处是A)减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B)节省存储空间
50、，降低上溢发生的机率节省存储空间，降低上溢发生的机率C)减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D)节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率自由区lefttoprighttop0MAXNUM-1两个栈共享邻接空间两个栈共享邻接空间n下列关于栈的叙述中正确的是下列关于栈的叙述中正确的是）在栈中只能插入数据）在栈中只能插入数据 B）在栈中只能删除数据）在栈中只能删除数据C）栈是先进先出的线性表）栈是先进先出的线性表 D）栈是后进先出的线性表）栈是后进先出的线性表n下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是）在队列中只能插入数据）在队列