计算机2级公共基础知识ww

1、2021/3/10讲解：XX1 计算机等级考试计算机等级考试 公共基础知识公共基础知识 讲解：XX第2页 2021/3/10 计算机二级考试公共基础知识计算机二级考试公共基础知识大纲大纲 q 数据结构与算法数据结构与算法 q 程序设计基础程序设计基础 q 软件工程基础软件工程基础 q 数据库设计基础数据库设计基础 这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个 （10分），总分值占到了试卷卷面分的30，是一个不小的比例。 讲解：XX第3页 2021/3/10 计算机二级考试公共基础知识试卷分析计算机二级考试公共基础知识试卷分析 章节章节 考试时间考试时间 数据结构数据结构

2、与算法与算法 程序设计程序设计 基础基础 软件工程软件工程 基础基础 数据库设计数据库设计 基础基础 2007年4月10分2分10分8分 2007年9月12分4分8分6分 2008年4月10分2分8分10分 2008年9月10分2分8分10分 2009年3月10分2分8分10分 2009年9月10分2分8分10分 2010年3月10分0分10分10分 讲解：XX第4页 2021/3/10 算法的基算法的基 本概念本概念 2.2.算法复杂算法复杂 度的概念和度的概念和 意义意义 数据结构的概念数据结构的概念 线性表线性表 栈和队列栈和队列 树与二叉树树与二叉树 查找技术查找技术 排序技术排序技术

3、 对于等级考试，这个部分的考核对于等级考试，这个部分的考核重点主要重点主要在在算法和数据结构的基本概算法和数据结构的基本概 念念、二叉树二叉树(遍历、结点），遍历、结点），还有还有排序和查找排序和查找考试中也经常会涉及到。考试中也经常会涉及到。 讲解：XX第5页 2021/3/10 算法的定义算法的定义 算法是程序设计的核心算法是程序设计的核心 算法是在有限步骤内求解某一问题所使用的一组定义明确的算法是在有限步骤内求解某一问题所使用的一组定义明确的 规则。通俗点说，就是计算机规则。通俗点说，就是计算机解题的过程解题的过程( (计算的方法计算的方法) )。在。在 这个过程中，无论是形成解题思路这

4、个过程中，无论是形成解题思路( (推理实现的算法推理实现的算法) )还是编还是编 写程序写程序( (操作实现的算法操作实现的算法) )，都是在实施某种算法。，都是在实施某种算法。 例：例： n个数从大到小进行排序。个数从大到小进行排序。 有多种排序方法有多种排序方法 ，常用的有冒泡排序、选择排序等。，常用的有冒泡排序、选择排序等。 讲课讲课 说课说课 讲解：XX第6页 2021/3/10 2 . 算法的基本特征算法的基本特征 一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征： n 有穷性有穷性 n 确定性确定性 n 输入输入 n 输出输出 n 可行性可行性 一个算法必须保

5、证执行有限步之后结束； 算法的每一步骤必须有确切的定义； 一个算法有0个或多个输入，以刻画运算对象的初始 情况，所谓0个输入是指算法本身定出了初始条件； 一个算法有一个或多个输出，以反映对输入数据加 工后的结果。没有输出的算法是毫无意义的； 算法原则上能够精确地运行，而且人们用笔和 纸做有限次运算后即可完成 拥有足够的情报拥有足够的情报 讲解：XX第7页 2021/3/10 u 算法与计算机程序算法与计算机程序 算法算法_是一组逻辑步骤是一组逻辑步骤 程序程序用计算机语言描述的算法用计算机语言描述的算法 INPUT r S=3.14 * r*r PTINT S 开始开始 输入输入R R S=3

6、.14 * R*R 输出输出S S 结束结束 问题： 输入园的半径， 计算园的面积 一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。 传统的算法传统的算法-图形法，如图形法，如“流程图流程图”和和N-S图图 目前常用的方法目前常用的方法-使用伪码描述算法。使用伪码描述算法。 讲解：XX第8页 2021/3/10 冒泡排序的方法：冒泡排序的方法： 1.1.扫描整个线性表，逐次对相扫描整个线性表，逐次对相 邻的两个元素进行比较，若为邻的两个元素进行比较，若为 逆序，则交换；第一趟扫描的逆序，则交换；第一趟扫描的 结果使最大的元素排到表的最结果使最大的元素排到表的最 后后 ；

7、 2.2.除最后一个元素，对剩余的除最后一个元素，对剩余的 元素重复上述过程，将次大的元素重复上述过程，将次大的 数排到表的倒数第二个位置；数排到表的倒数第二个位置； 3.3.重复上述过程；重复上述过程； 对于长度为对于长度为n n的线性表，冒泡排的线性表，冒泡排 序需要对表扫描序需要对表扫描n-1n-1遍。遍。 算法举例：算法举例：n个数排序个数排序 讲解：XX第9页 2021/3/10 4. 算法的两个基本要素：算法的两个基本要素： n 算术运算算术运算 n 关系运算关系运算 n 逻辑运算逻辑运算 n 数据传输数据传输 n 顺序顺序 n 选择选择 n 循环循环 u一是对数据对象的运算和操作

8、； u二是算法的控制结构。 u算法基本设计方法：列举法、归纳法、递推、递 归、减斗递推技术、回溯法 讲解：XX第10页 2021/3/10 评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求： n 时间复杂度：执行这个算法所需要的时间复杂度：执行这个算法所需要的计算工作量计算工作量 一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量 n 空间复杂度：执行这个算法所需要的空间复杂度：执行这个算法所需要的内存空间内存空间 算法在执行过程中临时占用的存储空间算法在执行

9、过程中临时占用的存储空间 时间复杂度时间复杂度它大致等于计算机它大致等于计算机执行一种简单操作所需的平均时间执行一种简单操作所需的平均时间与算法与算法 中进行中进行简单操作的次数的乘积简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用存储算法本身所占用 的存储空间的存储空间、算法中的输入输出数据所占用的存储空间算法中的输入输出数据所占用的存储空间和和算法在运行过程中算法在运行过程中 临时占用的存储空间临时占用的存储空间这三个部分这三个部分 讲解：XX第11页 2021/3/10 (1) 在计算机中，算法是指在计

10、算机中，算法是指_。 A. 查询方法查询方法 B. 加工方法加工方法 C. 解题方案的准确而完整的描述解题方案的准确而完整的描述 D. 排序方法排序方法 (2)下列叙述中正确的是下列叙述中正确的是 （07年年4月月） A)算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关 (3)算法的有穷性

