公共基础部分PPT讲稿.ppt

公共基础部分第1页，共65页，编辑于2022年，星期五第一部分第一部分 数据结构与算法数据结构与算法一、算法重点考点一、算法重点考点 1、算法的概念、算法的概念(记忆记忆)算法是指解决问题方案的准确而完整的描述算法是指解决问题方案的准确而完整的描述.2、算法的基本特征、算法的基本特征(记忆记忆)可行性可行性,确定性确定性,有穷性有穷性,拥有足够的情报拥有足够的情报 3、算法的控制结构、算法的控制结构(记忆记忆)顺序顺序 ,选择选择(分支分支),循环循环第2页，共65页，编辑于2022年，星期五4、算法设计基本方法、算法设计基本方法(理解理解+记忆记忆)列举法、归纳法、递推法、递归法、减半递推技术列举法、归纳法、递推法、递归法、减半递推技术比较递推法和递归法比较递推法和递归法 递推递推:从已知条件出发从已知条件出发,逐次推出中间结果和最后结果逐次推出中间结果和最后结果.递归递归:将问题逐层分解将问题逐层分解,解决简单问题解决简单问题,再朝逆方向综合再朝逆方向综合.递归算法递归算法要比要比递推算法递推算法清晰易读清晰易读,且易设计且易设计,但执行效率低但执行效率低第3页，共65页，编辑于2022年，星期五5、算法复杂度、算法复杂度 时间复杂度时间复杂度:是指执行算法所需要的计算工作量是指执行算法所需要的计算工作量.空间复杂度空间复杂度:是指执行算法所需要的存储空间是指执行算法所需要的存储空间.存储空间包括存储空间包括:算法程序所占空间算法程序所占空间,输入原始数据所占空间执输入原始数据所占空间执行算法时需要的额外空间行算法时需要的额外空间.如果如果额外空间额外空间是常量是常量,则称该算法是则称该算法是”原地工作原地工作”第4页，共65页，编辑于2022年，星期五二、数据结构的考点、数据结构的考点1、数据结构的概念、数据结构的概念 数据的逻辑结构数据的逻辑结构:指反应数据元素之间逻辑关系的数据结构指反应数据元素之间逻辑关系的数据结构.如：如：春夏秋冬春夏秋冬 数据的存储结构数据的存储结构(物理结构物理结构):指数据的逻辑结构在计算机中的存储形式指数据的逻辑结构在计算机中的存储形式.数据的数据的逻辑结构逻辑结构可以可以表示成多种存储结构表示成多种存储结构,不同的存储结不同的存储结构构,数据处理的效率不同数据处理的效率不同.第5页，共65页，编辑于2022年，星期五2、数据逻辑结构的两大结构、数据逻辑结构的两大结构线形结构线形结构和和非线形结构非线形结构的基本概念的基本概念 非空的数据结构非空的数据结构,满足下列条件则为线形结构满足下列条件则为线形结构(又称线性表又称线性表)(1)有且只有一个根结点有且只有一个根结点 (2)每个节点最多有一个前件每个节点最多有一个前件,也最多有一个后件也最多有一个后件.第6页，共65页，编辑于2022年，星期五1）、线形表的顺序存储结构）、线形表的顺序存储结构 是计算机中存储线形表的最简单的方法是计算机中存储线形表的最简单的方法.两个基本特点两个基本特点:(1)线形表中所有元素所占的空间都是连续的。线形表中所有元素所占的空间都是连续的。(2)线形表中各数据元素在存储空间中是按逻辑顺序依次存放线形表中各数据元素在存储空间中是按逻辑顺序依次存放.第7页，共65页，编辑于2022年，星期五2）、线性链表）、线性链表 (1)概念概念:线性表的链式存储结构称为线形链表线性表的链式存储结构称为线形链表.(2)存储原理存储原理:把存储结点分成两部分把存储结点分成两部分,第一部分存储数据元素第一部分存储数据元素,第二第二 部分存储下一元素的序号部分存储下一元素的序号(即存储结点的地址即存储结点的地址).(3)特点特点:各数据结点的存储序号是不连续的各数据结点的存储序号是不连续的,各结点在存储空间各结点在存储空间 中的位置与逻辑关系也不一致中的位置与逻辑关系也不一致.(4)特别说明特别说明 栈和队列也可以采用链式存储栈和队列也可以采用链式存储 。第8页，共65页，编辑于2022年，星期五3、栈及基本运算、栈及基本运算 (1)栈的概念栈的概念:栈是限定在一端插入与删除的栈是限定在一端插入与删除的线形表线形表.允许插入和删除端为栈顶允许插入和删除端为栈顶,另一端为栈底另一端为栈底,即满足即满足 ”先进后出先进后出”的原则的原则.FILO 或或LIFO“后进先出后进先出”(2)栈的基本运算栈的基本运算 入栈入栈:插入元素插入元素 出栈出栈:删除元素删除元素 读栈读栈:把栈顶元素赋给一个变量把栈顶元素赋给一个变量.第9页，共65页，编辑于2022年，星期五4、队列、队列 队列队列是允许在一端是允许在一端(队尾队尾)进行插入进行插入,而在另一端而在另一端(队头队头)进行删除的进行删除的线形表线形表.特点特点:“先进先出先进先出”FIFO 或或”后进后出后进后出”LILO 队列运算队列运算:入队入队:从队尾插入从队尾插入 退队退队:从队头删除从队头删除第10页，共65页，编辑于2022年，星期五三、树与二叉树三、树与二叉树1、概念：、概念：树：树：是一种简单的非线形结构，所有元素都有明显的层次是一种简单的非线形结构，所有元素都有明显的层次 结构。树根，子结点，树叶结构。树根，子结点，树叶 度：度：一个结点所拥有的后件个数。一个结点所拥有的后件个数。树的度：树的度：所有结点中最大的度称为树的度。所有结点中最大的度称为树的度。深度：深度：树的最大层数称为树的深度，根结点是第一层。树的最大层数称为树的深度，根结点是第一层。第11页，共65页，编辑于2022年，星期五2、二叉树、二叉树二叉树：二叉树：非空二叉树只有一个根结点，每个结点最多有两非空二叉树只有一个根结点，每个结点最多有两 棵子树，且分别称为左子树，右子树。棵子树，且分别称为左子树，右子树。特点特点 （1）在第）在第K层上，最多有层上，最多有2k-1（K=1）个结点）个结点 （2）深度为）深度为M的二叉树，最多有的二叉树，最多有2M-1个结点（深度指层数）个结点（深度指层数）（3）任何二叉树中，度为）任何二叉树中，度为0的结点（叶子）总比度为的结点（叶子）总比度为2的结的结 点多一个点多一个 （4）具有）具有n个结点的二叉树，深度至少为个结点的二叉树，深度至少为lon2n+1第12页，共65页，编辑于2022年，星期五3、完全二叉树和满二叉树、完全二叉树和满二叉树 完全二叉树完全二叉树 是指除最后一层外，每一层上的结点数均达到最大值，是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。在最后一层上只缺少右边的若干结点。满二叉树（最多结点）满二叉树（最多结点）满二叉树是指除最后一层外，每一层上的所有结点有满二叉树是指除最后一层外，每一层上的所有结点有 两个子结点，则在第两个子结点，则在第K层上有层上有2k-1个结点，深度为个结点，深度为m的的 满二叉树有满二叉树有2m-1个结点。个结点。第13页，共65页，编辑于2022年，星期五4、二叉树的遍历、二叉树的遍历 遍历：是指不重复访问二叉树中的所有结点。遍历：是指不重复访问二叉树中的所有结点。三种遍历方式：三种遍历方式：前续遍历（前续遍历（DLR）：）：先访问根结点，然后遍历左子树先访问根结点，然后遍历左子树,最后遍历右子树。最后遍历右子树。中序遍历（中序遍历（LDR）：）：首先遍历左子树，然后访问根结点，最后遍历右子树。首先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历（后序遍历（LRD）：）：首先遍历左子树，然后遍历右子树，最后访问根结点。首先遍历左子树，然后遍历右子树，最后访问根结点。第14页，共65页，编辑于2022年，星期五1.7查找技术查找技术指在一个给定的数据结构中查找某个指定的元素。指在一个给定的数据结构中查找某个指定的元素。一、顺序查找：一、顺序查找：1、顺序查找效率低、顺序查找效率低2、只能用顺序查找的两种情况：、只能用顺序查找的两种情况：无序表；无序表；有序表但采用链式存储结构。有序表但采用链式存储结构。3、长度为、长度为n的线性表，最坏情况下，顺序查找需比较的线性表，最坏情况下，顺序查找需比较n次次,最好一次最好一次比较就成功，平均情况下，要比较比较就成功，平均情况下，要比较n/2次。次。二、二分法查找：二、二分法查找：1、只适用顺序存储的有序表。、只适用顺序存储的有序表。2、最坏情况下，长度为、最坏情况下，长度为n的线性表需比较的线性表需比较log2n次次,最好一次比较就最好一次比较就成功。成功。第15页，共65页，编辑于2022年，星期五1.8排序技术排序技术l概念：概念：将一个无序序列整理成按值非递减顺序排序的有序序列。将一个无序序列整理成按值非递减顺序排序的有序序列。l分类：分类：一、交换类排序一、交换类排序冒泡排序法冒泡排序法快速排序法快速排序法二、插入类排序法二、插入类排序法简单插入排序简单插入排序希尔排序希尔排序三、选择类排序法三、选择类排序法简单选择排序简单选择排序堆排序堆排序第16页，共65页，编辑于2022年，星期五排序方法排序方法插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序简单插入排序简单插入排序希尔排序希尔排序简单选择排序简单选择排序堆排序堆排序冒泡排序冒泡排序快速排序快速排序第17页，共65页，编辑于2022年，星期五一、交换类排序l 冒泡排序法通过冒泡排序法通过相邻数据元素的交换相邻数据元素的交换逐步将线性表变逐步将线性表变成有序。成有序。l分别从线性表的两端，比较相邻元素大小，大的下分别从线性表的两端，比较相邻元素大小，大的下沉，小的上浮，来回比较。沉，小的上浮，来回比较。l假设线性表的长度为假设线性表的长度为n，则在最坏的情况下，冒泡排序需，则在最坏的情况下，冒泡排序需要经过要经过n/2遍的从前往后的扫描和遍的从前往后的扫描和n/2遍的从后往前的扫遍的从后往前的扫描，需要的比较次数为描，需要的比较次数为n(n-1)/2。第18页，共65页，编辑于2022年，星期五快速排序法快速排序法l分割思想：选取一个元素，小于它的移到分割思想：选取一个元素，小于它的移到前面，大于它的移到后面，不断分割。前面，大于它的移到后面，不断分割。l在最坏情况下需比较在最坏情况下需比较O(nlog2n)l在最好的情况下，需要比较在最好的情况下，需要比较n(n-1)/2第19页，共65页，编辑于2022年，星期五二、插入类排序法二、插入类排序法简单插入排序简单插入排序l将无序序列中的各元素依次插入到已有序的线性表中。将无序序列中的各元素依次插入到已有序的线性表中。l在最坏情况下，简单插入排序需要在最坏情况下，简单插入排序需要n(n-1)/2次比较。次比较。希尔排序希尔排序l基本思想是：将整个无序序列分割成若干小的子序列分别基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。按一定增量分组，增量逐渐减小。进行插入排序。按一定增量分组，增量逐渐减小。l最坏情况下，希尔排序所需要的比较次数为最坏情况下，希尔排序所需要的比较次数为O(n1.5)第20页，共65页，编辑于2022年，星期五三、选择类排序法简单选择排序简单选择排序l从中选出最小的元素，将它交换到表的最前面。从中选出最小的元素，将它交换到表的最前面。l简单选择排序在最坏情况下需比较简单选择排序在最坏情况下需比较n(n-1)/2次。次。堆排序堆排序l在最坏情况下需比较在最坏情况下需比较O(nlog2n)第21页，共65页，编辑于2022年，星期五排序总结好的情况：好的情况：n(n-1)/2第22页，共65页，编辑于2022年，星期五练习：第23页，共65页，编辑于2022年，星期五l在长度为在长度为n的有序线性表中进行二分查找。最坏的情况下，的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为需要的比较次数为 。l长度为长度为n的顺序存储线性表中，当在任何位置上插入一个的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个元素概率都相等时，插入一个元素所需移动元素的平均个数为数为 。l假设线性表的长度为假设线性表的长度为n，则在最坏情况下，冒泡排序需要的，则在最坏情况下，冒泡排序需要的比较次数为比较次数为 A)log2n B)n2 C)O(n1.5)D)n(n-1)/2第24页，共65页，编辑于2022年，星期五l 冒泡排序算法在最好的情况下的元素交换次数为冒泡排序算法在最好的情况下的元素交换次数为【1】。l在最坏情况下，堆排序需要比较的次数为在最坏情况下，堆排序需要比较的次数为【2】。l最简单的交换排序方法是最简单的交换排序方法是 A)快速排序快速排序 B)选择排序选择排序 C)堆排序堆排序D)冒泡排序冒泡排序l排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、序、【1】和选择排序等。和选择排序等。第25页，共65页，编辑于2022年，星期五l在下列几种排序方法中，要求内存量最大的是 A)插入排序 B)选择排序 C)快速排序D)归并排序l希尔排序属于 A)交换排序 B)归并排序 C)选择排序D)插入排序第26页，共65页，编辑于2022年，星期五第二部分第二部分 程序设计基程序设计基 结构化程序设计、面向对象程序设计结构化程序设计、面向对象程序设计1、程序设计方法和风格、程序设计方法和风格(清晰第一、效率第二清晰第一、效率第二)（一）源程序文档化（一）源程序文档化 （1）符号名的命名应具有一定的实际含义，便于理解）符号名的命名应具有一定的实际含义，便于理解 （2）程序应加上一定的注释，序言性注释和功能性注释）程序应加上一定的注释，序言性注释和功能性注释 （3）为使程序结构一目了然，可以利用空格、空行、）为使程序结构一目了然，可以利用空格、空行、缩进等技巧，是程序层次清晰缩进等技巧，是程序层次清晰 第27页，共65页，编辑于2022年，星期五（二）数据说明的方法（二）数据说明的方法 （1）数据说明的次序规范化）数据说明的次序规范化 （2）说明语句中变量安排有序化）说明语句中变量安排有序化 （3）使用注释来说明复杂数据的结构）使用注释来说明复杂数据的结构（三）语句的结构（三）语句的结构 （1）在一行内只写一条语句；尽量使用库函数。）在一行内只写一条语句；尽量使用库函数。（2）首先保证程序正确，然后再考虑提高效率。）首先保证程序正确，然后再考虑提高效率。（3）避免使用临时变量而使程序的可读性下降）避免使用临时变量而使程序的可读性下降 （4）避免不必要的转移，避免采用复杂的条件语句）避免不必要的转移，避免采用复杂的条件语句 （5）要模块化，是模块功能尽可能单一化。）要模块化，是模块功能尽可能单一化。高内聚，低耦合高内聚，低耦合 （6）利用信息隐蔽，确保每个模块的独立性）利用信息隐蔽，确保每个模块的独立性 （7）不要修补不好的程序，要重新编写）不要修补不好的程序，要重新编写第28页，共65页，编辑于2022年，星期五（四）输入和输出（四）输入和输出 （1）对所有的输入数据都要检验数据的合法性）对所有的输入数据都要检验数据的合法性 （2）检查输入项的各种重要组合的合理性）检查输入项的各种重要组合的合理性 （3）输入格式要简单，以使输入的步骤和操作简单）输入格式要简单，以使输入的步骤和操作简单 （4）输入数据时，应允许使用自由格式）输入数据时，应允许使用自由格式 （5）应允缺省值。）应允缺省值。（6）输入一批数据时，最好使用输入结束标志。）输入一批数据时，最好使用输入结束标志。（7）以交互输入）以交互输入/输出方式进行输入时，要采用人输出方式进行输入时，要采用人-机会机会 话给出明确的提示信息和运行的状态信息话给出明确的提示信息和运行的状态信息 （8）设计输出报表格式）设计输出报表格式第29页，共65页，编辑于2022年，星期五2、结构化程序设计、结构化程序设计 （1）设计原则：）设计原则：自顶向下、逐步求精、模块化、限制使用自顶向下、逐步求精、模块化、限制使用GOTO语句语句 （2）结构化程序的结构）结构化程序的结构 顺序结构顺序结构 选择结构（分支结构）选择结构（分支结构）重复结构（循环结构）重复结构（循环结构）第30页，共65页，编辑于2022年，星期五3、结构化程序设计的具体实施中，注意要素、结构化程序设计的具体实施中，注意要素 （1）使用顺序、选择和循环三种基本控制结构表示程序）使用顺序、选择和循环三种基本控制结构表示程序 的控制结构。的控制结构。（2）选用的控制结构只许有一个入口和一个出口）选用的控制结构只许有一个入口和一个出口 （3）程序模块化，每个模块也只能有一个入口和一个出口）程序模块化，每个模块也只能有一个入口和一个出口 （4）使用基本控制结构进行嵌套与组合来实现复杂结构）使用基本控制结构进行嵌套与组合来实现复杂结构 （5）用前后一致的方法来模拟）用前后一致的方法来模拟3种基本结构以外的控制结构种基本结构以外的控制结构 （6）严格控制）严格控制GOTO语句的使用语句的使用第31页，共65页，编辑于2022年，星期五4、面向对象程序设计、面向对象程序设计 优点优点 （1）与人类习惯的思维方法一致，面向对象的核心是对象）与人类习惯的思维方法一致，面向对象的核心是对象 （2）稳定性好）稳定性好 （3）可重用性好，可继承父类的所有属性和方法）可重用性好，可继承父类的所有属性和方法 （4）易于开发大型软件产品）易于开发大型软件产品 （5）可维护性好（原因）可维护性好（原因）稳定性好、容易修改、容易理解、易于测试和调试稳定性好、容易修改、容易理解、易于测试和调试第32页，共65页，编辑于2022年，星期五5、面向对象方法的基本概念、面向对象方法的基本概念 （1）对象）对象 对象是指一组属性以及这组属性上的专用操作的封装对象是指一组属性以及这组属性上的专用操作的封装 对象由对象名、属性和操作对象由对象名、属性和操作3部分组成。部分组成。对象的基本特点：对象的基本特点：标识惟一性、分类性、多态性标识惟一性、分类性、多态性 封装性、模块独立性好封装性、模块独立性好 （2）封装）封装 封装是一种信息隐蔽技术，用户只能看见对象封装界封装是一种信息隐蔽技术，用户只能看见对象封装界 面上的信息，对象的内部实现是隐蔽的。面上的信息，对象的内部实现是隐蔽的。第33页，共65页，编辑于2022年，星期五（3）属性）属性 属性就是对象的特征，是对象外观及行为的特征。属性就是对象的特征，是对象外观及行为的特征。（4）类和实例）类和实例 类：指具有共同属性、方法的对象的集合类：指具有共同属性、方法的对象的集合 实例：类的一个具体应用就是一个实例实例：类的一个具体应用就是一个实例（5）消息）消息 实例之间相互传递的信息叫消息实例之间相互传递的信息叫消息第34页，共65页，编辑于2022年，星期五（6）继承）继承 继承是在已有的类定义的基础上建立新类的定义技术。继承是在已有的类定义的基础上建立新类的定义技术。（7）多态性和动态绑定）多态性和动态绑定 多态性：多态性：指同一操作作用于不同对象可以有不同解释指同一操作作用于不同对象可以有不同解释 产生不同的执行结果。产生不同的执行结果。动态绑定：动态绑定：在运行过程中，当一个对象发送消息请求在运行过程中，当一个对象发送消息请求 服务时，根据接收对象的具体情况将请求的服务时，根据接收对象的具体情况将请求的 操作和具体实现的方法进行连接。操作和具体实现的方法进行连接。第35页，共65页，编辑于2022年，星期五例题讲解第36页，共65页，编辑于2022年，星期五l结构化程序设计的结构化程序设计的3种结构是种结构是 A)顺序结构、选择结构、转移结构顺序结构、选择结构、转移结构 B)分支结构、等价结构、循环结构分支结构、等价结构、循环结构 C)多分支结构、赋值结构、等价结构多分支结构、赋值结构、等价结构 D)顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构l在设计程序时，应采纳的原则之一是在设计程序时，应采纳的原则之一是 A)不限制不限制goto语句的使用语句的使用 B)减少或取消注解行减少或取消注解行 C)程序越短越好程序越短越好D)程序结构应有助于读者理解程序结构应有助于读者理解l 对建立良好的程序设计风格，下面描述正确的是对建立良好的程序设计风格，下面描述正确的是 A)程序应简单、清晰、可读性好程序应简单、清晰、可读性好 B)符号名的命名只要符合语法符号名的命名只要符合语法 C)充分考虑程序的执行效率充分考虑程序的执行效率 D)程序的注释可有可无程序的注释可有可无第37页，共65页，编辑于2022年，星期五l结构化程序设计主要强调的是 A)程序的规模B)程序的效率 C)程序设计语言的先进性 D)程序易读性l 以下不属于对象的基本特点的是 A)分类性 B)多态性 C)继承性D)封装性 l在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的 A)安全性B)一致性 C)可理解性D)合理性第38页，共65页，编辑于2022年，星期五l下列叙述中，不属于结构化程序设计方法的主要原则的是 A)自顶向下 B)由底向上 C)模块化 D)限制使用goto语句l 对象实现了数据和操作的结合，是指对数据和数据的操作进行 A)结合 B)隐藏 C)封装 D)抽象第39页，共65页，编辑于2022年，星期五l在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送A）调用语句 B）命令 C）口令 D）消息l下列对象概念描述错误的是A）任何对象都必须有继承性B）对象是属性和方法的封装体C）对象间的通讯靠消息传递D）操作是对象的动态属性第40页，共65页，编辑于2022年，星期五l在面向对象的程序设计中，类描述的是具有相似性质的一组【】l在面向对象方法中，类之间共享属性和操作的机制称为【】。l一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的【】。第41页，共65页，编辑于2022年，星期五l一个对象是类的一个【3】。l 在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为【4】。l 第42页，共65页，编辑于2022年，星期五l【3】是一种信息隐蔽技术，目的在于将对象的使用者和对象的设计者分开。l 源程序文档化要求程序应加注释。注释一般分为序言性注释和_。l在面向对象方法种，信息屏蔽是通过对象的_性来实现的。第43页，共65页，编辑于2022年，星期五结构化程序设计方法的主要原则可以概括为自顶结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、向下、逐步求精、_和限制使用和限制使用goto语句。语句。下面描述中，符合结构化程序设计风格的是下面描述中，符合结构化程序设计风格的是_。第44页，共65页，编辑于2022年，星期五。面向对象的程序设计方法中涉及的对象是系统面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个中用来描述客观事物的一个_。下面概念中，不属于面向对象方法的是下面概念中，不属于面向对象方法的是_第45页，共65页，编辑于2022年，星期五第三部分第三部分 软件工程软件工程一、基本概念一、基本概念1、软件定义和软件特点、软件定义和软件特点 定义：定义：软件是包括程序、数据及相关文档的完整指令。软件是包括程序、数据及相关文档的完整指令。与硬件相互依存，构成计算机系统。与硬件相互依存，构成计算机系统。特点特点1）软件是一种逻辑实体）软件是一种逻辑实体 （2）软件的生产和硬件不同，没有明显的制作过程）软件的生产和硬件不同，没有明显的制作过程 （3）软件在运行、使用期间不存在磨损、老化问题）软件在运行、使用期间不存在磨损、老化问题 （4）软件的开发和运行具有依赖计算机系统的特性）软件的开发和运行具有依赖计算机系统的特性 受计算机系统的限制，软件移植可能会有问题受计算机系统的限制，软件移植可能会有问题 （5）软件的复杂性高，成本昂贵）软件的复杂性高，成本昂贵 （6）软件开发涉及诸多社会因素）软件开发涉及诸多社会因素第46页，共65页，编辑于2022年，星期五2、软件危机与软件工程、软件危机与软件工程 软件危机：软件危机：指在软件在开发和维护过程中所遇到的一系列指在软件在开发和维护过程中所遇到的一系列 严重问题。包括成本、质量、生产率等严重问题。包括成本、质量、生产率等 软件工程：软件工程：是应用于计算机软件的定义、开发和维护的一是应用于计算机软件的定义、开发和维护的一 整套方法、工具、文档实践标准和工序整套方法、工具、文档实践标准和工序 核心思想是：核心思想是：把软件产品作为一个工程产品处理。把软件产品作为一个工程产品处理。软件工程三要素：软件工程三要素：方法、工具和过程方法、工具和过程第47页，共65页，编辑于2022年，星期五3、软件工程过程和软件生命周期、软件工程过程和软件生命周期 软件工程过程：软件工程过程：是指为了获得软件产品，由软件工程师完是指为了获得软件产品，由软件工程师完 成的一系列软件工程活动。成的一系列软件工程活动。软件工程四种活动：软件工程四种活动：软件规格说明、软件开发、软件确认、软件演进软件规格说明、软件开发、软件确认、软件演进 软件生命周期：软件生命周期：（1）可行性研究与计划确定）可行性研究与计划确定 （2）需求分析）需求分析 （3）软件设计（结构模块的划分）软件设计（结构模块的划分）（4）软件实现）软件实现 （5）软件测试）软件测试 （6）运行和维护）运行和维护 第48页，共65页，编辑于2022年，星期五4、软件工程的目标和原则、软件工程的目标和原则 目标：目标：付出较低的成本；达到要求的软件功能；付出较低的成本；达到要求的软件功能；取得较好的软件性能；开发的软件易于移植；取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；能按时完成开发，及时交付需要较低的维护费用；能按时完成开发，及时交付 原则：原则：抽象、信息隐蔽、模块化、局部化、确定性抽象、信息隐蔽、模块化、局部化、确定性 一致性、完备性和可验证性。一致性、完备性和可验证性。第49页，共65页，编辑于2022年，星期五二、结构化分析二、结构化分析1、需求分析、需求分析 定义：定义：通过文档描述用户解决问题或达到目标所需的条通过文档描述用户解决问题或达到目标所需的条 件或权能，及系统要满足合同、标准规范所具有件或权能，及系统要满足合同、标准规范所具有 的条件。的条件。需求分析阶段的工作：需求分析阶段的工作：需求获取、需求获取、需求分析、需求分析、编写需求规格说明书、编写需求规格说明书、需求评审需求评审第50页，共65页，编辑于2022年，星期五2、需求分析的方法、需求分析的方法 （1）结构化分析方法）结构化分析方法 SA：面向数据流的结构化分析方法面向数据流的结构化分析方法 JSD：面向数据结构面向数据结构Jackson方法方法 DSSD：面向数据结构的结构化数据系统开发方法面向数据结构的结构化数据系统开发方法 （2）面向对象的分析方法）面向对象的分析方法OOA第51页，共65页，编辑于2022年，星期五3、结构化分析方法、结构化分析方法 定义：就是使用数据流图（定义：就是使用数据流图（DFD）、数据字典（）、数据字典（DD）、）、结构化英语、判定表和判定树等工具，建立一种结构化英语、判定表和判定树等工具，建立一种 新的、称为结构化规格说明的目标文档。新的、称为结构化规格说明的目标文档。4、软件需求规则说明书、软件需求规则说明书 是需求分析阶段的最后成果，是软件开发中的重要文档之一是需求分析阶段的最后成果，是软件开发中的重要文档之一 第52页，共65页，编辑于2022年，星期五5、软件设计、软件设计 从技术观点来看，软件设计包括如下几个过程：从技术观点来看，软件设计包括如下几个过程：（1）软件结构设计：定义软件系统各部件之间的关系）软件结构设计：定义软件系统各部件之间的关系 （2）数据设计：将分析时创建的模型转为数据结构的定义）数据设计：将分析时创建的模型转为数据结构的定义 （3）接口设计：描述软件内部、软件和操作系统之间及软）接口设计：描述软件内部、软件和操作系统之间及软 件与人之间如何通信。件与人之间如何通信。（4）过程设计：把系统结构部件转换成软件的过程描述）过程设计：把系统结构部件转换成软件的过程描述 从工程管理来看，软件设计分为：从工程管理来看，软件设计分为：（1）概要设计：确定总体结构，模块的划分）概要设计：确定总体结构，模块的划分 （2）详细设计：确定每一模块的实现。）详细设计：确定每一模块的实现。第53页，共65页，编辑于2022年，星期五6、软件模块的独立性、软件模块的独立性 独立性：独立性：每个模块完成系统要求的独立的功能，与其他每个模块完成系统要求的独立的功能，与其他 模块的联系最少且接口简单。模块的联系最少且接口简单。独立性的两个标准：独立性的两个标准：耦合和内聚（应满足：低耦合、高内聚）耦合和内聚（应满足：低耦合、高内聚）耦合：模块之间联系的紧密程度。耦合：模块之间联系的紧密程度。内聚：模块内部各元素之间联系的紧密程度内聚：模块内部各元素之间联系的紧密程度第54页，共65页，编辑于2022年，星期五7、概要设计的准则、概要设计的准则 （1）提高模块独立性）提高模块独立性 （2）模块规模适度）模块规模适度 （3）深度、宽度、扇出和扇入适当）深度、宽度、扇出和扇入适当 好的软件结构设计应该满足：好的软件结构设计应该满足：顶层扇出教高、中间扇出教少、低层模块高扇入顶层扇出教高、中间扇出教少、低层模块高扇入 （4）使模块的作用域在该模块的控制域内）使模块的作用域在该模块的控制域内 （5）应减少模块的接口和界面的复杂性）应减少模块的接口和界面的复杂性 （6）设计成单入口和单出口的模块）设计成单入口和单出口的模块第55页，共65页，编辑于2022年，星期五8、数据流类型、数据流类型 两种：交换流和事物流两种：交换流和事物流第56页，共65页，编辑于2022年，星期五9、软件测试的目的和方法、软件测试的目的和方法 目的：目的：尽可能多地发现软件产品中的错误和缺陷。尽可能多地发现软件产品中的错误和缺陷。准则准则（1）所有测试应追溯到需求）所有测试应追溯到需求 （2）严格执行测试计划，排除测试的随意性）严格执行测试计划，排除测试的随意性 （3）充分注意测试中的群集显现）充分注意测试中的群集显现 （4）程序应避免检查自己的程序）程序应避免检查自己的程序 （5）穷举测试不能）穷举测试不能 （6）妥善保存测试计划、测试用例、出错统计）妥善保存测试计划、测试用例、出错统计 和最终分析报告，为维护提供方便。和最终分析报告，为维护提供方便。方法：方法：白盒测试：白盒测试：根据程序的内部逻辑来设计测试根据程序的内部逻辑来设计测试 黑盒测试：黑盒测试：根据程序的功能说明来设计测试根据程序的功能说明来设计测试第57页，共65页，编辑于2022年，星期五10、软件测试的实施过程、软件测试的实施过程 单元测试：对各模块进行正确性检验单元测试：对各模块进行正确性检验 集成测试：测试与组装软件的测试，发现与接口有关的问题集成测试：测试与组装软件的测试，发现与接口有关的问题 验收测试：验证软件的功能、性能验收测试：验证软件的功能、性能 系统测试：将测试确认的软件加入到计算机系统中进行测试系统测试：将测试确认的软件加入到计算机系统中进行测试第58页，共65页，编辑于2022年，星期五11、程序调试、程序调试 是指诊断和改正程序中是指诊断和改正程序中 的错误。的错误。其其关键是关键是推断程序内部的错误位置及原因。推断程序内部的错误位置及原因。调试的步骤：调试的步骤：错误定位错误定位修改设计和代码，以排除错误修改设计和代码，以排除错误进进 行回归测试，防止引进新的错误。行回归测试，防止引进新的错误。调试方法：调试方法：（1）强行排错法）强行排错法 （2）回溯法）回溯法 （3）原因排除法）原因排除法第59页，共65页，编辑于2022年，星期五第四部分第四部分 数据库基础知识数据库基础知识1、数据、数据库、数据库管理系统、数据库系统、数据、数据库、数据库管理系统、数据库系统 基本概念、关系基本概念、关系2、数据库系统的特点、数据库系统的特点 1）实现数据共享，减少数据冗余）实现数据共享，减少数据冗余 2）采用特定的数据模型）采用特定的数据模型 3）较高的数据独立性）较高的数据独立性 4）统一的数据控制功能）统一的数据控制功能3、数据库系统的发展、数据库系统的发展 几个阶段和各阶段的特点几个阶段和各阶段的特点第60页，共65页，编辑于2022年，星期五4、数据库系统的三级模式和两级映射、数据库系统的三级模式和两级映射 三级模式：三级模式：（1）概念模式：）概念模式：是数据库中对全局数据的逻辑结构和特征是数据库中对全局数据的逻辑结构和特征 的描述，是所有用户的公共数据视图。的描述，是所有用户的公共数据视图。中间层，反映设计者的全局数据逻辑要求中间层，反映设计者的全局数据逻辑要求 （2）外模式：）外模式：是指拥护能够看见、是使用的、局部的逻辑是指拥护能够看见、是使用的、局部的逻辑 结构和特征的描述。结构和特征的描述。最高层，反映用户要求最高层，反映用户要求 （3）内模式：）内模式：存储模式或物理模式，能给出数据库物理存存储模式或物理模式，能给出数据库物理存 储结构和存储方法。储结构和存储方法。最低层，反映存储形式最低层，反映存储形式 两个映射：两个映射：外模式外模式/概念模式映射，概念模式概念模式映射，概念模式/内模式映射内模式映射第61页，共65页，编辑于2022年，星期五5、三种数据模型及特点、三种数据模型及特点6、E-R模型模型 基本概念：基本概念：实体、属性、联系实体、属性、联系 实体集的三种关系：实体集的三种关系：一对一、一对多、多对多一对一、一对多、多对多 E-R模型的表示法：模型的表示法：矩形：表示实体矩形：表示实体 椭圆：表示实体的属性椭圆：表示实体的属性 菱形：表示实体联系菱形：表示实体联系 无向线段：连接实体和属性，连接实体和实体关系无向线段：连接实体和属性，连接实体和实体关系第62页，共65页，编辑于2022年，星期五7、关系的数据约束、关系的数据约束 （1）实体完整性规则：主键属性不能为空且唯一）实体完整性规则：主键属性不能为空且唯一 （2）参照完整性规则：外键的值不允许参照不存在的相应）参照完整性规则：外键的值不允许参照不存在的相应 表中的主键的值。表中的主键的值。（3）用户定义的完整性约束：）用户定义的完整性约束：用户根据具体应用的语意要求而自己定义的规则。用户根据具体应用的语意要求而自己定义的规则。第63页，共65页，编辑于2022年，星期五8、关系模型的运算、关系模型的运算 （1）基本运算）基本运算 插入、删除、修改、查询插入、删除、修改、查询 （2）扩充运算）扩充运算 并、差、交、笛卡尔集并、差、交、笛卡尔集 选择、投影、连接选择、投影、连接 =非、非、与、与、或或第64页，共65页，编辑于2022年，星期五9、数据库设计概述、数据库设计概述 数据库设计就是设计一个满足用户要求，性能良好的数据数据库设计就是设计一个满足用户要求，性能良好的数据 库。根本目标是解决数据共享问题。库。根本目标是解决数据共享问题。第65页，共65页，编辑于2022年，星期五