计算机国二office公共基础知识

1、文档编码 : CY5G1S3H4R10 HQ3R10D5W4J9 ZL6B6D7D4B2第 1 章 数据结构与算法（10-12 分）考点：1.算法 * * 2.数据结构 * 3.线性表及其次序储备结构4.栈和队列 * 5.线性链表 * 6.树与二叉树 * 7.查找技术 * 8.排序技术 * 一、数据结构与算法1、概念算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作2、数据的规律结构线性结构 例：一维数组、链表、栈、队列、串、线性表 非线性结构 例：多维数组、广义表、树、图 3、数据的储备结构 线性表 次序储备方法：线性表中全部元素所占的储备空间是连续的

2、是按规律次序依次存放的; 线性表中各数据元素在储备空间中链接储备方法：规律上相邻的结点,物理上也相邻,储备单元可以是连续的,也可以是不连续的运算机中有数据进行处理时,数据的储备结构对程序的执行效率有很大的关系一种数据的规律结构依据需要可以表示成多种储备结构；数组是数据的规律结构,可以用多种存储结构来表示线性链表：就是指线性表的链式储备结构,简称链表 4、算法的基本特点可行性：针对实际问题而设计的算法,执行后能够得到中意的结果确定性：算法中的每一个步骤都必需有明确的定义,不答应显现歧义性有穷性：算法必需在有限时间内做完,即必需在执行有限个步骤之后终止,算法程序的运行时间 是有限的拥有足够的情报：

3、要使算法有效必需为算法供应足够的情报当算法拥有足够的情报时,此算法才最有效的；而当供应的情报不够时,算法可能无效 5、算法的复杂度时间复杂度：该算法执行的时间耗费,是指执行算法所需要的运算工作量,即算法执行过程中所需要的基本运算次数空间复杂度：该算法执行时所耗费的储备空间 6、次序表和链表的比较：基于空间的考虑：1 次序表的储备空间是静态支配的,而链表的储备空间是动态支配的；2 次序表占的储备空间必需是连续的,而链表占的储备空间可以是连续的,也可是不连续的二、栈栈实际也是线性表,只不过是一种特殊的线性表；栈称为“先进后出 ”出栈D 入栈表或“后进先出 ” 表,次序储备、链式储备栈顶top 栈的

4、运算：求栈中元素的个数：栈底元素栈顶元素栈是限定在一端进行插入与删除的线性表,答应插入元素的一端为栈顶,C 答应删除元素的一端为栈底,栈顶元素总是最终被插入的元素,也是最B A 栈底 bottom 先被删除的元素；栈底元素就总是最先被插入而最终被删除的元素三、队列队列也是一种运算受限的线性表,是一种“先进先出 ” ,“ 后进后出 ” 的线性表,次序储备、链式储备队列的运算：求队列中元素的个数：当 rearfront 时, rear front 当 rearfront 时 ,rear-front+mm代表队列的容量 循环队列仍然是次序储备结构,是队列常接受的形式队列是一种线性表,它答应在一端进行

5、插入,在另一端进行删除出队front ：队头Rear：队尾四、树与二叉树（非线性结构）入队1、树节点：树中的每一个点叫做节点,分为根节点 0 或 1 个 、父节点、子节点度：一个结点拥有的子树数称为该结点的度；一棵树的度是指该树中结点的最大度数；度为1 的 树C G 二叉树C 完全二叉树 F 点节叫做 n1,度为 2 的节点叫做n2 叶子节点：度为零的结点称为叶子（没有子节点的节点）叫做 n0 A 深度：树中结点的最大层数称为树的高度或深度2、二叉树B 二叉树：由左树和右树组成,二叉树的度=1 D B E C F 性质 1：二叉树第性质 2：深度为 m的二叉树至多有 2 m-1 个结点 k=1

6、 D 性质 3：度为 2 的结点数为 n2,度为 0 的节点叫做 n0,就 n0=n2+1E F G （度为 0 的节点比度为 点个数： n=n0+n1+n22 的节点多一个） ,整个二叉树节性质 4：具有 n 个结点的完全二叉树的深度至少为log2n+1 ,其中log2n表示取 log 2n 的整数部分二叉树的遍历：遍历：是指沿着某条搜寻路线,依次对树中每个结点均做一次且仅做一次拜望（1）前序遍历：拜望根结点左子树右子树D B E A C F （2）中序遍历：左子树拜望根结点右子树（3）后序遍历：左子树右子树拜望根结点G 例：前序： ABDEGCF 中序： DBGEACF 后序： DGEBF

