计算机二级office(基础理论)

《计算机二级office(基础理论)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基础理论第一章1、算法：是指解题方案的准确而完整的描述2、算法的基本特征：可行性、确定性、又穷性、拥有足够的情报3、算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法4、算法的复杂度主要包括时间复杂度和空间复杂度5、用算法在执行过程中所需基本运算的执行次数来度量算法的工作量6、数据结构作为计算机的一门学科，主要研究和讨论一下三个方面的问题：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构（2）在对数据进行处理时，各数据元素在计算机中的储存关系，即数据的存储结构（3）对数据结构进行的运算7、数据的逻辑结构：是指带有结构的数据元素的集合8、数据结构应包含（1）表示数

2、据元素的信息（2）表示各数据元素之间的前后件关系9、所谓数据的逻辑结构，是指反应数据元素之间逻辑关系的数据结构10、数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构11、根据数据结构中各数据元素之间前后件关系的复杂程度一般将数据结构分为两大类型：线性结构与非线性结构12、如果一个非空的数据结构满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有一个前件，也最多有一个后件则称该数据结构为线性结构，又称线性表13、线性表是最简单、最常用的一种数据结构14、非线性表有以下结构特征（1）有且只有一个根结点a1，它无前件（2）有且只有一个终结点An，它无后件（3）除根结点与终结端外

3、，其他所有结点有且只有一个前件，也有且只有一个后件，线性表中结点的个数n称为为线性表长度，当n=0时，称为空表15线性表的顺序存储结构具有两个基本特点（1）线性表中所有元素所占的存储空间是连续的（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的16、顺序表的插入、删除运算17、栈：是限定在一端进行插入与删除的线性表18、栈是按照“先进后出”或“后进先出”的原则组织数据的，栈也被称为“先进后出”表或“后进先出”表19、栈中的个数=bottom-top+1(用值大的减值小的再加一)Top=0表示栈空top=m表示栈满支持子程序调用的数据结构是栈。栈的基本运算有三种：入栈、退栈、与读栈顶元素

4、20、队列：是指允许在一端进行插入、而在另一端进行删除的线性表21、队列称为“先进先出”或“后进后出”的线性表22、对列空与对列满的条件：队列空的条件为s=0，队列满的条件为s=1且ftont=rear23、入队运算、是指在循环队列的队尾加入一个新元素退队运算、是指在循环队列的排头位置退出一个元素并赋给指定的变量24、线性表的链式存储式结构称为线性链表。25、（1）在线性链表中查找指定元素（2）线性链表的插入、是指在链式存储结构下的线性表中插入一个新元素（3）线性链表的删除、是指在链式存储结构下的线性表中删除包含指定元素的结点26、树是一种简单的非线性结构27、树这种数据结构的基本特征（1）在

5、树结构中每一个结点只有一个前件，称为父结点没有前件的结点只有一个，称为树的根结点，简称为树的根。（2）在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点（3）在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0在树中，所有结点中的最大的度称为树的度28、树的最大层次称为树的深度29、在树中，以某结点的一个子结点为根构成的树称为该结点的一颗子树，叶子结点没有子树30、二叉树，是一种很有用的非线性结构31、二叉树的特点：（1）非空二叉树只有一个根结点（2）每一个结点最多有两颗子树，每一个结点的度最大为232、二叉树的基本性质：（1）在二叉树的

6、第k层上，最多有2的k-1次方（k>=1）个结点（2）深度为m的二叉树最多有2的m次方-1个结点（深度为m的二叉树是指二叉树共有m层）（3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个（4）具有n个结点的二叉树，其深度至少为【log2N】+1,其中【log2N】表示取其整数部分33、满二叉树与完全二叉树（1）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点（2）完全二叉树：除最后一层外，每一层上的结点树均达到最大值，在最后一层上只缺少右边的若干结点34、完全二叉树的性质：（1）具有m个结点的完全二叉树的深度为【log2N】+1（2）设完全二叉树共有n个结点35

7、、计算机中二叉树通常采用链式存储结构36、二叉树的遍历：是指不重复地访问二叉树中的所有结点（1）前序遍历（2）中序遍历（3）后序遍历37、二分法查找只适用于顺序存储的有序表。二分法查找只需要比较log2N次而顺序查找需要比较n次38、交换类排序法：冒泡排序法、快速排序法39、插入类排序法：简单插入排序法、希尔排序法40、选择类排序法：简单选择排序法、堆排序法第二章1、注释一般分为序言性注释、功能性