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

《计算机国二office公共基础知识.docx》由会员分享，可在线阅读，更多相关《计算机国二office公共基础知识.docx（11页珍藏版）》请在第一文库网上搜索。

1、第1章数据结构及算法(10-12分)考点：1 .算法(*)2 .数据结构(*)3 .线性表及其依次存储结构(*)4 .栈和队列(*)5 .线性链表(*)6 .树及二叉树(*)7 .查找技术(*)8.排序技术(*)一，数据结构及算法1,概念算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作2,数据的逻辑结构 线性结构(例：一维数组，链表，栈，队列，半，线性表)诽线性结构(例：多维数组，广义表，树，图)3,数据的存储结构(线性表) 依次存储方法：线性表中全部元素所占的存储空间是连续的;线性表中各数据元素在存储空间中是按逻辑依次依次存放的 链接存储方法：逻辑上相

2、邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的 计算机中有数据进行处理时，数据的存储结构对程序的执行效率有很大的关系 一种数据的逻辑结构依据须要可以表示成多种存储结构。数组是数据的逻辑结构，可以用多种存储结构来表示 线性链表：就是指线性表的链式存储结构，简称链表4,算法的基本特征 可行性：针对实际问题而设计的算法，执行后能够得到满足的结果 确定性：算法中的每一个步骤都必需有明确的定义，不允许出现歧义性 有穷性：算法必需在有限时间内做完，即必需在执行有限个步骤之后终止，算法程序的运行时间是有限的 拥有足够的情报：要使算法有效必需为算法供应足够的情报当算法拥有足够的情报时，此算法才

3、最有效的；而当供应的情报不够时，算法可能无效5,算法的困难度 时间困难度：该算法执行的时间耗费，是指执行算法所须要的计算工作量，即算法执行过程中所须要的基本运算次数 空间困难度：该算法执行时所耗费的存储空间6,依次表和链表的比较：基于空间的考虑：(1)依次表的存储空间是静态安排的，而链表的存储空间是动态安排的。(2)依次表占的存储空间必需是连续的，而链表占的存储空间可以是连续的，也可是不连续的入栈二，栈 栈实际也是线性表，只不过是一种特别的线性表。栈称为“先进后出”表或“后进先出”表，依次存储，链式存储 栈的计算：求栈中元素的个数：栈底元素一栈顶元素 栈是限定住端进行插入及删除的线性表，允许插

4、入元素的端为枝顶,允许删除元素的一端为栈底，栈顶元素总是最终被插入的元素，也是最先被删除的元素；栈底元素则总是最先被插入而最终被删除的元素三，队列 队列也是一种运算受限的线性表，是一种“先进先出”，“后进后出”的线性表，依次存储，链式存储 队列的计算：求队列中元素的个数：当rearfront时，rear-front当rearfront时，rear-Iront+mm（代表队列的容量） 循环队列仍旧是依次存储结构，是队列常采纳的形式 队列是一种线性表，它允许在一端进行插入，在另一端进行删front：队头Rear：队尾四，树及二叉树（非线性结构）1,树出队一一入队 节点：树中的每一个点叫做节点，分为

5、根节点（0或1个），父节点，子节点 度：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。度为1的点节叫做n1,度为2的节点叫做2 叶子节点：度为零的结点称为叶子（没有子节点的节点） 深度：树中结点的最大层数称为树的高度或深度2,二叉树 二叉树：由左树和右树组成，二叉树的度=D性质2：深度为m的二叉树至多有2-1个结点（k=1）性质3：度为2的结点数为n2,度为0的节点叫做n,贝（度为0的节点比度为2的节点多一个），整个二叉树节点个数：n-n+n1+n2性质4：具有n个结点的完全二叉树的深度至少为Iog2+1,其中1og2n表示取1og2n的整数部分二叉树的遍历：遍历：是

6、指沿着某条搜寻路线，依次对树中每个结点均做一次且仅做一次访问（1）前序遍历：访问根结点一一左子树一一右子树（2）中序遍历：左子树一一访问根结点右子树（3）后序遍历：左子树一一右子树一访问根结点例：前序：BDEGCF中序:DBGEACF后序：DGEBFCA五，排序 冒泡排序：是最简单的一种交换类排序法。在最坏的状况下，对长度为n的线性表排序，冒泡排序须要比较的次数为n（n-1）2,其时间困难度为0（一） 直接选择排序：最坏状况要比较的次数为0（一）,其时间困难度为OGO 直接插入排序：最坏的状况下，时间困难度为0（一） 快速排序：平均时间为O（n1（n）,最坏状况下，时间效率为0（/ 堆排序：最

7、坏状况下，时间困难度为0（n1og2n）各种内部排序方法的比较排序方法最坏时间直接插入0(n2)或n(n-1)2直接选择0(n2)或n(n-1)2冒泡0(n2)或n(n1)2快速0(n2)或n(n-1)2堆0(n1og2n)六，查找 依次查找：即适用依次存储结构，又适用链式存储结构。对长度为n的线性表进行依次查找，在最坏状况下须要比较n次 二分查找：要求线性表是有序表，另外，二分查找只适用依次存储结构，在链式存储结构上无法实现二分查找 二分法查找只适用于依次存储的有序表，在最坏状况下，二分查找须要比较Iogzn次 在平均状况下，在依次存储的线性表中查询一个元素，须要一半的元素，在最坏状况下，则

