全国计算机二级公共基础知识要点汇总

本文由不懂市长贡献
doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。
第一章
数据结构与算法
1.算法的基本特征:可行性,确定性,有穷 性,拥有足够的情报 2.算法的基本要素:一是对数据对象的 运算和操作;二是算法的控制结构 一个算法一般都可以用顺序,循环,选择 三种基本控制结构组合而成 3.算法设计基本方法:列举法,归纳法,递 推,递归,减半递推技术,回溯法 4.算法复杂度主要包括:时间复杂度,空 间复杂度 所谓时间复杂度是指算法所需要的 计算工作量 所谓空间复杂度是指执行这个算法 所需要的内存空间 5.数据结构作为计算机的一门科学,主要 研究和讨论的问题有以下三个方面:数据 的逻辑结构， 数据的存储结构，对各种 数据结构进行的运算 一般情况下,在具有相同特征的数据元素 集合中,各个数据元素之间存在某种关系 (即 联系),这种关系反映了该集合中的数 据元素艘固有的一种结构.在数据处理领 域中,通常把数据元素之间这种固有的关 系简单的用前后件关系来描述(即前件与 后件). 1)数据的逻辑结构:更通俗地说,数据结 构是指带有结构的数据元素的集合 数据元素之间的前后件关系是指它们的 逻辑关系,而与它们在计算机中的存储位 置无关.因此,上面所述的数据结构实际上 是数据的逻辑结构
2)数据的存储结构:是指数据的逻辑结构 在计算机存储空间中的存放形式也叫数 据的物理结构 一般来说,一种数据的逻辑结构根据需要 可以表示成多种存储结构,常用的存储结 构有顺序,链接,索引等存储结构 6.根据数据结构中各数据元素之间前后 件关系的复杂度,一般将数据结构分为两 大类型:线性结构，非线性结构 说明:在一个线性结构中插入或删除任何 一个结点后还应是线性结构 7.线性表:是一种线性结构;是最简单,最 常用的一种数据结构 线性表的顺序存储结构具有以下两个基 本特征:线性表中所有元素所占的存储空 间是连续的 线性表中各数据元素在存储空间中是按 逻辑顺序依次存放的 8.栈及其基本运算:1)栈实际上也是线性 表,只不过是一种特殊的线性表.在这种特 殊的线性表中,其插入与删除运算都只在 线性表的一端进行 2)在栈中允许 插入与删除的一端称为栈顶,而不允许插 入与删除的另一端称为栈底 3)栈是按 照"先进后出"或"后进先出"的原则组织数 据的 9.队列:是指允许在一端进行插入,而在 另一端进行删除的线性表 10.线性链表:在链式存储方式中,要求每 个结点由两部分组成:一部分用于存放数 据元素值,称为数据域;另一部分用于存放 指针,称为指针域 11.树:1)在树结构中,每个结点只有一个

前件,成为父结点
没有前件的结点只有一个,称为树的根 结点,简称为树的根 2)在树结构中,一个结点可以有多个后 件,它们都称为该结点的子结点。 没有 后件的结点称为叶子结点 3)在树结构中,一个结点所拥有的后件个 数称为该结点的度。 所有结点中的最大的 度称为树的度 4)树结构具有明显的层次关系,即树是一 种层次结构。 树的最大层次称为树的深度 12.二叉树:1)二叉树是一种很有用的非线 性结构 2)二叉树具有以下两个特点:非空二叉 树只有一个根结点 每一个结点最多有两棵子树,且分别称为 该结点的左子树与右子树 由以上特点可以看出,在二叉树中,没一个 结点的度最大为 2,即所有子树(左子树或 右子树)也均为二叉树. 在二叉树中,一 个结点可以只有左子树而没有右子树,也 可以只有右子树 而没有左子树 3)二叉树的基本性质:性质 1 ,2,3,4,5 4)两种特殊形态的二叉树:满二叉树:指的 是除最后一层外,每一层上的所有结点都 有两个子结点 完全二叉树:指的是除最后一层外,每一 层的结点数均达到最大值;在最后一层上 只缺少右边的若干结点 5)二叉树的遍历(很重要哦肯定要有这儿 的题的!) 13.查找技术:1)二分法查找:当有序线性 表为顺序存储是才能采用二分查找,并且, 二分查找的效率要比顺序查找高得多.
2)冒泡排序法:假设线性表的长度为 n,则 在最坏的情况下,冒泡排序需要经过 n/2 遍的从前往后的扫描和 n/2 遍的从后往前 的扫描,需要的比较次数为 n(n-1)/2. 3)简单插入排序法:在简单插入排序法中, 每一次后最多移掉一个逆序,因此,这种方 法的效率与冒泡排序法相同.在最坏情况 下,简单插入排序需要 n(n-1)/2 次比较 4)希尔排序法:希尔排序的效率与所选的 增量序列有关 5)简单选择排序法:在最坏情况下需要比 较 n(n-1)次 第二章 程序设计基础 1.结构化程序设计的原则:1)自顶向下 逐步求精 3)模块化 4)限制使用 goto 语句 2.结构化程序设计方法是程序设计的先 进方法和工具.采用结构化程序设计方法 编写程序,可使程序结构良好易读.易理解, 易维护 主要有三种结构:顺序结构,选择结构,重 复结构 遵循结构化程序的设计原则,按结构化程 序设计方法设计出的程序具有明显的优 点:其一,程序易于理解,使用和维护 其二,提高了编程工作的效率,降低了 软件开发成本 3.面向对象的程序设计:1)面向对象方 法之所以日益受到人们的重视和应用, 成为流行的软件开发方法,是源于面向 对象方法的以下主要优点:(1)与人类习 惯的思维方法一致稳定性好 (3)可重性 好 (4)易于开发大型软件产品 (5)可维 护性好 2)
2)对象具有如下一些基本特点:(1)标 识唯一性(2)分类性(3)多态性(4)

