公共基础部分

1、公共基础部分第1页，共65页，2022年，5月20日，6点11分，星期一第一部分 数据结构与算法一、算法重点考点 1 、算法的概念 (记忆) 算法是指解决问题方案的准确而完整的描述. 2 、算法的基本特征(记忆) 可行性, 确定性, 有穷性, 拥有足够的情报 3 、算法的控制结构(记忆) 顺序 , 选择(分支), 循环第2页，共65页，2022年，5月20日，6点11分，星期一4 、算法设计基本方法(理解+记忆) 列举法、归纳法、递推法、递归法、减半递推技术比较递推法和递归法 递推:从已知条件出发,逐次推出中间结果和最后结果. 递归:将问题逐层分解,解决简单问题,再朝逆方向综合. 递归算法要比

2、递推算法清晰易读,且易设计,但执行效率低第3页，共65页，2022年，5月20日，6点11分，星期一5 、算法复杂度 时间复杂度:是指执行算法所需要的计算工作量. 空间复杂度:是指执行算法所需要的存储空间. 存储空间包括:算法程序所占空间,输入原始数据所占空间执行算法时需要的额外空间. 如果额外空间是常量,则称该算法是”原地工作”第4页，共65页，2022年，5月20日，6点11分，星期一二、数据结构的考点1 、数据结构的概念 数据的逻辑结构: 指反应数据元素之间逻辑关系的数据结构.如：春夏秋冬 数据的存储结构(物理结构): 指数据的逻辑结构在计算机中的存储形式. 数据的逻辑结构可以表示成多种

3、存储结构, 不同的存储结构,数据处理的效率不同.第5页，共65页，2022年，5月20日，6点11分，星期一2 、数据逻辑结构的两大结构线形结构和非线形结构的基本概念 非空的数据结构,满足下列条件则为线形结构(又称线性表) (1)有且只有一个根结点 (2) 每个节点最多有一个前件,也最多有一个后件.第6页，共65页，2022年，5月20日，6点11分，星期一1）、线形表的顺序存储结构 是计算机中存储线形表的最简单的方法.两个基本特点: (1)线形表中所有元素所占的空间都是连续的。 (2)线形表中各数据元素在存储空间中是按逻辑顺序依次存放.第7页，共65页，2022年，5月20日，6点11分，星

4、期一2）、线性链表 (1)概念: 线性表的链式存储结构称为线形链表. (2)存储原理: 把存储结点分成两部分,第一部分存储数据元素,第二 部分存储下一元素的序号(即存储结点的地址). (3)特点: 各数据结点的存储序号是不连续的,各结点在存储空间 中的位置与逻辑关系也不一致. (4) 特别说明 栈和队列也可以采用链式存储 。 第8页，共65页，2022年，5月20日，6点11分，星期一3 、栈及基本运算 (1)栈的概念: 栈是限定在一端插入与删除的线形表. 允许插入和删除端为栈顶,另一端为栈底,即满足 ”先进后出”的原则.FILO 或LIFO “后进先出” (2)栈的基本运算 入栈:插入元素

5、出栈:删除元素 读栈:把栈顶元素赋给一个变量.第9页，共65页，2022年，5月20日，6点11分，星期一4 、队列 队列是允许在一端(队尾)进行插入,而在另一端(队头) 进行删除的线形表. 特点: “先进先出” FIFO 或”后进后出” LILO 队列运算: 入队:从队尾插入 退队:从队头删除第10页，共65页，2022年，5月20日，6点11分，星期一三、树与二叉树1、概念： 树：是一种简单的非线形结构，所有元素都有明显的层次 结构。树根，子结点，树叶 度：一个结点所拥有的后件个数。 树的度：所有结点中最大的度称为树的度。 深度：树的最大层数称为树的深度，根结点是第一层。 第11页，共65

