全国计算机等级考试公共基础知识

计算机等级考试公共基础知一 数据结构与算算法的基本特征（可行性、确定性、有穷性、输入和输出数据结构是一门研究数据组织，和运算的一般方法的学结构：顺序线性表是n(a1，a2，……，ai，……，an)nn=0后继.1个数据元素无前驱,最后一个数据元素无后继线性表的顺序结构及其插入与删除操线性表中数据元素类型一致，只有数据域，空间利用率高所有元素所占的空间是连续的各数据元素在空间中是按逻辑顺序依次存放的插入算法的分析EEis1(ni1)n12删除算法的分析EEdl1(ni)nnn2总结栈栈底——空栈——用顺序结构表示的顺序栈用一组连续的单元存放自栈底到栈顶的数据元素一般用一维数栈和队列通常采用的结构是链条结构和数树（Node：结点的度（Degree：结点拥有的数。（Leaf（Child：（Sibling（Parent树的深度（Depth)：树中结点的最大层次数。树的度：结点所具有的最大的度：M二叉树一种特殊的树形结构特点是树中每个结点最多只能有两棵(即二i2i-1（i1）k2k-1对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i=1,i是二叉树的根,无双亲;i>1,Parent(i)是结点|i/2|。2i>n,i无左孩子(i为叶子结点)Lchild(i)是2i。2i+1>n,iRchild(i)02树的结点无左、右之分，二叉树的结点有明确的左、右之分先序遍历(DLR):根结点，按先序遍历左，按先序遍历右。中序遍历(LDR):按中序遍历左，根结点，按中序遍历右。后序遍历(LRD):按后序遍历左，按后序遍历右，根结点先序遍历：DL 中序遍历：LD 后序遍历：LR 顺序查找（线性查找对给定的一关键字K，从线性表的一端开始，逐个进KK的记录或到达表的另其比顺序查找方法效率高，的情况下，需要比较log2n次

2号元素开始，顺序从数组中取出元素，并将该nO(n2)）nn-1趟O(n1.52n个元素中选出次小的记录交换到第二个位置上）一个非叶子结点的关键字大于等于（或小于等于的关键字的O(nlog2n)）最好平均顺序结构的n-n(n-正序的表，nn(n-与表的初始数据无关，nnn-n(n-正序的表，nn(n-n序二 程序设计基源程序的文档化：符号名:见名知注释（序言性和功能性注释GOTO3只有一个 限制使用goto语句结构化程序设计是把模块分割方法作为对大型系统进行分析的，使软件研制中存在的效率低质量难以保证调试复杂等问题3部分组成标识唯一性（对象可区分分类 （对象抽象成类多态 （同一操作可以是不同对象的行为封装 （只能看到对象的外部特性模块独立性好（对象内部各元素结合紧密、内聚性强一个类所包含的方法和数据描述一组对象的共为和属性。封装对象的内部实现受保护，外界不能消息继承多态性三 软件工程基、 、应用软件、系统软件、支撑软件（或工具软件软件早期的软件主要指程序，采用工作方式，缺少相关文档，质量低，这些问题称为“软件”，软件工程概念的出现源自于软。软件主要表现在成本、质量、生产率等问题软件工程是应用于计算机软件的定义开发和的一整套方法工具、方法：完成软件工程项目的技术过程：支持软件开发的各个环节的控制、管理将方法和工具综合起来,、将软件产品从提出实现使用到停止使用退役的过程称为软、。分为软件定义、软件开发及软件运行3个阶段是持续时间最可性，降低代价。6（1）（2）（3）接口设计是描述软件内部、软件和操作系统之间及软件与人之间如何软件实现：编程。高级程序员和程序员产生源程序运行与数据流图数据字典、严格的定义，使得用户和系统分析员对于输入、输出成分和、5数据结构、数据流、数据、和处理过程。数据字典是结构化分析的即完成该加工的一组动作是