《(完整版)计算机国二office公共基础知识.doc》由会员分享，可在线阅读，更多相关《(完整版)计算机国二office公共基础知识.doc（12页珍藏版）》请在金锄头文库上搜索。
1、(完整版)计算机国二office公共基础知识第1章 数据结构与算法(10-12分）考点：1. 算法（*）2. 数据结构(*）3. 线性表及其顺序存储结构(*)4. 栈和队列（*）5. 线性链表(）6. 树与二叉树(*）7. 查找技术（*)8. 排序技术(*）一、数据结构与算法1、概念算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作2、数据的逻辑结构l 线性结构(例：一维数组、链表、栈、队列、串、线性表)l 非线性结构（例：多维数组、广义表、树、图）3、数据的存储结构(线性表）l 顺序存储方法:线性表中所有元素所占的存储空间是连续的;线性表中各数据元素在存
2、储空间中是按逻辑顺序依次存放的l 链接存储方法：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的,也可以是不连续的l 计算机中有数据进行处理时，数据的存储结构对程序的执行效率有很大的关系l 一种数据的逻辑结构根据需要可以表示成多种存储结构.数组是数据的逻辑结构，可以用多种存储结构来表示l 线性链表:就是指线性表的链式存储结构,简称链表4、算法的基本特征l 可行性:针对实际问题而设计的算法，执行后能够得到满意的结果l 确定性：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性l 有穷性：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止,算法程序的运行时间是有限的l 拥有足够的情报
3、:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效5、算法的复杂度l 时间复杂度：该算法执行的时间耗费，是指执行算法所需要的计算工作量,即算法执行过程中所需要的基本运算次数l 空间复杂度：该算法执行时所耗费的存储空间6、顺序表和链表的比较：基于空间的考虑:(1)顺序表的存储空间是静态分配的,而链表的存储空间是动态分配的。（2）顺序表占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续的栈顶 topABCD栈底 bottom入栈出栈二、栈l 栈实际也是线性表，只不过是一种特殊的线性表。栈称为“先进后出表或“后进先出
4、”表，顺序存储、链式存储l 栈的计算：求栈中元素的个数:栈底元素栈顶元素l 栈是限定在一端进行插入与删除的线性表，允许插入元素的一端为栈顶，允许删除元素的一端为栈底，栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素则总是最先被插入而最后被删除的元素三、队列l 队列也是一种运算受限的线性表，是一种“先进先出”，“后进后出的线性表， 顺序存储、链式存储l 队列的计算：求队列中元素的个数：当rearfront时，rearfront 当rear=1)性质2：深度为m的二叉树至多有2m-1个结点(k=1)性质3：度为2的结点数为n2，度为0的节点叫做n0，则n0=n2+1（度为0的节点比度为
5、2的节点多一个），整个二叉树节点个数：n=n0+n1+n2性质4:具有n个结点的完全二叉树的深度至少为log2n+1,其中log2n表示取log2n的整数部分l 二叉树的遍历：遍历：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问(1）前序遍历:ABCDEGF访问根结点-左子树右子树（2）中序遍历：左子树访问根结点-右子树（3）后序遍历：左子树-右子树访问根结点例：前序：ABDEGCF中序：DBGEACF后序:DGEBFCA五、排序l 冒泡排序:是最简单的一种交换类排序法。在最坏的情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n(n1）/2，其时间复杂度为O（n2)l
6、直接选择排序：最坏情况要比较的次数为O(n2) ，其时间复杂度为O（n2）l 直接插入排序：最坏的情况下,时间复杂度为O(n2)l 快速排序：平均时间为O（nlog2n），最坏情况下，时间效率为O(n2）l 堆排序:最坏情况下,时间复杂度为O（nlog2n）各种内部排序方法的比较排序方法最坏时间直接插入O（n2) 或 n（n1）/2直接选择O（n2） 或 n（n-1)/2冒 泡O（n2） 或 n（n-1)/2快 速O(n2） 或 n(n1)/2堆O（nlog2n）六、查找l 顺序查找：即适用顺序存储结构，又适用链式存储结构.对长度为n的线性表进行顺序查找,在最坏情况下需要比较n次l 二分查找：
7、要求线性表是有序表,另外，二分查找只适用顺序存储结构，在链式存储结构上无法实现二分查找l 二分法查找只适用于顺序存储的有序表，在最坏情况下，二分查找需要比较log2n次l 在平均情况下，在顺序存储的线性表中查询一个元素，需要一半的元素，在最坏情况下,则需要比较线性表中所有的元素.第2章 程序设计基础（2-4分）考点：1. 程序设计方法和风格(*)2. 结构化程序设计（*）3. 面向对象的程序设计(*）一、程序设计方法与风格1、程序设计指设计、编制、调试程序的方法和过程2、良好的设计风格：（1）源程序文档化:程序注释的目的主要是方便其他人人阅读程序（程序中要有必要的注释）（2）数据说明的方法:数
8、据说明的次序要规范化，增强可读性（程序的可读性好）（3）语句的结构：一行只写一条语句；避免使用临时变量;避免彩复杂条件语句；应使用库函数；程序模块化；确保模块独立；不要修补不良结构的程序,避免滥用goto语句（4）输入输出：对输入数据检查合法性；排列合理;输入格式简单；应允许使用自由格式和默认值；应在屏幕上给出状态信息（输入数据前要有提示信息)*模块设计要保证低耦合、高内聚二、结构化程序设计1、结构化程序设计的原则：自顶向下、逐步求精、模块化及限制使用goto语句2、结构化程序的基本结构：顺序、选择、循环结构三、面向对象的程序设计1、对象的特点：标识唯一性、分类性、多态性、封装性、模块独立性好
9、（1）标识唯一性：对象是可以区分的(2）分类性：具有相同属性和操作的对象可以抽象成一个类（3）多态性：同一个操作可以是不同对象的行为，是指在类中定义名称相同的函数，但是这些函数的参数或者返回值的类型不同（4)封装性：对外部只提供接口，方便用户调用,内部实现对外不可见，可实现信息隐蔽，是指将对象分为内部实现和外部接口两个部分（5）模块独立性好：对象内部各种元素彼此结合紧密，内聚性好2、类：是具有共同属性、共同方法的一组对象的集合,是关于对象的抽象描述，反映属于该对象类型的所有对象的性质，类是对象的抽象,而一个对象则是其对应类的一个实例3、继承：是指能够直接获得已有的性质和特征，而不必重复地定义它
10、们4、多态性:对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性第3章 软件工程基础(8分）考点:1. 软件工程基本概念(*)2. 结构化分析方法（*）3. 结构化设计方法（*）4. 软件测试（*）5. 程序的调试(*)一、基本概念l 软件：包括程序、数据、文档的完整集合l 软件按功能分为：应用软件、系统软件、支撑软件二、软件工程l 软程包含3个要素:方法、工具和过程方法是完成软件开发各项任务的技术手段工具支持软件的开发、管理、文档生成过程支持软件开发的各个环的控制、管理l 软件工程研究的主要内容是软件开发技术和软件开发管理两个方面.l 软件工程
11、的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性 抽象:采用分层抽象、自顶向下、逐层细化的办法控制软件开发过程的复杂性信息隐蔽：将模块设计成“黑箱，实现的细节隐藏在模块内部.这就是信息封装，使用与实现分离的原则模块化：有助于信息隐蔽和抽象，有助于表示复杂的系统局部化：保证模块之间具有松散的耦合关系,模块内部具有较强的内聚，这有助于控制分解的复杂性确定性：软件开发过程中所有概念的表达应是确定的、无歧义的、规范的可验证性：开发大型的软件系统需要对系统自顶向下、逐层分解，以确保系统的正确性三、软件工程过程l 所进行的基本活动主要包含4种:软件规格说明、软件开发、软件确认、软件
12、演进软件规格说明：规定软件的功能以及运行的限制软件开发：产生满足规格说明的软件软件确认：确认能够满足用户提出的要求四、软件生命周期l 软件生存周期：通常把软件产品从提出、实现、使用、维护到停止使用、退役的过 程称为软件生命周期l 软件生命周期分为3个时期共8个阶段:1. 软件定义时期：包括问题定义、可行性和需求分析3个阶段2. 软件开发期：包括概要设计、详细设计、实现和测试4个阶段3. 运行维护期：即运行维护阶段l 软件生命周期各阶段的主要任务：1. 问题定义:2. 可行性研究与计划制定：3. 需求分析：对待开发软件提出需求进行分析并给出详细定义。编写软件规格说 明书及初步的用户手册,提交评审.4. 软件设计：通常又分为概要设计和详细设计两个阶段，给出软件的结构、模块 的划分、功能的分配以及处理流程。该阶段提交评审的文档有概要 设计说明书、详细设计说明书和测试计划初稿5. 软件实现：在软件设计的基础上编写程序。该阶段完成的文档有用户手册、操 作手册等面向用户的文档，以及为下一步做准备而编写的单元测试 计划6. 软件测试：在设计测试用例的基础上，检验软件的各个组成部分。编写测试分 析报告7. 运行维护:五、结构化分
