二级公共基础知识(新视野).ppt

1 全国计算机等级考试 二级 谭毓2 全国计算机等级考试 全国计算机等级考试 NationalComputerRankExamination 简称NCRE 是经原国家教育委员会 现教育部 批准 由教育部考试中心主办 面向社会 用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系 一年考查两次 分别在每年的三月和九月 3 考试时间 考试时间 上半年3月底 即3月份倒数第一个周六 下半年9月中旬 即9月份倒数第二个周六 考试方式为上机考试 即无纸化答题 4 考试方式 1 考试时间为130分钟 满分100分 其中选择题40分 上机操作题60分 2 无纸化考试中 总分达到60分且上机操作题达到36分 方能取得合格证书 3 无纸化考试中没有取得合格证书的考生 下一次考试不再安排补考 考生下一次考试需重新以新考生身份报名参加考试 5 选择题 选择题由专业课内容和公共基础知识部分组成 6 上机操作 上机操作由三道大题组成 1 基本操作 18分 2 简单应用 24分 3 综合应用 18分 考查内容全部来自专业内容 7 考试大纲 每门考试都有相应的考试大纲 全国计算机等级考试也不例外 考试大纲是引领我们学习复习的一条主线 因此 我们的学习不能离开考试大纲来进行 8 所选的课程名称 全国计算机等级考试二级教程 Access数据库程序设计关键字 Access数据库程序设计程序设计 Programming 是给出解决特定问题程序的过程 是软件构造活动中的重要组成部分 程序设计往往以某种程序设计语言为工具 给出这种语言下的程序 程序设计过程应当包括分析 设计 编码 测试 排错等不同阶段 专业的程序设计人员常被称为程序员 9 软件开发 举例 QQ飞信选课系统校园网人人网QQ好友 昵称 出生年月 住址等等这些信息是如何保存呢 保存到哪里了呢 10 二级公共基础知识 考试需知 考试内容及安排第一章算法与数据结构第二章程序设计基础第三章软件工程基础第四章数据库设计基础 11 一 涉及面广 但难度小 你应该知道 公共基础知识考题特点及复习建议 计算机等级二级理论考试中有关公共知识部分的题目共有15道 涉及算法及数据结构 程序设计基础 软件工程基础和数据库设计基础等四门学科 但是从整体上分析 考试中的考核内容的难度不大 考点也相对集中些 12 二 考核重点为基本概念 基本方法和基本运算 你应该知道 计算机等级二级理论考试中涉及的题目都是基本概念 基本方法和基本运算 考核以概念和认识性内容为主 理解性 应用性内容极少 13 三 考核重点是数据结构和算法 你应该知道 以下是对以往二级理论考试的大概统计 算法及数据结构 35 程序设计基础 10 软件工程基础 25 数据库设计基础 30 14 你应该知道 15 你应该知道 16 1 了解算法的基本概念和一些常用的算法 学会计算算法的时间复杂度 2 掌握数据结构的基本概念 并了解数据的逻辑结构和存储结构 学会利用图形的方式表示数据结构 算法与数据结构 3 了解线性表的基本概念 并掌握线性表的顺序存储结构以及顺序存储的线性表的基本运算 4 了解栈和队列的基本概念 并掌握它们的基本运算 5 了解线性链表的基本概念 并掌握线性链表的基本运算 同时 了解循环链表的基本概念和基本操作 6 理解树的概念 尤其是二叉树的基本概念和相关性质 掌握二叉树的存储结构和遍历技术 7 掌握查找技术 学会利用顺序查找和二分查找在数列中查找指定的数据 8 学会利用相关的排序技术实现无序数列的排序操作 17 1 了解软件工程的基本概念 2 了解软件工程过程与软件的生命周期 以及软件工程的目标和原则 软件工程 3 了解利用结构化分析法进行软件工程中的需求分析的方法 并了解需求分析的方法和需要完成的任务 4 了解数据流图的使用方法 5 了解如何利用结构化设计方法进行软件设计 并了解软件设计的一些常用工具 6 了解软件测试的目的和方法 以及软件测试的准则 了解常用的软件测试方法的区别和各自的功能与特点 7 了解程序调试的方法和原则 18 1 了解程序设计的方法 以及程序设计风格确立的一些因素 掌握程序设计的基本规则 2 了解结构化程序设计的基本原则 掌握结构化程序设计的基本结构与特点 程序设计基础 3 了解面向对象的程序设计方法 并理解面向对象方法的一些基本概念 数据库系统 1 了解数据库系统的基本概念 以及数据库系统的发展 2 了解数据模型的基本概念 并对E R模型 层次模型 网状模型和关系模型进行了解 并掌握关系模型的数据结构 关系的操作和数据约束等知识 3 了解关系模型的基本操作 掌握关系模型的基本运算及扩充运算 4 了解数据库的设计与管理 掌握数据库设计的几个阶段的方法和特点 19 第一章算法与数据结构 二级公共基础知识 返回 20 一 算法 1 算法的基本概念 算法是指一组有穷的指令集 是解题方案的准确而完整的描述 通俗地说 算法就是计算机解题的过程 算法具有确定性 有穷性 可行性 拥有足够的情报 输入和输出 等几个重要特性 记忆 21 2 算法的组成要素 对数据对象的运算和操作 算术运算 逻辑运算 关系运算 数据传输 算法中各操作之间的执行顺序 描述算法的工具通常有传统流程图 N S结构化流程图 算法描述语言等 一个算法一般可以用顺序 选择 循环三种基本结构组合而成 算法的控制结构 22 3 算法设计的基本方法 列举法归纳法递推递归 以简洁的形式设计和描述算法 减半递推技术回溯法 23 二 算法的复杂度 1 2 3 100 是算法效率的度量 是评价算法优劣的重要依据 1 时间复杂度 执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量 与问题规模和特定的输入有关 衡量的方法一般采用最坏情况复杂性2 空间复杂度 执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间 包括输入数据 程序本身 执行所需的额外空间 24 3 例题讲解 算法的时间复杂度是指 C A 执行算法程序所需要的时间B 算法程序的长度C 算法执行过程中所需要的基本运算次数D 算法程序中的指令条数算法的基本特征是可行性 确定性 1 和拥有足够的情报 答案 有穷性算法的空间复杂度是指 D A 算法程序的长度B 算法程序中的指令条数C 算法程序所占的存储空间D 执行过程中所需要的存储空间 25 在计算机中 算法是指 B A 加工方法B 解题方案的准确而完整的描述C 排序方法D 查询方法 算法分析的目的是 D A 找出数据结构的合理性B 找出算法中输入和输出之间的关系C 分析算法的易懂性和可靠性D 分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 1 答案 时间复杂度和空间复杂度 26 三 数据结构 DataStructure 1 数据结构研究的主要内容 当今计算机应用的特点 1 所处理的数据量大且具有一定的关系 2 对其操作不再是单纯的数值计算 而更多地是需要对其进行组织 管理和检索 在计算机中如何组织存放大量的数据元素 以便提高数据处理的效率 并且节省计算机的存储空间 便成了进行数据处理的关键问题 27 特点 每个学生的信息占据一行 所有学生的信息按学号顺序依次排列构成一张表格 表中每个学生的信息依据学号的大小存在着一种前后关系 这就是我们所说的线性结构 对它的操作通常是插入某个学生的信息 删除某个学生的信息 更新某个学生的信息 按条件检索某个学生的信息等 应用举例1 学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息 28 应用举例2 家庭血缘关系图表示家庭成员的辈分关系 使用下图1 1所示的形式描述 图1 1家庭血缘关系图 特点 在求解过程中 所处理的数据之间具有层次关系 这是我们所说的树形结构 对它的操作有 建立树形结构 输出终结点内容等 应用举例3 制定教学计划在制定教学计划时 需要考虑各门课程的开设顺序 有些课程需要先导课程 有些课程则不需要 而有些课程又是其他课程的先导课程 比如 计算机专业课程的开设情况如下表所示 29 这种数据可以用下面的图来表示 课程先后关系的图形描形式 图1 2计算机专业必修课程开设先后关系 30 数据结构的主要研究问题 31 2 基本概念和术语 数据结构是一门研究数据组织 存储和运算的一般方法的学科 例 整数 1 2 实数 1 1 1 2 字符串 Beijing 图形 声音 计算机管理图书问题 在图书馆里有各种卡片 有按书名编排的 有按作者编排的 有按分类编排 如何将查询图书的这些信息存入计算机中既要考虑查询时间短 又要考虑节省空间 最简单的办法之一是建立一张表 每一本书的信息在表中占一行 如 32 数据元素在计算机中的表示 数据结构是一门研究数据组织 存储和运算的一般方法的学科 如何将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 对数据结构中的节点进行操作处理 插入 删除 修改 查找 排序 33 数据元素 DataElement 数据元素是数据的基本单位 即数据集合中的个体 有时一个数据元素可由若干数据项 DataItem 组成 数据项是数据的最小单位 数据元素亦称节点或记录 数据结构可描述为Data Structure D R 有限个数据元素的集合 有限个节点间关系的集合 34 35 数据结构可描述为DS D R 例1 一年四季的数据结构可表示成B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 例2 家庭成员数据结构可表示成B D R D 父亲 儿子 女儿 R 父亲 儿子 父亲 女儿 36 数据结构也可用图形表示 一年四季的数据结构可表示成家庭成员数据结构可表示成 概念 结点 前件 后件 根结点 叶子 37 树形结构 全校学生档案管理的组织方式 计算机程序管理系统也是典型的树形结构 38 H G F E C D B A 树形结构 结点间具有分层次的连接关系 39 D 1 2 3 4 R 1 2 1 3 1 4 2 3 3 4 2 4 D 1 2 3 R 1 2 2 3 3 2 1 3 图形结构 节点间的连结是任意的 40 线性结构与非线性结构 线性结构 1 有且只有一个根结点 2 每一个结点最多有一个前件 也最多有一个后件 如 一年四季 26个英文字母非线性结构 线性以外的数据结构 如 反映家庭成员间辈分关系的数据结构 41 4 线性表 LinearList 线性表 具有线性结构的有限序列 数据元素在线性表中的位置只取决于它们自己的序号 即数据元素之间的相对位置是线性的 如图1 2 a 42 5 链式结构 链式存储结构就是在每个结点中至少包含一个指针域 用指针来体现数据之间逻辑上的联系 顺序存储 链式存储 43 3 例题讲解 数据处理的最小单位是 C A 数据B 数据元素C 数据项D 数据结构数据结构作为计算机的一门学科 主要研究数据的逻辑结构 对各种数据结构进行的运算 以及 A A 数据的存储结构B 计算方法C 数据映象D 逻辑存储数据结构包括数据的逻辑结构 数据的 4 以及对数据的操作运算 答案 物理结构 或存储结构 44 4 线性表 LinearList 线性表 具有线性结构的有限序列 数据元素在线性表中的位置只取决于它们自己的序号 即数据元素之间的相对位置是线性的 如图1 2 a 在非空线性表中 存在唯一的一个开始元素和一个末尾元素 队了这两个元素外 其他的元素都有且只有一个前件和一个后件 45 数据结构的主要研究问题 45 46 线性表的顺序存储结构及其插入与删除操作 特点 1 线性表中数据元素类型一致 只有数据域 存储空间利用率高 2 所有元素所占的存储空间是连续的 3 各数据元素在存储空间中是按逻辑顺序依次存放的 a 数据元素是随机存取的 b 做插入 删除时需移动大量元素 c 空间估计不明时 按最大空间分配 47 0 1 i 线性表的顺序存储结构 可用C语言中的一维数组来描述 第i个元素的ai存储地址 Loc ai Loc a1 i 1 m V V V i V m 1 intV M 其中 V是数组的名字 M是数组大小 假设数组中的元素是整型类型 插入运算 alength 插入算法的分析假设线性表中含有n个数据元素 在进行插入操作时 若假定在n 1个位置上插入元素的可能性均等 则平均移动元素的个数为 最坏情况下要移动全部的数据元素 n 48 X an ai ai 1 在进行删除操作时 若假定删除每个元素的可能性均等 则平均移动元素的个数为 最坏情况下要移动元素的个数为 n 1 分析结论顺序存储结构表示的线性表 在做插入或删除操作时 平均需要移动大约一半的数据元素 当线性表的数据元素量较大 并且经常要对其做插入或删除操作时 这一点需要值得考虑 删除算法的分析 49 an ai ai 1 50 顺序存储结构常用于线性数据结构 将逻辑上相邻的数据元素存储在物理上相邻的存储单元里 顺序存储结构的三个缺点 1 作插入或删除操作时 需移动大量元素 2 长度变化较大时 需按最大空间分配 3 表的容量难以扩充 存储内容 50 线性表的例题讲解 顺序存储方法是把逻辑上相邻的结点存储在物理位置 1 的存储单元中 答案 相邻长度为n的顺序存储线性表中 当在任何位置上插入一个元素概率都相等时 插入一个元素所需移动元素的平均个数为 2 答案 n 2线性表L a1 a2 a3 ai an 下列说法正确的是 D A 每个元素都有一个直接前件和直接后件B 线性表中至少要有一个元素C 表中诸元素的排列顺序必须是由小到大或由大到小D 除第一个元素和最后一个元素外 其余每个元素都有一个且只有一个直接前件和直接后件 51 52 数据结构中 与所使用的计算机无关的是数据的 C A 存储结构B 物理结构C 逻辑结构D 物理和存储结构下列叙述中 错误的是 B A 数据的存储结构与数据处理的效率密切相关B 数据的存储结构与数据处理的效率无关C 数据的存储结构在计算机中所占的空间不一定是连续的D 一种数据的逻辑结构可以有多种存储结构数据的存储结构是指 B A 数据所占的存储空间B 数据的逻辑结构在计算机中的表示C 数据在计算机中的顺序存储方式D 存储在外存中的数据 根据数据结构中各数据元素之间前后件关系的复杂程度 一般将数据结构分成 C A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构数据的逻辑结构有线性结构和 2 两大类 非线性结构当线性表采用顺序存储结构实现存储时 其主要特点是 1 答案 逻辑结构中相邻的结点在存储结构中仍相邻 53 54 6 线性链表 线性链表的基本概念 线性表的链式存储结构称为线性链表 每一个数据元素占用一个结点 每个结点由两个域组成 数据域和指针域 55 将存储空间中的每一个存储结点分为两部 一部分称为数据域 用于存储数据元素的值 另一部分称为指针域 用于存放下一个数据元素的存储序号 即存储结点的地址 也就是指向后件结点 线性链表中存储结点的结构如图2 20所示 55 56 1 比顺序存储结构的存储密度小 每个节点都由数据域和指针域组成 所以相同空间内假设全存满的话顺序比链式存储更多 2 逻辑上相邻的节点物理上不必相邻 3 插入 删除灵活 不必移动节点 只要改变节点中的指针 4 查找结点时链式存储要比顺序存储慢 链式存储结构特点 57 线性链表的物理结构 线性链表的逻辑结构图 HEAD 指向线性表中第一个结点的指针 称为头指针 当HEAD NULL 或0 时称为空表 对于线性链表 可以从头指针开始 沿着各个结点的指针扫描到链表中的所有结点 这种结构也叫单链表 58 单链表的基本运算 first new 单链表的插入 59 单链表的删除 first 删除a2结点 60 单链表的缺点 单链表中 每一个结点只有一个指针域 由这个指针只能找到后件结点 但不能找到前件结点 因此 只能顺指针向链尾方向进行扫描 在这种方式下 由某一个结点出发 只能找到它的后件 而为了找出它的前件 必须从头指针开始重新寻找 61 61 为了弥补线性单链表的这个缺点 在某些应用中 对线性链表中的每个结点设置两个指针 一个称为左指针 Llink 用以指向其前件结点 另一个称为右指针 Rlink 用以指向其后件的结点 这样的线性链表称为双向链表 其逻辑状态如图2 23所示 教材图1 91 62 循环链表的结构与前面所讨论的线性链表相比 具有以下两个特点 循环链表的头指针指向表头结点 在循环链表中 所有结点的指针构成了一个环状链 图2 29是循环链表的示意图 循环链表 62 63 在实际应用中 循环链表与线性单链表相比主要有以下两个方面的优点 在循环链表中 只要指出表中任何一个结点的位置 就可以从它出发访问到表中其他所有的结点 由于在循环链表中设置了一个表头结点 因此 在任何情况下 循环链表中至少有一个结点存在 从而使空表与非空表的运算统一 64 链表不具有的特点是 B A 不必事先估计存储空间B 可随机访问任一元素C 插入删除不需要移动元素D 所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构 线性链表属于 1 答案 存储结构线性表的顺序存储结构和线性表的链式存储结构分别是 B A 顺序存取的存储结构 顺序存取的存储结构B 随机存取的存储结构 顺序存取的存储结构C 随机存取的存储结构 随机存取的存储结构D 任意存取的存储结构 任意存取的存储结构 线性链表的例题讲解 64 5 栈 栈是一种特殊的线性表 它们是运算时要受到某些限制的线性表 故也称为限定性的数据结构 栈的定义 栈 限定只能在表的一端进行插入和删除的特殊的线性表 这种结构称为后进先出 设栈s a1 a2 ai an 其中a1是栈底元素 an是栈顶元素 栈顶 top 允许插入和删除的一端 约定top始终指向新数据元素将存放的位置 栈底 bottom 不允许插入和删除的一端 65 66 栈的演示 A B C D E 67 栈 存储结构顺序存储结构带链的栈基本运算入栈运算退栈运算读栈顶元素 68 举例 1 栈底至栈顶依次存放元素A B C D 在第五个元素E入栈前 栈中元素可以出栈 则出栈序列可能是 A ABCED B DBCEA C CDABE D DCBEA2 设一个栈的输入序列为A B C D 则借助一个栈所得到的输出序列不可能是 A A B C D B D C B A C A C D B D D A B C 队列的定义 队列 一种特殊的线性结构 限定只能在表的一端进行插入 在表的另一端进行删除的线性表 此种结构称为先进先出 FIFO 表 a1 a2 a3 an 1 an 队列示意图 队头 队尾 69 出队 入队 rear front 70 队列的存储结构 顺序存储结构循环队列考点 循环队列中元素的个数 r f m m带链的队列 71 循环队列及其运算 循环队列 将队列存储空间的最后一个位置绕到第一个位置 形成逻辑上的环状空间 供队列循环使用 循环队列的元素 从排头指针指向的后一个位置直到队尾指针指向的位置之间所有的元素 说明 为了能够区分队列满与空 设置一个标志s 71 队列空与满的条件 队列空时 s 0 队列满时 s 1且front rear 72 循环队列 元素个数 r f m m 73 1 插入一个新的队尾元素 称为入队 2 删除队头元素 称为退队 队列的主要运算 栈和队列的例题讲解 栈和队列的共同特点是 C A 都是先进先出B 都是先进后出C 只允许在端点处插入和删除元素D 没有共同点如果进栈序列为e1 e2 e3 e4 则可能的出栈序列是 B A e3 e1 e4 e2B e4 e3 e2 e1C e3 e4 e1 e2D 任意顺序一些重要的程序语言 如C语言和Pascal语言 允许过程的递归调用 而实现递归调用中的存储分配通常用 A A 栈B 堆C 数组D 链表 74 栈底至栈顶依次存放元素A B C D 在第五个元素E入栈前 栈中元素可以出栈 则出栈序列可能是 B A ABCEDB DCBEAC DBCEAD CDABE栈通常采用的两种存储结构是 A A 顺序存储结构和链表存储结构B 散列方式和索引方式C 链表存储结构和数组D 线性存储结构和非线性存储结构栈和队列通常采用的存储结构是 1 答案 链式存储和顺序存储下列数据结构中 按先进后出原则组织数据的是 B A 线性链表B 栈C 循环链表D 顺序表 75 当循环队列非空且队尾指针等于队头指针时 说明循环队列已满 不能进行入队运算 这种情况称为 2 答案 上溢由两个栈共享一个存储空间的好处是 B A 减少存取时间 降低下溢发生的机率B 节省存储空间 降低上溢发生的机率C 减少存取时间 降低上溢发生的机率D 节省存储空间 降低下溢发生的机率下列关于栈的叙述中正确的是 D 在栈中只能插入数据B 在栈中只能删除数据C 栈是先进先出的线性表D 栈是后进先出的线性表下列关于队列的叙述中正确的是 C 在队列中只能插入数据B 在队列中只能删除数据C 队列是先进先出的线性表D 队列是后进先出的线性表 76 77 7 树与二叉树 树的基本概念 前面我们讨论的线性表 栈 队列和数组等都是线性结构 而树是一种非线性数据结构 它的每一个结点 都可以有不止一个直接后继 除根外的所有结点 都有且只有一个直接前趋 这些数据结点按分支关系组织起 清晰地反映了数据元素之间的层次关系 78 数据结构的主要研究问题 78 79 现实世界中 能用树的结构表示的例子 学校的行政关系 P31 书的层次结构 P32 人类的家族血缘关系等 80 80 例 下图是一个有13个结点的树 其中A是根 其余结点为分三个互不相交的子集 子树 T1 B E F K L T2 F G T3 D H I J M T1 T2和T3都是根A的子树 81 81 树结构的基本术语 结点的度 结点所拥有子树的个数 图中A的度为3 C的度为1 F的度为0 叶子结点 树中度为0的结点 图中的K L F G M I J均称为叶子结点 或终端结点 子结点与父结点 把每一个结点的一个或多个后件称为该点的子结点 反之 这个结点称为其子结点的父结点 同一个父结点的子结点之间互称为兄弟 树的度 树中各结点的度的最大值 度不为0的结点为非终端结点同 又叫分支结点 结点的层次 根结点在第一层 同一层上左右结点的子结点都在下一层 A为第一层 B C D为第二层 树的深度 树中结点的最大层次称为树的深度或高度 图中树的深度为4 二叉树是一种很有用的非线性结构 二叉树具有以下两个特点 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 二叉树 BinaryTree 因为树的每个结点的度不同 存储困难 使得对树的处理算法很复杂 所以引出二叉树的讨论 82 83 83 84 性质1 二叉树的第k层上至多有2k 1 k 1 个结点 二叉树的性质 第一层 k 1 有21 1 1个节点 第二层 k 2 有22 1 2个节点 第三层 k 3 有23 1 4个节点 第四层 k 4 有24 1 8个节点 85 二叉树的性质 性质2 深度为m的二叉树中至多含有2m 1个结点 此树的深度m 4 共有24 1 15个结点 1 2 4 2m 1 2m 1 等比数列前M项和 性质3 在任意一棵二叉树中 度为0的结点 即叶子结点 总是比度为2的结点多一个 即n0 n2 1例子1 某二叉树中度为2的结点有18个 则该二叉树中有19个叶子结点 二叉树的性质 a a b b 两棵不同的二叉树 86 87 二叉树的性质 性质4 具有n个结点的二叉树 其深度不小于 log2n 1 其中 log2n 为log2n的整数部分 此树的深度m至少为4层 n 15 log2n 3 9069 log2n 3 88 满二叉树与完全二叉树 满二叉树是指除最后一层外 每一层上的所有结点都有两个子结点 完全二叉树是指这样的二叉树 除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 注意 满二叉树是完全二叉树 完全二叉树不一定是满二叉树 89 满二叉树的特点 每一层上都含有最大结点数 89 90 完全二叉树的特点 除最后一层外 每一层都取最大结点数 最后一层结点都集中在该层最左边的若干位置 90 91 91 92 完全二叉树的性质 性质1 具有n个结点的完全二叉树的深度为 log2n 1 其中 log2n 为log2n的整数部分 此树的深度为m 4层 n 13 log2n 3 7004 log2n 3 93 完全二叉树的性质 性质2 完全二叉树中度为1的结点数为0或1 n1 1n1 0 94 对于完全二叉树而言如果它的结点个数为偶数 则该二叉树中 叶子结点的个数 非叶子结点的个数如果它的结点个数为奇数 则该二叉树中 叶子结点的个数 非叶子结点的个数 1 即叶子结点数比非叶子结点数多一个 规律总结 2叶子结点32非叶子结点2 95 完全二叉树的性质 性质3 略 96 普通二叉树采用链式存储结构存储结点由两部分组成 数据域与指针域两个指针域 左指针域右指针域满二叉树与完全二叉树一般采用顺序存储结构 二叉树的存储结构 二叉树的遍历 每年都考 二叉树的遍历是指不重复地访问二叉树中的所有结点 这里的 访问 是指对结点进行某些操作 如打印输出 修改结点的数据信息等 二叉树的遍历可以分为三种 前序遍历 中序遍历 后序遍历 设访问根结点记作V 遍历根的左子树记作L 遍历根的右子树记作R 前序 VLR 即根左右 中序 LVR 即左根右 后序 LRV 即左右根 97 98 98 41089526731 例 结合下图所示的二叉树 写出该二叉树的前序 中序及后序遍历结果 后序遍历 中序遍历 前序遍历 12458109367 42108591637 99 例题讲解 1 设一棵完全二叉树共有700个结点 则在该二叉树中有350个叶子结点 2 在深度为5的满二叉树中 叶子结点的个数为 C A 32B 31C 16D 15 100 3 设一棵二叉树的中序遍历结果为DBEAFC 前序遍历结果为ABDECF 则后序遍历结果为 DEBFCA 例题讲解 4 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF 则该二叉树的后序遍历为 B A GEDHFBCAB DGEBHFCAC ABCDEFGHD ACBFEDHG 5 具有3个结点的二叉树有 D A 2种形态B 4种形态C 7种形态D 5种形态6 设有下列二叉树 对此二叉树前序遍历的结果为 B A ZBTTCPXAB ATBZXCTPC ZBTACTXPD ATBZXCPT 101 102 8 查找和排序 查找 又称为检索定义 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素 查找算法的评价主要考虑算法的时间复杂性 既可采用数量级的形式表示 也可采用平均检索 查找 长度 即在查找成功情况下的平均比较次数来表示查找可分为顺序查找和二分法查找两种 103 a 顺序查找 顺序查找又称线性查找 它是一种最简单 最基本的查找方法 基本思想是 从表中第一条记录开始 逐个进行记录的关键字和给定值的比较 若某个记录的关键字和给定值相等 则查找成功 否则 若直至最后一个记录 其关键字和给定值都不相等 则表明表中没有所查记录 查找不成功 12 32 25 104 二分查找又称折半查找 作为二分查找对象的表必须是顺序存储的有序表 即各记录的次序是按其关键字的大小顺序排列的表 b 二分查找 105 二分查找的具体做法是 先取表中间位置的记录关键字与给定值比较 若相等 则查找成功 否则 若给定值比该记录的关键字小 则给定值必在表的前半部分 在这前半部分中再取中间位置记录的关键字进行比较 就又可以排除这部分的一半 依次反复进行 直到找到给定值或找完全表而找不到为止 对于n较大时 查找长度可以近似地表示为 例 在递增有序表中查找元素22过程 106 排序是将一组杂乱无章的数据按一定的规律顺次排列起来 通常数据对象有多个属性域 即由多个数据成员组成 其中有一个属性域可用来区分对象 作为排序依据 该域称为关键字 key 排序的时间开销是衡量算法好坏的最重要的标志 对于长度为n的有序线性表 查找时最坏情况只需比较n次 排序 sort 107 a 交换类排序 交换类排序法 冒泡排序法 需要比较的次数为n n 1 2快速排序法 需要比较的次数为n n 1 2 108 b 插入类排序 插入类排序的基本方法是 每步将一个待排序的对象 按其关键字大小 插入到前面已经排好序的一组对象的适当位置上 直到对象全部插入为止 简单插入排序法 最坏情况需要n n 1 2次比较 希尔排序法 最坏情况需要O n1 5 次比较 109 c 选择类排序 选择类排序的思想是 每一趟 例如 第i趟 i 0 1 n 2 在后面n i个待排序对象中选出关键字最小 升序 若为降序 选出最大关键字 的对象 作为有序对象序列的第i个对象 待到第n 2趟作完 待排序对象只剩下1个 不用再选了 结束排序 简单选择排序法 最坏情况需要n n 1 2次比较 堆排序法 最坏情况需要O nlog2n 次比较 110 课后总复习 返回 111 从右图我们可以看出每条边对应一个结点只有根结点没有相应的边因此 结点数 边数 1 20 设树T的度为4 其中度为1 2 3 4的结点个数分别为4 2 1 1 则T中的叶子结点数为 一个度为4的结点有4条出边 一个度为3的结点有3条出边一个度为2的结点有2条出边 一个度为1的结点有1条出边叶子结点没有出边 所以 边数 N 1 4 2 2 3 1 4 1 15而结点数 边数 1 16叶子结点数 16 4 2 1 1 8 112 15 设一棵二叉树的中序遍历结果为DBEAFC 前序遍历结果为ABDECF 则后序遍历结果为 前序遍历特点 A为根结点中序遍历特点 DBE为左子树 FC为右子树 A B D E C F 前序遍历左子树BDE B为根中序遍历特点 D为左子树 E为右子树 FC右子树前序遍历右子树CF C为根中序遍历特点 F为左子树 则后序遍历的结果为 DEBFCA 113 第二章程序设计基础 二级公共基础知识 返回 114 内容1 程序设计方法与风格2 结构化程序设计3 面向对象的程序设计方法 对象 方法 属性及继承与多态性 115 一 程序设计方法与风格 如何形成良好的程序设计风格 1 源程序内部文档化 选择标识符的名字注释 序言性和功能性注释 程序的视觉组织 一般位于模块的首部 用于说明模块的相关信息 位于源程序模块内部 方法 结构化和面向对象程序设计风格 清晰第一 效率第二 116 显式地说明一切变量数据说明的次序应该规范化便于查找变量 按顺序排列 对复杂数据结构应注释说明 2 数据说明 3 语句的结构 每条语句简单明了限制GOTO语句的使用 尽量不用或少用 尽量只采用3种基本控制结构编程 顺序 选择 循环 4 输入和输出 对所有输入数据进行校验和合理性检查输入输出格式保持一致设计良好的输出报表 输入方式应力求简单 尽量避免给用户带来不必要的麻烦 交互式输入数据时应有必要的提示信息 程序应对输入数据的合法性进行检查 若用户输入某些数据后可能产生严重后果 应给用户输出必要的提示并要求用户确认 应根据系统的特点和用户的习惯设计出令用户满意的输入方式 输出数据的格式应清晰 美观 输出数据时要加上必要的提示信息 117 118 主要思想 对大型的程序设计 使用一些基本的结构来设计程序 无论多复杂的程序 都可以使用这些基本结构按一定的顺序组合起来 这些基本结构的特点都是只有一个入口 一个出口 由这些基本结构组成的程序就避免了任意转移 阅读起来需要来回寻找的问题 二 结构化程序设计 三种基本结构的特点只有一个入口只有一个出口基本结构中的每一部分都有机会执行到结构内不存在 死循环 三种基本结构顺序结构选择结构循环结构 119 设计原则1 模块化2 自顶向下3 逐步求精4 限制使用goto语句 二 结构化程序设计 结构化程序设计方法1 要求把程序的结构规定为顺序 选择和循环三种基本机构 并提出了自顶向下 逐步求精 模块化程序设计等原则 2 结构化程序设计是把模块分割方法作为对大型系统进行分析的手段 使其最终转化为三种基本结构 其目的是为了解决由许多人共同开发大型软件时 如何高效率地完成可靠系统的问题 3 程序的可读性好 可维护性好成为评价程序质量的首要条件 4 缺点 程序和数据结构松散地耦合在一起 解决此问题的方法就是采用面向对象的程序设计方法 OOP 120 三 面向对象的程序设计方法 面向对象的程序设计 Object OrientedProgramming OOP 是一种把面向对象的思想应用于软件开发过程中 指导开发活动的系统方法 简称OOP方法 它是建立在对象概念 对象 类和继承 基础上的方法 121 面向对象程序设计方法的优点1 与人类习惯的思维方法一致2 稳定性好3 可重用性好 提高软件生产率最主要的方法 4 易于开发大型软件产品5 可维护性好 面向对象的程序设计以对象为核心 强调对象 抽象性 封装性 继承性 多态性 122 基本概念对象 Object 对象用来表示客观世界中的任何实体 它既包括数据 属性 也包括作用于数据的操作 行为 一个对象把属性和行为封装为一个整体 一个对象通常可由对象名 属性和操作3部分组成 属性 通常是一些数据 有时它也可以是另一个对象 事件 是由对象识别的一个动作 用户可以编写相应代码对此动作进行响应 如单击 双击 移动等 方法 对象中的属性只能通过该对象所提供的操作来存取或修改 面向对象 ObjectOriented OO 从该问题所涉及的对象入手来研究问题 123 对象的基本特点标识唯一性分类性多态性封装性模块独立性 124 类 Class 类是一组具有相同属性和相同操作 方法 的对象的集合 一个类定义了一组大体上相似的对象 一个类所包含的方法和数据描述一组对象的共同行为和属性 类是在对象之上的抽象 对象是类的具体化 是类的实例 125 消息 Message 消息是一个实例与另一个对象之间传递的信息 它请求对象执行某一处理或回答某一要求的信息 它统一了数据流和控制流 或者说一个对象通过向另一对象发送信息来请求其服务 126 多重继承图 继承 指能够直接获得已有的性质和特征 不必重复地定义它们单继承 指一个类只允许有一个父类多重继承 指一个类允许有多个父类 127 继承的优点可以共享程序代码和数据结构 减少程序中的冗余信息 提高软件的可重用性 便于软件修改维护 多态性 Polymorphism 不同的对象收到同一消息可以产生完全不同的行为 这一现象叫做多态性多态性机制显著提高了软件的可重用性和可扩充性 128 四 例题讲解 结构化程序设计的3种结构是 D A 顺序结构 选择结构 转移结构B 分支结构 等价结构 循环结构C 多分支结构 赋值结构 等价结构D 顺序结构 选择结构 循环结构在设计程序时 应采纳的原则之一是 D A 不限制goto语句的使用B 减少或取消注解行C 程序越短越好D 程序结构应有助于读者理解 129 结构化程序设计主要强调的是 D A 程序的规模B 程序的效率C 程序设计语言的先进性D 程序易读性以下不属于对象的基本特点的是 C A 分类性B 多态性C 继承性D 封装性 130 对建立良好的程序设计风格 下面描述正确的是 A A 程序应简单 清晰 可读性好B 符号名的命名只要符合语法C 充分考虑程序的执行效率D 程序的注释可有可无在结构化程序设计思想提出之前 在程序设计中曾强调程序的效率 现在 与程序的效率相比 人们更重视程序的 C A 安全性B 一致性C 可理解性D 合理性 131 下列叙述中 不属于结构化程序设计方法的主要原则的是 B A 自顶向下B 由底向上C 模块化D 限制使用goto语句对象实现了数据和操作的结合 是指对数据和数据的操作进行 C A 结合B 隐藏C 封装D 抽象在面向对象方法中 一个对象请求另一个对象为其服务的方式是通过发送 D A 调用语句B 命令C 口令D 消息 132 信息隐蔽的概念与下述哪一种概念直接相关 B A 软件结构定义B 模块独立性C 模块类型划分D 模块耦合度下列对对象概念描述错误的是 A A 任何对象都必须有继承性B 对象是属性和方法的封装体C 对象间的通讯靠消息传递D 操作是对象的动态属性 面向对象的设计方法与传统的面向过程的方法有本质的不同 它的基本原理是 C A 模拟现实世界中不同事物之间的联系B 强调模拟现实世界中的算法而不强调概念C 使用现实世界的概念抽象地思考问题从而自然地解决问题D 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考在面向对象的程序设计中 类描述的是具有相似性质的一组 1 答案 对象在面向对象方法中 类之间共享属性和操作的机制称为 2 答案 继承一个类可以从直接或间接的祖先中继承所有属性和方法 采用这个方法提高了软件的 3 答案 可重用性 134 在面向对象的模型中 最基本的概念是对象和 4 答案 类在面向对象的设计中 用来请求对象执行某一处理或回答某些信息的要求称为 5 答案 消息在程序设计阶段应该采取 6 和逐步求精的方法 把一个模块的功能逐步分解 细化为一系列具体的步骤 进而用某种程序设计语言写成程序 答案 自顶向下 7 是一种信息隐蔽技术 目的在于将对象的使用者和对象的设计者分开 答案 封装源程序文档化要求程序应加注释 注释一般分为序言性注释和 8 答案 功能性注释在面向对象方法中 信息屏蔽是通过对象的 9 性来实现的 答案 封装类是一个支持集成的抽象数据类型 而对象是类的 10 答案 实例在面向对象方法中 类之间共享属性和操作的机制称为 11 答案 继承 136 第三章软件工程基础 二级公共基础知识 返回 137 问题 软件分析 软件设计 软件测试 软件调试 2 各个阶段该做些什么 有些什么样的方法和工具 3 什么是软件工程 为什么提出软件工程的概念 1 软件开发的步骤 138 内容1 软件工程基本概念 软件生命周期概念 软件工具与软件开发环境 2 结构化分析方法 数据流图 数据字典 软件需求规格说明书 3 结构化设计方法 总体设计与详细设计 4 软件测试的方法 白盒测试与黑盒测试 测试用例设计 软件测试的实施 单元测试 集成测试和系统测试 5 程序的调试 静态调试与动态调试 139 一 基本概念 软件 1 机器可执行的程序和数据2 与软件开发 运行 维护 使用等有关的文档计算机软件是由程序 数据及相关文档构成的完整集合 软件特点 软件是一种逻辑实体 具有抽象性 软件没有明显的制作过程 使用期间不存在磨损 老化问题 对硬件和环境具有依赖性 软件复杂度高 成本昂贵 软件开发涉及诸多的社会因素 140 软件分类 应用软件事务处理软件 工程与科学计算软件 实时处理软件 嵌入式软件 人工智能软件 Word QQ 迅雷系统软件操作系统 编译程序 汇编程序 网络软件 数据管理系统支撑软件 工具软件 需求分析工具软件 设计工具软件 编码工具软件 测试工具软件 维护工具软件 Delphi PowerBuilder 141 二 软件危机与软件工程 软件危机 是指在计算机软件开发和维护过程中所遇到的一系列严重的问题 1 需求增长得不到满足2 开发成本和进度无法控制3 质量难以保证4 开发生产率的提高赶不上硬件的发展和应用需求的增长主要表现在 成本 质量 生产率等问题 142 二 软件危机与软件工程 软件工程 软件工程是指应用计算机科学 数学及管理科学等原理 以工程化的原则和方法来解决软件问题的工程 其目的是提高软件生产率 提高软件质量 降低软件成本 方法 完成软件工程项目的技术手段 工具 支持软件的开发 管理 文档生成 过程 支持软件开发的各个环节的控制 管理 软件工程三要素 143 二 软件工程过程与软件生命周期 软件工程过程 把用户的要求转变成软件产品的过程叫做软件开发过程四种基本活动PlanDoCheckAction 软件生命周期将软件产品从提出 实现 使用维护到停止使用退役的过程称为软件生命周期 分为软件定义 软件开发及软件运行维护3个时期 维护是持续时间最长 花费代价最大的一个时期 软件工程学的一个目的就是提高软件的可维护性 降低维护代价 几个活动阶段 可行性研究需求分析概要设计详细设计 实现测试运行和维护 软件工程的目标在给定的成本 进度的前提下 开发出具有有效性 可靠性 可理解性 可维护性 可适应性 可移植性 可追踪性和可互操作性且满足用户需求的产品 软件工程鼓励研制和采用各种先进的软件开发方法 工具和环境 软件工程的理论和技术研究的内容软件开发技术和软件工程管理 146 抽象确定性模块化信息隐藏 软件工程的原则 局部化完备性一致性可验证性 147 软件开发工具和软件开发环境软件开发工具 用来辅助软件开发 运行 维护 管理 支持等过程中的活动的软件 软件开发环境 支持软件产品开发的软件系统 它由软件工具和环境集成机制构成 148 二 软件分析及其方法 一 需求分析软件需求是指用户对目标软件系统在功能 行为 性能 设计约束等方面的期望 要做的工作需求获取 需求分析 编写需求规格说明书 需求评审需求分析方法结构化分析方法 xx 面向对象的分析方法 149 二 结构化分析方法 基本思想将系统分析看成工程项目 有计划 有步骤地进行工作 开发策略面向数据流 自顶向下 逐步求精 150 二 结构化分析的常用工具 数据流图数据流图的4种基本的图形符号P49数据字典数据字典是结构化分析方法的核心判定树判定表 151 二 软件需求规格说明书 是需求分析阶段得出的最主要的文档作为确认测试和验收的依据软件需求规格说明书应具有完整性 无歧义性 正确性 可验证性 可修改性等特性 其中最重要的是无歧义性 152 三 软件设计 重要性占据软件项目开发总成本大部分 保证软件质量的关键软件设计作出的决策 最终影响软件实现的成败软件设计是软件工程和软件维护的基础过程概要设计和详细设计 153 软件设计 基本原理模块化抽象信息隐藏和局部化模块独立性 高内聚 低耦合 154 结构化设计方法概要设计 任务 设想供选择的方案选取合理的方案推荐最佳方案功能分解设计软件结构设计数据库制定测试计划书写文档 155 概要设计设计工具结构图 程序结构图 的基本图符P55面向数据流的设计方法数据流类型 变换型和事务型 156 概要设计设计原则提高模块独立性规模适中信息屏蔽 抽象的原则一致性原则明确性原则模块间的耦合度尽可能小 模块内部组合尽可能紧凑 内聚性高 模块的扇入和扇出系数合理模块的规模适当 157 详细设计任务 为软件结构图中的每一个模块确定实现算法和局部数据结构 用某种选定的表达工具表示算法和数据结构的细节 工具 程序流程图 基本图符P58 N S图PAD图表格工具语言工具 158 四 软件测试 意义目的为了发现错误 希望能以最少人力和时间发现潜在各种错误和缺陷 保证系统质量和可靠性的关键步骤 测试方法人工测试机器测试 提问 测试能否发现程序中的所有错误 答案 不能 159 软件测试的