7、CA 五、排序冒泡排序：是最简洁的一种交换类排序法；在 最坏 的情形下,对长度为 n 的线性表排序,冒泡排序需要比较的次数为 nn-1/2,其 时间复杂度为 On 2 直接选择排序：最坏情形要比较的次数为 On 2,其 时间复杂度为 On 2直接插入排序：最坏的情形下,时间复杂度为 On 2快速排序：平均时间为 Onlog 2n ,最坏情形下,时间效率为 On 2 堆排序：最坏情形下,时间复杂度为 Onlog2n 各种内部排序方法的比较排序方法 最坏时间直接插入 On 2 或 nn-1/2 直接选择 On 2 或 nn-1/2 冒 泡 On 2 或 nn-1/2 快 速 On 2 或 nn-1

8、/2 堆 Onlog 2n 六、查找次序查找：即适用次序储备结构,又适用链式储备结构；对长度为 n 的线性表进行次序查找,在最坏情形下需要比较 n 次二分查找：要求线性表是有序表,另外,二分查找只适用次序储备结构,在链式储备结构上无法实现二分查找二分法查找只适用于次序储备的有序表,在最坏情形下,二分查找需要比较 log2n 次在平均情形下,在次序储备的线性表中查询一个元素,需要一半的元素,在 最坏情形 下,就需要比较线性表中 全部 的元素；第 2 章 程序设计基础（2-4 分）考点：1. 程序设计方法和风格 * 2. 结构化程序设计 * 3. 面对对象的程序设计 * 一、程序设计方法与风格 1

9、、程序设计 指设计、编制、调试程序的方法和过程 2、良好的设计风格：（1）源程序文档化：程序注释的目的主要是便利其他人人阅读程序（程序中要有必要的注释）（2）数据说明的方法：数据说明的次序要规范化,增强可读性（程序的可读性好）（3）语句的结构：一行只写一条语句；防止使用临时变量；防止彩复杂条件语句；应使用库函数；程序模块化；确保模块独立；不要修补不良结构的程序,防止滥用 goto 语句（4）输入输出：对输入数据检查合法性；排列合理；输入格式简洁；应答应使用自由格式和默认值；应在屏幕上给出状态信息（输入数据前要有提示信息）* 模块设计要保证低耦合、高内聚 二、结构化程序设计 1、结构化程序设计的

10、原就：自顶向下、逐步求精、模块化及限制使用 goto 语句 2、结构化程序的基本结构：次序、选择、循环结构三、面对对象的程序设计 1、对象的特点：标识唯独性、分类性、多态性、封装性、模块独立性好（1）标识唯独性：对象是可以区分的（2）分类性：具有相同属性和操作的对象可以抽象成一个类（3）多态性：同一个操作可以是不同对象的行为,是指在类中定义名称相同的函数,但是这些 函数的参数或者返回值的类型不同（4）封装性：对外部只供应接口,便利用户调用,内部实现对外不行见,可实现信息隐匿,是 指将对象分为内部实现和外部接口两个部分（5）模块独立性好：对象内部各种元素彼此结合紧密,内聚性好 2、类：是具有共同

11、属性、共同方法的一组对象的集合,是关于对象的抽象描述,反映属于该对象类型的全部 对象的性质, 类是对象的抽象,而一个对象就是其对应类的一个实例 3、继承：是指能够直接获得已有的性质和特点,而不必重复地定义它们 4、多态性：对象依据所接收的消息而做出动作,同样的消息被不同的对象接收时可导致完全不同的行为,该现象称为多态性第 3 章 软件工程基础（8 分）考点：1. 软件工程基本概念 * 2. 结构化分析方法 * 3. 结构化设计方法 * 4. 软件测试 * 5. 程序的调试 * 一、基本概念软件：包括 程序、数据、文档 的完整集合软件按功能分为：应用软件、系统软件、支撑软件二、软件工程软程包含