6、页，2022年，5月20日，6点11分，星期一2、二叉树二叉树：非空二叉树只有一个根结点，每个结点最多有两 棵子树，且分别称为左子树，右子树。特点 （1）在第K层上，最多有2k-1（K=1）个结点 （2）深度为M的二叉树，最多有2M-1个结点（深度指层数） （3）任何二叉树中，度为0的结点（叶子）总比度为2的结 点多一个 （4）具有n个结点的二叉树，深度至少为lon2n+1第12页，共65页，2022年，5月20日，6点11分，星期一3、完全二叉树和满二叉树 完全二叉树 是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。 满二叉树（最多结点） 满二叉树是指除最后

7、一层外，每一层上的所有结点有 两个子结点，则在第K层上有2k-1个结点，深度为m的 满二叉树有2m-1个结点。第13页，共65页，2022年，5月20日，6点11分，星期一4、二叉树的遍历 遍历：是指不重复访问二叉树中的所有结点。 三种遍历方式： 前续遍历（DLR）： 先访问根结点，然后遍历左子树,最后遍历右子树。 中序遍历（LDR）： 首先遍历左子树，然后访问根结点，最后遍历右子树。 后序遍历（LRD）： 首先遍历左子树，然后遍历右子树，最后访问根结点。第14页，共65页，2022年，5月20日，6点11分，星期一1.7查找技术指在一个给定的数据结构中查找某个指定的元素。一、顺序查找：1、顺

8、序查找效率低2、只能用顺序查找的两种情况：无序表；有序表但采用链式存储结构。3、长度为n的线性表，最坏情况下，顺序查找需比较n次,最好一次比较就成功，平均情况下，要比较n/2次。二、二分法查找：1、只适用顺序存储的有序表。2、最坏情况下，长度为n的线性表需比较log2n次,最好一次比较就成功。第15页，共65页，2022年，5月20日，6点11分，星期一1.8排序技术概念： 将一个无序序列整理成按值非递减顺序排序的有序序列。分类：一、交换类排序冒泡排序法快速排序法二、插入类排序法简单插入排序希尔排序三、选择类排序法简单选择排序堆排序第16页，共65页，2022年，5月20日，6点11分，星期一

9、排序方法插入排序选择排序交换排序归并排序简单插入排序希尔排序简单选择排序堆排序冒泡排序快速排序第17页，共65页，2022年，5月20日，6点11分，星期一一、交换类排序 冒泡排序法通过相邻数据元素的交换逐步将线性表变成有序。分别从线性表的两端，比较相邻元素大小，大的下沉，小的上浮，来回比较。假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。第18页，共65页，2022年，5月20日，6点11分，星期一快速排序法分割思想：选取一个元素，小于它的移到前面，大于它的移到后面，不断分割。在最坏情况下需比较O(

10、nlog2n)在最好的情况下，需要比较n(n-1)/2第19页，共65页，2022年，5月20日，6点11分，星期一二、插入类排序法简单插入排序将无序序列中的各元素依次插入到已有序的线性表中。在最坏情况下，简单插入排序需要n(n-1)/2次比较。希尔排序基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。按一定增量分组，增量逐渐减小。最坏情况下，希尔排序所需要的比较次数为O(n1.5)第20页，共65页，2022年，5月20日，6点11分，星期一三、选择类排序法简单选择排序从中选出最小的元素，将它交换到表的最前面。简单选择排序在最坏情况下需比较n(n-1)/2次。堆排序在最坏情况下

11、需比较O(nlog2n)第21页，共65页，2022年，5月20日，6点11分，星期一排序总结好的情况：n(n-1)/2第22页，共65页，2022年，5月20日，6点11分，星期一练习：第23页，共65页，2022年，5月20日，6点11分，星期一在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 。长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为 。 假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为 A) log2n B) n2 C) O(n1.5) D) n(n-1)/2第24页，共65页，2022年

12、，5月20日，6点11分，星期一 冒泡排序算法在最好的情况下的元素交换次数为 【1】 。 在最坏情况下，堆排序需要比较的次数为 【2】 。 最简单的交换排序方法是 A) 快速排序 B) 选择排序 C) 堆排序D) 冒泡排序排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、 【1】 和选择排序等。第25页，共65页，2022年，5月20日，6点11分，星期一在下列几种排序方法中，要求内存量最大的是 A) 插入排序 B) 选择排序 C) 快速排序D) 归并排序希尔排序属于 A) 交换排序 B) 归并排序 C) 选择排序D) 插入排序第26页，共65页，2022年，5月20日，6点11

