全国计算机等级考试二级公共基础知识点总结

1、1、 算法是指解决方案的准确而完整的描述2、 算法的四个基本特性： 可行性 确定性 有穷性 拥有足够的情报3、 算法有两个基本的要素组成： 一、数据对象的运算和操作 二、算法的控制结构4、 计算机中的基本操作 算术运算 逻辑运算 关系运算 数据运算5、 算法的控制结构给出了算法的基本框架，不仅决定了算法中各操作的执行顺序，而且也直接反应了算法的设计是否符合结构化的原则。一个算法都可以用顺序、选择、循环3钟基本控制结构组成6、 算法的复杂度主要包括时间复杂度和空间复杂度7、 算法的时间复杂度是执行算法所需要的计算工作量。 他不仅应该与使用的计算机、程序设计语言及程序编制者无关，而且应该与算法实现

2、过程中的许多细节无关。8、 算法的空间复杂度是指执行这个算法所需要的内存空间。9、 如果一个数据结构中没有一个数据元素，则称该数据结构为空的数据结构。10、 根据数据结构中个数据元素之间前后件关系的复杂程度，一般将数据结构分为 线性结构 和 非线性结构11、 如果一个非空的数据结构满足 1、有且只有一个根结点； 2、 每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性结构又称线性表。12、 在一个线性结构中插入或删除任何一个结点后还是线性结构。13、 在计算机中存放线性表，一种最简单的方法是顺序存储。、14、 线性表的顺序存储结构具有两个基本的特点：一、线性表中所有元素

3、所占的存储空间是连续的。二、线性表中各数据在存储空间中是按逻辑顺序依次存放的。15、 线性表的插入运算和删除运算 P.8-916、 栈是一种特殊的线性表，其插入和删除只能在表的一端进行。17、 在栈中允许插入与删除的一端称为栈顶，而不允许插入与删除的一端称为栈底，栈的修改原则是先进后出或后进先出。18、 入栈运算： 1、首先将栈顶指针进1，然后将新元素入到栈顶指针指向的位置。19、 退栈预算：首先将栈顶元素赋予一个指定的变量，然后将栈顶指针退1。20、 队列：是指允许在一端进行插入、而在另一端进行删除的线性表，允许插入的一端称为队尾，允许删除的一端称为排头。队列又称 先进先出 或 后进后出的线

4、性表，体现了“先来先服务的原则”21、 队列的顺序存储结构一般采用循环队列的形式。即 将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供列队循环使用。22、 线性表的顺序存储结构具有简单、运算方便等优点。但是对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序的存储结构，二是采用链式存储结构23、 链式存储结构中，要求每个结点有两部分组成： 一 用于存放数据元素值，称为数据域。 另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。24、 在链式存储结构中的存储空间可以不连续，各数据结点的存储结构与数据之间的逻辑关系可以不一致，而数据元素之间的逻

5、辑关系是由指针域来确定的。链式存储方式既可以用于表示线性结构，也可以表示非线性结构25、 线性链表： 线性表的链式存储结构称为线性链表。26、 树： 树是一种简单的非线性结构。在树结构中，每一个结点只有一个前件，称为父结点，没有前结点的只有1个，称为根结点，简称为树的根。每一个结点可以有多个后件，他们都称为子结点。27、 二叉树是一种重要的非线性结构。二叉树具有两个特点： 非空二叉树只有一个根结点。每个结点最多有两颗子树，且分别称为该结点的左子树与右子树。28、 在二叉树的第K层上，最多有2k-1（k>=1）个结点29、 深度为M 的二叉树最多有2M-1个结点。深度为M 的二叉树是指二叉

6、树共有M 层。30、 在任意一颗二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。31、 具有N个结点的二叉树，其深度至少为log2n+1,32、 满二叉树，除了最后一层外，每一层上的所有结点都有两个子结点的二叉树为满二叉树。即深度为K 的满二叉树，其第K层上有2k-1个结点，且深度为M 的满二叉树共有2M-1个结点。33、 在计算机中，二叉树通常采用链式存储结构。与线性链表类似，用于存储二叉树中各元素的存储结点也有两部分组成：数据域和指针域。34、 二叉树的遍历可以分为三种： 前序遍历 中序遍历 后序遍历35、 前序遍历： 首先访问根结点，然后遍历左子树，最后遍历右子树。36、 中

7、序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。37、 后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。38、 顺序查找：又称顺序搜索，一般指在线性表中查找指定元素。对于大的线性表来说，顺序查找效率很低。但在以下两种情况只能用顺序查找： 1、如果线性表是无序的（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能顺序查找。2、即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。39、 二分法查找: 二分法查找只能用于顺序存储的有序表。对于长度为N 的有序线性表，在最坏的情况下，二分查找只需要比较log2n次，而顺序查找则需要比较N 次。40、 交换类排序