11、是指算法的有穷性是指 (08年年4月月) A）算法程序的运行时间是有限的）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的）算法程序的长度是有限的 D）算法只能被有限的用户使用）算法只能被有限的用户使用 (c) (B) 算法习题: (A) 讲解：XX第12页 2021/3/10 (4) 算法的时问复杂度是指算法的时问复杂度是指 (2010年年3月月) A)算法的执行时间算法的执行时间 B)算法所处理的数据量算法所处理的数据量 C)算法程序中的语句或指令条数算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次

12、数算法在执行过程中所需要的基本运算次数 (5) 算法的空间复杂度是指算法的空间复杂度是指 (09年年9月月) A）算法在执行过程中所需要的计算机存储空间）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量）算法所处理的数据量 C）算法程序中的语句或指令条数）算法程序中的语句或指令条数 D）算法在执行过程中所需要的临时工作单元数）算法在执行过程中所需要的临时工作单元数 (6) 下列叙述中正确的是下列叙述中正确的是 (06年年9月月) A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小）一

13、个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对）上述三种说法都不对 (D) 计算工作量 (A) (D) 讲解：XX第13页 2021/3/10 u 算法的时间复杂度是指算法的时间复杂度是指 A) 执行算法程序所需要的时间执行算法程序所需要的时间 B) 算法程序的长度算法程序的长度 C) 算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数算法程序中的指令条数 u 算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1】

14、和拥有足够的情报。和拥有足够的情报。 u 算法的空间复杂度是指算法的空间复杂度是指 A) 算法程序的长度算法程序的长度 B) 算法程序中的指令条数算法程序中的指令条数 C) 算法程序所占的存储空间算法程序所占的存储空间 D) 执行过程中所需要的存储空间执行过程中所需要的存储空间 u 在计算机中，算法是指在计算机中，算法是指 A) 加工方法加工方法B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法排序方法D) 查询方法查询方法 例题讲解例题讲解 有穷性有穷性 讲解：XX第14页 2021/3/10 u算法分析的目的是算法分析的目的是 A) 找出数据结构的合理性找出数据结构