13、分，星期一第二部分 程序设计基 结构化程序设计、面向对象程序设计1、程序设计方法和风格(清晰第一、效率第二)（一）源程序文档化 （1）符号名的命名应具有一定的实际含义，便于理解 （2）程序应加上一定的注释，序言性注释和功能性注释 （3）为使程序结构一目了然，可以利用空格、空行、 缩进等技巧，是程序层次清晰 第27页，共65页，2022年，5月20日，6点11分，星期一 （二）数据说明的方法 （1）数据说明的次序规范化 （2）说明语句中变量安排有序化 （3）使用注释来说明复杂数据的结构 （三）语句的结构 （1）在一行内只写一条语句；尽量使用库函数。 （2）首先保证程序正确，然后再考虑提高效率。

14、（3）避免使用临时变量而使程序的可读性下降 （4）避免不必要的转移，避免采用复杂的条件语句 （5）要模块化，是模块功能尽可能单一化。 高内聚，低耦合 （6）利用信息隐蔽，确保每个模块的独立性 （7）不要修补不好的程序，要重新编写第28页，共65页，2022年，5月20日，6点11分，星期一（四）输入和输出 （1）对所有的输入数据都要检验数据的合法性 （2）检查输入项的各种重要组合的合理性 （3）输入格式要简单，以使输入的步骤和操作简单 （4）输入数据时，应允许使用自由格式 （5）应允缺省值。 （6）输入一批数据时，最好使用输入结束标志。 （7）以交互输入/输出方式进行输入时，要采用人-机会 话

15、给出明确的提示信息和运行的状态信息 （8）设计输出报表格式第29页，共65页，2022年，5月20日，6点11分，星期一2、结构化程序设计 （1）设计原则： 自顶向下、逐步求精、模块化、限制使用GOTO语句 （2）结构化程序的结构 顺序结构 选择结构（分支结构） 重复结构（循环结构）第30页，共65页，2022年，5月20日，6点11分，星期一3、结构化程序设计的具体实施中，注意要素 （1）使用顺序、选择和循环三种基本控制结构表示程序 的控制结构。 （2）选用的控制结构只许有一个入口和一个出口 （3）程序模块化，每个模块也只能有一个入口和一个出口 （4）使用基本控制结构进行嵌套与组合来实现复杂

16、结构 （5）用前后一致的方法来模拟3种基本结构以外的控制结构 （6）严格控制GOTO语句的使用第31页，共65页，2022年，5月20日，6点11分，星期一4、面向对象程序设计 优点 （1）与人类习惯的思维方法一致，面向对象的核心是对象 （2）稳定性好 （3）可重用性好，可继承父类的所有属性和方法 （4）易于开发大型软件产品 （5）可维护性好（原因） 稳定性好、容易修改、容易理解、易于测试和调试第32页，共65页，2022年，5月20日，6点11分，星期一5、面向对象方法的基本概念 （1）对象 对象是指一组属性以及这组属性上的专用操作的封装 对象由对象名、属性和操作3部分组成。 对象的基本特点

17、：标识惟一性、分类性、多态性 封装性、模块独立性好 （2）封装 封装是一种信息隐蔽技术，用户只能看见对象封装界 面上的信息，对象的内部实现是隐蔽的。第33页，共65页，2022年，5月20日，6点11分，星期一（3）属性 属性就是对象的特征，是对象外观及行为的特征。（4）类和实例 类：指具有共同属性、方法的对象的集合 实例：类的一个具体应用就是一个实例（5）消息 实例之间相互传递的信息叫消息第34页，共65页，2022年，5月20日，6点11分，星期一（6）继承 继承是在已有的类定义的基础上建立新类的定义技术。（7）多态性和动态绑定 多态性：指同一操作作用于不同对象可以有不同解释 产生不同的执