封装性 (5)模块独立性好 3)广义地说,继承是指能够直接获得已 有的性质和特征,而不必重复定义它们 第三章 软件工程基础 1.软件工程概念的出现源自软件危机 所谓软件危机是泛指在计算机软件的 开发和维护过程中所遇到的一系列严 重问题.实际上,几乎所有的软件都不同 程度地存在这些问题 2.软件工程包括三个要素:即方法,工具 和过程方法是指完成软件工程项目的 技术手段 工具支持软件的开发,管理,文档生成 过程支持软件开发的各个环节的控制, 管理 3.软件生命周期:通常,将软件产品从提 出,实现,使用维护到停止使用退役的过 程称为软件生命周期 软件生命周期可分为软件定义,软件开发 及软件运行维护三个阶段 4.软件工程的 目标:1)基于软件工程的目标,软件工程的 理论和技术性研究的内容主要包括:软件 开发技术 和软件工程管理 软件开发技术包括:软件开发方法学,开 发过程,开发工具和软件工程环境 软件工程管理包括:软件管理学,软件工 程经济学,软件心理学等内容 5.结构化分析的常用工具:数据流图,数 据字 6.软件需求规格说明书:1)作用:便于用户, 开发人员进行理解和交流
反应出用户问题的结构,可以作为软件 开发工作的基础和依据 作为确认测试和验收的内容 2)内容:软件需求规格说明书是作为需 求分析的一部分而指定的可交付文档. 说明书把软件计划中确定的软件范围 加以展开,制定出完整的信息描述,详细 的功能说明恰当的检验标准以及其他 与要求有关的数据 7.从工程管理角度来看,软件设计分两步 完成:概要设计和详细设计 8.软件设计的基本原理:(1)抽象(2)模块化 (3)信息隐蔽 (4)模块独立性 模块的独立程度是评价设计好坏的重要 度量标准.衡量软件的模块独立性使用耦 合性和内聚性两个定性的度量标准 。它 们是相互关联的.一般较优秀的软件设计, 应尽量做到高内聚,低耦合 9.数据流类型(面向数据流的设计方 法):典型的数据流类型有两种:变换型 和事务型 10.软件测试的方法和技术是多种多 样的.对于软件此时方法和技术,可以从 不同的角度加以分类:若从是否需要执 行被测软件的角度,可以氛围静态测试 和动态测试 若按照功能划分可以分为白盒测试和 黑盒测试 白盒测试的主要方法有逻辑覆盖,基本 路径测试等 黑盒测试是对软件已经实现的功能是 否满足需求进行测试和验证
黑盒测试方法主要有等价类划分法,边 界值分析法,错误递推法,因果图等,主 要 用于软件确认测试 11.软件测试过程一般按 4 个步骤进行,即 单元测试,集成测试,验收测试(确认测试) 和系统测试 第四章 数据库设计基础 1.数据库中的数据具有"集成","共享"之特 点

2.数据库管理系统简称 DBMS 目前流 行的 DBMS 均为关系数据库系统 3.数据库系统(简称 DBS)由如下几部分组 成:数据库(数据),数据库管理系统(软件), 数据库管理员(人员),硬件平台(硬件),软 件平台(软件) 4.数据库系统的发展:文件 系统阶段,层次数据库与网状数据库系统 阶段,关系数据库系统阶段 5.数据库系统的基本特点:数据的集成 性，数据的高共享性与低冗余性， 数据 独立性，数据统一管理与控制 6.数据库系统的三级模式:概念模式:概念 模式是数据库系统中全局数据逻辑结构 的描述,是全体用户(应用)公共数据视图 外模式:又叫用户模式 内模式:它给出了数据库物理存储结构与 物理存取方法,如数据存储的文件结构,索 引集簇及 hash 等存取方式与存取路径 7.数据模型按不同的应用层次分成三种 类型,它们是概念数据模型,逻辑数据模型, 物理数据模型 目前,逻辑数据模型也有很多种,较为成 熟并先后被人们大量使用过的有:层次 模型,网状模型,关系模型,面向对象模 型等
8.E-R 模型的基本概念:实体,属性,联系 (一对一,一对多,多对多) 9.关系模型:1)关系的数据结构:二维表由 表框架及表的元组组成 在表框架中按行可以存放数据,每行数据 成为元组,一个元组是由 n 个元组分量所 组成 2)关系操纵:数据查询,数据删除,数据插 入,数据修改 3)关系中的数据约束:实体完整性约束， 参照完整性约束， 用户定义的完整性约束 4)关系模型有插入,删除,修改和查询四种 操作,它们又可以进一步分解成六种基本 操作:关系的属性指定，关系的元组的选 择，两个关系的合并，关系的查询，关系 元组的插入，关系元组的删除 5)关系模型的基本运算:插入,修改,删除, 查询 投影运算,选择运算,笛卡尔运算 6)关系代数中的扩充运算:交运算,除运算, 连接与自然连接运算

1