15、的合理性 B) 找出算法中输入和输找出算法中输入和输 出之间的关系出之间的关系 C) 分析算法的易懂性和可靠性分析算法的易懂性和可靠性 D) 分析算法的效率分析算法的效率 以求改进以求改进 u算法的工作量大小和实现算法所需的存储单元多少算法的工作量大小和实现算法所需的存储单元多少 分别称为算法的分别称为算法的 【1】 。 时间复杂度和空间复杂度时间复杂度和空间复杂度 讲解：XX第15页 2021/3/10 计算机在进行数据处理时，实际需要处理的数据元素一般有计算机在进行数据处理时，实际需要处理的数据元素一般有 很多，而这些大量的数据元素都需要存放在计算机中，因此，大量很多，而这些大量的数据元素

16、都需要存放在计算机中，因此，大量 的的数据元素在计算机中如何组织，以便提高数据处理的效率，并且数据元素在计算机中如何组织，以便提高数据处理的效率，并且 节省计算机的存储空间，节省计算机的存储空间，这是进行数据处理的关键问题。这是进行数据处理的关键问题。 程序程序=算法算法+数据结构数据结构 数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。 一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系 的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。 一般情况下，在具有相同特征的数据元素集合中，各个数据一般情况下，在具有相同特征的数据元素集合中，各个数

17、据 元素之间存在有某种关系（即联系），这种关系反映了该集元素之间存在有某种关系（即联系），这种关系反映了该集 合中的数据元素所固有的一种结构。合中的数据元素所固有的一种结构。 超市的物品如何超市的物品如何 存放才好找且节存放才好找且节 省空间呢？省空间呢？ 讲解：XX第16页 2021/3/10 二二. 数据结构数据结构 数据结构是指相互有关联的数据元素的集合。数据结构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门学科，它数据结构是研究数据和数据之间关系的一门学科，它 包括三个方面。包括三个方面。 （1）数据集合中各数据元素之间所固有的逻辑关系，）数据集合中各数据元素

18、之间所固有的逻辑关系， 即数据的逻辑结构；即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中）在对数据进行处理时，各数据元素在计算机中 的存储关系，即数据的存储结构；的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。）对各种数据结构进行的运算。 讲解：XX第17页 2021/3/10 u 1. 逻辑结构逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结数据的逻辑结构是指反映数据元素之间逻辑关系的数据结 构。构。 数据的逻辑结构包含：数据的逻辑结构包含： （1）表示数据元素的信息；）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。）表示各数据元

19、素之间的前后件关系。 例：例： 1. 一年四季的数据结构一年四季的数据结构 B=(D,R) D=春，夏，秋，冬春，夏，秋，冬 R=(春，夏春，夏) ,(夏，秋夏，秋),(秋，冬秋，冬) 2. 家庭成员的数据结构家庭成员的数据结构 B=(D,R) D=父亲，儿子，女儿父亲，儿子，女儿 R=(父亲，儿子父亲，儿子) ,(父亲，女儿父亲，女儿) 春夏秋冬 数据结构的图形表示数据结构的图形表示 父亲 儿子女儿 讲解：XX第18页 2021/3/10 u常见的常见的逻辑结构逻辑结构有：有： 线性结构、树形结构和图形结构。线性结构、树形结构和图形结构。 线性结构线性结构 树形结构树形结构 图形结构图形结构

20、 u 线性结构线性结构 结构中的每个元素之间存在一个对一个的关系；结构中的每个元素之间存在一个对一个的关系； u 树形结构树形结构 结构中的每个元素之间存在一个对多个的关系；结构中的每个元素之间存在一个对多个的关系； u 图形结构或网状结构图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。结构中的每个元素之间存在多个对多个的关系。 其中，其中，树形结构和图形结构统称为非线形结构树形结构和图形结构统称为非线形结构。数据的逻辑结构可以。数据的逻辑结构可以 用二元关系表示，也可以直观地用图形来表示。用二元关系表示，也可以直观地用图形来表示。 讲解：XX第19页 2021/3/10 u 2

21、. 存储结构（物理结构存储结构（物理结构） 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计 算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与 它们的逻辑关系不一定是相同的，而且一般也不可能相同。它们的逻辑关系不一定是相同的，而且一般也不可能相同。 如：如：一年四季 家庭成员 计算机存储空间怎样存放？ 存储结构指数据结构在计算机存储空间中的具体实现。存储结构指数据结构在计算机存储空间中的具体实现。 常见的存储结构有：常见的存储结构有： n 顺序存储结构