8、法：是指借助数据元素之间的相互交换进行排序的一种方法。包括 冒泡排序法和 快速排序法。41、 冒泡排序法：一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为N,则在最坏的情况下，冒泡排序需要经过N/2遍从前往后的扫描和N/2遍从后往前的扫描，需要的比较次数为n(n-1)/2.但一般情况下要小于这个工作量。42、 快速排序法：是一种交换类的排序方法，但由于它比冒泡排序法的速度快，因此称为快速排序法。43、 插入类排序法 包括 简单插入类排序法 希尔排序法 44、 简单插入排序法的效率与冒泡排序法相同。在最坏的情况下需要n(n-1)/2 次比较45、 希

9、尔排序的效率与所选取的增量序列有关。在最坏的情况下，希尔排序所需要的比较次数为 O(n1.5)46、 选择类排序法 包括 简单选择排序法 和 堆排序法47、 简单排序法在最坏的情况下需要比较N(n-1)/2次48、 堆排序法在最坏情况下需要比较O(nlog2n)49、 就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计两个阶段。50、 面向对象设计的主要优点是：与人类习惯的思维方法一致；稳定性好；可重用性好；易于开发大型软件产品；可维护性好。51、 清晰第一，效率第二 的论点已经成为当今主导的程序设计风格。52、 结构化程序实际方法的主要原则为自顶向下，逐步求精，模块

10、化，限制使用GOTO语句53、 结构化程序语言仅使用顺序、选择、重复3钟基本控制结构就足以表达出各种其他形式的程序设计方法。54、 顺序就够是一种简单的程序设计结构，它是最基本、最常用的结构。55、 选择结构又称为分支结构，它包括简单选择结构和分支选择结构。56、 重复结构又称为循环结构。在程序设计语言中，重复结构对应两类循环语句，对先判断后执行循环体的称为当型循环结构。对先执行循环体后判断的称为直到型循环结构。即直到型循环至少执行一次运算。57、 遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的特点。一、程序结构良好、易读、易理解、易维护。二、可以提高编程工作的效率，降低

11、软件开发成本。58、 对象是面向对象方法中最基本得概念。对象具有以下的一些基本特点：1、标识的唯一性。2、分类性。3、多态性。、4、封装性。5、模块独立性好。59、 类：将属性、操作相似的对象归为类。即类是具有共同属性、共同方法的对象的集合。60、 消息：一个消息有三部分组成：1、接受消息的对象名称、2、消息标识符3、零个或多个参数。61、 在面向对象方法中，实现信息隐蔽是依靠对象的封装。62、 程序中添加的必要注释：程序的代码要层次分明，清晰明了，满足视觉要求。注释一般分为序言性注释和功能性注释。序言性注释通常位于程序的开头部分，他给出了程序的整体说明。功能性注释一般嵌在源程序体之中，主要描

12、述其后的语句或程序。63、 从程序行文角度，编写程序源代码应该注意 源程序文档化、程序的语句结构、数据的说明和输入输出等方面的要求。64、 衡量模块的独立程度使用耦合性和内聚性两个度量标准。模块的内聚程度越高越独立，耦合程序越低越独立。65、 继承性是面向对象的方法的一个主要特性。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可以当作基类来引用，新类相应的可当做派生类来引用。这种层次结构系统的一个重要性质是继承性，一个类直接继承其父类的描述或特性，子类自动的共享基类中定义的数据和方法。66、 通常，将软件产品从提出、实行、使用维护到停止使用退役的过程称为软件的生命周期。软件生存期一

13、般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。67、 软件工程的概念出现源自 软件危机。 而软件危机归结为成本、质量、生产率的问题。68、 软件工程是建立并使用完善的工程化原则。软件工程主要包括3个要素：方法、工具、过程。69、 软件工程的核心思想是把软件产品看做是一个工程产品来处理。70、 软件工程的原则： 抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。71、 结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。72、 结构化分析方法的实质：着眼于数据流、自顶向下、逐层分解、建立系统的流程。以数据流图和数据字典为主要工具，建立系统的逻辑模型

14、。73、 数据流图 从数据传递和加工的角度来刻画数据流从输入到输出的移动变换过程。74、 数据字典是结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个有组织的列表，具有精确、严格的定义，使得用户和系统分析员对于输入、存储成分和中间的计算结构有共同的理解。符号含义示例及说明=被定义为+与X=a+b 表示 X 由 a 和 b 组成 | 或X=a|b 表示 X 由 a 或 b 组成 重复X=a 表示 X 由 0 个或多个 a 组成m n重复X=2a5 表示 X 中最少出现 2 次 a ，最多出现 5 次 a ， 5 、 2 为重复次数的上下限（ ）可选X= （ a ） 表示 a 可在 X 中出现，也可不出现“ ”数据元素X= “ a” 表示 X 是取值为字符 a 的数据元素连接符X=19 表示 X 可取 1 到 9 中的任意一个值* *注释*a* 表示 a 为说明或注释75、 表 4-6 数据字典中采用的符号76、 判定树和判定表77、 软件需求规格说明书 是需求分析阶段的最后成果，是软件开发的重要文档之一。78、 软件需求规格说明书的作用。1、便于用户、开发人员进行理解和交流。2、反映出用户问题的结构。可以作为软件开发工具的基础和依据。3、作为确认测试和验收的依据。