8、须要比较线性表中全部的元素。第2章程序设计基础（2-4分）考点：1 .程序设计方法和风格（*）2 .结构化程序设计（*）3 .面对对象的程序设计（*）一，程序设计方法及风格1,程序设计指设计，编制，调试程序的方法和过程2,良好的设计风格：（1）源程序文档化：程序注释的目的主要是便利其他人人阅读程序（程序中要有必要的注释）（2）数据说明的方法：数据说明的次序要规范化，增加可读性（程序的可读性好）（3）语句的结构：一行只写一条语句；避开运用临时变量；避开彩困难条件语句；应运用库函数；程序模块化；确保模块独立；不要修补不良结构的程序，避开滥用goto语句（4）输入输出：对输入数据检查合法性；排列合理

9、；输入格式简单；应允许运用自由格式和默认值;应在屏幕上给出状态信息（输入数据前要有提示信息）*模块设计要保证低耦合，高内聚二，结构化程序设计1,结构化程序设计的原则：自顶向下，逐步求精，模块化及限制运用goto语句2,结构化程序的基本结构：依次，选择，循环结构三，面对对象的程序设计1,对象的特点：标识唯一性，分类性，多态性，封装性，模块独立性好(I)标识唯一性：对象是可以区分的(2)分类性：具有相同属性和操作的对象可以抽象成一个类(3)多态性：同一个操作可以是不同对象的行为，是指在类中定义名称相同的函数，但是这些函数的参数或者返回值的类型不同(4)封装性：对外部只供应接口，便利用户调用，内部实

10、现对外不可见，可实现信息隐藏，是指将对象分为内部实现和外部接口两个部分(5)模块独立性好：对象内部各种元素彼此结合紧密，内聚性好2,类：是具有共同属性，共同方法的一组对象的集合，是关于对象的抽象描述，反映属于该对象类型的全部对象的性质，类是对象的抽象，而一个对象则是其对应类的一个实例3,继承：是指能够直接获得已有的性质和特征，而不必重复地定义它们4,多态性：对象依据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性第3章软件工程基础(8分)考点：1 .软件工程基本概念(*)2 .结构化分析方法(*)3 .结构化设计方法(*)4 .软件测试(*)5 .程序

11、的调试(*)基本概念 软件：包括程序，数据，文档的完整集合 软件按功能分为：应用软件，系统软件，支撑软件二，软件工程 软程包含3个要素：方法，工具和过程方法是完成软件开发各项任务的技术手段工具支持软件的开发，管理，文档生成过程支持软件开发的各个环的限制，管理 软件工程探讨的主要内容是软件开发技术和软件开发管理两个方面。 软件工程的原则：抽象，信息隐藏，模块化，局部化，确定性，一样性，完备性，可验证性抽象：采纳分层抽象，自顶向下，逐层细化的方法限制软件开发过程的困难性信息隐藏：将模块设计成“黑箱”，实现的细微环节隐藏在模块内部。这就是信息封装，运用及实现分别的原则模块化：有助于信息隐藏和抽象，有

12、助于表示困难的系统局部化：保证模块之间具有松散的耦合关系，模块内部具有较强的内聚，这有助于限制分解的困难性确定性：软件开发过程中全部概念的表达应是确定的，无歧义的，规范的可验证性：开发大型的软件系统须要对系统自顶向下，逐层分解，以确保系统的正确性三，软件工程由I1 所进行的基本活动主要包含4种：软件规格说明，软件开发，软件确认，软件演进软件规格说明：规定软件的功能以及运行的限制软件开发：产生满足规格说明的软件软件确认：确认能够满足用户提出的要求四，软件生命周期 软件生存周期：通常把软件产品从提出，实现，运用，维护到停止运用，退役的过程称为软件生命周期 软件生命周期分为3个时期共8个阶段：1 .

13、软件定义时期：包括问题定义，可行性和需求分析3个阶段2 .软件开发期：包括概要设计，具体设计，实现和测试4个阶段3 .运行维护期：即运行维护阶段软件生命周期各阶段的主要任务：1 .问题定义：2 .可行性探讨及安排制定：3 .需求分析：对待开发软件提出需求进行分析并给出具体定义。编写软件规格说明书及初步的用户手册，提交评审。4 .软件设计：通常又分为概要设计和具体设计两个阶段，给出软件的结构，模块的划分，功能的安排以及处理流程。该阶段提交评审的文档有概要设计说明书，具体设计说明书和测试安排初稿5 .软件实现：在软件设计的基础上编写程序。该阶段完成的文档有用户手册，操作手册等面对用户的文档，以及为

14、下一步做打算而编写的单元测试安排6 .软件测试：在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告7 .运行维护：五，结构化分析方法1,需求分析和需求分析方法(1),需求分析阶段的工作： 需求获得 需求分析 需求编写规格说明书 需求评审（2）,需求分析方法：常用见的需分析方法：（1）结构化分析方法（2） 面对对象的分析方法：分为静态分析方法和动态分析方法2,结构化分析方法运用数据流图（DH）,数据字典（DD）,结构化英语，判定表和判定树等工具，实质是眼于数据流，自顶向下，对系统的功能进行逐层分解，以数据流图和数据字典为主要工具，建立系统的逻辑模型3,结构化分析方法的常用工具（1）数据流图（DFD） 数据流图是描述数据处理过程的工具，它是结构化程序设计理论在软件需求分析阶段的运用 程序流程图，NT图，PAD图是具体设计过程中常用的图形工具数据流：加工：-（又称转换）存储文件：（U（又称数据源）源/潭：（表示系统和环境的接口）*请留意：数据流图:-1示的限制流有本质不同,千