22、顺序存储结构 n 链式存储结构链式存储结构 n 索引存储结构索引存储结构 只抽象地反映数据元素之间的关系的结构，只抽象地反映数据元素之间的关系的结构， 而不管其存储方式的数据结构称为逻辑结而不管其存储方式的数据结构称为逻辑结 构。构。 一种一种数据结构可以根据需要表示成一种或数据结构可以根据需要表示成一种或 多种存储结构多种存储结构。 讲解：XX第20页 2021/3/10 u 3. 数据的运算数据的运算 n 检索检索 n 插入插入 n 删除删除 n 更新更新 n 排序排序 通常，一个数据结构中的元素结点可能是动态变化的。根据需要通常，一个数据结构中的元素结点可能是动态变化的。根据需要 或在处

23、理过程中，可以在一个数据结构中增加一个新结点（插入运或在处理过程中，可以在一个数据结构中增加一个新结点（插入运 算），也可以删除某个结点（删除运算），除此之外，对数据结构算），也可以删除某个结点（删除运算），除此之外，对数据结构 的运算还有查找、分类、合并、分解、复制和修改。的运算还有查找、分类、合并、分解、复制和修改。 在对数据结构的处理过程中，不仅数据结构中结点的个数在动态在对数据结构的处理过程中，不仅数据结构中结点的个数在动态 变化，而且，各数据元素之间的关系也有可能在动态地变化。变化，而且，各数据元素之间的关系也有可能在动态地变化。如： 无序表变有序表 数据结构是研究数据和数据之数据结

24、构是研究数据和数据之 间关系的一门学科，研究以下三间关系的一门学科，研究以下三 方面内容：方面内容： n 数据的逻辑结构数据的逻辑结构 n 数据的存储结构数据的存储结构 n 数据的运算数据的运算 父亲 儿子女儿 2021/3/10年11月21 日讲解：XX 第第21 21|92|92页页 常见的数据结构常见的数据结构 u 数据结构分类数据结构分类 线性结构与非线性结构线性结构与非线性结构两大类型 线性结构：一个非空的数据结构若满足下面的两个条件，则这种数据一个非空的数据结构若满足下面的两个条件，则这种数据 结构即为结构即为。 有且仅有一个根结点；有且仅有一个根结点； 除第一个结点外，每一个结点

25、最多有一个前件；除第一个结点外，每一个结点最多有一个前件； 除最后一个结点外，每一个结点最多有一个后件。除最后一个结点外，每一个结点最多有一个后件。 常见的线性结构有：常见的线性结构有： 2021/3/10年11月21 日讲解：XX 第第2222|92|92页页 a1a2a5a3a4HEAD 319510 线性链表的逻辑状态线性链表的逻辑状态 常见的非线性结构有树、常见的非线性结构有树、 非线性结构一个数据结构不是线性结构。一个数据结构不是线性结构。 讲解：XX第23页 2021/3/10 线性表是由线性表是由n（n0）个数据元素）个数据元素 a1，a2，ai，an组成的一个有限序列。组成的一

26、个有限序列。 春春 夏夏 秋秋 冬冬 记录记录1 02011001 张三张三 男男 记录记录2 02011003 李四李四 女女 记录记录3 记录记录4 讲解：XX第24页 2021/3/10 特点：特点： 顺序存储结构把顺序存储结构把逻辑上相逻辑上相 邻邻的数据元素存储在的数据元素存储在物理上相邻物理上相邻 的存储单元里，顺序存储结构的存储单元里，顺序存储结构只只 存储结点的值存储结点的值，不存储结点间的，不存储结点间的 关系，结点间的关系由存储单元关系，结点间的关系由存储单元 的邻接关系来体现。的邻接关系来体现。 a1 a2 ai an 存储地址存储地址 2000 2004 2000+4*

27、(i-1) 2000+4*(n-1) 占占4个字节个字节 第i个数的地址第一个数的地址L为该类型数所占的字节 线性表的存储结构有两种：线性表的存储结构有两种： u 顺序存储结构顺序存储结构 u 链式存储结构链式存储结构 讲解：XX第25页 2021/3/10 u 顺序表的插入运算顺序表的插入运算 u 顺序表的删除运算顺序表的删除运算 在线性表顺序存储情况下，要插入或删除一个元在线性表顺序存储情况下，要插入或删除一个元 素，都会由于数据元素的移动而消耗大量的处理时间，素，都会由于数据元素的移动而消耗大量的处理时间， 所以这种存储方式对于小线性表或其中数据元素不经所以这种存储方式对于小线性表或其中

