计算机等级考试二级MSOFFICE公共基础知识.pdfVIP

第一部分二级公共基础知识（10 分） 第一章：基本数据结构与算法（3 分） 1.算法的基本概念 1.1 算法是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法。 1.2 算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。有穷性指的算法运算时 间是有限的。 1.3 算法复杂度：时间复杂度与空间复杂度。 算法的时间复杂度是指执行算法所需要的计算工作量，即算法在执行过程中的基本运算次数。 算法的空间复杂度是指算法在执行过程中所需要的内存空间。两者没有直接关系。 2.数据结构的定义 2.1 数据结构，通俗的讲就是数据元素之间的前后间关系，一个数据结构通常用图形表示。 其中数据元素用一个方框表示，称作数据结点，而各个元素之间的关系用一条有向线段表示， 从前个结点指向后个结点。 比如一年四季数据结构和家庭成员辈分关系数据结构： 在这种数据结构的图形中，没有前结点的称为根结点，没有后结点的称为终端结点即叶子结 点，春和父亲是根结点，冬，儿子，女儿是叶子结点。 对于数据结构的计算，插入就是新增一个结点，删除就是删除一个结点，插入删除是数据结 构的两种基本运算。 2.2 线性结构与非线性结构 根据数据结构中各元素之间前后关系的复杂程度，一般将数据结构分为两大类型：线性结构 与非线性结构。 线性结构，又称为线形表，是指满足两个条件的数据结构，有且只有一个根结点，每个结点 最多有一个前结点，也最多有一个后结点，不满足这两个条件的就是非线性结构。常见的线 性结构有：线性表、栈、队列、线性链表、循环队列等，其中栈和队列是两种特殊的线性结 构。 3.栈和队列的定义 3.1 栈：是只能在线性结构的一端进行计算（插入或删除）。允许插入或者删除的那段叫栈顶， 不允许插入和删除的叫栈底。总是先进后出，后进先出。栈底指针不变，栈中元素随栈顶指 针的变化而动态变化。 3.2 队列：只能在表的一端进行插入（队尾），在表的另一端进行删除的线性表（队头），是 先进先出表。 3.3 队列的顺序存储结构一般采用循环队列的形式，是一种顺序存储结构。循环队列的队头 指针与队尾指针都不是固定的，随入队与出队操作变化，队列中的元素随队头指针与队尾指 针的变化而动态变化。 4.树的基本概念，二叉树的定义及其存储结构 常见的非线性结构有两个：树和二叉树。在树结构中每个结点只有一个前件，称为父结点， 每个父结点可以有多个后结点，后结点称为子结点。树的根结点没有前件，树具有层次结构， 树的层次叫树的深度。根结点在第一层。二叉树是每个结点最多有两个结点的树(左右子树)， 分支称为二叉树的度，也就是说二叉树最多有两个度，对于度为0 的结点（也就是叶子结点） 总比度为2 的结点多一个。总结：叶子结点+度为2 的结点+度为1 的结点=总结点数；对于 二叉树的第N 层，最多有2n-1 个结点。 5.查找和排序 5.1 遍历：前序遍历、中序遍历、后序遍历。前序遍历：先查根结点再查左子树，最后右子 树；中序遍历：先左子树，然后根结点，最后右子树；后序遍历：先左右子树，最后根结 点。例如：A 是根，B 是左,C 是右,那么前序是ABC ，中序是BAC，后序是BCA 5.2 排序：对于长度为N 的线性表排序，除了堆排序算法的比较次数是 ， 其他的：快速排序、冒泡排序、简单插入排序次数都是n(n-1)/2。 第二章：程序设计基础（2 分） 1.程序设计方法与风格：经过了结构化程序设计和面向对象的程序设计阶段。设计风格是： 源程序文档化、数据说明的方法要规范有序、语句的结构要简单易懂，避免滥用goto 语句、 输入和输出注重风格。 2.结构化程序设计：四条基本原则：（1）自顶向下（先考虑整体）（2 ）逐步求精（一步步细 化）（3 ）模块化（将复杂目标分解为多个小目标）（4 ）限制使用goto 语句（goto 语句的数 量与程序质量成反比）。 3.面向对象的程序设计：对象是软件系统中用来描述客观事物的一个实体，有如下一些基本 特点：标识唯一性、分类性、多态性、封装性、模块独立性好。对象间通信靠消息传递，继 承的指能够直接获得已有的性质和特征，而不必重复定义他们，继承是指类之间共享属性和 操作的机制。 第三章：软件工程基础（3 分） 1.软件工程的基本概念 1.1 软件工程源于软件危机，是指在计算机软件的开发和维护过程中遇到的一系列严重为题。 软件需求的增长得不到满足，软件开发成本和进度无法控制，软件质量难以保证，软件补课 维护和维护度非常低，软件的成本不断提高，软件开发生产了的提高赶不上硬件的