18、行结果。 动态绑定：在运行过程中，当一个对象发送消息请求 服务时，根据接收对象的具体情况将请求的 操作和具体实现的方法进行连接。第35页，共65页，2022年，5月20日，6点11分，星期一例题讲解第36页，共65页，2022年，5月20日，6点11分，星期一结构化程序设计的3种结构是 A) 顺序结构、选择结构、转移结构 B) 分支结构、等价结构、循环结构 C) 多分支结构、赋值结构、等价结构 D) 顺序结构、选择结构、循环结构在设计程序时，应采纳的原则之一是 A) 不限制goto语句的使用 B) 减少或取消注解行 C) 程序越短越好D) 程序结构应有助于读者理解 对建立良好的程序设计风格，下

19、面描述正确的是 A) 程序应简单、清晰、可读性好 B) 符号名的命名只要符合语法 C) 充分考虑程序的执行效率 D) 程序的注释可有可无第37页，共65页，2022年，5月20日，6点11分，星期一结构化程序设计主要强调的是 A) 程序的规模B) 程序的效率 C) 程序设计语言的先进性 D) 程序易读性 以下不属于对象的基本特点的是 A) 分类性 B) 多态性 C) 继承性D) 封装性 在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的 A) 安全性B) 一致性 C) 可理解性D) 合理性第38页，共65页，2022年，5月20日，6点11分，

20、星期一下列叙述中，不属于结构化程序设计方法的主要原则的是 A) 自顶向下 B) 由底向上 C) 模块化 D) 限制使用goto语句 对象实现了数据和操作的结合，是指对数据和数据的操作进行 A) 结合 B) 隐藏 C) 封装 D) 抽象第39页，共65页，2022年，5月20日，6点11分，星期一在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送A）调用语句 B）命令 C）口令 D）消息下列对象概念描述错误的是A）任何对象都必须有继承性B）对象是属性和方法的封装体C）对象间的通讯靠消息传递D）操作是对象的动态属性第40页，共65页，2022年，5月20日，6点11分，星期一在面向对

21、象的程序设计中，类描述的是具有相似性质的一组 【】 在面向对象方法中，类之间共享属性和操作的机制称为 【】 。 一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的 【】 。 第41页，共65页，2022年，5月20日，6点11分，星期一一个对象是类的一个 【3】 。 在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为 【4】 。 第42页，共65页，2022年，5月20日，6点11分，星期一 【3】 是一种信息隐蔽技术，目的在于将对象的使用者和对象的设计者分开。 源程序文档化要求程序应加注释。注释一般分为序言性注释和_。在面向对象方法种，信息屏蔽是通过

22、对象的_性来实现的。第43页，共65页，2022年，5月20日，6点11分，星期一结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、_和限制使用goto语句。下面描述中，符合结构化程序设计风格的是_。第44页，共65页，2022年，5月20日，6点11分，星期一。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个_。下面概念中，不属于面向对象方法的是_第45页，共65页，2022年，5月20日，6点11分，星期一第三部分 软件工程一、基本概念1、软件定义和软件特点 定义：软件是包括程序、数据及相关文档的完整指令。 与硬件相互依存，构成计算机系统。 特点1）软件是一种逻辑实

23、体 （2）软件的生产和硬件不同，没有明显的制作过程 （3）软件在运行、使用期间不存在磨损、老化问题 （4）软件的开发和运行具有依赖计算机系统的特性 受计算机系统的限制，软件移植可能会有问题 （5）软件的复杂性高，成本昂贵 （6）软件开发涉及诸多社会因素第46页，共65页，2022年，5月20日，6点11分，星期一2、软件危机与软件工程 软件危机：指在软件在开发和维护过程中所遇到的一系列 严重问题。包括成本、质量、生产率等 软件工程：是应用于计算机软件的定义、开发和维护的一 整套方法、工具、文档实践标准和工序 核心思想是： 把软件产品作为一个工程产品处理。 软件工程三要素： 方法、工具和过程第4

