全国计算机等级考试—公共基础知识部分复习简纲
本章应考重点：本章内容在二级笔试中会出现5—6题，是公共基础知识部分出题量比较多的一章，所占分值也比较大,约10分
1.1 算法
1. 算法是指解题方案的准确而完整的描述。
2. 算法的基本特征
a可行性b确定性c有穷性d拥有足够的情报
3. 算法的复杂度
a算法时间复杂度：是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量
b 算法的空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本概念
1 数据结构是指互相有关联的数据元素的集合
2 数据结构 a 数据的逻辑结构 1表示数据元素的信息 2 表示各数据元素之间的前后件关系
b 数据的存储结构 顺序存储
链接存储
索引存储
c 对各种数据结构进行的运算
托奶李天王3数据结构的图形表示
一个数据结构除了用二元关系外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合点D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称结点：为了进以步表示数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。
4 数据结构分为二大类 线性结构 a有且只有一个根结点b 每个结点最多有一个前件，也最多有一个后件
常见的线性结构有线性表，队列，线性链表，栈
非线性结构 不满足线性结构条件的数据结构
常见的非线性结构有树，二叉树，和图等
1.3线性表及其顺序存储结构
1线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。表中的每个数据元素，除了第一个外，由且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以是空表
2线性表是一种存储结构 顺序结构 a线性表中所有元素所占的存储空间是连续的
b线性表中个数据元素在存储空间中是按逻辑顺序依次存放的
链式结构
3顺序表的插入，删除运算
a 顺序表的插入运算，插入结束后，线性表的长度增加了1，顺序表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。
b 顺序表的删除运算，删除结束后，线性表的长度减少了1，顺序表的删除运算时需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。插入删除运算不方便
1.4栈和队列
1栈及其基本运算
栈是限定在一端进行插入与删除运算的线性表。栈是按照“先进后出”或“后进先出”的原则来组织数据的。
栈具有记忆作用
栈的基本运算 a入栈运算 b出栈运算 c读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化
2队列及其基本运算
队列是指允许在一端（队尾）进行插入，一端（队头）进行删除的线性表
队列是“先进先出”或“后进后出”的线性表
队列运算包括 a入队运算 b出队运算
3循环队列及其运算
循环队列的初始状态为空，即rear=front=m
循环队列的基本运算分为入队运算和退队运算
队列空的条件：s=0
队列满的条件：s=1 front=rear
1.5线性链表
1线性表顺序存储缺点
A插入或删除的运算效率很低
B线性表的顺序存储结构下，线性表的存储空间不便扩充
C线性表的顺序存储结构不便于对存储空间的动态分配
2线性链表：线性表的链式存储结构称为线性链表，是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。在链式存储方式中每个结点由二部分组成：数据域，指针域
线性链表分为单链表，双向链表和循环链表三种类型
3线性链表的基本运算
a在线性链表中包含指定元素的结点之前插入一个新元素
b在线性链表中删除包含指定元素的结点
c将二个线性链表按要求合并成一个线性链表
d将一个线性链表按要求进行分解
e逆转线性链表 f 复制线性链表 g线性链表的排序 h线性链表的查
4循环链表及其基本运算
循环链表是另一种形式的链式存储结构，与线性链表相比，具有以下二个特点
a在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点，循环链表的头指向表头结点。
b 循环链表中最后一个结点的指针域不为空，而是指向表头结点，即在循环表中，所有结点的指针构成一个环状链
在对循环链表进行插入与删除的过程中，实现了空表与非空表的运算统一
1.6树与二叉树
1树的基本概念
树是一种简单的非线性结构。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度
2二叉树及其基本性质
（1）什么是二叉树
二叉树是一种很有用的非线性结构 a 非空二叉树只有一个根结点 b 每个结点最多有二棵子树，且分别称为左子树和右子树
二叉树的度可以是0，1，2
（2）二叉树的基本性质
性质1 在二叉树的第k层上，最多有2k-1（k>=1）个结点
性质2 深度为m哈尔滨市旅行社的二叉树最多有2m-1个结点
性质3 在任意一棵二叉树中度数为0的结点总比度为2的结点多一个
性质4 具有n个结点的二叉树，其深度至少为[ log2n ]表示取log2n的整数部分
3满二叉树：除最后一层外，每层上的所有结点都有二个子结点
完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点87红楼梦演员重聚
4 二叉树的存储结构，二叉树通常采用链式存储结构
5 二叉树的遍历
（1）前序遍历（DLR）根左右
（2）中序遍历（LDR）左根右
（3）后序遍历（LRD）左右根
1.7查技术
1顺序查
2二分法查
1.8排序技术
类别 | 排序方法 | 基本思想 | 时间复杂度 |
交换类 | 冒泡排序 | 相邻元素比较，不满足条件交换 | n(n-1)/2 |
快速排序 | 选择基准元素，通过交换，划分成二个子序列 | O(nlog2n) | |
插入类 | 简单插入排序 | 待排序的元素看成为一个有序表和无序表，将无序表中元素插入到有序表中 | n(n-1)/2 |
希尔排序 | 分割成若干个子序列分别进行直接插入排序 | O(n1.5) | |
选择类 | 简单选择排序 | 扫描整个线性表，从中选出最小的元素，将他交换到表的最前面 | n(n-1)/2 |
堆排序 | 选建堆，然后建堆顶元素与堆中最后一个元素交换，再调整为堆 | O(nlog2n) | |
第二章 程序设计基础
本章在考试中会出现一题左右，所占分值大约占2分，是出题量较小的一章。本章内容较少，所以大家尽量不要失分啊！这样会比较可惜。
2.1程序设计风格
程序设计的风格主要强调：“清晰第一，效率第二”
（1） 源程序文档化
符号名的命名。符号名能反映它所代表的实际东西，应有一定的实际含义
程序的注释，分为序言性注释和功能性注释
视觉组织
（2） 数据说明数据说明的次序规范化说明语句中变量安排有序化使用注释来说明复杂数据的结构
（3） 语句的结构
（4） 输入和输出
注意点
信息隐蔽是指采用封装技术，将程序模块的实施细节隐藏起来，使模块接口尽量简单。即指在设计和确定模块时，使得一个模块的内包含的信息（过程或数据），对于不需要这些信息的其他模块来说，是不能访问的。
2.2结构化程序设计（面向过程的程序设计方法）
1.结构化程序设计方法的主要原则可以概括为
a 自顶而下
b 逐步求精
c 模块化
d 限制使用 goto 语句
2.结构化程序的基本结构：顺序结构，选择结构（分支结构），重复结构（循环结构）
2.3面向对象的程序设计
面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡人们在现实生活中常用的思维来认识，理解和描述客观事物，强调最终建立的系统能够映射问题域。
二级VB面向对象方法的主要优点
（1） 与人类习惯的思维方法一致
（2） 稳定性好
（3） 可重用性好
（4） 易于开发大型软件产品
（5） 可维护性好
.【注意】
推荐书籍面向对象的程序设计主要考虑的是提高软件的的可重用性
对象是面向对象方法中最基本的概念，对象是属性和方法的封装体
属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变
操作描述了对象执行的功能，操作也称为方法或服务。操作是对象的动态属性。
一个对象由对象名，属性和操作三个部分组成
对象的基本特点:标识唯一性，分类性，多态性，封装性，模块独立性好
类是指具有共同属性，共同属性，共同方法的对象的集合。所有类是对象的抽象，对象是对应类的一个实例
消息是一个实例与另一个实例之间传递的信息。消息的组成包括：
（1） 接收消息的对象的名称
（2） 消息标识符也称消息名
（3） 零个或多个参数
继承是指能够直接获得已有的性质和特征，而不必重复定义他们
多态性是对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动。
在面向对象技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息可以发送给父类对象也可以发送给子类对象。
多态性机制增加了面向对象软件系统的灵活性，减少了信息的，而且显著提高了软件的可重用性可扩充性。
第三章 软件工程基础
本章应考点拨：本章在笔试中一般占8分左右，约3道选择题，1道填空题，是公共基础部分比较重要的一章。本章主要考察对基本概念的识记，有少量对基本原理的理解，没有实际
运用，因此在复习本章时，重点应放在基本概念的记忆和基本原理的理解。
3.1软件工程基本概念
1软件的相关概念
何以笙箫默主题曲计算机软件是包括程序，数据及相关文档的完整集合
软件的特点包括
（1） 软件是一种逻辑实体，而不是物理实体，具有抽象性
（2） 软件的生产与硬件不同，他没有明显的制作过程
（3） 软件在运行，使用期间不存在磨损和老化问题
（4） 软件的开发，运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题
（5） 软件复杂性高，成本昂贵
（6） 软件开发涉及诸多的社会因素
2软件危机与软件工程
软件工程源于软件危机
软件危机表现为
（1） 软件需求的增长得不到满足
（2） 软件开发成本和进度无法控制
（3） 软件质量难以保证
（4） 软件不可维护或维护程度非常低
（5） 软件的成本不断提高
（6） 软件开发生产率的提高跟不上硬件的发展和应用需求的增长
总之可以将软件危机归结为成本，质量，生产率等问题
软件工程
（1） 软件开发技术
（2） 软件工程管理
软件工程的主要思想是将工程化原则运用到软件开发过程，他包括3个要素：方法，工具，过程
软件工程过程是把输入转化为输出的一组彼此相关的资源和活动
3软件的生命周期
软件生命周期：软件产品从提出，实现，使用维护到停止使用退役的过程。生命周期分为软件定义，软件开发，软件运行维护三个阶段
（1） 软件定义阶段：包括制定计划和需求分析
发布评论