12、3 个要素： 方法、工具和过程方法是完成软件开发各项任务的技术手段工具支持软件的开发、治理、文档生成过程支持软件开发的各个环的把握、治理软件工程争论的主要内容是软件开发技术和软件开发治理两个方面；软件工程的原就：抽象、信息隐匿、模块化、局部化、确定性、一样性、完备性、可验证性抽象：接受分层抽象、自顶向下、逐层细化的方法把握软件开发过程的复杂性信息隐匿：将模块设计成“ 黑箱”实现分别的原就,实现的细节隐匿在模块内部；这就是信息封装,使用与模块化：有助于信息隐匿和抽象,有助于表示复杂的系统 局部化：保证模块之间具有松散的耦合关系,模块内部具有较强的内聚,这有助于把握分解 的复杂性 确定性：软件开发

13、过程中全部概念的表达应是确定的、无歧义的、规范的 可验证性：开发大型的软件系统需要对系统自顶向下、逐层分解,以确保系统的正确性三、软件工程过程所进行的基本活动主要包含4 种：软件规格说明、软件开发、软件确认、软件演进软件规格说明：规定软件的功能以及运行的限制软件开发：产生中意规格说明的软件软件确认：确认能够中意用户提出的要求四、软件生命周期软件生存周期：通常把软件产品从提出、实现、使用、爱护到停止使用、退役的过程称为软件生命周期软件生命周期分为 3 个时期共 8 个阶段：1. 软件定义时期：包括问题定义、可行性和需求分析 3 个阶段2. 软件开发期：包括 概要设计、详细设计、实现和测试 4 个

14、阶段3. 运行爱护期：即运行爱护阶段软件生命周期各阶段的主要任务：1. 问题定义：2. 可行性争论与方案制定：3. 需求分析：对待开发软件提出需求进行分析并给出详细定义；编写软件规格说明书及初步的用户手册,提交评审；4. 软件设计：通常又分为概要设计和详细设计两个阶段,给出软件的结构、模块的划分、功能的支配以及处理流程；该阶段提交评审的文档有概要设计说明书、详细设计说明书和测试方案初稿5. 软件实现：在软件设计的基础上编写程序；该阶段完成的文档有用户手册、操作手册等面对用户的文档,以及为下一步做预备而编写的单元测试方案6. 软件测试：在设计测试用例的基础上,检验软件的各个组成部分；编写测试分析

15、报告7. 运行爱护：五、结构化分析方法1、需求分析和需求分析方法1 、需求分析阶段的工作：需求猎取需求分析需求编写规格说明书需求评审2 、需求分析方法：常用见的需分析方法：（ 1）结构化分析方法静态分析 方法和 动态分析 方法（ 2）面对对象的分析方法：分为2、结构化分析方法使用 数据流图（ DFD）、数据字典（DD）、结构化英语、判定表和判定树等工具,实质是眼于数据流、自顶向下、对系统的功能进行逐层分解、以数据流图和数据字典为主要工具,建立系统的规律模型 3、结构化分析方法的常用工具（1）数据流图（ DFD）数据流图是描述数据处理过程的工具,它是结构化程序设计理论在软件需求分析阶段的 运用

16、程序流程图、 N-S 图、 PAD图是详细设计过程中常用的图形工具 数据流：加工： 又称转换 储备文件： 又称数据源 源/ 潭： 表示系统和环境的接口* 请留意：数据流图与程序流程图中表示的把握流有本质不同,千万不要混淆（2）数据字典：其中有 4 种类型的条目：数据流、数据项、数据储备、加工,对数据流图中全部元 素的定义的集合,是结构化分析的核心；它以一种预备的,无二义性的说明方式为系统的分析、设计爱护供应了有关元素的一样性定义和详细的描述；4、软件需求规格说明书 软件需求规格说明书的标准：正确性、无歧义性、完整性、可验证性、一样性、可懂得性、可修改性、可追踪性六、结构化设计方法1、软件设计概

