《全国计算机二级公共基础知识总结.ppt》由会员分享，可在线阅读，更多相关《全国计算机二级公共基础知识总结.ppt（174页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 一、涉及面广，但难度小一、涉及面广，但难度小一、涉及面广，但难度小一、涉及面广，但难度小 公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议公共基础知识考题特点及复习建议 计算机等级二级理论计算机等级二级理论计算机等级二级理论计算机等级二级理论考试中有关公共知识部分的题考试中有关公共知识部分的题考试中有关公共知识部分的题考试中有关公共知识部分的题目共有目共有目共有目共有15 15 15 15道，涉及道，涉及道，涉及道，涉及算法及数据结构算法及数据结构、程序设计基础程序设计基础、软件软件工程基础工程基础和和和和数据库设计基础数据库设计基础等四门课程，尽管
2、知识面大，等四门课程，尽管知识面大，等四门课程，尽管知识面大，等四门课程，尽管知识面大，但是从整体上分析，考核的内容难度不大，考点也相对但是从整体上分析，考核的内容难度不大，考点也相对但是从整体上分析，考核的内容难度不大，考点也相对但是从整体上分析，考核的内容难度不大，考点也相对集中些。集中些。集中些。集中些。1二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法二、考核重点为基本概念、基本方法 和基本运算和基本运算和基本运算和基本运算 计算机等级二级理论计算机等级二级理论计算机等级二级理论计算机等级二级理论考试中考试中考试中考试中涉及的题目涉及的题
3、目涉及的题目涉及的题目都是都是都是都是基本概念基本概念基本概念基本概念、基本方法基本方法基本方法基本方法和和和和基本运算基本运算基本运算基本运算，考核，考核，考核，考核以概念和认识性内容为主，理解性、应用性以概念和认识性内容为主，理解性、应用性以概念和认识性内容为主，理解性、应用性以概念和认识性内容为主，理解性、应用性内容偏少内容偏少内容偏少内容偏少 。2三、考核重点是数据结构和算法三、考核重点是数据结构和算法三、考核重点是数据结构和算法三、考核重点是数据结构和算法以下是对以往二级理论以下是对以往二级理论以下是对以往二级理论以下是对以往二级理论考试考试考试考试的大概统计：的大概统计：的大概统计
4、：的大概统计：v 算法及数据结构算法及数据结构算法及数据结构算法及数据结构：35%35%35%35%v 程序设计基础程序设计基础程序设计基础程序设计基础：10%10%10%10%v 软件软件软件软件工程基础工程基础工程基础工程基础：26%26%26%26%v 数据库设计基础数据库设计基础数据库设计基础数据库设计基础：29%29%29%29%3四、几点复习及应试建议四、几点复习及应试建议四、几点复习及应试建议四、几点复习及应试建议vv 复习的关键是复习的关键是考生必须准确判断和掌握常见考点考生必须准确判断和掌握常见考点vv 公共基础知识部分的知识点多、杂，考生在学习过程中应理公共基础知识部分的知
5、识点多、杂，考生在学习过程中应理 清其中的清其中的脉络关系（即框架提纲）脉络关系（即框架提纲），才能有效地组织和记住，才能有效地组织和记住 各知识点各知识点vv多做习题，多做习题，强化知识点学习强化知识点学习。41 1、了解算法的基本概念和一些、了解算法的基本概念和一些常用的算法常用的算法，学会计算算法的，学会计算算法的时间复杂度时间复杂度；2 2、掌握数据结构的基本概念，并了解数据的、掌握数据结构的基本概念，并了解数据的逻辑结构逻辑结构和和存储结构存储结构，学会利，学会利 用图形的方式表示数据结构用图形的方式表示数据结构 ；学学学学习习习习目目目目标标标标与与与与要要要要求求求求 算法与数据
6、结构：算法与数据结构：算法与数据结构：算法与数据结构：3 3、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的 线性表的基本运算；线性表的基本运算；4 4、了解栈和队列的基本概念，并掌握它们的基本运算；、了解栈和队列的基本概念，并掌握它们的基本运算；5 5、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循 环链表的基本概念和基本操作；环链表的基本概念和基本操作；6 6、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存、理解树的
7、概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存 储结构和遍历技术；储结构和遍历技术；7 7、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；8 8、学会利用相关的排序技术实现无序数列的排序操作。、学会利用相关的排序技术实现无序数列的排序操作。51 1、了解软件工程的基本概念；、了解软件工程的基本概念；2 2、了解软件工程过程与软件的、了解软件工程过程与软件的生命周期生命周期，以及软件工程的，以及软件工程的目标和原则目标和原则；学学学学习习习习目目目目标标标标与与与与要要要要求求求求 软件工程软件工程软件工
8、程软件工程：3 3、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解需需 求分析的方法和需要求分析的方法和需要完成的任务；完成的任务；4 4、了解数据流图的使用方法；、了解数据流图的使用方法；5 5、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些 常用工具；常用工具；6 6、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件 测试方法的区别和各自的功能与特点；测试方法的区别和各自
9、的功能与特点；7 7、了解程序调试的方法和原则、了解程序调试的方法和原则 。61 1、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序 设计的基本规则；设计的基本规则；2 2、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点;学学学学习习习习目目目目标标标标与与与与要要要要求求求求 程序设计基础程序设计基础程序设计基础程序设计基础：3 3、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。、了解面向对象的程序设计方法，并理解面向
10、对象方法的一些基本概念。数据库系统数据库系统数据库系统数据库系统：1 1、了解数据库系统的基本概念，以及数据库系统的发展；、了解数据库系统的基本概念，以及数据库系统的发展；2 2、了解数据模型的基本概念，并对、了解数据模型的基本概念，并对E-RE-R模型、层次模型、网状模型和关系模型模型、层次模型、网状模型和关系模型 进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；3 3、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；4 4、了解数据库的设计与
11、管理，掌握数据库设计的几个阶段的方法和特点。、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。7算算算算法法法法与与与与数数数数据据据据结结结结构构构构一、算法（一、算法（algorithm）1 1、算法的基本概念、算法的基本概念(汉诺塔的例子)算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法具有可行性可行性、确定性确定性、有穷性有穷性、输入输入和输出输出（拥有足够的情报）等个重要特性。8学学学学习习习习目目目目标标标标与与与与要要要要
12、求求求求2 2、算法的基本要素、算法的基本要素(1)对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输 算法中各操作之间的执行顺序；描述算法的工具通常有传统流程图、N-S结构化流程 图、算法描述语言等；一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。(2)算法的控制结构：10算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3、算法设计的基本方法、算法设计的基本方法及例子1.列举法（列出所有可能，再逐一检验，得到符合条件的结果）百钱买百鸡2.归纳法（通过特殊情况，经过分析，最后找出一般关系）3.递推（从已知的初始条件出发，逐步推算，得到结果）猴子分食桃子 4.递
13、归（将问题逐层分解，最后归结为一些最简单的问题）求年龄问题5.减半递推（重复将问题的规模减半，而问题性质不变）二分法求方程实根6.回溯法（以最优方式向前试探，如果失败，则后退再选）八皇后问题11算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3 3 3、算法的复杂度、算法的复杂度、算法的复杂度、算法的复杂度(1)(1)时间复杂度时间复杂度v 依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分析估算法。v 一个算法是由控制结构（顺序、分支和循环）和原操 作构成的，算法时间取决于两者的综合效果。v 算法中基本操作重复执行次数n和算法执行时间同步 增长，称作
14、算法的时间复杂度。12算算算算法法法法与与与与数数数数据据据据结结结结构构构构(2)(2)空间复杂度空间复杂度v 一般是指执行这个算法所需要的内存空间。v 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。v 一个上机执行的程序除了需要存储空间来寄存本身所用 指令、常数、变量和输入数据外，也需要一些对数据进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。13算算算算法法法法与与与与数数数数据据据据结结结结构构构构3 3、例题讲解、例题讲解v 算法的时间复杂度是指算法的时间复杂度是指(C C )A A、执行算法程序所需
15、要的时间执行算法程序所需要的时间 B B、算法程序的长度算法程序的长度 C C、算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D D、算法程序中的指令条数算法程序中的指令条数v 算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、【1 1】和拥有足够和拥有足够 的情报。的情报。【答案】【答案】:有穷性有穷性v 算法的空间复杂度是指算法的空间复杂度是指(D D )A)A)算法程序的长度算法程序的长度 B)B)算法程序中的指令条数算法程序中的指令条数 C)C)算法程序所占的存储空间算法程序所占的存储空间 D)D)执行过程中所需要的存储空间执行过程中所需要的存储空
16、间14算算算算法法法法与与与与数数数数据据据据结结结结构构构构v 在计算机中，算法是指（B B）A)加工方法 B)B)解题方案的准确而完整的描述解题方案的准确而完整的描述 C)排序方法 D)查询方法v 算法分析的目的是(D D)A)找出数据结构的合理性 B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)D)分析算法的效率以求改进分析算法的效率以求改进v 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的【1 1】。【答案】【答案】:时间复杂度和空间复杂度时间复杂度和空间复杂度15算算算算法法法法与与与与数数数数据据据据结结结结构构构构二、数据结构（二、数据结构（D
17、ata Structure）1 1、数据结构研究的主要内容、数据结构研究的主要内容v当今计算机应用的特点：1、所处理的数据量大且具有一定的关系；2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。对数据的讨论不单单是数据本身，还要包括数据与对数据的讨论不单单是数据本身，还要包括数据与数据之间的关系。数据之间的关系。下面各例表示不同的数据采用不同的数据结构来组织。下面各例表示不同的数据采用不同的数据结构来组织。16特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的
18、操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。v 应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。17v 应用举例2家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。图图图图 1-1 1-1 1-1 1-1 家庭血缘关系图特点：在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构；对它的操作有：建立树形结构，输出最结点内容等等。18v 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比
19、如，计算机专业课程的开设情况如下表所示：19这种数据可以用下面的图来表示：19v课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业必修课程开设先后关系2020 1 1、数据的、数据的逻辑结构逻辑结构 2 2、数据的、数据的存储结构存储结构 3 3、数据的、数据的运算运算：检索、排序、插入、删除、修改等。：检索、排序、插入、删除、修改等。A A线性结构线性结构B B非线性结构非线性结构A A顺序存储顺序存储 B B链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面(亦称物理结构亦称物理结构
20、)数据结构的主要研究问题：21212 2、基本概念和术语、基本概念和术语 数据结构是一门研究数据数据数据数据组织组织、存储存储和运算运算的一般方法的学科。例：整数整数(1,2)、实数实数(1.1,1.2)字符串字符串(Beijing)、图形图形、声音声音。计算机管理图书问题：在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如：2222数据元素在计算机中的表示 数据结构是一门研究数据数据数据数据组织组织、存储存储和运算运算的一般方法的学科。如何将
21、0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9 对数据结构中的节点进行操作处理对数据结构中的节点进行操作处理（插入、删除、修改、查找、排序）（插入、删除、修改、查找、排序）2323v 数据元素数据元素(Data Element)Data Element)数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元素可由若干数据项数据项(Data ItemData Item)组成。数据项是数据的最小单位。数据元素亦称节点
22、节点或记录记录。数据结构可描述为数据结构可描述为 Group=Group=（D D，R R）有限个数据元素的集合有限个数据元素的集合有限个节点间关系的集合有限个节点间关系的集合2424数据结构可描述为数据结构可描述为 Group=（D，R）l 例例1：一年四季的数据结构可表示成：一年四季的数据结构可表示成B=（D，R）D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）l 例例2：家庭成员数据结构可表示成：家庭成员数据结构可表示成B=（D，R）D=父亲，儿子，女儿父亲，儿子，女儿 R=（父亲，儿子），（父亲，女儿）（父亲，儿子），（父亲，女
23、儿）25数据结构也可用图形表示数据结构也可用图形表示l一年四季的数据结构可表示成一年四季的数据结构可表示成l家庭成员数据结构可表示成家庭成员数据结构可表示成冬冬春春夏夏秋秋父亲父亲儿子儿子女儿女儿（概念：结点、前件、后件、根结点、叶子）26v 树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式计算机程序管理系统也是典型的计算机程序管理系统也是典型的树形结构树形结构。271 14 42 23 3 D=1,2,3,4 D=1,2,3,4R=(1,2),(1,3),R=(1,2),(1,3),(1,4),(2,3),(1,4),(2,3),(3,4),(2,4)(3,4),(2,4)2 2
24、1 13 3 D=1,2,3 D=1,2,3 R=(1,2),(2,3),(3,2),(1,3)R=(1,2),(2,3),(3,2),(1,3)v 图形结构图形结构节点间的连结是任意的节点间的连结是任意的283 3、例题讲解、例题讲解v数据处理的最小单位是数据处理的最小单位是(C C )A)A)数据数据 B)B)数据元素数据元素 C)C)数据项数据项 D)D)数据结构数据结构v数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及(A A )A)A)数据的存储结构数据的存储结构
25、B)B)计算方法计算方法 C)C)数据映象数据映象 D)D)逻辑存储逻辑存储v数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【4 4】以及对数据的以及对数据的操作运算。操作运算。【答案【答案】物理结构（或存储结构）物理结构（或存储结构）29v 线性结构与非线性结构：线性结构与非线性结构：v 线性结构：有且只有一个根结点；每一个结线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。点最多有一个前件，也最多有一个后件。如：一年四季，如：一年四季，2626个英文字母个英文字母v非线性结构：线性以外的数据结构。非线性结构：线性以外的数据结构。如：反映家庭成
26、员间辈分关系的数据结构如：反映家庭成员间辈分关系的数据结构 算算算算法法法法与与与与数数数数据据据据结结结结构构构构30结点间是以线性关系联结，结点间是以线性关系联结，如前面提到的：一年四季26个英文字母 线性 有限 序列4、线性表、线性表（Linear List）v 线性表线性表：具有线性结构的有限序列。A AB BC CD DZ Z春春夏夏秋秋冬冬31学生成绩表学生成绩表线性表线性表32数据元素、结点、记录数据项线性33v线性表的定义线性表的定义:线性表线性表是是n n个元素的有限序列，它们之间的关系可以排成个元素的有限序列，它们之间的关系可以排成一个线性序列：一个线性序列：a1a1，a2
27、a2，aiai，anan 其中其中n n称作表的称作表的长度长度，当，当n=0n=0时，称作时，称作空表空表。v线性表的特点：线性表的特点：1 1、线性表中所有元素的性质相同。、线性表中所有元素的性质相同。2 2、除第一个和最后一个数据元素之外，其它数据元素有且、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，最仅有一个前驱和一个后继。第一个数据元素无前驱，最 后一个数据元素无后继。后一个数据元素无后继。3 3、数据元素在表中的位置只取决于它自身的序号。、数据元素在表中的位置只取决于它自身的序号。v在线性表上常用的运算有：在线性表上常用的运算有：
28、初始化、求长度、取元素、修改、前插、删除、检索、排序初始化、求长度、取元素、修改、前插、删除、检索、排序3434v 线性表的线性表的 顺序存储结构 及其及其 插入 与与 删除 操作操作特点：特点：1 1、线性表中数据元素类型一致，只有数据域，存储空间、线性表中数据元素类型一致，只有数据域，存储空间 利用率高。利用率高。2 2、所有元素所占的存储空间是连续的。、所有元素所占的存储空间是连续的。3 3、各数据元素在存储空间中是按逻辑顺序依次存放的、各数据元素在存储空间中是按逻辑顺序依次存放的 （a a）做插入、删除时需移动大量元素。做插入、删除时需移动大量元素。（b b）空间估计不明时，按最大空间
29、分配。空间估计不明时，按最大空间分配。算算算算法法法法与与与与数数数数据据据据结结结结构构构构35顺顺序序存存储储存储地址存储地址存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素1 1L L L Lo o o oL Lo o+mL Lo o+(i-1)+(i-1)mLo+Lo+（n-1)n-1)mLoc(Loc(元素元素i)=Li)=Lo o+（i-1)i-1)m每个元素所占用每个元素所占用的存储单元个数的存储单元个数v 线性表的线性表的 顺序存储结构顺序存储结构：首地址首地址起始地址起始地址基地址基地址36v插入运算插入运算a ai-1i-1.a a2 2a a1 1a
30、 alengthlengtha ai+1i+1a ai ia alengthlength插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：37X Xa ai-1i-1.a a2 2a a1 1a alengthlengtha ai+1i+1a ai iX X37在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。v删
31、除算法的分析删除算法的分析3838q 线性表的例题讲解线性表的例题讲解v 顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1 1】的存储单元中。的存储单元中。【答案【答案】相邻相邻v 长度为长度为n n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平均个数 为为【2 2】。【答案【答案】n/2n/2v 线性表线性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列说法正确的是（下列说法正
32、确的是（D D）A)A)每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B)B)线性表中至少要有一个元素线性表中至少要有一个元素 C)C)表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D)D)除第一个元素和最后一个元素外，其余每个元素都有一除第一个元素和最后一个元素外，其余每个元素都有一 个且只有一个直接前件和直接后件个且只有一个直接前件和直接后件3939 数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的(C C )A)A)存储结构存储结构B)B)物理结构物理结构 C)C)逻辑结构逻辑结构D)
33、D)物理和存储结构物理和存储结构 下列叙述中，错误的是（下列叙述中，错误的是（B B ）A)A)数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B)B)数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C)C)数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D)D)一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 数据的存储结构是指（数据的存储结构是指（B B ）A A）数据所占的存储空间数据所占的存储空间 B B）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的
34、表示 C C）数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D D）存储在外存中的数据存储在外存中的数据40 根据数据结构中各数据元素之间前后件关系的复杂程度，一般根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成将数据结构分成(C C)A)A)动态结构和静态结构动态结构和静态结构 B)B)紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C)C)线性结构和非线性结构线性结构和非线性结构 D)D)内部结构和外部结构内部结构和外部结构 数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【2 2】两大类。两大类。非线性结构非线性结构 当线性表采用顺序存储结构实现存储时，其
35、主要特点是当线性表采用顺序存储结构实现存储时，其主要特点是【1】。【答案【答案】逻辑结构中相邻的结点在存储结构中仍相邻。逻辑结构中相邻的结点在存储结构中仍相邻。4141a1a2.an进栈进栈出栈出栈栈顶栈顶栈底栈底5 5、堆栈和队列、堆栈和队列q 堆栈和队列的定义堆栈和队列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为些限制的线性表，故也称为限定性的数据结构。限定性的数据结构。v 堆栈的定义堆栈的定义堆栈：堆栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表,此种此种
36、 结构称为结构称为后进先出。后进先出。设栈设栈s=s=（a a1 1，a a2 2，a ai i，a an n）,其中其中a a1 1是是栈底栈底元素，元素，a an n是是栈顶栈顶元素。元素。栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端；约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。4242v 队列的定义队列的定义队列：队列：一种特殊的线性结构，限定只能在表的一端进行插入，一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删
37、除的线性表在表的另一端进行删除的线性表 。此种结构称为。此种结构称为先进先进 先出（先出（FIFO）表表。a1 ,a2 ,a3 ,a4 ,an-1 ,an队队 列列 示示 意意 图图队队头头队队尾尾v 队列的主要运算队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；4343q 堆栈和队列的例题讲解堆栈和队列的例题讲解v栈和队列的共同特点是（栈和队列的共同特点是（C C ）A)A)都是先进先出都是先进先出 B)B)都是先进后出都是先进后出 C)C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D)D)没有共同点
38、没有共同点v如果进栈序列为如果进栈序列为e1,e2,e3,e4e1,e2,e3,e4，则可能的出栈序列是（则可能的出栈序列是（B B ）A)e3,e1,e4,e2 A)e3,e1,e4,e2 B)e4,e3,e2,e1B)e4,e3,e2,e1 C)e3,e4,e1,e2 C)e3,e4,e1,e2 D)D)任意顺序任意顺序4444la=42+b8 82 26 6lb=63+clc=32+dld=1+2=8 +b=2 +c=6 +d=3826u 一些重要的程序语言一些重要的程序语言(如如C C语言和语言和PascalPascal语言语言)允许过程允许过程的递归调用。而实现递归调用中的存储分配通
39、常用（的递归调用。而实现递归调用中的存储分配通常用（A A ）A)A)栈栈B)B)堆堆 C)C)数组数组 D)D)链表链表45v当循环队列非空且队尾指针等于队头指针时，说明循环队列已当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为满，不能进行入队运算。这种情况称为【2 2】。答案：答案：上溢上溢 v由两个栈共享一个存储空间的好处是（由两个栈共享一个存储空间的好处是（B B ）A)A)减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B)B)节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率 C)C)减少存取时间，降低上溢发生
40、的机率减少存取时间，降低上溢发生的机率 D)D)节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率v下列关于栈的叙述中正确的是（下列关于栈的叙述中正确的是（D D ）)在栈中只能插入数据在栈中只能插入数据 B B）在栈中只能删除数据在栈中只能删除数据C C）栈是先进先出的线性表栈是先进先出的线性表 D D）栈是后进先出的线性表栈是后进先出的线性表v下列关于队列的叙述中正确的是（下列关于队列的叙述中正确的是（C C ）在队列中只能插入数据）在队列中只能插入数据 B B）在队列中只能删除数据在队列中只能删除数据C C）队列是先进先出的线性表队列是先进先出的线性表 D D）队列是后进先
41、出的线性表队列是后进先出的线性表46两个栈共享只有两个栈两个栈共享只有两个栈都多时才溢出。不共享都多时才溢出。不共享的话，两个栈只有一个的话，两个栈只有一个栈多就溢出，栈多就溢出，RearRear队尾队尾FrontFront队头队头46v 栈底至栈顶依次存放元素栈底至栈顶依次存放元素A A、B B、C C、D D，在第五个元素在第五个元素E E 入栈前，栈中元素可以出栈，则出栈序列可能是（入栈前，栈中元素可以出栈，则出栈序列可能是（B B ）A)ABCEDA)ABCED B)DCBEAB)DCBEA C)DBCEA C)DBCEA D)CDABE D)CDABE 47D D出出C C出出B B
42、出出 E E出出A A出出 E E进进 时间顺序出栈：出栈：进栈：进栈：47 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。v 顺序存储结构的三个缺点：1.作插入或删除操作时，需移动大量元数。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。存储内容存储内容元素元素n n.元素元素i i.元素元素2 2元素元素1 148486 6、线性表的链式存储 线性链表线性链表v线性链表的基本概念：线性链表的基本概念：线性表的链式存储结构称为线性链表。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结
43、点。算算算算法法法法与与与与数数数数据据据据结结结结构构构构49将存储空间中的每一个存储结点分为两部：v一部分称为数据域，用于存储数据元素的值；v另一部分称为指针域，用于存放下一个数据元素的存储序号（即存储结点的地址），也就是指向后件结点.线性链表中存储结点的结构如图2.20所示5050 指向线性表中第一个结点的指针HEAD称为头指针。当HEAD=NULL（或0）时称为空表。对于线性链表，可以从头指针开始，沿着各个结点的指针扫描到链表中的所有结点。线性链表的逻辑结构图所示511、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。2、
44、逻辑上相邻的节点物理上不必相邻。3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。4、查找结点时链式存储要比顺序存储慢。v 链接存储结构特点：链接存储结构特点：算算算算法法法法与与与与数数数数据据据据结结结结构构构构525353v 线性链表的基本运算：线性链表的基本运算：线性链表的运算主要有以下几个：线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前在线性链表中包含指定元素的结点之前 插入插入一个新元素。一个新元素。在线性链表中在线性链表中删除删除包含指定元素的结点。包含指定元素的结点。将两个线性链表按要求将两个线性链表按要求合并合并成一个线性成一个线性 链表。链表。5
45、4 线性链表的线性链表的 插入插入 运算：运算：线性链表的插入线性链表的插入是指在链式存储结构下是指在链式存储结构下的线性表中插入一个新元素。的线性表中插入一个新元素。为了要在线性链表中插入一个新元素，为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，然后将存首先要给该元素分配一个新结点，然后将存放新元素值的结点链接到线性链表中指定的放新元素值的结点链接到线性链表中指定的位置。位置。算算算算法法法法与与与与数数数数据据据据结结结结构构构构555656 线性链表的删除线性链表的删除指在链式存储结构下的指在链式存储结构下的线性表中删除包含指定元素的结点。线性表中删除包含指定元素的结点
46、。为了在线性链表中删除包含指定元素的为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。然后将要删除结点放回到可利用栈。线性链表的线性链表的 删除删除 运算：运算：算算算算法法法法与与与与数数数数据据据据结结结结构构构构575858 循环链表的结构与前面所讨论的线性链表相比，具有以下循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：两个特点：循环链表的头指针指向表头结点。循环链表的头指针指向表头结点。在循环链表中，所有结点的指针构成了一个环状链。在循环链表中，所有结点的指针构成了一个环状链。图图
47、2.292.29是循环链表的示意图。是循环链表的示意图。v循环链表：循环链表：5959 在实际应用中，循环链表与线性单链表相在实际应用中，循环链表与线性单链表相比主要有以下两个方面的优点：比主要有以下两个方面的优点：在循环链表中，只要指出表中任何一个结点在循环链表中，只要指出表中任何一个结点 的位置，就可以从它出发访问到表中其他所的位置，就可以从它出发访问到表中其他所 有的结点。有的结点。由于在循环链表中设置了一个表头结点，因由于在循环链表中设置了一个表头结点，因 此，在任何情况下，循环链表中至少有一个此，在任何情况下，循环链表中至少有一个 结点存在，结点存在，从而使空表与非空表的运算统一从而
48、使空表与非空表的运算统一。算算算算法法法法与与与与数数数数据据据据结结结结构构构构60v链表不具有的特点是（链表不具有的特点是（B B ）A)A)不必事先估计存储空间不必事先估计存储空间 B)B)可随机访问任一元素可随机访问任一元素 C)C)插入删除不需要移动元素插入删除不需要移动元素 D)D)所需空间与线性表长度成正比所需空间与线性表长度成正比v数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1 1】。【答案【答案】存储结构存储结构u 栈栈通常采用的两种存储结构是（通常采用的两种存储结构是（A A ）A)A)顺序存储结构和链表存储结构顺序存储结构和
49、链表存储结构 B)B)散列方式和索引方式散列方式和索引方式 C)C)链表存储结构和数组链表存储结构和数组 D)D)线性存储结构和非线性存储结构线性存储结构和非线性存储结构q 线性链表的例题讲解线性链表的例题讲解6161u 线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是(C C)A)A)顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构B)B)顺序存取的存储结构、随机存取的存储结构顺序存取的存储结构、随机存取的存储结构C)C)随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构D)D)任意存取的存
50、储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构顺序存储结构的地址在内存中是连续的所以可以通过计算地址实现随机存取，而链式存储结构的存储地址不一定连续，只能通过第1个结点的指针顺序存取；627 7、树与二叉树：、树与二叉树：v 树的基本概念：树的基本概念：前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。63算算算算法法法法与与与与数数数数据据据据结结结结构构构构现实世界中，能用树的结构表示的例子现实