发布时间 : 星期二 文章计算机二级公共基础知识要点更新完毕开始阅读
公用基础上 一：算法的概念
算法是指用系统的方法描述解决问题的策略机制。 算法的基本特征（4或5点）： 有穷性、确定性（指意义确定），可行性（程序运行时，所需要的资源很容易获取）、拥有足够的情报=（有零个或多个输入、至少要有一个输出）。 算法的构成要素：（简单了解）
对数据对象的运算和操作、算法的控制结构 二：算法复杂度
时间复杂度概念：执行算法所需要的计算工作量（基本工作量）。 工作量大称为时间复杂度高。
时间复杂度的值 1、最坏情况复杂性 2、期望复杂性 空间复杂度概念：执行算法所需要的内存空间。 需要的内存空间越多，空间复杂度越高。 内存空间包括三部分：算法程序所占空间、输入初始数据所占空间、算法执行中所需额外空间。
时空复杂度（综合考虑时间空间两因素） 最坏情况时间复杂度
（冒泡排序、快速排序、简单插入、简单选择）————n(n-1)/2 希尔排序O（n的1.5次方） O代表最坏情况时间复杂度的符号 堆排序O(n log以2为底n的对数) 顺序排序 n
二分查找 log以二为底n的对数 三、数据结构的基本概念
数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相应的运算，设计出相应的运算，而且确保经过这些运算后，所得到的的新结构仍然是原来的结构类型。 通常把数据的逻辑结构称为数据结构。 (线性结构 非线性结构 第28分钟 1、栈和队列都是线性表
2、线性表两种存储形式：顺序存储【随机访问】。。。。逻辑相邻物理相邻，链式存储【顺序访问】。。。。逻辑相邻物理不相邻。 循环队列属于链式存储
3、 第55分钟：单链表头节点的作用：方便…便于…有利于…。
数据域data 指针域 next 单链表的插入操作（节点后）：1. s.next=p.next 2. p.next=s 单链表的插入操作（节点前）
单链表的删除操作（删除第i个节点）：p.next=p.next.next 循环链表、双链表
双链表的插入操作：1. s.pre=p.pre 2.p.pre.next=s 3.s.next=p 4.p.pre=s 我的重点 双链表的删除操作：1.p.pre.next=p.next 2.p.next.pre=p.pre我的重点)
四、树与二叉树
（1）开始结点为根结点，终端结点为叶子结点。 分支结点
树是由n个结点构成的有限集T, 当n=0时称为空树。否则满足以下条件： 1． 有且只有一个特定的称为根的结点。
2． 其余的结点分为m个互不相交的子集，每个子集本身又是一棵树，称为根的子树。 （2）结点的度：指该结点有多少棵子树。某棵树的度指这棵树的所有结点的度中最大的度数，即度的最大值。度为0指叶子结点
（3）结点的层数：结点的层数从根算起（根为第一层），任何一个结点所在的层数等于其双亲所在的层数+1。 树中结点的最大层数叫做树的高度或深度。
二叉树的基本性质（二叉树不是树）
1、二叉树第i层上的结点数目最多为2的i-1次方（i>=1） 2、深度为k的二叉树至多有2的k 次方减1个结点。 3、在任意一颗二叉树中，若终端结点的个数为n0，度为2的结点数为n2,则n0=n2+1. 二叉树结点度数一共有三种：0度、1度、2度 满二叉树是每一层的结点数都达到最大值。
完全二叉树特点：1.只有最下面两层上的结点的度允许小于二。2.最下面一层的结点必须集中在该层的最左边。
满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。
完全二叉树的性质
设完全二叉树有n个结点，从根结点开始按层序给所有结点i编号：i=1,2,3…..n, 则：（1）若i=1，I 为根结点。I >1 ，则该结点的父亲编号为i/2 向下取整。
（2）若编号I 的结点有左孩子、右孩子，则左孩子的编号为2i，右孩子编号为2i+1 （3）一棵完全二叉树有n 个结点，则叶子结点数为n/2向上取整。
二叉树的遍历
先序（根左右）、中序（左根右）、后序（左右根）遍历
第二章结构化程序设计
1、结构化程序设计原则：
自顶向下，逐步求精，模块化，限制使用goto 语句 2、面向对象程序设计：
对象的基本特点（标识唯一性、分类性、多态性、封装性、模块独立性好） 类是具有相同属性、共同方法的对象的集合 消息是一个实例与另一个实例之间传递的信息，它统一了数据流与控制流 继承是父类和子类之间共享数据、方法的机制。 多态是相同的消息，不同对象具有不同的反应能力。
第三章 软件工程
软件定义：软件=程序+数据+文档
软件危机表现：软件需求的增长得不到满足、用户不满意。
软件开发成本和进度无法控制 软件质量难以保证
软件不可维护或维护程度低 软件成本不断提高
开发生产率的提高赶不上硬件的发展和应用需求的增长
软件工程三要素：工具、过程（支持软件开发的全过程）、方法 软件生命周期：定义、开发、维护（费用最高）三阶段 （1）定义阶段（可行性研究、需求分析）
需求分析里常用的工具有数据流程图DFD、数据字典DD、判定表和判定树。
需求分析的环节：需求获取、需求分析、编写需求规格说明书（是整个分析的阶段性成果）、需求评审
（2）开发阶段（总体设计、详细设计、实现、测试） 测试分为黑盒测试---测功能、白盒测试---测路径 （3）维护阶段（使用、维护、退役）
维护活动包括：改正性、适应性、完善性和预防性维护。
结构化分析方法：常用工具DFD（椭圆表加工、有向箭头表数据流、等号表存储文件、
矩形表源和潭）
模块化原则
高内聚、低耦合
程序调试的方法：强行排错、回溯法、归纳法、演绎法
数据库设计：
数据模型的分类：概念模型（E-R模型：矩形表实体集，椭圆表属性，菱形表关系，直线连接各部分）、逻辑模型（层次、网状、关系）、物理模型
在二维表中元组的分量不能再分成更小的数据项
长度为n的字符串，其子串的数目为1+……+n+1 相同的字符算不同