计算机二级公共课基础知识考点详解(适用于office WPS)
4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历
1.算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。
2.算法的基本要素:
考点2 算法复杂度
即算法的工作量=f(n)
考点3 数据结构的定义
数据结构作为计算机的一门学科，主要研究和讨论以下三个方面:
(1)数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构;
(2)在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构;
考点4 线性结构与非线性结构
1.3 栈及线性链表
考点5 栈及其基本运算
当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不
可能再进行入栈操作。
首先将栈顶元素(栈顶指针指向的元
素)赋给一个指定的变量，然后将栈顶指针减一(即top减1)。
当栈顶指针为0时，说明栈空，不可进行退栈
个称为右指针，用以指向其后件结点。而数据元素之间的逻辑关系是由指针域来确定的。
1.4 树与二叉树
考点7 树与二叉树及其基本性质
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的
结点只有一个，称为树的根结点。
没有后件的结点
称为叶子结点。二叉树，而树结构中的每一个结点的度可以是任意的。
另外，二叉树中的每个结点的子树被明显地分为左子
树和右子树。
个结点既没有左子树也没有右子树时，该结点即为叶子结点。
在满二叉树中，
1.5 查找技术
从线性表的第一个元素开始，依次将线性表中
的元素与被查找的元素相比较，若相等则表示查找成功;若线性表中所有的元素都与被查找元素进行了比较但都不相等，则表示查找失败。
1.6 排序技术
考点11 交换类排序法
排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则
大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。
冒泡排序法的平均执行时间是O(n
2)，而快速排序法的平均执行时间是O(nlog2n)。
1.7 例题详解
入数据所有的可能取值范围、输入各种数据或数据集的概率有关。
【例2】在数据结构中，从逻辑上可以把数据结构分成___。
C)紧凑结构和非紧凑结构 D)动态结构和静态结构
解析:逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结
构表示数据元素之间为一对多或者多对一的关系，所以答案为B)。
【例3】以下___不是栈的基本运算。
A)判断栈是否为素空 B)将栈置为空栈
C)删除栈顶元素 D)删除栈底元素
解析:栈的基本运算有:入栈，出栈(删除栈顶元素)，初始化、置空、判断栈是否为空或满、提取栈
顶元素等，对栈的操作都是在栈顶进行的。
【例4】链表不具备的特点是___。
A)可随机访问任意一个结点 B)插入和删除不需要移动任何元素
解析:顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。
以答案为A)。
【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是
A)ACBED B)DEABC
C)DECAB D)EDBAC
解析:后序遍历的顺序是"左子树-右子树-根结点";中序遍历顺序是"左子树-根结点-右子树";前
序遍历顺序是"根结点-左子树-右子树"。
为D)。
解析:对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。
二分查找查找不成功的关键字比
【例7】在快速排序过程中，每次划分，将被划分的表(或子表)分成左、右两个子表，考虑这两个子
表，下列结论一定正确的是___。
解析:快速排序基本思想是:任取待排序表中的某个元素作为基准(一般取第一个元素 )，通过一趟排
序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码
则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。
【例1】问题处理方案的正确而完整的描述称为___。
解析:计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。
【例2】一个空的数据结构是按线性结构处理的，则属于___。
如果对数据结构的运算是
按线性结构来处理的，则属于线性结构，否则属于非线性结构。
叶子结点数目等于树结点总数减去度不
解析:二分查找，也称折半查找，它是一种高效率的查找方法。
但二分查找有条件限制:要求表必须用
顺序存储结构，且表中元素必须按关键字有序(升序或降序均可)。
经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是结构化程序设计的原则、
面向对象方法的基本概念，读者应对此部分进行重点学习。
1.结构化程序设计方法的四个原则
考点1 结构化程序设计的原则
结构化程序设计方法引入了工程化思想和结构化
思想，使大型软件的开发和编程得到了极大的改善。
结构化程序设计方法的主要原则为:自顶向下、逐步求
精、模块化和限制使用goto语句。
程序设计时，应先考虑总体，后考虑细节;先考虑全局目标，后考虑局部目标;不要一开始就过多追求众多的细节，先从
最上层总目标开始设计，逐步使问题具体化。
考点2 面向对象方法的基本概念
当使用"对象"这个术语时，既可以指一个具体的对象，也可以泛指一般的对象，但是当使用"实例"这个术语时，必须是指一个
具体的对象。
通常把对对象的操作也称为方法或服务。
属性值应该指
的是纯粹的数据值，而不能指对象。
(2)类和实例
它描述了属于该对象类型的所有对象的性质，而一个对象
则是其对应类的一个实例。
消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制
是指，一个类允许有多个父类。
对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行动，该现象称
为多态性。
一个窗口是对象，它包含
了窗口的属性(如大小、颜色等)及其操作(如打开、关闭等)。
解析:20世纪70年代提出了"结构化程序设计(structured programming)"的思想和方法。
结构化程序设
计方法引入了工程化思想和结构化思想，使大型软件的开发和编程得到了极大的改善。
【例2】结构化程序设计方法的主要原则有下列4项，不正确的是___。
A)自下向上 B)逐步求精
解析:结构化程序设计方法的主要原则为:
(3)模块化:把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称
为一个模块。
【例3】面向对象的开发方法中，类与对象的关系是___。
A)抽象与具体 B)具体与抽象
C)部分与整体 D)整体与部分
解析:现实世界中的很多事物都具有相似的性质，把具有相似的属性和操作的对象归为类，也就是说类是具有共同属性、共同方法的对象的集合，是对对象的抽象。
它描述了该对象类型的所有对象的性质，而一
个对象则是对应类的一个具体实例。
【例1】在面向对象方法中，使用已经存在的类定义作为基础建立新的类定义，这样的技术叫做___。
有的类可当作基类来引用，则新类相应地可当作派生类来引用。
【例2】对象的基本特点包括___、分类性、多态性、封装性和模块独立性好等5个特点。
解析:对象具有如下的基本特点:
对象是可区分的，并且由对象的内在本质来区分;
可以将具有相同属性和操作的对象抽象成类;
同一个操作可以是不同对象的行为;
只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法;
(5)模块独立性。
答案:标识惟一性
【例3】对象根据所接收的消息而做出动作，同样的消息被不同的对象所接收时可能导致完全不同的行
为，这种现象称为___。
解析:对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该
现象称为多态性。
经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是软件生命周期、软件设计
的基本原理，软件测试的目的、软件调试的基本概念，读者应对此部分进行重点学习。
1.软件的概念、软件生命周期的概念及各阶段所包含的活动
2.概要设计与详细设计的概念、模块独立性及其度量的标准、详细设计常用的工具
3.软件测试的目的、软件测试的4个步骤、
4.软件调试的任务
考点1 软件定义与软件特点
软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。
数据是使程序能
正常操纵信息的数据结构。
可见，软件由两部分组成:
(1)机器可执行的程序和数据;
(2)机器不可执行的，与软件开发、运行、维护、使用等有关的文档。
软件的特点:(1)软件是逻辑实体，而不是物理实体，具有抽象性;
(3)使用期间不存在磨损、老化问题;
(4)软件的开发、运行对计算机系统具有依赖性;
小提示:应用软件是为解决特定领域的应用而开发的软件;系统软件是计算机管理自身资源，提高计算机使用效率并
为计算机用户提供各种服务的软件;支撑软件是介于两者之间，协助用户开发软件的工具性软件。
考点2 软件工程过程与软件生命周期
一般包括可行性分析研究
与需求分析、设计、实现、测试、交付使用以及维护等活动，如图3-1所示。
生命周期的主要活动阶段是:可行性研究与计划制定、需求分析、软件设计、软件实施、软件测试及运
行与维护。
3.2 结构化设计方法
考点3 软件设计的基本概念
软件设计应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高
(3)接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信;(4)过程设计则是把系统结构部件转换为软件的过程性描述。
抽象的层次从概要设计到详
细设计逐步降低。
模块化是指解决一个复杂问
题时自顶向下逐层把软件系统划分成若干模块的过程。
(3)信息隐蔽:信息隐蔽是指在一个模块内包含的信息(过程或数据)，对于不需要这些信息的其他模
(4)模块独立性:模块独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系
最少且接口简单。
衡量软件的模块独立性使用耦合性和内
聚性两个定性的度量标准。
一个模块的内聚性越强则该模块的
模块独立性越强。
内聚是从功能角度来衡量模块的联系，它描述的是模
块内的功能联系。
内聚有如下种类，它们之间的内聚度由弱到强排列:偶然内聚、逻辑内聚、时间内聚、过
耦合性取决于各个模块之间接口的复杂度、调用方式以
及哪些信息通过接口。
耦合可以分为下列几种，它们之间的耦合度由高到低排列:内容耦合、公共耦合、外
一般较优秀的软件设计，应尽量做到高内聚，低
耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。
讲，模块化设计总是希望模块之间的耦合表现为非直接耦合方式。
但是，由于问题所固有的复杂性和结构化设计的原则，非直
接耦合是不存在的。
考点4 详细设计
详细设计的任务是为软件结构图中的每个模块确定实现算法和局部数据结构，用某种选定的表达表示工
具算法和数据结构的细节。
详细过程设计的常用工具有:
(3)语言工具:PDL(伪码)。
过程设计语言(PDL)也称为结构化的语言和伪码，它是一种混合语言，采用英语的词汇和结构化程序
设计语言，类似编程语言。
相同点是三种图都有顺序结构，选择结构和多分支选择，并且N-S图和PAD图还有相同的WHILE重复型、UNTIL重复型;
不同点是程序流程图没有WHILE重复型、UNTIL重复型而有后判断重复型和先判断重复型。
考点5 软件测试的目的
其工作量、成本占总工作量、总成
(2)一个好的测试用例是能够发现至今尚未发现的错误的用例;
考点6 软件测试的实施
单元测试的技术可以采用
静态分析和动态测试。
成测试时将模块组装成程序，通常采用两种方式:非增量方式组装和增量方式组装。
确认测试的任务是验证软件的功能和性能，以及其他特性是否满足了需求规格说明中确定的各种需求，
包括软件配置是否完全、正确。
确认测试的实施首先运用黑盒测试方法，对软件进行有效性测试，即验证被
测软件是否满足需求规格说明确认的标准。
系统测试是通过测试确认软件，作为整个基于计算机系统的一个元素，与计算机硬件、外设、支撑软件、
数据和人员等其他系统元素组合在一起，在实际运行(使用)环境下对计算机系统进行一系列的集成测试和
系统测试的具体实施一般包括:功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测
3.4 软件的调试
程序的调试任务是诊断和改
正程序中的错误。
程序调试活动由两部分组成，一是根据错误的迹象确定程序中错误的确切性质、原因和位置;二是对程
调试原则可以从以下两个方面考虑:
表现，而没有修改错误本身;注意修正一个错误的同时有可能会引入新的错误;修改错误的过程将迫使人们
暂时回到程序设计阶段;修改源代码程序，不要改变目标代码。
经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是数据库管理系统，数据库
基本特点，数据库系统的三级模式及二级映射，E-R模型，关系模型和关系代数，读者应对此部分进行重点
1.数据的概念、数据库管理系统提供的数据语言、数据管理员的主要工作、数据库系统阶段的特点、
数据的物理独立性及逻辑独立性、数据统一管理与控制、三级模式及两级映射的概念
考点1 数据、数据库、数据库管理系统
数据库是长期储存在计算机内、有组织的、可共享的大量数据的集合，它具有统一的结构形式并存放于
数据库管理系统(DBMS，Database Management System)是数据库的机构，它是一种系统软件，负责数
据库中的数据组织、数据操作、数据维护、控制及保护和数据服务等。
数据库管理系统是数据系统的核心，
主要有如下功能:数据模式定义、数据存取的物理构建、数据操纵、数据的完整性、安全性定义和检查、数
据库的并发控制与故障恢复、数据的服务。
为完成数据库管理系统的功能，数据库管理系统提供相应的数据语言:数据定义语言、数据操纵语言、
当数据的物理结
构(包括存储结构、存取方式等)改变时，如存储设备的更换、物理存储的更换、存取方式改变等，应用程
序都不用改变。
数据的逻辑结构改变了，如
修改数据模式、增加新的数据类型、改变数据间联系等，用户程序都可以不变。
考点4 数据库系统的内部结构体系误区警示:
三级模式都有几种名称，读者应该熟记每个模式的另一些
(1)概念模式，也称逻辑模式，是对数据库系统中全局数据逻辑结构的描述，是全体用户(应用)公
(2)外模式，外模式也称子模式，它是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描
述，它是由概念模式推导而出来的，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。一个概念模式
分为两个阶段:把现实世界中的客观对象抽
象为概念模型;把概念模型转换为某一DBMS支持的数据模型。
两个实体集间的联系实际上是实体集间的函数关系，这种函数关系可以有下面几种:一对一的联系、一
对多或多对一联系、多对多。
考点7 层次模型满足下面两个条件的基本层次联系的集合为层次模型。
(2)除根结点以外的其他结点有且仅有一个双亲结点。
考点8 关系模型
疑难解答:E-R图是如何向关系模式转换的
考点9 关系代数
1.关系模型的基本操作
考点10 数据库设计概述
数据库设计中有两种方法，面向数据的方法和面向过程的方法:
们是:需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段和进
一步修改阶段。