C语言课程课件 二级C语言等级考试 公共基础知识 part2

第1页知识点复习：先（前）序遍历（DLR）根左右中序遍历（LDR）左根右后序遍历（LRD）左右根uu 二叉树的性质：二叉树的性质： 在二叉树的第i层上最多有2i-1个结点二叉树上叶子结点数比度为2的结点数多1uu 二叉树的遍历：二叉树的遍历：第2页u 设有下列二叉树：对此二叉树前序遍历的结果为 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPTu 设有下列二叉树：对此二叉树的中序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA第3页排序方法插入排序选择排序交换排序归并排序简单插入排序 希尔排序简单选择排序 堆排序起泡排序快速排序第4页1.7.2.2 插入排序 简单插入、希尔排序1、简单插入排序: 基本思想：从数组的第2号元素开始，顺序 从数组中取出元素，并将该元素插入到其左端 已排好序的数组的适当位置上。第5页待排元素序列：53 27 36 15 69 42第一次排序： 27 53 36 15 69 42第二次排序： 27 36 53 15 69 42第三次排序： 15 27 36 53 69 42第四次排序： 15 27 36 53 69 42第五次排序： 15 27 36 42 53 69 直接插入排序示例对于有n个数 据元素的待排 序列，插入操 作要进行n-1 趟最坏情况下：需要n(n-1)/2次比较 最好：n-1次比较第6页希尔排序：希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体 记录进行一次直接插入排序.最坏情况下：需要O(n1.5 )次比较(O代表不超过括号内数值 的最大整数值。)第7页1、简单选择排序 思想：首先从1n个元素中选出关键字最小的记录交换 到第一个位置上。然后再从第2 个到第n个元素中选出次 小的记录交换到第二个位置上，依次类推。1.7.2.3 选择排序 简单选择排序、堆排序简单选择排序法, 最坏情况需要n(n-1)/2次比较； 第8|92页n初态： 15，14，22，30，37，15，11n第一趟： 11 14，22，30，37，15，15n第二趟： 11，14 22，30，37，15，15n第三趟： 11，14，15 30，37，22，15n第四趟： 11，14，15，15 37，22，30n第五趟： 11，14，15，15，22 37，30n第六趟： 11，14，15，15，22，30 37有序序列例：设待排数据元素的关键字为（15，14，22，30 ，37，11），每一趟排序后的序列状态如图所示：第9页2、堆排序（也是一种选择排序）堆是具有特定条件的顺序存储的完全二叉树897624331510112536497856(a):堆顶元素取最大值(b):堆顶元素取最小值堆排序需要比较的 次数为O(nlog2n)(1) 堆的示例 第10页1.7.2.4 交 换 排 序交换排序的特点在于交换。有冒泡和快速排序两种。 1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较， 大则交换，关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上；依次类推，则完成排序。第11页冒泡排序冒泡排序 u 冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比较，若 为逆序，则交换；第一趟扫描的结果使最大(或最小)的 元素排到表的最后(或最前) ；n除最后(或最前)一个元素，对剩余的元素重复上述过程 ，将次大(或次小)的数排到表的倒数(或正数)第二个位置；n重复上述过程；n对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。 第12页初始 第一趟 第二趟 第三趟 第四趟 第五趟 序列 排序后 排序后 排序后 排序后 排序后 26 18 18 18 18 9 18 26 26 26 9 15 32 32 32 9 15 18 54 47 9 15 26 47 9 15 32 9 15 47 15 54设待排数据元素的关键字为（ 26,18,32,54,47,9,15 )冒泡排序法，需要比较的次数为n(n-1)/2； 第13页2、快速排序 (对冒泡排序的改进）思想：通过一趟排序将待排序列分成两部分， 使其中一部分记录的关键字均比另一部分小，再分 别对这两部分排序，以达到整个序列有序。时间复杂度：O(log2n) 当待排序列逆序时，蜕变成冒泡排序，时间复杂度: O(n(n-1)/2)第14|92页排序法小结：排序法小结：u 简单选择排序法, 最坏情况需要n(n-1)/2次比较；u 冒泡排序法, 最坏情况需要n(n-1)/2次比较；u 希尔排序法, 最坏情况需要O(n1.5)次比较；u 堆排序法, 最坏情况需要O(nlog2n)次比较；u 快速排序, 最坏情况需要n(n-1)/2次比较；第15|92页排序查找方面的考题：排序查找方面的考题：(1) 对对于长长度为为n的线线性表，在最坏情况下，下列各排序法所对应对应 的比较较次数中正确 的是（2005年4月）A) 冒泡排序为为n/2 B) 冒泡排序为为nC) 快速排序为为n D) 快速排序为为n(n-1)/2 (2) 下列排序方法中，最坏情况下比较较次数最少的是（09年3月） A）冒泡排序 B）简单选择简单选择 排序C）直接插入排序 D）堆排序DD第16页2.程序设计基础第17页第二章第二章 程序设计基础程序设计基础内容内容： 1. 程序设计方法与风格。 2. 结构化程序设计。 3. 面向对象的程序设计方法，对象，方法，属 性及继承与多态性。第18页1. 源程序的文档化n符号的命名:见名知意n注释（序言性和功能性注释）n程序的视觉组织:空格、空行、缩进。 2. 数据说明n数据说明的次序应该规范化n变量安排有序化n对复杂数据结构应注释说明 3. 语句的结构n每条语句简单明了n尽量不用或少用GOTO语句n尽量只采用3种基本控制结构编程 4. 输入和输出n对所有输入数据进行校验和合理性检查n输入输出格式保持一致n设计良好的输出报表清晰第一，效率第二2.1.2 程序设计风格第19页第20页2.2 结构化程序设计2.2.1 基本概念u 三种基本结构n顺序结构n选择结构n循环结构 u 三种基本结构的特点n只有一个入口n只有一个出口n每一个基本结构中的每一部分都有机会执行到n结构内不存在“死循环”第21页2.2.2 设计原则n自顶向下（先总体，后细节）n逐步求精（设计子目标过渡）n模块化 （分解总目标）n限制使用goto语句结构化程序设计方法特点n要求把程序的结构规定为顺序、选择和循环三种基本机构，并 提出了自顶向下、逐步求精、模块化程序设计等原则。第22页2.3.2 基本概念 u 对象(Object)n对象是系统中用来描述客观事物的一个实体，是构成系统 的一个基本单位，它既包括数据（属性），也包括作用于 数据的操作（行为）。n一个对象把属性和行为封装为一个整体n一个对象通常可由对象名、属性和操作3部分组成n属性即对象所包含的信息n操作描述了对象执行的功能，操作也称为方法或服务。2.3 面向对象的程序设计第23页u 主要优点n与人类习惯的思维方法一致n稳定性好n可重用性好（*）n可维护性好n易于开发大型软件产品n对象的基本特性：（1）标识唯一性 （对象可区分）（2）分类性 （对象抽象成类）（3）多态性 （同一操作可以是不同对象的行为）（4）封装性 （只能看到对象的外部特性）信息隐蔽性是通过对象 的封装性来实现的。（5）模块独立性好（对象内部各元素结合紧密、内聚性强）第24页u 结构化程序设计的3种结构是A) 顺序结构、选择结构、转移结构 B) 分支结构、等价结构、循环结 构C) 多分支结构、赋值结构、等价结构 D) 顺序结构、选择结构、循环结 构u 在设计程序时，应采纳的原则之一是A) 不限制goto语句的使用 B) 减少或取消注解行C) 程序越短越好 D) 程序结构应有助于读者理解u 程序设计语言的基本成分是数据成分、运算成分、控制成分和A) 对象成分B) 变量成分C) 语句成分D) 传输成分例题讲解第25页u 结构化程序设计主要强调的是 A) 程序的规模B) 程序的效率C) 程序设计语言的先进性 D) 程序易读性 u 以下不属于对象的基本特点的是A) 分类性 B) 多态性 C) 继承性D) 封装性 u 对建立良好的程序设计风格，下面描述正确的是A) 程序应简单、清晰、可读性好 B) 符号名的命名只要符合语法C) 充分考虑程序的执行效率 D) 程序的注释可有可无 u 在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率， 现在，与程序的效率相比，人们更重视程序的A) 安全性B) 一致性 C) 可理解性D) 合理性 u 对象实现了数据和操作的结合，是指对数据和数据的操作进行A) 结合 B) 隐藏 C) 封装 D) 抽象第26页3.软件工程基础u 软件工程n软件工程是应用于计算机软件的定义、开发 和维护的一整套方法、工具、文档、实践标 准和工序。n其目的是提高软件生产率、提高软件质量、 降低软件成本。n它所包含的内容有以下两方面：n 软件开发技术 主要有软件开发方法学、 软件工具、软件工程环境。n 软件工程管理 主要有软件管理、软件工 程经济学。第27页第28页软件生命周期n将软件产品从提出、实现、使用、维护到 停止使用退役的过程称为软件生命周期n分为软件 定义、软件开发及软件运行维护 3个阶段。n维护是持续时间最长，花费代价最大的一 个阶段，软件工程学的一个目的就是提高 软件的可维护性，降低维护代价。n6个活动阶段n制定计划：确定系统的总体目标。 参加人员有用户、项目负责人和系统分析员，产生文档有可行 性分析报告、项目计划书等n需求分析：对开发软件提出的需求进行分析并给出详细定 义。n软件设计：分为概要设计和详细设计。n软件实现：编程。高级程序员和程序员产生源程序清单n软件测试：在设计测试用例的基础上，检验软件的各个组 成部分。产生软件测试计划和软件测试报告n运行与维护第29页第30页制定计划需求分析软件设计实现测试运行和维护确定系统的总体目标需求规格说明书概要设计说明书 详细设计说明书 测试计划初稿完成程序代码 用户手册 单元测试计划检验软件 测试分析报告制定计划需求分析概要设计实现测试退役详细设计使用维护定义阶段开发阶段维护阶段第31页需求分析与结构化分析