《全国计算机二级公共基础知识要点ppt课件.ppt》由会员分享，可在线阅读，更多相关《全国计算机二级公共基础知识要点ppt课件.ppt（226页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、全国计算机等级考试全国计算机等级考试二级公共基础知识二级公共基础知识基本要求基本要求 n1. 掌握算法的基本概念。掌握算法的基本概念。n2. 掌握基本掌握基本数据结构数据结构及其操作。及其操作。n3. 掌握基本排序和查找算法。掌握基本排序和查找算法。n4. 掌握逐步求精的结构化掌握逐步求精的结构化程序设计程序设计方法。方法。n5. 掌握掌握软件工程软件工程的基本方法，具有初步应的基本方法，具有初步应用相关技术进行软件开发的能力。用相关技术进行软件开发的能力。n6. 掌握掌握数据库数据库的基本知识，了解关系数据的基本知识，了解关系数据库的设计。库的设计。 考试内容考试内容基本数据结构与算法基本数
2、据结构与算法程序设计基础程序设计基础软件工程基础软件工程基础数据库设计基础数据库设计基础内容内容2006/92007/42007/92008/42008/91010821284612846102810102810一、 基本数据结构与算法 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结
3、构及其插入与删除运线性表的定义；线性表的顺序存储结构及其插入与删除运算。算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5. 线性单链表、双向链表与循环链表的结构及其基本运算。线性单链表、双向链表与循环链表的结构及其基本运算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。选择类排序，插入类排序）。
4、 二、 程序设计基础1. 程序设计方法与风格。程序设计方法与风格。2. 结构化程序设计。结构化程序设计。3. 面向对象的程序设计方法，对象，方面向对象的程序设计方法，对象，方法，属性及继承与多态性。法，属性及继承与多态性。 三、 软件工程基础1. 软件工程基本概念，软件生命周期概念，软软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。件工具与软件开发环境。2. 结构化分析方法，数据流图，数据字典，软结构化分析方法，数据流图，数据字典，软件需求规格说明书。件需求规格说明书。3. 结构化设计方法，总体设计与详细设计。结构化设计方法，总体设计与详细设计。4. 软件测试的方法，白盒测试与黑盒
5、测试，测软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、试用例设计，软件测试的实施，单元测试、集成测试和系统测试。集成测试和系统测试。5. 程序的调试，静态调试与动态调试。程序的调试，静态调试与动态调试。四、数据库设计基础1. 数据库的基本概念：数据库，数据库管理系数据库的基本概念：数据库，数据库管理系统，数据库系统。统，数据库系统。2. 数据模型，实体联系模型及数据模型，实体联系模型及E-R图，从图，从E-R图导出关系数据模型。图导出关系数据模型。3. 关系代数运算，包括集合运算及选择、投影、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。连接
6、运算，数据库规范化理论。4. 数据库设计方法和步骤：需求分析、概念设数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。计、逻辑设计和物理设计的相关策略。考试方式1、 公共基础的考试方式为笔试，与公共基础的考试方式为笔试，与C语言语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C+）的笔试部分合为一）的笔试部分合为一张试卷。公共基础部分占全卷的张试卷。公共基础部分占全卷的30分。分。2、 公共基础知识有公共基础知识有10道选择题和道选择题和5道填空题。道填空题。 学习方法n理解基本概念理解基本概念n多做练习多做练习n适当记忆一
7、些名词适当记忆一些名词n与所学的与所学的VFPcAccess程序设计知识程序设计知识结合起来，以增加对知识的理解能力结合起来，以增加对知识的理解能力1. 基本数据结构与算法1.1 算法1.1.1 算法算法(algorithm)基本概念基本概念对特定问题求解步骤的一种描述，它是一组严谨地对特定问题求解步骤的一种描述，它是一组严谨地定义运算顺序的规则，并且每一个规则都是定义运算顺序的规则，并且每一个规则都是有效有效的，的，且是且是明确明确的，此顺序将在的，此顺序将在有限的次数有限的次数下终止。下终止。算法算法一级算法一级算法:S1:输入圆的半径输入圆的半径r;S2:求周长求周长2r;S3:求面积求
8、面积 r2;S4:输出输出周长和面积周长和面积;例题例题:已知圆的半径已知圆的半径,求周长和面积求周长和面积.程序程序do while .t. input “输入圆的半径：输入圆的半径：” to r if r0 ?“输入不能是负数，重新输入！输入不能是负数，重新输入！” loop else exit endifenddo S=pi()*r*rL=2*pi()*r?S,L算法的基本特征算法的基本特征:(1)可行性可行性(2)确定性确定性(3)有穷性有穷性(4)输入和输出输入和输出（拥有足够的情报）（拥有足够的情报）1.1.2 算法的基本要素算法的基本要素 1、对数据对象的运算和操作、对数据对象的
9、运算和操作n算术运算算术运算n逻辑运算逻辑运算n关系运算关系运算n数据传输数据传输2、算法的控制结构、算法的控制结构n算法中各操作之间的执行顺序算法中各操作之间的执行顺序n一个算法一般可以用一个算法一般可以用顺序、选择、循环顺序、选择、循环三种基本结三种基本结构组合而成。构组合而成。input “输入圆的半径：输入圆的半径：” to rif r0 ?“输入不能是负数，重新输入！输入不能是负数，重新输入！” 循环输入循环输入relse 退出循环退出循环endifS=pi()*r*rL=2*pi()*r输出输出S,L算术运算算术运算逻辑运算逻辑运算关系运算关系运算数据传输数据传输顺序、选择、顺序、
10、选择、循环三种基循环三种基本结构本结构1.1.3 算法设计基本方法算法设计基本方法n列举法列举法n归纳法归纳法n递推递推n递归（以简洁的形式设计和描述算法）递归（以简洁的形式设计和描述算法）n减半递推技术减半递推技术n回溯法回溯法1.2 算法复杂度算法复杂度1.2.1 时间复杂度时间复杂度n是指执行算法所需要的计算工作量。是指执行算法所需要的计算工作量。n通常有事后统计法和通常有事后统计法和事前分析估算法事前分析估算法。算法在执行过程中所需算法在执行过程中所需基本运算基本运算的执行次数来度量算法的执行次数来度量算法的工作量的工作量.算法所执行的基本运算次数与算法所执行的基本运算次数与问题的规模
11、问题的规模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=2 0i=3 1i=4 2i=n n-2 1+2+3+(n-2)= (n-1)(n-2)/2O（ ）2n例子例子2：+x;O（ 1 ）例子例子3： for (i=1 ;i=n;+i) +x;O（ n ）时间复杂度：时间复杂度：O(n*n-3n+2
12、)/2)基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：1X增增1基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：X增增1n1.2.2 算法的空间复杂度算法的空间复杂度n 一般是指执行这个算法所需要的内存空间一般是指执行这个算法所需要的内存空间n一个算法所占用的存储空间包括一个算法所占用的存储空间包括算法程序算法程序所占所占的空间、的空间、输入的初始数据输入的初始数据所占的存储空间以及所占的存储空间以及某种某种数据结构数据结构所需要的附加存储空间所需要的附加存储空间n 一个上机执行的程序除了需要存储空间来寄一个上机执行的程
13、序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。一些为实现计算所需信息的辅助空间。n 算法的时间复杂度是指算法的时间复杂度是指A) 执行算法程序所需要的时间执行算法程序所需要的时间 B) 算法程序的长度算法程序的长度C) 算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数算法程序中的指令条数n算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。
14、和拥有足够的情报。n算法的空间复杂度是指算法的空间复杂度是指 A) 算法程序的长度算法程序的长度 B) 算法程序中的指令条数算法程序中的指令条数 C) 算法程序所占的存储空间算法程序所占的存储空间 D) 执行过程中所需要的存储空间执行过程中所需要的存储空间n在计算机中，算法是指在计算机中，算法是指 A) 加工方法加工方法B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法排序方法D) 查询方法查询方法例题讲解例题讲解有穷性有穷性n算法分析的目的是算法分析的目的是 A) 找出数据结构的合理性找出数据结构的合理性 B) 找出算法中输入和输出之间的关系找出算法中输入和输出之间的
15、关系 C) 分析算法的易懂性和可靠性分析算法的易懂性和可靠性 D) 分析算法的效率以求改进分析算法的效率以求改进n算法的工作量大小和实现算法所需的存储单元多少分别称为算法算法的工作量大小和实现算法所需的存储单元多少分别称为算法的的 【1】 。时间复杂度和空间复杂度时间复杂度和空间复杂度1.2 数据结构n数据结构的定义n数据的逻辑结构和存储结构n数据结构的图形表示n线性结构与非线性结构1.2.1 数据结构研究的主要内容数据结构研究的主要内容(1)数据集中数据之间的逻辑关系数据集中数据之间的逻辑关系线性线性树树图图(2)数据的存储结构数据的存储结构(3)各种数据结构的运算各种数据结构的运算能输入到
16、计算机中能输入到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合。符号的集合。整数整数(1,2)(1,2)、实数、实数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、图形、声音。图形、声音。1.2.2 基本概念和术语 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。计算机管理图书问题计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中如何将查询图书
17、的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间既要考虑查询时间短，又要考虑节省空间 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。最简单的办法之一是建立一张表，最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如每一本书的信息在表中占一行，如 如何将如何将0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9这这1010个数存放在个数存放在计算机中能最快地达到你所需要的目的？计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同目的不同，最佳的存储方方法就不同。 从大到小排
18、列：从大到小排列：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 数据元素在数据元素在计算机中的表示计算机中的表示 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。对数据结构中的节点进行对数据结构中的节点进行操作处理操作处理(插入、删除、修改、查找、排序插入、删除、修改、查找、排序)（1 1）数据元素）数据元素(Data Element)(Data Element) 数据元素是数据的基本单位，即数据数据元素
19、是数据的基本单位，即数据集合中的个体。集合中的个体。 有时一个数据元数可由若干有时一个数据元数可由若干数据项数据项(Data Item)(Data Item)组成。数据项是数据的最小组成。数据项是数据的最小单位。单位。数据元素亦称数据元素亦称节点节点或或记录记录。 1数据的逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。 A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个
20、方面 数据结构可描述为数据结构可描述为 Group=（D，R）（2）逻辑结构）逻辑结构有限个数据元素的集合有限个数据元素的集合有限个数据元素有限个数据元素间关系的集合间关系的集合线性线性树树图图常用数据结构常用数据结构:A.线性结构线性结构 (A , B , C , ，X ,Y , Z)例例:学生成绩表学生成绩表8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成绩成绩姓名姓名学号学号线性表线性表栈栈后进先出后进先出队列队列先进先出先进先出例例: :英文字母表英文字母表数据结构数据结构S=(D,R)D
21、=春春,夏夏,秋秋,冬冬R=,什么型的数据结构什么型的数据结构?用图形工具用图形工具春春夏夏秋秋冬冬线性结构线性结构树形结构树形结构例例:全校学生档案管理的组织方式全校学生档案管理的组织方式例例:计算机文件管理系统也是典型的树形结构计算机文件管理系统也是典型的树形结构B非线性结构非线性结构1423 例例:数据结构数据结构B(D,R) D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3), (3,4) , (2,4) 213例例:数据结构数据结构C(D,R)D= 1 , 2 , 3 R= , , , 图形结构图形结构元素元素n n.元素元素i i.元素
22、元素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基地址基地址顺序存储结构，将逻辑上相邻的顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存数据元素存储在物理上相邻的
23、存储单元里储单元里,具有以下特点具有以下特点:1.随机存取。随机存取。2.作插入或删除操作时，需移动作插入或删除操作时，需移动大量元数。大量元数。3.长度变化较大时，需按最大空长度变化较大时，需按最大空间分配。间分配。4.表的容量难以扩充。表的容量难以扩充。 2、链式存储、链式存储 每个节点都由两部分组成：每个节点都由两部分组成： 数据域数据域和和指针域指针域。数据域数据域存放元素本身的数据，存放元素本身的数据，指针域指针域存放指针。存放指针。数据元素之间逻辑上的联系由数据元素之间逻辑上的联系由指针来体现。指针来体现。例：线性表例：线性表(zhao,qian,sun,li,zhou,wu,zh
24、eng,wang)链式存储结构：链式存储结构：存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针通常我们把链表画成用通常我们把链表画成用箭头箭头相链接的结点的序列，结点相链接的结点的序列，结点之间的箭头表示链域中的指针。之间的箭头表示链域中的指针。zhaoqiansunlizhouwuzhengwang /H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针1.比顺序存
25、储结构多用空间比顺序存储结构多用空间(存储密度小存储密度小) (每个节点都由数据域和指针每个节点都由数据域和指针域域组成组成)。2.逻辑上相邻的节点物理上不必相邻。逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活插入、删除灵活 (不必移动节点，只要改变节点中的指针不必移动节点，只要改变节点中的指针)。4.非随机存取。非随机存取。链接存储结构特点：链接存储结构特点： 1数据的逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。 A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B
26、 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面数据结构的三个方面 (亦称物理结构亦称物理结构)n链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比n数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。 n数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 A) 存储结构存储结构B) 物理结
27、构物理结构 C) 逻辑结构逻辑结构D) 物理和存储结构物理和存储结构 n数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【1】 两大类。两大类。n数据的存储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据 例题讲解例题讲解存储结构存储结构 非线性结构非线性结构n顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中。的存储单元中。 n数据处理
28、的最小单位是数据处理的最小单位是 A) 数据数据 B) 数据元素数据元素 C) 数据项数据项 D) 数据结构数据结构n数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及 A) 数据的存储结构数据的存储结构 B) 计算方法计算方法 C) 数据映象数据映象 D) 逻辑存储逻辑存储n线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结
29、构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 相邻相邻n根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构 n数据结构包括数据的逻辑结构、数据的数
30、据结构包括数据的逻辑结构、数据的 【2】 以及对数据以及对数据的操作运算。的操作运算。n数据的基本单位是数据的基本单位是 【5】 。n下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素1.3 线性表线性表1.3.1 线性表的概念线性表
31、的概念线性表的定义：线性表的定义： 线性表线性表是是n个元素的有限序列，它们之间的关系可以排成一个元素的有限序列，它们之间的关系可以排成一 个线性序列：个线性序列： (a1，a2， ，ai， ，an) 其中其中n称作表的称作表的长度长度，当，当n=0时，称作时，称作空表空表。线性表的特点：线性表的特点：1.线性表中所有元素的性质相同。线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继前驱和一个后继.第一个数据元素无前驱第一个数据元素无前驱,最后一个数据元素无后继。最后一个数据元素无后继。
32、3.数据元素在表中的位置只取决于它自身的序号。数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有：在线性表上常用的运算有：初始化、求长度、取元素、修改、初始化、求长度、取元素、修改、前插、删除、检索、排序。前插、删除、检索、排序。1.4 线性表的顺序存储结构及其插入与删除操作线性表的顺序存储结构及其插入与删除操作n特点：特点： 1.线性表中数据元素类型一线性表中数据元素类型一 致，只致，只有数据域，存储空间利用率高。有数据域，存储空间利用率高。 2.所有元素所占的存储空间是连续的所有元素所占的存储空间是连续的 3.各数据元素在存储空间中是按逻辑各数据元素在存储空间中是按逻辑顺序依
33、次存放的顺序依次存放的 4. 做插入、删除时需移动大量元素。做插入、删除时需移动大量元素。 5. 空间估计不明时，按最大空间分配。空间估计不明时，按最大空间分配。 顺序存储结构：顺序存储结构：存储地址存储地址数据数据7891011121314zhaoqiansunlizhouwuzhengwang7基地址基地址元素元素a an n.元素元素a ai i.元素元素a a2 2元素元素a a1 1bb+mb+(i-1)*m b+(maxlen-1)*m存储地址存储地址内存状态内存状态Loc(元素元素i)=b +（i-1)*m顺序存储结构示意图顺序存储结构示意图(顺序表顺序表)：首地址首地址起始地址
34、起始地址基地址基地址每个元素所占用每个元素所占用的存储单元个数的存储单元个数 1- 1插入运算插入运算ai-1.a2a1alengthai+1ai xai-1.a2a1alengthai+1ai X插入算法的分析插入算法的分析: 假设线性表中含有假设线性表中含有n个数据元素，在进行插入操作个数据元素，在进行插入操作时，若假定在时，若假定在n+1个位置上插入元素的可能性均等，则个位置上插入元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为：1n1iis2n1)i(n1n1E 1- 2删除运算删除运算ai-1.a2a1alengthai+1aiai-1.a2a1alengthai+1删
35、除算法的分析删除算法的分析: 在进行删除操作时，若假定删除每个元素的可能性均等，则在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为：总结总结: 顺序存储结构表示的线性表，在做插入或删除操作时，平均需顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。常要对其做插入或删除操作时，这一点需要值得考虑。n1idl21ni)(nn1En链表不具有的特点是链表不具有的特点是A) 不必事先估计存储
36、空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比n顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元中。的存储单元中。n长度为长度为n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平均个数为为 【1】 。n线性表若采用顺序存储结构时，要求内存中可用存储单元线性表若采用顺序存储
37、结构时，要求内存中可用存储单元的地址的地址 A) 必须是连续的必须是连续的 B) 部分地址必须是连续的部分地址必须是连续的 C) 一定是不连续的一定是不连续的 D) 连续不连续都可以连续不连续都可以例题讲解例题讲解相邻相邻2nn线性表线性表L=(a1,a2,a3,ai，an)，下列说法正确的是，下列说法正确的是 A) 每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D) 除第一个元素和最后一个元素外，其余每个元素都有一个除
38、第一个元素和最后一个元素外，其余每个元素都有一个 且只有一个直接前件和直接后件且只有一个直接前件和直接后件n线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 n下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存
39、储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 n根据数据结构中各数据元素之间前后件关系的复杂程根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成度，一般将数据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非
40、线性结构 D) 内部结构和外部结构内部结构和外部结构n当线性表采用顺序存储结构实现存储时，其主要特点当线性表采用顺序存储结构实现存储时，其主要特点是是 【1】 。随机存取随机存取1.5线性表的链式存储结构及其插入与删除操作线性表的链式存储结构及其插入与删除操作zhaoqiansunlizhouwuzhengwang /H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针单链表单链表baPbaP1-1单链表的插入运算单链表的插入运算xS在在P所指向的结点之后插入新的结点所指向的结点之
41、后插入新的结点1-2单链表单链表删除运算删除运算Laaian ai-1ai+1要求要求:删除结点删除结点ai。1-3. 循环链表循环链表: 首尾相接的链表。首尾相接的链表。 将最后一个结点的空指针改为指向头结点，从任一结点出发均可将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。找到其它结点。a1a2ana3L.带头结点的单链表带头结点的单链表a1a2ana3L.循环单链表循环单链表特点特点: 可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的所有结点.1-4 双向链表双向链表 在每个结点中设置两个指针，一个指向后继，一个在每个结点中设置两个指针，一个
42、指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。高效率。datanextbefore1.6线性表的应用：应用最广的数据结构。线性表的应用：应用最广的数据结构。.高级语言中的数组；高级语言中的数组；计算机的文件系统；计算机的文件系统；计算机的目录系统；计算机的目录系统；电话号码查询系统（可采用顺序表或单链表结构电话号码查询系统（可采用顺序表或单链表结构）；）；各种事务处理（各种事务处理（可采用顺序表或单链表结构可采用顺序表或单链表结构）;n链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间
43、B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比n用链表表示线性表的优点是用链表表示线性表的优点是A) 便于随机存取便于随机存取 B) 花费的存储空间较顺序存储少花费的存储空间较顺序存储少C) 便于插入和删除操作便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同数据元素的物理顺序与逻辑顺序相同n长度为长度为n的顺序存储线性表中的顺序存储线性表中,当在任何位置上插入一个元素概当在任何位置上插入一个元素概率都相等时率都相等时,插入一个元素所需移动元素的平均个数为插入一个元素所需移动元素的平
44、均个数为 【1】 。n在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是 A) 方便运算的实现方便运算的实现 B) 使单链表至少有一个结点使单链表至少有一个结点 C) 标识表结点中首结点的位置标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现说明单链表是线性表的链式存储实现例题讲解例题讲解2nn非空的循环单链表非空的循环单链表head的尾结点的尾结点(由由p所指向所指向) ，满足，满足 A) p-next=NULLB) p=NULL C) p-next=head D) p=head n循环链表的主要优点是循环链表的主要优点是 A) 不再需要头指针了不再需要头指针了 B)
45、 从表中任一结点出发都能访问到整个链表从表中任一结点出发都能访问到整个链表 C) 在进行插入、删除运算时，能更好的保证链表不断开在进行插入、删除运算时，能更好的保证链表不断开 D) 已知某个结点的位置后，能够容易的找到它的直接前件已知某个结点的位置后，能够容易的找到它的直接前件n当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为不能进行入队运算。这种情况称为 【2】 。n用链表表示线性表的突出优点是用链表表示线性表的突出优点是 【1】 。上溢上溢插入、删除灵活插入、删除灵活1.7 栈和队列栈和队列1
46、.7.1 栈和队列的定义栈和队列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为要受到某些限制的线性表，故也称为限定性的数据限定性的数据结构结构。1 .栈栈栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。栈顶栈顶表尾。表尾。栈底栈底表头。表头。空栈空栈不含元素的空表。不含元素的空表。a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,an)后进先出后进先出（LIFO）2. 栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a2 a1 a1 a2 top 用顺序存
47、储结构表示的栈用顺序存储结构表示的栈: 顺序栈用一组连续的存储单元存放自栈底到栈顶的数据顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量元素，一般用一维数组表示，设置一个简单变量top指示栈顶位指示栈顶位置，称为置，称为栈顶指针栈顶指针，它始终指向待插入元素的位置。它始终指向待插入元素的位置。基本运算：基本运算：压（进）栈：压（进）栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：空桟：topbase非空桟：非空桟：top始终在桟顶元素的后一个位
48、置始终在桟顶元素的后一个位置桟的元素个数：桟的元素个数： 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
49、,e3入队入队4.队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3 2 1 0 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终始终指向队尾元素的位置指向队尾元素的位置rear-front循环队列循环队列基本思想：基本思想：把队列设想为一个循环的表，臆想把队列设想为一个循环的表，臆想elem0接接在在elemmaxsize-1之后之后.frontrearMaxsize-101 e3 e4 rear
50、=3front0012345frontABCDEFrear上溢上溢0012345frontrear下溢下溢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一些重要的程序语言一些重要的程序语言