28、数据元素不经 常变动的线性表是合适的。常变动的线性表是合适的。 线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。 讲解：XX第26页 2021/3/10 插入运算插入运算 ai-1.a2a1 alength ai+1ai x ai-1.a2a1 alength ai+1ai X 插入算法的分析插入算法的分析: : 假设线性表中含有假设线性表中含有n n个数据元素，在进行插入操作时，若假个数据元素，在进行插入操作时，若假 定在定在n+1n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：个位置上插入元素的可能性均等，则平均移动元素的个数为： 1n 1i is 2 n 1)

29、i(n 1n 1 E 讲解：XX第27页 2021/3/10 删除运算删除运算 ai-1.a2a1 alength ai+1ai ai-1.a2a1 alength ai+1 删除算法的分析删除算法的分析: : 在进行删除操作时，若假定删除每个元素的可能性均等，则在进行删除操作时，若假定删除每个元素的可能性均等，则 平均移动元素的个数为：平均移动元素的个数为： 总结总结: : 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移 动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做动大约一半的数据元素。当线性表的数据元

30、素量较大，并且经常要对其做 插入或删除操作时，这一点需要值得考虑。插入或删除操作时，这一点需要值得考虑。 n 1i dl 2 1n i)(n n 1 E 讲解：XX第28页 2021/3/10 u 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。 u 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻， 而且各数据元素的存储顺序也是任意的。各数据元素的先后而且各数据元素的存储顺序也是任意的。各数据元素的先后 关系是由各结点的指针域指示。关系是由各结点的指针域指示。 u 链式存储结构的每一个存储结点不仅存储结点的值，而且

31、存链式存储结构的每一个存储结点不仅存储结点的值，而且存 储结点之间的关系：储结点之间的关系： u 链式存储结构分为单链表、双向链表、循环链表链式存储结构分为单链表、双向链表、循环链表 u 线性链表不能随机存取线性链表不能随机存取 数据域数据域指针域指针域 讲解：XX第29页 2021/3/10 设线性表为设线性表为（a1，a2，a3，a4，a5） 1a29 2 3a11 4 5a410 6 7 8 9a35 10a50 HEAD 3 a1a2a5a3a4HEAD 319510 线性链表的逻辑状态线性链表的逻辑状态 线性链表线性链表的物理状态的物理状态 1 a1 2 a2 3 a3 4 a4 5

32、 a5 6 7 注意:1 2 3 此类编号不 代表所在的 地址单元的 地址编码 线性表的链式存储结构线性表的链式存储结构 及其插入与删除操作及其插入与删除操作 讲解：XX第30页 2021/3/10 zhaoqiansun lizhouwu zhengwang / H 存储地址存储地址数据数据 1 7 13 19 25 31 37 43 li qian sun wang wu zhao zheng zhou 指针指针 43 13 1 null 37 7 19 25 31 头指针头指针 单链表单链表 讲解：XX第31页 2021/3/10 单链表的插入运算单链表的插入运算 在在P所指向的结点之后

33、插入所指向的结点之后插入 新的结点新的结点 单链表单链表删除运算删除运算 P ba x S b aP La aian ai-1ai+1 要求要求:删除结点删除结点ai。 讲解：XX第32页 2021/3/10 循环链表循环链表: 首尾相接的链表。首尾相接的链表。 将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其 它结点它结点。 a1 a2ana3 L . 带头结点的单链表带头结点的单链表 a1a2ana3 L . 循环单链表循环单链表 特点特点: 可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的

34、所有结点. 讲解：XX第33页 2021/3/10 双向链表的存储结构双向链表的存储结构 在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接 确定一个结点的前驱和后继结点。可提高效率。确定一个结点的前驱和后继结点。可提高效率。 HEAD 31510 a2 a3 a4 a1 提问：单向链表的缺点是什么？ 提示：如何寻找结点的直接前趋。 双向链表可以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一在双向链表的结点中有两个指针域，其一指向直接后继，另一 指向直接前趋。指向直接前趋。 双向循环链表双

35、向循环链表 讲解：XX第34页 2021/3/10 u 线性表的应用：应用最广的数据结构。线性表的应用：应用最广的数据结构。 u .高级语言中的数组；高级语言中的数组； u 计算机的文件系统；计算机的文件系统； u 计算机的目录系统；计算机的目录系统； u 电话号码查询系统（可采用顺序表或单链表结电话号码查询系统（可采用顺序表或单链表结 构构）；）； u 各种事务处理（各种事务处理（可采用顺序表或单链表结构可采用顺序表或单链表结构）; 讲解：XX第35页 2021/3/10 栈和队列栈和队列是两种特殊的线性表，它们是运算时是两种特殊的线性表，它们是运算时 要受到某些限制的线性表，故也称为要受到

36、某些限制的线性表，故也称为限定性限定性 的数据结构的数据结构。 讲解：XX第36页 2021/3/10 1 .栈栈 栈栈是限定仅在表尾进行插入或删除操作的线性表。是限定仅在表尾进行插入或删除操作的线性表。 栈顶栈顶表尾。表尾。 栈底栈底表头。表头。 空栈空栈不含元素的空表。不含元素的空表。 a1 a2 an 栈底栈底 栈顶栈顶 进栈进栈 出栈出栈 栈栈s=(a1,a2,an) 后进先出或先后进先出或先 进后出（进后出（LIFO） 讲解：XX第37页 2021/3/10 u栈的物理存储结构可以用顺序结构，也可以用链表栈的物理存储结构可以用顺序结构，也可以用链表 结构。结构。 u下面讨论顺序存储结

37、构中栈元素的插入和删除运算。下面讨论顺序存储结构中栈元素的插入和删除运算。 n 顺序栈的进栈和出栈运算顺序栈的进栈和出栈运算 n栈的基本运算有三种：入栈、退栈和读栈顶元素栈的基本运算有三种：入栈、退栈和读栈顶元素 在顺序栈中插入和删除运算不需要在顺序栈中插入和删除运算不需要 移动表中其他数据元素移动表中其他数据元素。 讲解：XX第38页 2021/3/10 2. 栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a2 a1 a1 a2 top 用顺序存储结构表示的栈用顺序存储结构表示的栈: 顺序栈用一组连续的存储单元存放自栈底到栈顶的顺序栈用一组连续的存储单元存放自栈底到栈顶的 数据元

38、素，一般用一维数组表示，设置一个简单变量数据元素，一般用一维数组表示，设置一个简单变量top指示指示 栈顶位置，称为栈顶位置，称为针栈顶指针栈顶指，它始终指向待插入元素的位置。它始终指向待插入元素的位置。 基本运算：基本运算： 压（进）栈：压（进）栈：PUSH 出栈：出栈：POP 读栈顶元素：读栈顶元素：gettop 讲解：XX第39页 2021/3/10 例子：例子： top base E D C B A top base C B A base top A base top 空桟：空桟：topbase 非空桟：非空桟：top始终在桟顶元素的后一个位置始终在桟顶元素的后一个位置 桟的元素个数：

39、桟的元素个数： top-base 上溢上溢 下溢下溢 讲解：XX第40页 2021/3/10 2 2、队列、队列 定义：一种特殊的线性结构，限定只能在表的一端进行插入，定义：一种特殊的线性结构，限定只能在表的一端进行插入， 在在 表的另一端进行删除的线性表表的另一端进行删除的线性表 。此种结构称为先进先出。此种结构称为先进先出 （FIFO）表。）表。 a1 , a2 , a3 , a4 , an-1 , an 队队 列列 示示 意意 图图 队头队头 队尾队尾 先进先出先进先出 后进后出后进后出 （LIFO） 讲解：XX第41页 2021/3/10 e3 e4 (c) e1,e2出队，出队，e4

40、入队入队 队队 满满 rear =3 front e1 e2 e3 (b) rear front (b)e1,e2,e3入队入队 队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3 2 1 0 (a) rear=front=-1(队空）队空） rear front 空队列空队列: 非空队列非空队列: 队列元素个数队列元素个数: rear=front=-1 front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终指向队始终指向队 尾元素的位置尾元素的位置 rear-front 讲解：XX第42页 2021/3/10 队列的物理存储结构可以用顺序结构，也可以

41、用链式结队列的物理存储结构可以用顺序结构，也可以用链式结 构。构。 u 顺序队列的运算顺序队列的运算 栈有三种操作：栈有三种操作： 入栈出栈读栈顶元素入栈出栈读栈顶元素 队列有三种操作：入队出队读队首元素队列有三种操作：入队出队读队首元素 例：有入栈元素序列：例：有入栈元素序列：ABCD，求可能的出栈序列，求可能的出栈序列 如是队列又是什么情况呢？如是队列又是什么情况呢？ 讲解：XX第43页 2021/3/10 把队列的存储空间在逻辑上看作一个环，当把队列的存储空间在逻辑上看作一个环，当R指向存储空指向存储空 间的末端后，就把它重新置于始端。间的末端后，就把它重新置于始端。 u 循环队列的运算

42、循环队列的运算 队列中进行插入的一端称做队尾队列中进行插入的一端称做队尾(rear),进行删除的一端进行删除的一端 称做队首称做队首(front)。 习题：数据结构分为逻辑结构和存储结构，循环队习题：数据结构分为逻辑结构和存储结构，循环队 列属于列属于【 】结构。（结构。（2005年年9月）月） 答案：存储结构。答案：存储结构。 讲解：XX第44页 2021/3/10 frontrear Maxsize-1 0 1 e3 e4 rear =3 front 讲解：XX第45页 2021/3/10 00 1 2 3 4 5 front A B C D E F rear 上溢上溢 00 1 2 3

43、4 5 front rear 下溢下溢 front=rear 队满队满 front=rear 队空队空 讲解：XX第46页 2021/3/10 数据存储结构方面的考题数据存储结构方面的考题 1：数据的存储结构是指：数据的存储结构是指 （2005年年4月）月） A) 存储在外存中的数据存储在外存中的数据 B) 数据所占的存储空间量数据所占的存储空间量 C) 数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 2. 下列叙述中正确的是下列叙述中正确的是 （2009年年3月）月） A）栈是）栈是“先进先出先进先出”的线性表的线

