计算机二级公共基础考点.docx

《计算机二级公共基础考点.docx》由会员分享，可在线阅读，更多相关《计算机二级公共基础考点.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、优质文本第一章 数据结构与算法1.1算法1.算法的根本特征：1可行性；2确定性；3有穷性；4拥有足够的情报。2.算法的根本要素：1算法中对数据的运算和操作；算术运算：主要包括加、减、乘、除等运算。逻辑运算：主要包括“与、“或、“非等运算。关系运算：主要包括大于、等于、小于、不等于等运算。数据传输：主要包括赋值、输入、输出等操作。2算法的控制结构：一个算法一般都可以用顺序、选择、循环三种根本控制结构组合而成。3.算法设计根本方法：列举法、归纳法、递推、递归包括直接递归与间接递归、减半递推技术、回溯法等。4.算法复杂度1算法的时间复杂度：所谓算法的时间复杂度，是指执行算法所需要的计算工作量；2算法

2、的空间复杂度：一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。1.2数据结构的根本概念1数据的逻辑结构:所谓数据的逻辑结构，是反映数据元素之间逻辑关系的数据结构。2数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。1.3线性表及其存储结构1 线性表的根本概念：如果一个非空的数据结构满足以下两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。那么称该数据结构为线性结构，线性结构又称线性表。2线性表的顺序存储结构： 根本特点：线性表中所有元素所占的存储空间是连续的 ；线性表中各数据元素在存储空间中是按逻辑顺序依次存放

3、的。 主要运算：线性表的插入、线性表的删除、线性表的查找、线性表的排序、线性表的分解、线性表的合并、线性表的复制、线性表的逆转等。1.4栈和队列 栈和队列是一种特殊的线性表。1栈：是限定在一端进行插入与删除的线性表。栈是按照“先进后出或“后进先出的原那么组织顺序的。栈的根本运算有三种：入栈、退栈与读栈顶元素。2队列：是指允许在一端进行插入、而在另一端进行删除的线性表。队列是按照“先进先出或“后进后出的原组织数据的。在实际应用中，队列的顺序存储结构一般采用循环队列的形式。循环队列有两种根本运算：入队运算与退队运算。1.5树与二叉树1树的根本概念：树是一种简单的非线性结构，在树结构中，每一个结点只

4、有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，他们都称为该结点的子结点。没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度，在树中，叶子结点没有子树。2二叉树及其根本性质一、二叉树的特点：非空二叉树只有一个根结点;每一个结点最多只有一个最多只有两棵子树且分别称为该结点的左子树与右子树。二、二叉树的分类满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均到达最大值；在最后一层上只缺少右边的假设干结点。三、二叉树的根本性质

5、 性质1 在二叉树的第K层，最多有2K-1K1个结点。 性质2 深度为m的二叉树做多有2m-1个结点。 性质3 在任意一颗二叉树中，度为0的结点即叶子结点总是比度为2的结点多一个。 性质4 具有n个结点的二叉树，其深度至少为log2 n+1其中log2 n表示取log2 n的整数局部。 性质5 具有n个结点的完全二叉树的深度为log2 n+1。 性质6 设完全二叉树共有n个结点，如果从根结点开始，按层序每一层从左到右用自然数1，2，3.n,那么对于编号为kk=1,2,n的结点有以下结论：假设k=1，那么该结点为根结点，它没有父结点；假设k1,那么该结点的父结点编号为k/2。假设2kn,那么编号

6、为k的结点的左子结点编号为2k；否那么该结点无左右子结点。假设2k+1n,那么编号为k的结点的右子结点编号为2k+1;否那么该结点无左子结点。四、二叉树的存储结构：在计算机中，二叉树通常采用链式式存储空间。五、二叉树的遍历 二叉树的遍历是指不重复的访问二叉树中的所有结点。1. 前序遍历中左右访问2. 中序编历左中右访问3. 后序遍历左右中访问1.6查找技术1.顺序查找 以下情况只能采用顺序查找：1如果线性表为无序表即表中元素的排列是无序的，那么不管是顺序存储结构还是链式存储结构，都只能用顺序查找：2即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。2.二分法查找对于长度为n的有序线性表