24、7页，共65页，2022年，5月20日，6点11分，星期一3、软件工程过程和软件生命周期 软件工程过程：是指为了获得软件产品，由软件工程师完 成的一系列软件工程活动。 软件工程四种活动： 软件规格说明、软件开发、软件确认、软件演进 软件生命周期： （1）可行性研究与计划确定 （2）需求分析 （3）软件设计（结构模块的划分） （4）软件实现 （5）软件测试 （6）运行和维护 第48页，共65页，2022年，5月20日，6点11分，星期一4、软件工程的目标和原则 目标：付出较低的成本；达到要求的软件功能； 取得较好的软件性能；开发的软件易于移植； 需要较低的维护费用；能按时完成开发，及时交付 原则

25、：抽象、信息隐蔽、模块化、局部化、确定性 一致性、完备性和可验证性。第49页，共65页，2022年，5月20日，6点11分，星期一二、结构化分析1、需求分析 定义：通过文档描述用户解决问题或达到目标所需的条 件或权能，及系统要满足合同、标准规范所具有 的条件。 需求分析阶段的工作： 需求获取、 需求分析、 编写需求规格说明书、 需求评审第50页，共65页，2022年，5月20日，6点11分，星期一2、需求分析的方法 （1）结构化分析方法 SA：面向数据流的结构化分析方法 JSD：面向数据结构Jackson方法 DSSD：面向数据结构的结构化数据系统开发方法 （2）面向对象的分析方法OOA第51

26、页，共65页，2022年，5月20日，6点11分，星期一3、结构化分析方法 定义：就是使用数据流图（DFD）、数据字典（DD）、 结构化英语、判定表和判定树等工具，建立一种 新的、称为结构化规格说明的目标文档。4、软件需求规则说明书 是需求分析阶段的最后成果，是软件开发中的重要文档之一 第52页，共65页，2022年，5月20日，6点11分，星期一5、软件设计 从技术观点来看，软件设计包括如下几个过程： （1）软件结构设计：定义软件系统各部件之间的关系 （2）数据设计：将分析时创建的模型转为数据结构的定义 （3）接口设计：描述软件内部、软件和操作系统之间及软 件与人之间如何通信。 （4）过程设

27、计：把系统结构部件转换成软件的过程描述 从工程管理来看，软件设计分为： （1）概要设计：确定总体结构，模块的划分 （2）详细设计：确定每一模块的实现。第53页，共65页，2022年，5月20日，6点11分，星期一6、软件模块的独立性 独立性：每个模块完成系统要求的独立的功能，与其他 模块的联系最少且接口简单。 独立性的两个标准： 耦合和内聚（应满足：低耦合、高内聚） 耦合：模块之间联系的紧密程度。 内聚：模块内部各元素之间联系的紧密程度第54页，共65页，2022年，5月20日，6点11分，星期一7、概要设计的准则 （1）提高模块独立性 （2）模块规模适度 （3）深度、宽度、扇出和扇入适当 好

28、的软件结构设计应该满足： 顶层扇出教高、中间扇出教少、低层模块高扇入 （4）使模块的作用域在该模块的控制域内 （5）应减少模块的接口和界面的复杂性 （6）设计成单入口和单出口的模块第55页，共65页，2022年，5月20日，6点11分，星期一8、数据流类型 两种：交换流和事物流第56页，共65页，2022年，5月20日，6点11分，星期一9、软件测试的目的和方法 目的：尽可能多地发现软件产品中的错误和缺陷。 准则 （1）所有测试应追溯到需求 （2）严格执行测试计划，排除测试的随意性 （3）充分注意测试中的群集显现 （4）程序应避免检查自己的程序 （5）穷举测试不能 （6）妥善保存测试计划、测试用例、出错统计 和最终分析报告，为维护提供方便。 方法：白盒测试：根据程序的内部逻辑来设计测试 黑盒测试：根据程序的功能说明来设计测试第57页，共65页，2022年，5月20日，6点11分，星期一10、软件测试的实施过程 单元测试：对各模块进行正确性检验 集成测试：测试与组装软件的测试，发现与接口有关的问题 验收测试：验证软件的功能、性能 系统测试：将测试确认的软件加入到计算机系统中进行测试第58页，共65页，2022年，5月20日，6点11分，星期一11、程序调试 是指诊断和改正程序中 的错误。 其关键是推断程序内部的错误位置及原因。 调试