Ms office 基础知识总结算法：解决问题的操作步骤.(程序可以描述算法)算法的基本特征：1.算法所执行的基本运算次数与问题的规模有关。
2. 算法的空间复杂度:执行这个算法所需要的内存空间。
算法执行期间所需要的储存空间包括3各部分1) 输入数据所占的储存空间2) 程序本身所占的储存空间3) 算法执行过程中所需要的额外空间。
降低算法的复杂程度方法：1) 减少输入数据所占的储存空间以及额外空间2) 采用压缩储存技术。
数据结构：相互有关联的数据元素的集合数据结构分为：1. 数据逻辑结构•步骤可以实现，执行结果达到预期目的。
•步骤明确，不摸棱两可，不准有多义性。
•有限个时间完成。
•算法在拥有足够的输入信息和初始化信息时，才有效的，当提供情报不够时，算法可能无效。
2.数据的储存结构数据的结构表示：B=(D,R)B表示数据结构，D表示数据元素的合集，R是D上关系集合例如：把一日三餐看做一个数据结构，则可表示成：B= {D，R}D= {早餐，午餐，晚餐}R= {（早餐，午餐），（午餐，晚餐）}节点：用中间标有元素值得方框表示数据元素，一般称之为数据节点。
3.线性结构和非线性结构4.线性表及其顺序储存结构1)线性表的基本概念：数据结构中，线性结构习惯称为线性表，线性表是最简单也最常用的一种数据结构。
线性表是n(n≥0)个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。
线性表要么是空表，要么可以表示为(a1 ,a2 , … , a i , … , a n)其中，a i(i=1,2,…,n)是线性表的数据元素，也称为线性表的一个节点，同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。
数组，矩阵，向量等都是线性表。
非线性表的特征：●只有一个根节点，即节点a1,它无前件；●有且只有一个终端节点，即节点a n,它无后件；●除根节点与终端节点外，其他所有节点有且只有一个前件，也有且只有一个后件。
节点个数n称为线性表的长度，当n=0时，称为空表。
（2）线性表的顺序储存结构线性表可以采用顺序储存和链式储存两种储存结构。
做法：将线性表中的元素一个接一个地储存在一片相邻的储存区域中。
顺序表的两个特征:●线性表中所有元素所占的储存空间是连续的；●线性表中各数元素在储存空间中是按逻辑顺序依次存放的。
4，栈和队列(1)栈是一种特殊的线性表；允许插入与删除的一端称为栈顶不允许插入与删除的另一端称为栈底当栈中没有元素时，称为空栈。
修改原则：“后进先出”或“先进后出”栈顶表示:top.栈底表示：bottom栈的计算方式有3种：入栈，退栈和读栈顶元素。
可以采用顺序方式和链接方式实现。
(2)队列及其基本运算1队列的定义:允许在一端插入，再另一端进行删除的线性表；允许进行删除运算的一端称为队头；允许进行插入运算的一端称为队尾队列称为“先进先出”或“后进后出”的线性表Rear表示队尾；front表示队头(3)循环队列及其运算；循环队列：将队列储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
Rear表示队尾；front表示队头循环队列的初始状态为空，即front=rear=m用s来区分队列满还是队列空。
当s=0时表示队列为空；当s=1且front=rear时表示对满。
5.线性链表（1）线性表的基本概念（1）线性链表：线性表的链式存储结构，简称链表。
这种链表每个节点只有一个指针域，又称为单链表。
指向第一个数据元素的头指针HEAD等于NULL或者0时，称为空表。
一个指针域存放前件的地址，称为左指针；一个指针域存放后件的地址，称为右指针；（2）带链的栈栈采用链式存储结构表示，组织成一个单链表。
称为带链的栈。
（3）带链的队列与栈类似，可采用链式存储结构表示。
用一个单链来表示队列，队列中的每一个元素对应链表中的一个节点（4）顺序表和链表的比较（3）循环链表所有节点的指针构成了一个环状链。
6.树与二叉树（1）树的基本概念是一种简单的非线性结构（2）二叉树及其基本性质（1）二叉树的定义：与树不同，但它与树结构很相似特点：●二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点；●每个节点最多有两棵子树，即二叉树中不存在度大于2的节点；●二叉树的子树有左右之分，其次序不能任意颠倒。
（2）性质1)在叉树的第K层上，最多有2K－1（K≥1）个节点2)深度为m的二叉树中，最多有2m－1个节点。
3)对任何一颗二叉树，度为0的节点（即叶子节点）总是比度为2的节点多一个。
4)具有n个节点的二叉树，其深度至少为[log2n]+1,其中【log2n】表示为log2n的整数部分。
（3）满二叉树和完整二叉树指出最后一层外，每一层上的所有节点都有两个子节点的二叉树。
即满二叉树在其第K层上有2K－1个节点，深度为M的满二叉树共有2M－1个节点。
完全二叉树是指最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干节的二叉树。
满二叉树一定是完全二叉树，完全二叉树一般不是满二叉树。
完全二叉树的特点：●叶子节点只可能在最后两层出现；●对于任一节点，若其右子树的深度为M则该节点左子树的深度为M或M＋1.。
性质5：具有n个节点的完全二叉树的深度为【log2n】＋1.。
(3)二叉树的存储结构采用链式存储结构，用于存储二叉树中元素的存储节点由数据域和指针域两部分组成二叉树的存储结构中每一个存储节点有两个指针域，所以，二叉树的链式储存结构也称为二叉链表满二叉树于完全二叉树可以按层次进行顺序存储。
（4）二叉树的遍历：指不重复的访问二叉树的所有节点。
在遍历二叉树过程中先左后右。
二叉树的遍历可以分为3种：前序遍历(DLR)中序遍历（LDR）后序遍历（LRD）。
7.查找技术（1）顺序查找思想：从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果相等，则查找成功，停止查找；若整个线性表扫描完毕，没有找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败。
●最好的情况下，第一个元素就是要查找的元素，则比较次数为1.●最坏的情况下，最后一个元素才是要查找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，比较次数为n次。
●平均情况下，大约需要比较n/2次。
线性表为有序不管是顺序还是链式存储结构顺序线性表为无序如果只能用链式存储结构查找（2）二分法查找线性表必须满足两个条件：1)用顺序存储结构；2)线性表是有序表(非递减排列，从小到大排列，允许相邻元素相等)3)对于长度为n的查询方法●如果于中间值相等，则查找成功，结束查找；●如果小于中间值，则在线性表的后半部分以二分法继续查找；如果大于中间项的值，则在线性表的后半部分以二分法继续查找；顺序查找法每一次指将查找范围减少1；二分法每次可将查找范围减少原来的一半，二分法查找只需要比较log2n次。
8．排序技术指将一个无序序列整理成按值非减顺序排序列的有序序列。
（1）交换类排序法借助数据元素“交换”；来进行的排序1)冒泡排序法基本思想是通过两两相邻数据元素之间的比较和交换，不断地消去逆序直到有序为止。
对于长度为n的线性表排序，冒泡排序需要比较的次数为n(N-1)/2。
2)快速排序基本思想：再待排序的n个元素中取一个元素K（通常取第一元素），以元素K作为分割线标准，把所有大于K元素的数据元素都移到K后面。
但实际的排序效率要比冒泡排序高得多。
（2）插入类排序法每次将一个排序元素，按其元素值得大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。
1.简单插入排顺序是把n个待排序的元素看成是一个有序表和一个无序表，（有序表含一个元素，无序表含另一个元素，每次取无序表中的第一个元素插到有序表中的正确位置，使之增加一个元素的新的有序表。
依序向后移动。
最后长度为n无序表为空，排序完成。
2.希尔排序先取一个整数(称为增量)d1＜n，把全部元素分成d1个组，所有距离为d1倍数的元素放在一组中，组成了一个子序列，对每个子序列分别进行简单插入排序。
然后取d2＜d1重复上述分组和排序工作，直到d i=1，即所有记录在一组中为止。
需要比较次数为n r(1＜r＜2)（3）选择类排序法通过每一趟从待排序序列中选出最小的元素，序列放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。
1.简单选择排序法先从所有n个待排序的数据元素中选择最小的元素，将该元素与第1个元素交换，从剩下的n-1个元素中选出最小的元素与第2个元素交换。
重复这样的操作直到有序为止。
2.堆排序法若有n个元素的序列（h1,h2,h3……h n）,将元素按顺序组成一颗完全二叉树，当且仅当满足下列条件是称为堆。
h i≥h2i h i≤h2i或者h i≥h2i+1 h i≤h2i+1第一种情况称为大根堆，第二种情况称为小根堆堆排序最坏的情况需要nlog2n次比较。
（2）1．2程序设计基础1.程序设计风格主要注意；（1）源程序文档化。
（2）数据说明风格。
（3）语句的结构。
（4）输入和输出。
2.结构化程序设计（1）结构化程序设计原则是自顶向下，逐步求精，模块化及限制使用goto语句。
（2）结构化程序设计的基本结构“顺序结构”“选择结构”和“循环结构”3种基本结构，其共同特征是：严格地只有一个入口和一个出口。
优点：●程序易于理解，使用和维护；●提高了编程工作的效率，降低了软件开发成本。
3.面向对象的程序设计(1)面向对象方法的优点●与人类习惯的思维方法一致●稳定性好；●可重用性好：●容易开发大型软件产品：●可维护性好。
（2）面向对象方法的基本概念1. 对象1.软件工程的基本概念（1）软件的定义于特点计算机软件是由程序，数据及相关文档构成的完整集合，与计算机硬件一起组成计算机系统。
其中程序和数据是机器可执行的，文档是机器不可知性的。
特点：（1）软件是一种逻辑实体，具有抽象性。
（2）软件没有没有明显的制作过程。
（3）软件在使用期间不存在磨损，老化问题。
（4）对软件和环境具有依赖性。
、（5）软件复杂性高，成本昂贵。
（6）软件开发涉及诸多的社会因素。
（2）软件的分类有应用软件，系统软件，支撑软件（或工具软件）1.系统软件——是管理计算机的资源，提高计算机的使用效率，为用户提高各种服务的软件。
2.应用软件——为了应用与特定的领域而开发的软件。
3.支撑软件——介于系统软件和应用软件之间，协助用户开发软件工具型软件，其中包括帮助程序人员开发和维护软件产品的工具软件，也包括帮助管理人员控制开发进程和项目管理的工具软件。
4.软件工具（5）二叉树的存储结构；采用链式存储结构，存储节点由数据域和指针域两部分构成。
（5）需要分析方法●结构化分析方法●面向对象分析方法（概念原则，过程步骤，表示方法，提交文档）●从分析建模的特性来划分（静态分析方法和动态分析方法）●结构化分析是使用数据流图，数据字典，结构化英语，判定表和判定数等工具，1)数据流图上的每个元素都必须命名。