44、性表 B）队列是）队列是“先进后出先进后出”的线性表的线性表 C）循环队列是非线性结构）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 3. 数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于 。 4. 下列数据结构中，属于非线性结构的是下列数据结构中，属于非线性结构的是 A）循环队列）循环队列 B) 带链队列带链队列 C) 二叉树二叉树 D）带链栈）带链栈 答案：答案：D。 答案：答案：D。 答案：线性结构。答案：线性结构。 答案：答案：c 讲解：XX第

45、47页 2021/3/10 5。下列叙述中正确的是（下列叙述中正确的是（ ）。）。 （2008年年9月）月） A）顺序存储结构的存储一定是连续的，链式存储结构的存储空）顺序存储结构的存储一定是连续的，链式存储结构的存储空 间不一定是连续的间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性）顺序存储结构只针对线性结构，链式存储结构只针对非线性 结构结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间 答案：答案：A。 6 6。

46、下列关于栈的叙述正确的是。下列关于栈的叙述正确的是 （2008年年4月）月） A A）栈按）栈按“先进先出先进先出”组织数据组织数据 B)B)栈按栈按“先进后出先进后出”组织数据组织数据 C C）只能在栈底插入数据）只能在栈底插入数据 D D）不能删除数据）不能删除数据 答案：答案：B。 7. 一个队列的初始状态为空。现将元素一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3， 2，1依次入队，然后再依次退队，则元素退队的顺序为依次入队，然后再依次退队，则元素退队的顺序为 【1】 。（。（2010 年年3月）月） 答案：答案：A，B，C，D，E，F，5，4，3，2，1 讲解：X

