计算机二级msoffice考试有关公共基础知识点总结.pdfVIP

第一部分算法与数据结构历年比例41%

1、算法

◆问题处理方案的正确而完整的描述称为算法;算法分析的目的是,分析算法的效率以求改进;算法的基本

特征是可行性、确定性、有穷性和拥有足够情报;

◆算法的有穷性是指：算法程序的运行时间是有限的;

◆算法的复杂度是衡量算法好坏的度量,分为时间复杂度和空间复杂度;

★★时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度是指算法执行过程中所需的存储空

间;

◆算法时间复杂度或空间复杂度中的一项的值,没有办法推出另一项的值;

2、数据结构

◆数据结构分为逻辑结构和存储结构;线性结构和非线性结构属于逻辑结构;顺序、链式、索引属于存储结

构物理结构;循环队列属于存储结构;

★数据的存储结构又称为物理结构,是数据的逻辑结构在计算机存储空间中的存放形式;

◆一个逻辑结构可以有多种存储结构,且各种存储结构影响数据处理的效率;程序执行的效率与数据的存储

结构密切相关;

◆数据结构分为线性结构和非线性结构,带链的队列属于线性结构;

◆线性表的存储结构主要分为顺序存储结构和链式存储结构;顺序存储结构的存储一定是连续的,链式存储

的存储空间不一定是连续的;

◆有序线性表既可以采用顺序存储结构,也可以采用链式存储结构;

◆队列是一种特殊的线性表,循环队列按照先进先出原则组织数据;循环队列是队列的顺序存储结构;

◆数据的独立性分为物理独立性和逻辑独立性;当数据的存储结构改变时,其逻辑结构可以不变,因此,基于

逻辑结构的应用程序可以不用修改,称为物理独立性;

3、栈和队列

★★栈是一种特殊的线性表,是只能在一端进行插入和删除的线性表,特点是FILOFirstInLastOut;

★★栈是先进后出的线性表;栈具有记忆作用;对栈的插入与删除操作中,不需要改变栈底指针;假定让元素

1、2、3、A、B依次入栈,则出栈的顺序是：B、A、3、2、1;

◆栈与队列都是线性结构,树是非线性结构;支持子程序调用的数据结构是栈;

◆栈与队列的共同点是,都只允许在端点处插入和删除元素;

◆栈只能顺序存储的描述是错误的;栈可以有顺序和链式两种存储方式;

★★队列是允许在一段插入,在另一端进行删除的线性表,其特点是先进先出;

◆循环队列中元素的个数是由队头指针和队尾指针共同决定;循环队列的头指针为front,尾指针为rear,容

量为maxSize,则循环队列中元素的个数是rear-front+maxSizemodmaxSize;

4、线性链表

◆线性链表是线性表的链式存储结构;用链表表示线性表的优点是便于插入和删除操作;

◆线性链表的存储空间不一定连续,且个元素的存储顺序是任意的;

5、查找技术

◆对于长度为n的线性表,顺序查找最坏情况下需要比较n次;对数据是否有序没有要求;◆顺序查找最好

情况下查询次数是1,最坏情况下是n,平均为1+n/2;

★★对于长度为n的有序线性表,二分法最坏情况下只需要比较log2n次;数据必须有序

◆能用二分法进行查找的是顺序存储的有序线性表;

6、排序技术

★★对于长度为n的线性表,冒泡排序、快速排序、简单插入排序、简单选择排序这四种排序方式在最坏情

况下的比较次数相同,都是nn-1/2;堆排序的效率最高,是nlog2n;★★希尔排序最坏情况下需要次比较;希尔排

序属于插入类排序法;

◆已知数据表A中每个元素距最终位置不远,为节省时间,应该采用的算法是直接插入排序;选择排序、插入

排序、快速排序、归并排序中对内存要求最大的是归并排序;

第二部分软件工程基础历年比例27%

1、软件工程基本概念

★★软件是包括程序、数据及相关文档的完整集合,软件是一种逻辑产品;软件工程三要素包括方法、工具

和过程,其中过程支持软件开发的各个环节的控制和管理;

◆软件工程的核心思想：把软件产品当作是一个工程产品来处理,强调在软件开发过程中应用工程化原则;

◆从工程管理角度,软件设计一般分为两步完成,它们是概要设计和详细设计;

★★软件生命周期可分为多个阶段,一般分为定义阶段、开发阶段和维护阶段,编码和测试属于开发阶段;

◆需求分析阶段产生的主要文档是软件需求规格说