17、述（1）软件设计的基础：从工程治理的角度来看可分为两步：概要设计和详细设计；软件设计包括软件结构设计、数据设计、接口设计、过程设计概要设计：将软件需求转化为软件体系结构 详细设计：确立每个模块的实现算法和局部数据结构 结构设计：定义软件系统各主要部件之间的关系 数据设计：将分析时创建的模型转化为数据结构的定义 接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信 过程设计：把系统结构部件转换成软件的过程描述（2）软件设计的基本原理和原就：模块化抽象信息隐匿模块独立性模块独立性： 一般来说,要求模块之间的耦合尽可能弱,即模块尽可能独立,且要求模块的 内聚程度尽可能高；内聚性和耦合性

18、是一个问题的两个方向,耦合性能程度弱 的模块,其内聚程序确定高 内聚性：是一个模块内部包含的信息,对于不需要这些信息的其他模块来说是不能拜望的；是一个模块内部各个元素间彼此结合的紧密程序的度量 耦合性：是模块间相互连接的紧密程度的度量 对于模块进行设计时,应当尽量做到高内聚、低耦合,即减弱模块之间的耦和性和提高模块 的内聚性 ,这样有利于提高模块的独立性 2、概要设计（1）编写概要设计文档：概要设计阶段文档有概要设计说明书、数据库设计说明书和集成测试方案 等；（2）概要设计文档评审：在文档编写完成后,要对设计部分是否完整地实现了需求中规定 的功能、性能等要求,设计方案的可行性,关键的处理及内外

19、部接口定义正确性、有效性,各部分之间 的一样性等进行评审；3、详细设计D B E A C F 任务是为软件结构图中的每一个模块的的确现算法和局部数据结构程序流程图（ PFD）：方框表示一个加工步骤菱形表示一个规律条件箭头表示把握流 如右图,宽度是4 G 4、软件系统结构图的宽度：整体把握跨度（最大块数的层）的显示七、软件测试 1、软件测试目的软件测试就是在软件投入运行之前,尽可能多地发觉软件中的错误 2、软件测试方法, 发觉程序中的错误依据软件是否需要被执行,可以分为静态测试和动态测试,假如依据功能划分,可以分为白盒测试和 黑盒测试（1）静态测试：包括代码检查、静态结构分析、代码质量度量等,是

20、指不在运算机上运行被测试程 序,而接受其他手段来达到对程序进行检测的目的,包括人工测试和运算机帮忙静态分析方法；（2）动态测试：主要通过人工进行分析；通过运行软件来检验软件中的动态行为和运行结果的正确 性,并用所设计的测试用倒对程序进行检测的方法（3）白盒测试（结构测试） ：是把程序看成装在一只透亮的白盒子里,测试者完成明白程序的结构和 处理过程,保证所测模块中每一独立路径至少执行一次；保证所测模块全部判定的每一分支至少执行一次；验证全部内部数据结构的有效性；主要方法有规律掩盖、基本路径测试等；（4）黑盒测试（功能测试） ：把程序看成一只黑盒子,测试者完成不明白,或不考虑程序的结构和处理过程,

21、也称为功能测试或数据驱动测试,测试时不考虑程序内部细节、结构和实现方式、仅检验程序结果与说明书的一样性；测试方法主要有：等价划分法、边界分析法、错误估量法、因果图等,主要用于软件确认测试 3、软件测试的实施（1）单元测试：也称模块测试,模块是软件设计的最小单位,单元测试是对模块进行正确性的检验；可以接受静态测试或者动态测试,动态测试通常以白盒测试为主,测试其结构,以 黑盒测试法为辅,测试其功能（2）集成测试：也称组装测试,它是对各模块依据设计要求组装成的程序进行测试,主要目的是发 现与接口有关的错误（3）确认测试的任务是检验软件的功能、性能及其他特点是否与用户的需求一样,它是以需求规格 说明书

22、作为依据的测试；确认测试通常接受黑盒测试（4）系统测试：目的是在真实的系统工作环境下检验软件是否能与系统正确连接,发觉软件与系统 需求不一样的地方 测试用例是为测试设计的数据,测试用倒由测试输入数据与之对应的预期输出结果两部分组成；测试用倒的格式为 （输入值集） ,（输出值集） 八、程序的调试程序调试的任务是诊断和改正程序中的错误, 改正以后仍需要再测试第 4 章 数据库设计基础（8-10 分）考点：1.数据库系统的基本概念 * 2.数据模型 * 3.关系代数 * 4.数据库设计与治理 * 一、数据库系统的基本概念 1、数据、数据库、数据库治理系统（1）数据库（ DB）（2）数据库治理系统（D