47、X第48页 2021/3/10 9. 设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向指向 队头元素的前一位置队头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)， 则该循环队列中共有则该循环队列中共有 【2】 个元素。个元素。 （2010年年3月）月） 8。假设用一个长度为。假设用一个长度为50的数组（数组元索的下标从的数组（数组元索的下标从0 到到49）作为栈的存储空间，栈底指针）作为栈的存储空间，栈底指针bottom指间栈底指间栈底 元素，栈顶指针元素，栈顶指针top指向栈顶元素，如果指向栈顶元素，如果bottom=49

48、， top=30（数组下标），则栈中具有（数组下标），则栈中具有【 】个元素。个元素。 （2009年年3月）月） 答案：答案：19 答案：答案：15 4650110 讲解：XX第49页 2021/3/10 u链表不具有的特点是链表不具有的特点是 A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素 C) 插入删除不需要移动元素插入删除不需要移动元素 D) 所需空间与线性表长度成正比所需空间与线性表长度成正比 u数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。 u数据结构中，与所使用的计算机无关的是数据的数

49、据结构中，与所使用的计算机无关的是数据的 A) 存储结构存储结构B) 物理结构物理结构 C) 逻辑结构逻辑结构D) 物理和存储结构物理和存储结构 u数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【1】 两大类。两大类。 u数据的存储结构是指数据的存储结构是指 A）数据所占的存储空间）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示 C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式 D）存储在外存中的数据）存储在外存中的数据 例题讲解例题讲解 存储结构存储结构 非线性结构非线性结构 讲解：XX第50页 2021/3/10 u 顺序存储方