7、，在最坏情况下，二分法查找只需要比拟log2 n次，而顺序查找需要比拟n次。1.7排序技术1.交换类排序法 冒泡排序法：假设线性表的长度为n，那么在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比拟次数为n(n-1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。 快速排序法2.插入类排序法简单插入排序法：在简单插入排序法中，每一次比拟后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比拟。希尔排序法：希尔排序法的效率与所选取的增量序列有关。4. 选择类排序法 简单项选择择排序法：简单项

8、选择择排序法在最坏情况下需要比拟n(n-1)/2次。 堆排序法：堆排序的方法对于规模较小的线性表并不适宜，但对于规模较大的线性表来说是很有效的。在最坏情况下，堆排序需要比拟的次数为(n log2 n)。第二章 程序设计根底2.1程序设计风格与方法1.程序设计风格：清晰第一，效率第二。2.程序设计应注重和考虑的因素： 源程序文档化：a、符号名的命名；b、程序注释包括序言性注释和功能性注释；c、视觉组织。 数据说明的方法：a、数据说明的次序标准化；b、说明语句中变量安排有序化；c、使用注释来说明复杂数据的结构。 语句的结构：程序编写应优先考虑清晰性，防止采用复杂的条件语句。 输入和输出2.2结构化

9、程序设计1.结构化程序设计的原那么：自顶向下，逐步求精，模块化，限制使用goto语句。2.结构化程序的根本结构与特点1根本结构：顺序结构、选择结构、重复结构。2特点：结构良好、易读、易理解、易维护。2.3面向对象的程序设计1.面向对象方法的优点 1与人类习惯的思维方法一致； 2稳定性好； 3可重用性好； 4易于开发大型软件产品； 5可维护性好2.面向对象方法的根本概念 1对象的根本特点：标识唯一性、分类性、多态性、封装性、模块独立性好。 2类和实例 类是一个支持集成的抽象数据类型，而对象是类的实例。 3消息：通常一个消息由以下三局部组成：a、接受消息的对象的名称；b、消息标识符也叫消息名；c、

10、零个或多个参数。 4继承：继承是面向对象的方法的一个主要特征，继承具有传递性，它分为单继承与多重继承。 5多态性：多态性机制不仅增加了面向对象软件系统的灵活性，进一步减少了信息冗余，而且显著的提高了软件的可重用性和可扩充性。 第三章 软件工程根底3.1软件工作根本概念1.软件的定义：计算机软件是计算机系统中与硬件相互依存的另一局部，是包括程序、数据、及相关文档的完整集合。软件开发过程中需要应用工程化原那么。软件工作包括3个要素，即方法、工具和过程，方法是完成软件工程工程的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。2.软件工程过程软件工程过程通常包含4

11、种根本活动：软件规格说明、软件开发、软件确认、软件确认。3.软件生命周期可以将软件生命周期分为软件定义、软件开发及软件运行维护。软件生命周期的主要活动阶段是：可行性研究与方案制定；需要分析；软件设计；软件实现；软件测试；运行和维护。5. 软件工程的目标与原那么（1） 软件工作的目标：在给定本钱、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。基于软件工程的目标，软件工程的理论和技术性研究的内容主要包括:软件开发技术和软件工程管理。（2） 软件工程的原那么 根本原那么包括：抽象、信息隐蔽、模块化、局部化、确定性、

12、一致性、完备性和可验证性。6. 软件开发工具与软件开发环境软件开发环境或软件工程环境是全面支持软件开发全过程的软件工具集合。3.2结构化分析方法结构化方法包括已经形成了配套的结构化分析方法、结构化设计方法和结构化编程方法，其核心和根底是结构化程序设计理论。1. 需求分析与需要分析方法（1） 需求分析：需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析将创立所需的数据模型、功能模型和控制模型（2） 需求分析分析阶段的工作：a、需求获取；b、需求分析；c、编写需求规格说明书；d、需求评审。（3） 需求分析分析方法常

13、见的分析方法有：结构化分析方法。主要包括：面向数据流的结构化分析方法、面向数据结构的Jackson方法、面向数据结构的结构化数据系统开发方法。面向对象的分析方法。从需求分析建立的模型的特性来分，需求分析方法又分为静态分析方法和动态分析方法。2. 结构化分析方法结构化分析方法的实质是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图DFD和数据字典DD为主要工具，建立系统的逻辑模型。结构化分析的常用工具：数据流图DFD；数据字典DD；判定树：判定表。3. 软件需求规格说明书的特点：正确性；无歧义性；完整性；可验证性；一致性；可理解性；可修改性；可追踪性。 3.3结构化设计方法1.软

14、件设计的根本原理包括抽象、模块化、信息隐蔽、模块独立性。模块独立独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。一般较优秀的软件设计，应尽量做到高内聚低耦合。2.概要设计1软件概要设计的根本任务是：设计软件系统结构；数据结构及数据库设计；编写概要设计文档。2数据流类型：典型的数据流有两种：变换型和事务型。3设计的准那么提高模块独立性；模块规模适中；深度、宽度、扇出和扇入适当；使模块的作用域在该模块的控制域内；应减少模块的接口和界面的复杂性；设计成单入口、单出口的模块；设计功能可预测的模块。4. 详细设计1常见的过程设计工具：图形工具：程序流程图、

15、N-S图方框图、问题分析图PAD图、HIPO。表格工具：判定表。语言工具：伪码PDL。3.4软件测试1.软件测试的目的：发现错误2.软件测试的准那么 1所以测试都应追溯到需求； 2严格执行测试方案，排除测试的随意性； 3充分注意测试中的群集现象； 4程序员应防止检查自己的程序； 5穷举测试不可能； 6妥善保存测试方案、测试用例、出错统计和最终分析报告，为维护提供方便。3.软件测试技术与方法综述 假设从是否需要执行被测软件的角度，可以分为静态测试和动态测试方法。假设按照功能划分可以分为白盒测试和黑盒测试方法。5. 软件测试的实施4个步骤：1单元测试；2集成测试；3确认测试；4系统测试。3.5程序

16、的调试1.程序调试的任务：诊断和修改程序中的错误。2程序调试的根本步骤 1错误定位；2修改设计和代码，以排除错误；3进行回归测试，防止引进新的错误。3.程序调试的原那么 1确定错误的性质和位置时的考前须知： 分析思考与错误征兆有关的信息； 避开死胡同； 只把调试工具当作辅助手段来使用； 防止用试探法；（3） 修改错误的原那么 在出现错误的地方，很可能还有别的错误； 修改错误的一个常见失误是只修改了这个错误的征兆或这个错误的表现，而没有修改错误本身； 注意修正一个错误的同时有可能会引入新的错误； 修改错误的过程将迫使人们暂时回到程序设计阶段； 修改源代码程序，不要改变目标代码。（4） 软件调试方

17、法：强行排错法；回溯法；原因排除法。第三章 数据库设计根底4.1数据库系统的根本概念1.数据库DB数据库是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。2.数据库管理系统DBMS数据库管理系统是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据效劳等。数据库管理系统是数据库系统的核心，它具有如下几个方面的具体功能；数据库模式定义；数据存取的物理构建；数据操纵；数据的完整性、平安性定义与检查；数据库的并发控制与故障恢复；数据的效劳。3.数据库管理员DBA 数据库管理员其主要工作如下：1数据库设计

18、；2数据库维护；3改善系统性能，提高系统效率。4.数据库系统DBS 数据库系统由如下几局部组成：数据库(数据)、数据库管理系统软件、数据库管理员人员、系统平台之一_硬件平台、系统平台之二_软件平台。这五个局部构成了一个以数据库为核心的完整的运行实体，称为数据库系统。6. 数据库应用系统DBAS数据库应用系统是数据库系统再加上应用软件及应用界面这三者所组成，具体包括：数据库、数据库管理系统、硬件平台、软件平台、应用软件、应用界面。 7. 数据库系统的根本特点（1） 数据的集成性：2数据的高共享性与低冗余性；3数据独立性；4数据统一管理与控制。8.数据库系统的三级模式 1概念模式：以概念模式为框架

19、所组成的数据库叫概念数据库。2外模式：以外模式为框架所组成的数据库叫用户数据库。 3内模式：以内模式为框架所组成的数据库叫物理数据库。这三种数据库中只有物理数据库是真实存在于计算机外存中。8.数据库系统的两级映射：概念模式到内模式的映射、外模式到概念模式的映射。4.2数据模型1.数据模型的根本概念：数据模型分为两个阶段：由现实世界开始，经历信息世界而至计算机世界，从而完成整个转化。数据模型所描述的内容有三个局部，他们是数据结构、数据操作与数据约束。2.E-R模型实体联系模型1根本概念： E-R模型将现实世界的要求转化成实体、联系、属性等几个根本概念，以及他们间的两种根本连接关系，并且可以用一种

20、图非常直观地表示出来。2E-R模型的图示法 实体集表示法：矩形 属性表示法：椭圆 联系表示法：菱形3.层次模型：层次模型的根本结构是树形结构。4.网状模型：在网状模型的标准中，根本结构简单二级树叫系，系的根本数据单位是记录。5.关系模型：关系模型采用二维表来表示，简称表。二维表由表框架及表的原组组成。表框架由n个命名的属性组成，n称为属性元数。关系模型的数据操纵即是建立在关系上的数据操纵，一般有查询、增加、删除及修改四种操作。4.3关系代数1.关系模型的根本运算：1插入；2删除；3修改；4查询：用于查询的三个操作无法用传统的集合运算表示，需要引入一些新的运算。 投影运算；选择运算：笛卡儿积运算

21、2.关系代数中的扩充运算：1交运算；2除运算；3连接与自然连接运算。4.4数据库设计与管理1.数据库设计概述 数据库设计的根本任务是根据用户对象的信息需求、处理需求和数据库的支持环境包括硬件、操作系统与DBMS设计出数据模式。在数据库设计中有两种方法，一种是以信息需求为主，兼顾处理需求，称为面向数据的方法；另一种方法是以处理需求为主，兼顾信息需求，称为面向过程的方法。数据库设计目前一般采用生命周期法，即将整个数据库应用系统的开发分解成目标独立的假设干阶段，它们是：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。在数据库设计中采用上面几个阶段中的前四个阶段，并且重点以数据结构与模型的设计为主线。2.数据库概念设计的过程：1选择局部应用；2视图设计：一般有三种设计次序：自顶向下、由底向上、由内向外。3视图集成。3.数据库管理1数据库的建立；2数据库的调整；3数据库的重组；4数据库平安性控制与完整性控制；5数据库的故障校复；6数据库监控。