23、BMS）：数据库语言：数据定义语言（DDL）：负责数据的模式定义和数据的物理存取构建 数据库操纵语言（DML）：负责数据的操纵,包括查询及增、删除、改操作 数据把握语言：负责数据完整性、安全性的定义与检查以及并发把握、数据复原等功能（3）数据库系统（DBS）三者关系： DBS包含 DB和 DBMS 2、数据库系统的进展（1）、人工治理阶段：在工人治理阶段,数据不储存,没有对数据进行治理的软件,数据不能共享（2）、文件系统阶段：这个时期数据治理的特点是：数据需要长期保留在外储备器中供反复使用；程序和数据之间有了确定的独立性；文件夹形式已经多样化；数据的储备基本上 以记录为单位, 供应了简洁的数据

24、共享与数据治理才能,但它不能供应完整的、统一的治理和共享数据的才能（3）、数据库系统阶段：实现了数据共享,削减了数据冗余；接受了特定的数据模型；真正统一的数据把握功能,能够为多个用户和应用程序供应共享资源 具有数据的集成性（4）、分布式数据库系统阶段 3、数据库系统的基本特点数据库治理系统是数据库系统的核心 数据库系统特点：数据高度集成 数据统一治理把握数据独立性 共享性与低冗余性 4、数据库系统的内部结构体系概念模式：是数据库系统中全局数据规律结构的描述,此种描述是一种抽象的描述,不但要描述 概念记录类型,而且要描述记录之间的联系、所答应的操作、数据的一样性、安全性和其他数据 把握方面的要求

25、外模式：也称为数据库的用户式或子模式,是从概念模式导出的子模式,用户可以通过子模式描 述语言来描述用户级数据库的记录,仍可以利用数据语言对这些记录进行操作；用户使用数据操纵语言对数据库进行操作,实际上是对外模式的外部记录进行操作内模式：也称为数据库的物理式或储备模式；它是由系统程序员设计和组织的、是系统程序员所看到和所懂得的数据库,它给出了数据库物理储备结构与物理存取方法；DBMS一般供应相关的内模式描述语言（DLL）数据库系统一般分为物理独立性与规律独立性两级；物理独立性指数据的物理结构的转变；在数 据系统中,数据的物理结构并不愿定与规律结构一样 概念模式是一个全局模式,而外模式是用户的局部

26、模式,内模式处于底层,它反映了数据在运算机物 理结构中的实际储备形式,概念模式处于中层,它反映了设计者的数据全局规律要求,而外模式处于 最外层,它反映了用户对数据的要求二、数据模型 分为层次模型、网状模型、关系模型 基本概念：一对一、一对多、多对多 E-R 模型：实体集 矩形：实体集椭圆：属性 菱形：联系属性1、层次模型 层次模型的结构是树形结构 联系 2、网状模型 用网状结构表示实体及其之间联系的模型 3、关系模型关系模型接受二维表来表示,每行数据称为元组 ,列叫做 属性以及 用户定义的完整关系模型答应定义三类数据约束,它们是实体完整性约束、参照完整性约束性约束三、关系代数 1、传统的集合运算 并、交、差、笛卡尔积（1）并（）：由 2 个关系运算生成第（记录）的个数相加 例： RS 3 个关系,要求两个关系的元数（字段名称）必需相同,元组R S T 3A B A B A B m 1 1 3 m 1 n 2 3 5 n 2 1 3 （2）交（）：由 2 个关系运算生成第 3 个关系,要求两个关系的元数（字段名称）必需相同,第个关系中只保留前 2 个关系中相同的元组 3 5 例： RS R S T 1A B A B A B m 1 1 3 n 2 n 2 （3）差（ - ）：由 2 个关系运算生成第n 2 3 个关系,要求两个关系的元数（字段名称）必需相同,从第个关系中减去第2 个