50、法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元的存储单元 中。中。 u 数据处理的最小单位是数据处理的最小单位是 A) 数据数据 B) 数据元素数据元素 C) 数据项数据项D) 数据结构数据结构 u 数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数 据结构进行的运算，以及据结构进行的运算，以及 A) 数据的存储结构数据的存储结构 B) 计算方法计算方法 C) 数据映象数据映象 D) 逻辑存储逻辑存储 u 线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序

51、存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 相邻相邻 讲解：XX第51页 2021/3/10 u 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结 构分成构分成 A) 动态结构和静态结构动态结构

52、和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构 u 数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【2】 以及对数据的操作运算。以及对数据的操作运算。 u 数据的基本单位是数据的基本单位是 【5】 。 u 下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储

53、结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 存储结构存储结构 数据元素数据元素 讲解：XX第52页 2021/3/10 u链表不具有的特点是链表不具有的特点是 A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素 C) 插入删除不需要移动元素插入删除不需要移动元素 D) 所需空间与线性表长度成正比所需空间与线性表长度成正比 u顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【2】 的存储单元的存储单元 中。中。 u长度为长度为n的顺序存

54、储线性表中，当在任何位置上插入一个元素概率都相的顺序存储线性表中，当在任何位置上插入一个元素概率都相 等时，插入一个元素所需移动元素的平均个数为等时，插入一个元素所需移动元素的平均个数为 【1】 。 u线性表若采用顺序存储结构时，要求内存中可用存储单元的地址线性表若采用顺序存储结构时，要求内存中可用存储单元的地址 A) 必须是连续的必须是连续的 B) 部分地址必须是连续的部分地址必须是连续的 C) 一定是不连续的一定是不连续的 D) 连续不连续都可以连续不连续都可以 例题讲解例题讲解 相邻相邻 2 n 讲解：XX第53页 2021/3/10 u 线性表线性表L=(a1,a2,a3,ai，an)

55、，下列说法正确的是，下列说法正确的是 A) 每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D) 除第一个元素和最后一个元素外，其余每个元素都有一个除第一个元素和最后一个元素外，其余每个元素都有一个 且只有一个直且只有一个直 接前件和直接后件接前件和直接后件 u 线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、

56、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 u 下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻

57、辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 讲解：XX第54页 2021/3/10 u 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数 据结构分成据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构 u 当线性表采用顺序存储结构实现存储时，其主要特点是当线性表采用顺序存储结构实现存储时，其主要特点是 【1】 。 随机存取随机存取 讲解：XX第55页 2021/3/10

58、 u链表不具有的特点是链表不具有的特点是 A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素 C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比 u用链表表示线性表的优点是用链表表示线性表的优点是 A) 便于随机存取便于随机存取 B) 花费的存储空间较顺序存储少花费的存储空间较顺序存储少 C) 便于插入和删除操作便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同数据元素的物理顺序与逻辑顺序相同 u长度为长度为n的顺序存储线性表中的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时当在

59、任何位置上插入一个元素概率都相等时, 插入一个元素所需移动元素的平均个数为插入一个元素所需移动元素的平均个数为 【1】 。 u在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是 A) 方便运算的实现方便运算的实现 B) 使单链表至少有一个结点使单链表至少有一个结点 C) 标识表结点中首结点的位置标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现说明单链表是线性表的链式存储实现 例题讲解例题讲解 2 n 讲解：XX第56页 2021/3/10 u 非空的循环单链表非空的循环单链表head的尾结点的尾结点(由由p所指向所指向) ，满足，满足 A) p-next=NULLB)

60、 p=NULL C) p-next=head D) p=head u 循环链表的主要优点是循环链表的主要优点是 A) 不再需要头指针了不再需要头指针了 B) 从表中任一结点出发都能访问到整个链表从表中任一结点出发都能访问到整个链表 C) 在进行插入、删除运算时，能更好的保证链表不断开在进行插入、删除运算时，能更好的保证链表不断开 D) 已知某个结点的位置后，能够容易的找到它的直接前件已知某个结点的位置后，能够容易的找到它的直接前件 u 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，当循环队列非空且队尾指针等于队头指针时，说明循环队列已满， 不能进行入队运算。这种情况称为不能进行入队