大学计算机第四章.ppt
《大学计算机第四章.ppt》由会员分享,可在线阅读,更多相关《大学计算机第四章.ppt(69页珍藏版)》请在三一文库上搜索。
1、第四章 软件基础 第2页 计算机二级考试公共基础知识 q 基本数据结构与算法(教材4.2节) q 程序设计基础 q 软件工程基础 q 数据库设计基础(教材第8章自学) 二级考试科目分成二级语言程序设计(C、C、Java、Visual Basic)和二级数据库程序设计(Visual FoxPro、Access)两类。 公共基础知识在各科笔试中的比重为30% (教材4.1节自学) 第3页 算法算法 算法的基本概念 算法的表示 常用算法 算法的评价 一、基本数据结构与算法一、基本数据结构与算法 数据结构数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术 第4页 对对解题方案准
2、确而完整的描述解题方案准确而完整的描述称为算法。 称为算法。 程序用计算机语言描述的算法 流程图图形化的算法(机械图) 算法是程序设计的核心 算法的基本概念算法的基本概念 INPUT r S=r*r*3.14 PTINT S 开始 输入 R S=R*R*3.14 输出S 结束 问题: 输入园的半径, 计算园的面积 起止框 输入输出框 处 理 框 第5页 算法分为两类: uu 数值计算数值计算算法算法 n 求数值解 n 特点:少量的输入、输出,复杂的运算 uu 非数值计算非数值计算算法算法 n 数据处理 n 特点:大量的输入、输出,简单的运算 第6页 算法的两个要素: 操作操作 n 算术运算 n
3、 关系运算 n 逻辑运算 n 数据传输 控制结构控制结构 n 顺序 n 选择 n 循环 第7页 算法的基本特征 是一组严谨地定义运算顺序的规则,每一个规则都是有效 的,是明确的,此顺序将在有限的次数下终止。 n 有穷性 n 确定性 n 可行性 n 输入 n 输出 算法在执执行有穷穷步骤骤后结结束,且每一步都能在 有限时间时间 内完成。 算法中的每一步操作的内容和顺顺序必须须含义义确 切,不能有二义义性。 算法中的每一步操作都必须须是可执执行的,也称 之为为有效性。 算法中有零个或多个输输入。这这些输输入数据应应在 算法操作前提供。 算法的目的是用来解决一个给给定的问题问题 ,因此 ,它应应向人
4、们们提供产产生的结结果。 拥有足够的情报 第8页 算法的表示算法的表示 描述算法的方法有多种: n自然语言 n传统流程图 nN-S流程图 n伪代码 n计算机语言 第9页 A CB 变量C是一个 临时工作单元 ,用来保存中 间结果。 算法举例算法举例 两个变量的值交换 有红、蓝两个墨水瓶,要求将其互换。 C=B B=A A=C 高级语言 语句实现 第一步 第二步 第三步 第10页 计数器和累加器 计数器计数器 ( ( 统计入场人数统计入场人数 ,超过,超过100100人结束人结束 ) ) i=i+1i=i+1 累加器累加器 sum=sum+x 进入一个人 i=0) A BD FE C GHI J
5、KM n 根:only one n 若n=0,则称为空树; n 否则,当n1时,其余结 点被分成m(m0)个互不相交 的子集T1,T2,.,Tm, 每个子集又是一棵树。由此 可以看出,树的定义是递归 的。 n Question:如何辨别根? A 只有一个 结点的树 第40页 树型结构的常用术语树型结构的常用术语 A BD FE C GHI JKM n 结点的度结点的度 一个结点的子树的个数; Q:结点A、D的度数?( ) n 树的度树的度 树中所有结点度的最大值; Q:右图中树的度?( ) n 终端终端( (叶子叶子) )结点结点 度为0的结点; Q:图中叶子结点有几个?( ) n n 非终端
6、结点非终端结点 度不为0的结点; Q:图中非终端结点有几个?( ) 3 3 7 5 第41页 树型结构的常用术语树型结构的常用术语 A BD FE C GHI JKM n 结点的层次结点的层次 树中根结点的层次 为1,根结点子树的根为第2层, 以此类推; Q:图中结点F的层次? n 树的深度树的深度 树中所有结点层次 的最大值; Q:图中树的深度? n 有序树、无序树有序树、无序树 如果树中每 棵子树从左向右的排列拥有一定 的顺序,不得互换,则称为有序 树,否则称为无序树。 第42页 二叉树的概念二叉树的概念 定义:定义:二叉树是一种有序的树形结构。它与一般 树形结构的区别是: n 每个结点最
7、多有两棵子树; n 子树有左右之分,次序不能任意颠倒。 二叉树的5种基本形态 第43页 二叉树的性质二叉树的性质 【性质1】 在二叉树的第i层上最多有2i-1个结点(i1) A BC D FE H G I=1 2 i-1=1 I=2 2 i-1=2 I=3 2 i-1=4 第44页 【性质2】深度为h的二叉树最多有2h -1个结点(h 1) n n 满二叉树:满二叉树:如果一个深度为k的二叉树拥有2K-1个结 点,则将它称为满二叉树。 n n 完全二叉树:完全二叉树:有一棵深度为k,具有n个结点的二叉树 ,若将它与一棵同深度的满二叉树中的所有结点按从 上到下,从左到右的顺序分别进行编号,且该二
8、叉树 中的每个结点分别与满二叉树中编号为1n的结点位 置一一对应,则称这棵二叉树为完全二叉树。 第45页 12 13 14 15 8 9 10 11 4 5 6 7 1 2 3 满二叉树 完全二叉树 12 13 8 9 10 11 4 5 6 7 1 2 3 完全二叉树是满二叉树 满二叉树也是完全二叉树 叶子结点 只能出现 在最后两层 第46页 12 13 8 9 10 11 4 5 6 1 2 3 非完全二 叉树 深度为4的 完全二叉树 8 4 5 6 7 1 2 3 4 5 6 7 1 2 3 9 12 13 8 9 10 11 4 1 2 深度为4的 完全二叉树 3 5 6 7 第47页
9、 【性质3】二叉树上叶子结点数比度为2的结点数多1 A BC D FE H G 度为2的结点 叶子结点 第48页 N=N0+N1+N2 (1) 除根结点外每个结点均有一个分 支进入,设二叉树中所有进入分 支数为M,总结点数: N=M+1 (2) 由于分支是由非叶子结点射入, 结点度为1射入1个分支, 结点度为2射入2个分支,故 M=N1+2N2 (3) 将(3)代入(2)式有 N=N1+2N2+1 (4) 比较(1)式与(4)有 N0+N1+N2=N1+2N2+1 化简后得 N0=N2+1 即叶子结点数比结点度为2的结点 数多1. A BC D FE H G N0为结点度为0,即叶子结点数 N
10、1为结点度为1的结点数 N2为结点度为2的结点数 N为树的总结点数 N=N0+N1+N2 N=3+2+2=8 第49页 【性质4】具有n个结点的完全二叉树的深度为 log2n+1 其中,log2n 的结果是不大于log2n的最大整数 A B A B C A BC FE log22+1=2 log25+1=3 取整的表示 第50页 u 一棵二叉树第六层(根结点为第一层)的结点数最多 为 _ 个。 u 某二叉树中度为2的结点有18个,则该二叉树中有 _ 个叶子结点。 u 在深度为5的完全二叉树中,度为2的结点数最多 为 _ 。 练习: 32 19 15 分析:完全二叉树的特例 是满二叉树,总结点数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学计算机 第四
链接地址:https://www.31doc.com/p-2227435.html