二级公共选择题是所有二级科目的共同试题(占10分)，涉及到数据结构、数据库、软件工程的基础知识。下面的模拟试题仿照“未来教育题库真题”精心设计，从不同视角进行解读，如果对“未来教育题库真题”理解不深，可以通过这套模拟试题加深理解，如果已经完全搞懂“未来教育题库真题”，这套模拟试题就不必看了。
二级语言类及数据库类科目获证条件：总分达到60分且选择题得分达到50%及以上（即选择题得分要达到20分及以上）的考生方可取得合格证书。由此看来，考生应当重视公共选择题。
第1题 下列叙述中错误的是
（A） 设计算法时，要考虑时间复杂度和空间复杂度
（B） 算法不等于计算方法
（C） 算法就是程序
（D） 算法是指解题方案的准确而完整的描述
答案 C
知识点
① 算法是指解题方案的准确而完整的描述。
② 算法不等于程序，也不等于计算方法。
③ 算法的时间复杂度是指执行算法所需要的计算工作量。
④ 算法的空间复杂度是指执行算法所需要的内存空间。
⑤ 设计算法必须考虑时间复杂度和空间复杂度。
⑥ 算法的时间复杂度与空间复杂度是衡量算法性能的最重要指标。
⑦ 算法的时间复杂度与空间复杂度之间不存在必然联系。
孪生题1 下列叙述中错误的是
（A） 设计算法时，要考虑时间复杂度和空间复杂度
（B） 算法不等于计算方法
（C） 设计算法时，要考虑数据结构的选取和设计
（D） 设计算法时，只需考虑算法的正确性
答案 D
孪生题2 对于给定算法，下列叙述中错误的是
（A） 若时间复杂度大，则空间复杂度可能小
（B） 若时间复杂度大，则空间复杂度也可能大
（C） 时间复杂度与空间复杂度之间没有必然联系
（D） 若时间复杂度小，则空间复杂度必定小
答案 D
第2题 下列叙述中错误的是
（A） 有两个以上(含两个)根结点的数据结构一定是非线性结构
（B） 循环链表是线性结构
（C） 只有一个根结点的数据结构一定是线性结构
（D） 双向链表是线性结构
答案 C
知识点
① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构，二叉树是典型的非线性结构，如下图所示：
其中，圆圈表示数据结点，有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点，没有后继的结点叫做终端结点或叶结点。在上图的线性表中，B是根结点，E是终端结点，X的前趋是U，X的后继是K。在上图的二叉树中，R是根结点，A、D、M、G都是叶结点，X的前趋是R，X的后继是C和D，结点C和D之间没有关系。任意两个结点之间要么没有关系，要么是前趋后继关系。
若一个数据结构只有一个根结点，其任一结点至多有一个前趋、至多有一个后继，则该数据结构称为线性结构。如果一个数据结构不是线性结构，就称为非线性结构。
② 由线性结构的定义可知，有两个以上根结点的数据结构一定是非线性结构。
③ 只有一个根结点的数据结构可能是线性结构，如上图中的线性表；也可能是非线性结构，如上图中的二叉树。
④ 如上图所示，用结点和有向线段的图所表示的数据结构，称为逻辑结构。逻辑结构在机器内存中的表示形式，称为存储结构。一种逻辑结构可有多种不同的存储结构。
⑤ 在C语言中，若用结构体的数据域存储线性表的结点值，用结构体的指针域表示结点间的前趋后继关系，则这种存储结构叫做线性链表。例如：①中的线性表可表示为多种线性链表，如下图所示，但它们都是线性表的存储结构，都属于线性结构。
因此，循环链表是线性结构，双向链表也是线性结构。
第3题 在非空二叉树中，记度数为0、1、2的结点个数分别为n0、n1、n2，下列叙述中正确的是
（A） n0 = n2 – 1
（B） n0 = n2 + 1
（C） n0 = 2×n2 – 1
（D） n0 = 2×n1 + 1
答案 B
知识点
① 设有非空二叉树，如下图所示。因为二叉树为层次结构，所以将有向线段改为无向线段，并把无向线段叫做边，约定根结点在第1层。对于上下相邻的两层，上层结点为前趋，下层结点为后继，例如：X的后继是C和D，X的前趋是R，因此，下面的两棵二叉树等价。
② 结点的度数就是它的后继结点的个数。在二叉树中，结点的最大度数为2。在上面的二叉树中，度为0的结点(即叶结点)共有4个，分别是A、D、M、G；度为1的结点共有1个，即S；度为2的结点共有3个，分别是R、X、C。
③ 在非空二叉树中，记度数为0、1、2的结点个数分别为n0、n1、n2，则n0 = n2 + 1成立。
证明：设边的总数为m
自上而下观察可知，除根结点外，每条边均对应一个结点，故有
n0 + n1 + n2 = m + 1
再观察可知，度为2的结点均关联2条边，度为1的结点均关联1条边，度为0的结点无关联边，故有
m = 2×n2 + n1
所以，将m代入上式，有
n0 + n1 + n2 = 2×n2 + n1 + 1
即有
n0 = n2 + 1
④ 随便画一棵简单二叉树，具体数一数，也可选出正确答案。
第4题 在最坏情况下，下列各组排序法比较次数的数量级不同的是
（A） 堆排序与希尔排序
（B） 冒泡排序与快速排序
（C） 简单插入排序与简单选择排序
（D） 简单插入排序与冒泡排序
答案 A
知识点
① 排序算法的时间复杂度分析很难理解，且不同教材给出的结论不完全一致。作为二级考生，应以教育部考试中心指定教材的结论为准，见下面的②③④⑤。解答此题需要牢记若干结论。
② 简单插入排序、简单选择排序、冒泡排序都是基本排序算法，在最坏情况下，这三种排序算法的比较次数均为Ο(n2)。
③ 希尔排序是对简单插入排序的改进，在最坏情况下，其比较次数为Ο(n1.5)。
④ 快速排序是对冒泡排序的改进，在最坏情况下，其比较次数为Ο(n2)。
⑤ 堆排序是对简单选择排序的改进，在最坏情况下，其比较次数为Ο(n×log2n)，括号内是n与以2为底的n的对数的乘积。
⑥ 记号Ο(*)为数量级符号，比较次数为Ο(n2)的含义是：比较次数与n2同数量级，或者说，比较次数的增长率与n2的增长率相同。
⑦ 比较操作是排序算法的基本操作，比较操作的次数直接反映算法的执行时间。
⑧ n反映问题的规模，这里n是被排序元素的个数。
孪生题1 在最坏情况下，下列排序法比较次数的数量级小于Ο(n2)的是
（A） 堆排序
（B） 简单选择排序
（C） 快速排序
（D） 冒泡排序
答案 A
第5题 软件生命周期的含义是
（A） 软件产品从提出到实现的过程
（B） 软件产品从提出、实现、使用维护到停止使用退役的过程
（C） 软件产品开发与维护的阶段
（D） 软件产品从使用维护到停止使用退役的过程
答案 B
知识点
① 定义：软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。
第6题 在面向对象的程序设计中，对象将数据(属性)和操作(方法)结合在一起，这是通过下列哪种机制实现的
（A） 继承
（B） 多态
（C） 抽象
（D） 封装
答案 D
知识点
① 在面向对象的程序设计实践中，对象是对客观世界中任何实体的抽象，根据编程需要，抽取客观实体的若干属性和一组相关操作。属性的具体值是刻画实体的数据，针对数据的各种操作称为方法。例如：Windows系统中的窗口是对象，其属性有位置、大小、标题等等，其方法有打开、关闭、最小化等等。
② 由刻画实体的各种数据和一组相关操作封装而成的整体就是对象。
③ 继承是指直接获得已有的性质和特征的机制。
④ 多态机制使得同一消息被不同对象接收时，产生完全不同的行为。
孪生题1 在面向对象的程序设计中，封装机制实现了
（A） ……
（B） 数据和操作的结合
（C） ……
（D） ……
第7题 下列哪种方法属于黑盒测试
（A） 语句覆盖
（B） 等价类划分
（C） 分支覆盖
（D） 基本路径测试
答案 B
解析 此题宜考前强化记忆，二级考纲只要求软件工程的初步知识，考生往往基础知识不足，不易理解。
知识点
① 软件测试是为发现错误而执行程序的过程。
② 白盒测试把测试对象看作透明的盒子，根据程序内部逻辑结构及有关信息来设计测试用例，对程序所有的逻辑路径进行测试 。
③ 黑盒测试把测试对象当成不透明的盒子，完全不考虑程序内部逻辑结构和特性，只依据程序的需求和规格说明，检查程序功能是否符合其功能说明。
④ 白盒测试的常用方法有：逻辑覆盖测试和基本路径测试。逻辑覆盖测试又细分为语句覆盖、路径覆盖、判定覆盖(也叫分支覆盖)、条件覆盖、判定-条件覆盖(也叫条件-分支覆盖)。
⑤ 黑盒测试的常用方法有：等价类划分、边界值分析、错误推测、因果图。
注：若把白盒测试与黑盒测试的方法任意混在一起，考生必须能够辨别区分，这是最常见的一种题型。
孪生题1 下列哪种方法属于白盒测试
（A） ……
（B） 条件覆盖
（C） ……
（D） ……
孪生题2 下列哪种方法属于白盒测试
（A） ……
（B） 逻辑覆盖
（C） ……
（D） ……
孪生题3 下列哪种方法属于白盒测试
（A） 等价类划分
（B） 边界值分析
（C） 判定-条件覆盖
（D） 错误推测法
答案 C
第8题 在数据库系统中，数据模型的三个组成要素是
（A） 层次模型、网状模型、关系模型
（B） 数据插入、数据删除、数据修改
（C） 概念模式、外模式、内模式
（D） 数据结构、数据操作、数据约束
答案 D
解析 考查数据模型的三要素。此题宜考前强化记忆，二级考纲只要求数据库系统的初步知识，考生往往基础知识不足，不易理解。
知识点
① 数据模型是对现实世界数据特征的抽象，是一种模型。数据模型由数据结构、数据操作、数据约束三个要素组成。一定要牢记！
② 数据结构描述数据库的组成对象以及对象之间的联系 ，是对系统静态特性的描述。
③ 数据操作是指对数据库中各种对象(型)的实例(值)允许执行的操作的集合，包括操作及有关的操作规则，是对系统动态特性的描述。
④ 数据约束是指数据的完整性约束条件，是一组完整性规则。
⑤ 完整性规则是特定的数据模型中数据及其联系所具有的制约和依存规则，用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效和相容。
孪生题 下列哪一项不是数据模型的组成要素
（A） 数据操作
（B） 数据结构
（C） 数据约束
（D） ……
第9题 在大学里，一门课程可由若干个学生选修，而一名学生可以选修多门课程，则课程与学生之间具有
（A） 一对一联系
（B） 一对多联系
（C） 多对一联系
（D） 多对多联系
答案 D
解析 该题型需要初步的举一反三、比猫画虎能力。
知识点
① 客观存在并可相互区别的事物称为实体，同一类型实体的集合称为实体集。例如：一个学生、一名员工、一门课程等都是实体，而全体学生就构成一个实体集。
② 实体之间存在着三种联系，即一对一、一对多、多对多的联系。
③ 一所学校只有一个正校长，而一个正校长只领导一个学校，则学校与正校长之间具有一对一联系。
④ 一个班级有若干名学生，而一个学生只在一个班级中学习，则班级与学生之间具有一对多联系。
⑤ 一个教师能够讲授多门课程，而一门课程可由多个教师讲授，则教师与课程之间具有多对多联系。一门课程可由若干个学生选修，而一名学生可以选修多门课程，则课程与学生之间也是多对多联系。
⑥ 考生要能从类似③④⑤的具体实例中识别联系的类型。
孪生题1 在学校里，一个班级有若干名学生，而一个学生只在一个班级中学习，则班级与学生之间具有
（A） ……
（B） 一对多联系
（C） ……
（D） ……
孪生题2 一个系统由若干部件组成，而一个部件又由若干零件组成；反过来说，一个零件可用于多个不同的部件，而一个部件又可用于多个不同的系统。那么系统与部件之间具有
（A） ……
（B） 多对多联系
（C） ……
（D） ……
孪生题3 一个系统由若干部件组成，而一个部件又由若干零件组成；反过来说，一个零件可用于多个不同的部件，而一个部件又可用于多个不同的系统。那么部件与零件之间具有
（A） ……
（B） ……
（C） 多对多联系
（D） ……
孪生题4 在工厂，一种原材料可存放于多个仓库；一个仓库可存放多种原材料。那么仓库与原材料之间具有
（A） ……
（B） ……
（C） 多对多联系
（D） ……
孪生题5 在奥运会，一名运动员可参加多个项目；多名运动员可参加同一个项目。那么运动员与项目之间具有
（A） ……
（B） ……
（C） 多对多联系
（D） ……
孪生题6 在工厂，一种零件可存放于多个仓库；一个仓库可存放多种零件。那么仓库与零件之间具有
（A） ……
（B） ……
（C） 多对多联系
（D） ……
孪生题7 在大学里，一名学生可以选修多门课程，则学生与课程之间具有
（A） 一对一联系
（B） 一对多联系
（C） 多对一联系
（D） 多对多联系
参考答案 B
解：在大学里，一名学生可以选修多门课程，而一门课程可由多名学生选修，这是普遍的实际情况，学生与课程之间属于多对多联系。但在考试中，有像本题一样的题型，只给出″一名学生可以选修多门课程″，而不提″一门课程可由多名学生选修″，对于这种情况，可推测命题者的意图是让选″一对多联系″。
第10题 设关系数据库包含学生关系S、课程关系C、选修关系SC：
S（学号，姓名，性别，年龄，学院）
C（课程号，课程名，学分）
SC（学号，课程号，成绩）
则查询′信息学院′的学生学号、姓名和选修课程号的关系表达式为
答案 C
解析 该题型需要初步的举一反三、比猫画虎能力。
知识点
① 关系的直观形式是一张二维表，不妨设学生关系S、课程关系C、选修关系SC的内容分别是：
二维表中的行称为元组、列称为属性。这三个关系的模式分别记作：
S（学号，姓名，性别，年龄，学院）
C（课程号，课程名，学分）
SC（学号，课程号，成绩）
② 选项
的运算过程是：先对关系S执行选择运算
即把学生关系S的学院属性值为 ′信息学院′ 的元组挑出来构成一个新关系，如下图所示：
再对关系
执行投影运算
即把关系
的学号、姓名、课程号这三个属性列挑出来构成一个新关系。所谓投影，可设想用灯光照射指定的属性列而得到的影像。因为关系
不含课程号，所以投影运算无法进行，选项A是错误的
③ 选项
的运算过程是：先对关系S和SC执行自然连接运算
它要求S和SC具备相同属性列，否则无法进行运算。这里S和SC的相同属性列是学号。自然连接
的操作过程是：对于S的每一个元组，在SC中找出与之学号相同的各个元组(剔除相同属性学号列)并逐一与之拼接成新的元组，这样得出的全体新元组构成一个新关系，就是自然连接的结果，如下图所示：
再对关系
执行选择运算
即把关系
的学院属性值为′信息学院′的元组挑出来构成一个新关系，如下图
但题目要求查询学院为 ′信息学院′ 的学号、姓名和课程号共3个属性列，而这里却得到了7个属性列，因此选项B也是错误的。
④ 选项
的运算过程是：对选项B的运算结果继续进行投影运算
即把关系
的学号、姓名、课程号这三个属性列挑出来构成一个新关系。所谓投影，可设想用灯光照射这三个指定的属性列而得到的影像，如下图
显然，这正好符合题目要求，因此选项C是正确的。
⑤ 选项
的运算过程是：先对关系
(参见②)进行投影运算
即把关系
的学号和姓名这两个属性列挑出来构成一个新关系，如下图：
再将关系
与SC进行自然连接运算
它的操作过程是：对于
的每一个元组，在SC中找出与之学号相同的各个元组(剔除相同属性学号列)并逐一与之拼接成新的元组，这样得出的全体新元组构成一个新关系，就是自然连接的结果，如下图所示：
显然，这个结果不符合题目要求，因此选项D是错误的。
孪生题1 设关系数据库包含学生关系S、课程关系C、选修关系SC：
S（学号，姓名，性别，年龄，学院）
C（课程号，课程名，学分）
SC（学号，课程号，成绩）
则查询学院为 ′电气学院′ 的学生学号、姓名、选修课程号和成绩的关系表达式为
（A） ……
（B）
（C） ……
（D） ……
孪生题2 设关系数据库包含学生关系S、课程关系C、选修关系SC：
S（学号，姓名，性别，年龄，学院，籍贯）
C（课程号，课程名，学分）
SC（学号，课程号，成绩）
则查询籍贯为 ′河北′ 的学生学号、姓名和选修课程号的关系表达式为
（A） ……
（B）
（C） ……
（D） ……
第11题 带有头结点的非空单链表所表示的数据结构
（A） 既有根结点，也有叶结点
（B） 既无根结点，也无叶结点
（C） 只有根结点，但无叶结点
（D） 没有根结点，但有叶结点
答案 A
知识点
① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构，二叉树是典型的非线性结构，如下图所示：
其中，圆圈表示数据结点，有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点，没有后继的结点叫做终端结点或叶结点。在上图的线性表中，B是根结点，E是叶结点，X的前趋是U，X的后继是K。在上图的二叉树中，R是根结点，A、D、M、G都是叶结点，X的前趋是R，X的后继是C和D，结点C和D之间没有关系。任意两个结点之间要么没有关系，要么是前趋后继关系。
若一个数据结构只有一个根结点，其任一结点至多有一个前趋、至多有一个后继，则该数据结构称为线性结构。如果一个数据结构不是线性结构，就称为非线性结构。
② 非空线性表至少含有一个结点。如果线性表只有一个结点，那么它既是根结点，也是叶结点。如果线性表含有两个以上结点，那么前端是根结点，末端是叶结点。如下图所示：
③ 如上图所示，用结点和有向线段的图所表示的数据结构，称为逻辑结构。逻辑结构在机器内存中的表示形式，称为存储结构。一种逻辑结构可有多种不同的存储结构。
④ 在C语言中，若用结构体的数据域存储线性表的结点值，用结构体的指针域表示结点间的前趋后继关系，则这种存储结构叫做线性链表。例如：①中的线性表可表示为多种线性链表，如下图所示，但它们都是线性表的存储结构，都属于线性结构。
⑤ 综上所述，带有头结点的非空单链表所表示的数据结构是线性结构的线性表，既有根结点，也有叶结点。
孪生题 非空循环链表所表示的数据结构
（A） ……
（B） 既有根结点，也有叶结点
（C） ……
（D） ……
第12题 某树只有度为3的结点和叶结点(度为0)，若叶结点个数为69，则度为3的结点个数为
（A） 33
（B） 34
（C） 35
（D） 36
答案 B
知识点
① 有一种树，只含有度为3的结点和叶结点(度为0的结点)，如下图所示，(a)、(b)、(c)都是这样的树。记度为3的结点个数为n3，叶结点的个数为n0，则n0 = 2×n3 + 1。
证明：设边的总数为m
自下而上观察可知，除根结点外，每个结点均对应一条边，故有
n0 + n3 – 1 = m
再观察可知，度为3的结点均向下关联3条边，叶结点无关联边，故有
m = 3×n3
所以，有
n0 + n3 – 1 = 3×n3
即有
n0 = 2×n3 + 1
孪生题1 某树只有度为3的结点和叶结点(度为0)，若度为3的结点个数为18，则叶结点个数为
（A） ……
（B） ……
（C） 37
（D） ……
孪生题2 某树共有结点20个，且只有度为3的结点和叶结点(度为0)，若叶结点个数为9，则度为3的结点个数为
（A） ……
（B） ……
（C） 这样的树不存在
（D） ……
答案 C
解：
因为 n0 = 9，所以n3 = (n0 – 1) / 2 = 4
又因 n0 + n3 = 9 + 4 = 13 ≠ 20， 所以这样的树不存在
第13题 设循环队列的存储空间为Q(1：m)，初始空队列状态为 front = rear = 1，经过一系列入队操作和出队操作后，front = m-1、rear = m-2，则队列中的元素个数为
（A） 0
（B） 1
（C） m
（D） m – 1
答案 D
知识点
① 现实生活中的排队购票、买饭等服务活动，在程序设计中，通常采用队列来解决问题。队列的基本操作是入队操作和出队操作。若队列未满，则可执行入队操作；若队列未空，则可执行出队操作。队列逻辑结构是线性表，但只在前端删除(出队)、在后端插入(入队)，故称为操作受限的线性表。在内存中，通常采用一维数组作为队列的存储结构。为了提高存储空间利用率，假想数组的首、尾元素也是相邻的，这就是循环队列，如下图所示：
② 对于循环队列Q(1：m)，其存储结构的一维数组下标从1至m。初始空队列有两种情况：front = rear = 1 或 front = rear = m均可。若队列非空，则规定变量front的值是队头元素的前面紧邻元素的下标，变量rear是队尾元素的下标。如下图所示：
③ 入队操作：若队列未满，则先令rear加1(若rear加1后等于m+1则令rear为1)，再将入队新元素赋值于下标rear指示的元素，成为新队尾元素。
④ 出队操作：若队列未空，则先令front加1(若front加1后等于m+1则令front为1)，再读取队头元素，即以front为下标的元素。
⑤ 记非空队列的当前元素个数为n。若front < rear(上图状态1)，则n = rear – front；若front > rear(状态2)，则n = m – (front – rear)。m是数组总容量。
例如：对于上图的状态1(m = 12时)：n = rear – front = 10 – 3 = 7
对于上图的状态2：n = m – (front – rear) = 12 – (8 – 3) = 7
注：根据front与rear的大小，直接套用公式，与初始状态无关。
⑥ 经过一系列的出队、入队操作后，若front = rear，则表明队列空或队列满。为了区分这两种状态，需要引入标志变量s，定义如下：
在队列操作过程中，要适时设置s的值。当检测到s=0时，表明队空；当检测到s=1且front = rear时，表明队满，这时循环队列Q(1：m)的元素个数为m。
⑦ 以上为国家指定考试用书关于循环队列的论断，考生备考应以此为准。事实上，关于循环队列的操作，存在多种不同的处理方式，但与二级考试无关，不再补充。
孪生题1 设循环队列的存储空间为Q(1：m)，初始空队列状态为 front = rear = m，经过一系列入队和出队操作后，front = m-2，rear = m，则当前队列中的元素个数为
（A） ……
（B） ……
（C） 2
（D） ……
孪生题2 设循环队列的存储空间为Q(1：m)，初始空队列状态为 front = rear = 1，经过一系列入队和出队操作后，front = m-1，rear = m，则当前队列中的元素个数为
（A） ……
（B） ……
（C） 1
（D） ……
孪生题3 设循环队列的存储空间为Q(1：m)，初始空队列状态为 front = rear = 1，经过一系列入队操作和出队操作后，front = 21，rear = 15。接着，在队列中寻找最大值，在最坏情况下，需要比较的次数是
（A） m – 5
（B） m – 6
（C） 5
（D） 6
答案 B
解：无论寻找最大值，还是寻找最小值，在最坏情况下，需要比较的次数都是当前队列中的元素个数，所以，在本质上，就是求当前队列中的元素个数。
因为 front > rear，所以当前队列中的元素个数
n = m – (front – rear) = m – (21 – 15) = m – 6
注：直接套用公式，与初始状态无关。
孪生题4 关于循环队列，下列陈述中正确的是
（A） 队中元素个数只随队头指针的变化而变化
（B） 队中元素个数只随队尾指针的变化而变化
（C） 队中元素个数随队头指针和队尾指针的变化而变化
（D） 队中元素个数保持恒定不变
答案 C
第14题 下列哪一项是软件需求规格说明书的作用
（A） 可行性研究的依据
（B） 确认测试和验收的依据
（C） 单元测试的依据
（D） 集成测试的依据
答案 B
知识点
① 软件需求规格说明书的作用有三条：
- 便于用户和开发人员进行理解和交流。
- 反映用户问题的逻辑结构，是软件开发工作的基础和依据。
- 是确认测试和验收的依据。
注：务必牢记！若与其它选项混在一起，也必须能够区分。
② 软件需求规格说明书是需求分析阶段的结果文档。在软件生命周期的诸阶段中，可行性研究在先、而需求分析在后，因此，需求规格说明书不可能作为可行性研究的依据，选项A是错误的。
③ 单元测试的依据是软件详细设计规格说明书和源程序，因此选项C是错的。
④ 集成测试的依据是软件概要设计规格说明书，因此选项D是错的。
孪生题 下列哪一项不是软件需求规格说明书的作用
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
第15题 在数据流图(DFD)中出现的对象都必须在下列哪一项中定义
（A） 数据流图(DFD)
（B） 数据字典(DD)
（C） 判定树
（D） 判定表
答案 B
解析 考查数据流图与数据字典的关系。
知识点
① 需求分析是软件生命周期的一个重要阶段，分析用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。
② 常见的需求分析方法有：结构化分析方法和面向对象的分析方法。
③ 结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用，着眼于数据流、自顶向下、逐层分解、建立系统的处理流程，以数据流图(DFD)和数据字典(DD)为主要工具，建立系统的逻辑模型。
④ 结构化分析方法的常用工具有：数据流图、数据字典、判定树、判断表。
⑤ 数据流图从数据传递和加工的角度，刻画数据流从输入到输出的移动变换过程。
⑥ 数据字典对数据流图中出现的对象进行准确严格的定义。
孪生题 在数据字典(DD)中定义的对象都来自
（A） ……
（B） ……
（C） 数据流图(DFD)
（D） ……
第16题 在数据库系统的三级模式中，模式有
（A） 1个
（B） 2个
（C） 3个
（D） 多个
答案 A
解析 考查数据库系统三级模式结构的特征。
知识点
① 数据库系统由外模式、模式、内模式三级构成，如下图所示：
② 模式也叫逻辑模式或概念模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。一个数据库只有一个模式。数据库管理系统提供模式数据定义语言(模式DDL)来定义模式。
③ 外模式也叫子模式或用户模式，是数据库用户(应用程序员或最终用户)能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。一个数据库可以有多个外模式。数据库管理系统提供外模式数据定义语言(外模式DDL)来定义外模式。
④ 内模式也叫存储模式或物理模式，是对数据物理结构和存储方式的描述，是数据在数据库内部的组织方式。一个数据库只有一个内模式。
⑤ 对于每个外模式，都有一个外模式/模式映像，定义该外模式与模式之间的对应关系，这个映像通常包含在对应外模式的描述中。当模式改变时，由数据库管理员对各个外模式/模式映像作相应改变，使外模式保持不变，从而使基于外模式的应用程序不必修改，保证了数据与应用程序的逻辑独立性，简称数据的逻辑独立性。
⑥ 模式/内模式映像，定义数据全局逻辑结构与存储结构之间的对应关系，这个映像通常包含在模式的描述中。当数据库的存储结构改变时，由数据库管理员对模式/内模式映像作相应改变，使模式保持不变，从而应用程序也不必修改，保证了数据与应用程序的物理独立性，简称数据的物理独立性。
孪生题1 在数据库系统的三级模式中，外模式有
（A） ……
（B） ……
（C） 多个
（D） ……
孪生题2 下列哪一种模式是对数据物理结构和存储方式的描述，是数据在数据库内部的组织方式
（A） ……
（B） ……
（C） 内模式
（D） ……
你还能再设计一道题吗？
第17题 设有关系R，如下图所示：
则执行关系运算
后，得到的新关系是
（A）
（B）
（C）
（D）
答案 C
解析 考查选择运算σ的运算规则，σ是运算符。
知识点
① 关系的直观形式是一张二维表，给定关系R的内容是：
关系二维表中的行称为元组、列称为属性。关系R记作：
R（A，B，C，D，E）
其中A、B、C、D、E为属性名。
② 执行选择运算
就是要把满足条件 A=B ∧ D<90的所有元组挑出来、构成一个新关系，就是把属性A与属性B的值相等、且属性D的值小于90的所有元组挑出来，其中的逻辑与运算符∧表示″同时成立″的意思，即要求A=B 和 D<90同时成立，整个条件A=B ∧ D<90才算满足。满足该条件的所有元组，这里只有一个，即
（a3，a3，c3，88，e3）
因此，所得新关系为
孪生题 设有关系R，如下图所示：
则执行关系运算
后，得到的新关系是
（A） ……
（B）
（C） ……
（D） ……
第18题 在最坏情况下，下列算法的时间复杂度最高的是
（A） 堆排序
（B） 快速排序
（C） 二分查找(折半查找)
（D） 顺序查找
答案 B
解析 算法时间复杂度分析很难理解，需要牢记若干结论。
知识点
① 排序算法的时间复杂度分析很难理解，且不同教材给出的结论不完全一致。作为二级考生，应以教育部考试中心指定教材的结论为准，见下面的②③④⑤。
② 简单插入排序、简单选择排序、冒泡排序都是基本排序算法，在最坏情况下，这三种排序算法的比较次数均为Ο(n2)。
③ 希尔排序是对简单插入排序的改进，在最坏情况下，其比较次数为Ο(n1.5)。
④ 快速排序是对冒泡排序的改进，在最坏情况下，其比较次数为Ο(n2)，因此快速排序并不总是快的。
⑤ 堆排序是对简单选择排序的改进，在最坏情况下，其比较次数为Ο(n×log2n)，括号内是n与以2为底的n的对数的乘积。
⑥ 在最坏情况下，顺序查找算法的比较次数为Ο(n)。
⑦ 在最坏情况下，二分查找算法的比较次数为Ο(log2n)。
⑧ 记号Ο(*)为数量级符号，如：比较次数为Ο(n2)的含义是：比较次数与n2同数量级，或者说，比较次数的增长率与n2的增长率相同。
⑨ 比较操作是排序算法和查找算法的基本操作，比较次数直接反映算法的执行时间。
⑩ n反映问题的规模，例如：n是被排序元素的个数或查找范围内元素的个数。
孪生题1 在最坏情况下，下列算法的时间复杂度最低的是
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
孪生题2 在最坏情况下，二分查找算法的时间复杂度是
（A） ……
（B） ……
（C） Ο(log2n)
（D） ……
第19题 下列陈述中正确的是
（A） 循环队列是队列的逻辑结构
（B） 具有某种特点的二叉树可以不采用二叉链表来存储
（C） 二分查找(折半查找)只适用于顺序存储的线性表
（D） 含有多个指针域的链表一定是非线性结构
答案 B
解析 考查数据结构的若干基本结论。
知识点
① 现实生活中的排队购票、买饭等服务活动，在程序设计中，通常采用队列来解决问题。队列的基本操作是入队操作和出队操作。若队列未满，则可执行入队操作；若队列未空，则可执行出队操作。队列逻辑结构是线性表，但只在前端删除(出队)、在后端插入(入队)，故称为操作受限的线性表。在内存中，通常采用一维数组作为队列的存储结构，为充分利用存储空间，通常假想数组的首、尾元素也是相邻的，这就是循环队列，可见，循环队列是队列的存储结构，如下图所示
② 任何二叉树都可以采用二叉链表存储结构，如下图所示：
在二叉链表中，每个结点含有一个数据域和左、右两个指针域，分别指向左、右孩子结点。
③ 具有某种特点的二叉树，如满二叉树或完全二叉树，也可以采用一维数组作为其顺序存储结构，下图给出三层(根结点在第1层)的满二叉树以及所有可能的完全二叉树，并在每个结点的下方附着编号，编号从1开始，自上而下、自左而右依次编排：
满二叉树的特点是：各层结点数均达到其最大值，第k层结点数最大值为2k-1。完全二叉树的特点是：与满二叉树相比，只在最底层自右而左依次缺失若干结点。满二叉树也算作完全二叉树。试画出四层的满二叉树及其所有可能的完全二叉树。
④ 设完全二叉树有n个结点，k是某结点的编号，则
⑴ 若k=1，则该结点为根结点；若k>1，则其父结点编号为└k/2┘。
⑵ 若2k≤n，则编号为k的结点的左孩子结点的编号为2k，否则没有左孩子。
⑶ 若2k+1≤n，则编号为k的结点的右孩子结点的编号为2k+1，否则没有右孩子。
注：运算符└x┘表示取不超过x的最大整数，例如：└5┘=5，└4.1┘=└4.9┘=4
满二叉树或完全二叉树的顺序存储结构就是基于上述性质工作的。对于给定结点，通过其编号可以找到其父结点、左子结点或右子结点。
⑤ 二分查找(折半查找)要求线性表采用顺序存储结构且有序，升序或降序均可，这里以升序为例陈述算法：
二分查找算法：首先拿要找的值x与数组的中间元素进行比较，若x小于中间元素的值，则查找转向低半区进行，否则转向高半区进行。无论出现哪种情形，下一步均是比较x与所选半区的中间元素。这种将查找范围一分为二的过程不断继续直到查到目标元素或查找范围缩变为空时结束。
例如：在下面的顺序存储线性表(升序)中，查找45是否存在的过程：
先拿45与中间元素67比较，因45<67，故在低半区(6,12,45)继续查找，再拿45与中间元素12比较，因45>12，故在高半区(45)继续查找，再拿45与中间元素45比较，因45=45，故找到目标，算法结束。
中间元素的下标常由查找范围的左端下标l与右端下标r按下式计算：
中间元素的下标 = └(l+r)/2┘
⑥ 含有多个指针域的链表可以是非线性结构，如上面表示二叉树的二叉链表；也可以是线性结构，如下面表示线性表的双向链表：
练习题
试为自己设计一道孪生题，举一反三，可以从问题的反面来考虑。
孪生题 下列陈述中正确的是
（A） 非线性结构只能采用链式存储
（B） 非线性结构只能采用多重链表存储
（C） 线性结构必须采用顺序存储
（D） 有些数据结构只能采用链式存储
答案 D
解：二叉链表的每个结点均有两个指针域。对一般的树形逻辑结构，每个结点的孩子结点数多寡不一，自然采用指针域个数不同的结点，这种链式结构叫多重链表。
在数据结构中，存在两类存储结构，采用一维数组实现的存储结构叫顺序存储结构，通过数组元素之间的物理邻接关系来表示结点之间的前趋后继关系。为结点设置指针域，通过指针表示前趋后继关系的存储结构叫链式存储结构。
具有某种特点的二叉树，如满二叉树或完全二叉树，可以采用顺序存储，因此选项A和B都是错的。线性表、队列、栈等线性结构既可采用顺序存储，也可采用链式存储，因此选项C也是错误的。非完全二叉树、一般树结构、网状图结构等非线性结构只能采用链式存储，因此选项D是正确的。
第20题 某二叉树共有500个结点，其中含有206个叶结点，则度数为1的结点有
（A） 88个
（B） 89个
（C） 107个
（D） 不存在这种树
答案 B
知识点
① 设有非空二叉树，如下图所示。因为二叉树为层次结构，所以将有向线段改为无向线段，并把无向线段叫做边，约定根结点在第1层。对于上下相邻的两层，上层结点为前趋，下层结点为后继，例如：X的后继是C和D，X的前趋是R，因此，下面的两棵二叉树等价。
② 结点的度数就是它的后继结点的个数。在二叉树中，结点的最大度数为2。在上面的二叉树中，度为0的结点(即叶结点)共有4个，分别是A、D、M、G；度为1的结点共有1个，即S；度为2的结点共有3个，分别是R、X、C。
③ 在非空二叉树中，记度数为0、1、2的结点个数分别为n0、n1、n2，则 n0 = n2 + 1成立。
证明：设边的总数为m
自上而下观察可知，除根结点外，每条边均对应一个结点，故有
n0 + n1 + n2 = m + 1
再观察可知，度为2的结点均关联2条边，度为1的结点均关联1条边，度为0的结点无关联边，故有
m = 2×n2 + n1
所以，有
n0 + n1 + n2 = 2×n2 + n1 + 1
即有
n0 = n2 + 1
④ 本题求解如下：
解： 记度数为0、1、2的结点个数分别为n0、n1、n2
已知 n0 = 206，所以 n2 = n0 – 1 = 205
又知 n0 + n1 + n2 = 500，所以 n1 = 500 – n0 – n2 = 89
⑤ 拓展思考：
只要满足n0 = n2 + 1，n2 > 0，n1 > 0这三个条件，则结点总数为n0 + n1 + n2的二叉树一定能够构造出来。为什么？
提示：根据条件n0 = n2 + 1，可定义二元组(n2，n0)，对所有这种二元组(1，2)、(2，3)、(3，4)、……中的任意一个二元组，均可构造一颗完全二叉树，沿着其中任意一个叶结点的方向，可以添加任意个度为1的结点(这里只添加n1个)，同时保持n2和n0不变，这样，结点总数为n0 + n1 + n2的二叉树就被构造出来了。（记住结论即可）
注：完全二叉树的概念可参见公共选择题第19题。
孪生题1 某二叉树共有450个结点，其中度为2的结点有205个，则度为1的结点有
（A） ……
（B） ……
（C） 39个
（D） ……
解： 记度数为0、1、2的结点个数分别为n0、n1、n2
已知 n2 = 205，所以 n0 = n2 + 1 = 206
又知 n0 + n1 + n2 = 450，所以 n1 = 450 – n0 – n2 = 39
孪生题2 某二叉树共有403个结点，其中度为2的结点有201个，则叶结点有
（A） ……
（B） ……
（C） 202个
（D） ……
解：记度数为0、1、2的结点个数分别为n0、n1、n2
已知 n2 = 201，所以 n0 = n2 + 1 = 202
又知 n0 + n1 + n2 = 403，所以 n1 = 403 – n0 – n2 = 0
孪生题3 某二叉树共有400个结点，其中度为2的结点有201个，则叶结点有
（A） ……
（B） ……
（C） 不存在这种树
（D） ……
解：记度数为0、1、2的结点个数分别为n0、n1、n2
已知 n2 = 201，所以 n0 = n2 + 1 = 202
又知 n0 + n1 + n2 = 400，所以 n1 = 400 – n0 – n2 = -3
因为n1不可能为负数，所以不存在这种树
孪生题4 某二叉树共有17个结点，度为1的结点有4个，则叶结点有
（A） ……
（B） ……
（C） 7个
（D） ……
解：记度数为0、1、2的结点个数分别为n0、n1、n2
已知 n1 = 4，又知 n0 + n1 + n2 = 17
所以 n0 + n2 = 17 – n1 = 17 – 4 = 13
因为 n0 = n2 + 1，所以 n2 = n0 – 1
所以 n0 + n0 – 1 = 13
即有 n0 = 7
孪生题5 某二叉树有70个叶结点、60个度为1的结点，则该树的结点总数是
（A） 199
（B） 200
（C） 201
（D） 202
解：记度数为0、1、2的结点个数分别为n0、n1、n2
已知 n0 = 70
所以 n2 = n0 – 1 = 70 – 1 = 69
已知 n1 = 60
所以 n0 + n1 + n2 = 70 + 60 + 69 = 199
你还能再设计两道孪生题吗？
第21题 设循环队列的存储空间为Q(1：m)，初始空队列状态为 front = rear = m，经过一系列入队操作和出队操作后，front = rear，则队列中的元素个数为
（A） 0
（B） m
（C） 0 或 m
（D） 无法确定
答案 C
解析
如果理解或记住了下面的知识点，就不难选择。当front = rear时，可能队空，也可能队满，因此选项C是正确的。
知识点
① 现实生活中的排队购票、买饭等服务活动，在程序设计中，通常采用队列来解决问题。队列的基本操作是入队操作和出队操作。若队列未满，则可执行入队操作；若队列未空，则可执行出队操作。队列逻辑结构是线性表，但只在前端删除(出队)、在后端插入(入队)，故称为操作受限的线性表。在内存中，通常采用一维数组作为队列的存储结构。为了提高存储空间利用率，假想数组的首、尾元素也是相邻的，这就是循环队列，如下图所示：
② 对于循环队列Q(1：m)，存储结构的一维数组下标从1至m。初始空队列通常约定两种情况：front = rear = 1 或 front = rear = m。若队列非空，则规定变量front的值是队头元素的前面紧邻元素的下标，变量rear是队尾元素的下标。如下图所示：
③ 入队操作：若队列未满，则先令rear加1(若rear加1后等于m+1则令rear为1)，再将入队新元素赋值于下标rear指示的元素，成为新队尾元素。
④ 出队操作：若队列未空，则先令front加1(若front加1后等于m+1则令front为1)，再读取队头元素，即以front为下标的元素。
⑤ 记非空队列的当前元素个数为n。若front < rear(上图状态1)，则n = rear – front；若front > rear(状态2)，则n = m – (front – rear)。m是数组总容量。
例如：对于上图的状态1(m = 12时)：n = rear – front = 10 – 3 = 7
对于上图的状态2：n = m – (front – rear) = 12 – (8 – 3) = 7
⑥ 经过一系列的出队、入队操作后，若front = rear，则表明队列空或队列满。为了区分这两种状态，需要引入标志变量s，定义如下：
在队列操作过程中，要适时设置s的值。当检测到s=0时，表明队空；当检测到s=1且front = rear时，表明队满，这时循环队列Q(1：m)的元素个数为m。
⑦ 以上为国家指定考试用书关于循环队列的论断，考生备考应以此为准。事实上，关于循环队列的操作，存在多种不同的处理方式，但与二级考试无关，不再补充。
孪生题 设循环队列的存储空间为Q(1：100)，初始空队列状态为 front = rear = 100，经过一系列入队操作和出队操作后，front = rear = 50，则队列中的元素个数为
（A） 0
（B） 100
（C） 0 或 100
（D） 50
答案 C
你还能再设计两道孪生题吗？
第22题 在结构化程序设计中，所采用的基本控制结构包括
（A） 顺序结构、选择结构、循环结构
（B） 层次结构、网状结构
（C） 主模块、子模块
（D） 主函数、自定义函数、库函数
答案 A
知识点
① 结构化程序设计是20世纪70年代提出的程序设计思想和方法，提倡采用顺序结构、选择结构、循环结构这三种基本控制结构来编写程序，使得程序结构良好、容易理解和维护，是经过长期实践检验的有效方法。
② 顺序结构按照语句的书写顺序逐条执行。
③ 选择结构，也叫分支结构，根据条件表达式的真假或表达式的多个不同取值，转向执行不同的语句分支。
④ 循环结构，也叫重复结构，反复计算条件表达式的值，只要为真，就重复执行同一段代码，直到条件表达式的值变成假为止。
孪生题 下列哪一项不属于结构化程序设计的三种基本控制结构
（A） 顺序结构
（B） 选择结构
（C） 顺序结构
（D） GOTO语句
第23题 在软件测试中，要用一系列测试用例去执行程序，目的是
（A） 发现错误
（B） 改正错误
（C） 发现并改正错误
（D） 功能演示
答案 A
知识点
① 软件测试是为了发现错误而执行程序的过程。可见，发现错误才是软件测试的根本目的。
孪生题 软件测试的目的在于
（A） ……
（B） 发现程序的错误
（C） ……
（D） ……
第24题 下列哪一项属于系统软件
（A） 操作系统
（B） 图书管理信息系统
（C） 需求分析工具软件
（D） Office办公套件
答案 A
知识点
① 软件按功能或作用通常可分为：系统软件、应用软件、支撑软件。
② 系统软件是与硬件亲密接触，使各个硬部件、相关软件和数据协同、高效工作，为用户提供各种服务的软件。操作系统、编译程序、汇编程序、数据库管理系统、设备驱动程序、通信与网络处理程序等都属于系统软件。
③ 应用软件是解决特定领域的具体问题的软件，要在操作系统的支持下运行。工程与科学计算软件、商务数据处理软件、实时控制软件、嵌入式软件、人工智能软件、桌面办公软件、财务管理软件等都属于应用软件。
④ 支撑软件，也叫工具软件，是指协助用户开发软件的工具性软件。需求分析工具、设计工具、编码工具、测试工具、维护工具、项目管理工具、配置管理工具等工具软件都属于支撑软件。
⑤ 常见题型是把各类软件的具体实例混杂在一起，要求辨别、归类。
注：粗体字要强化记忆。
孪生题1 下列哪一项属于系统软件
（A） ……
（B） 数据库管理系统
（C） ……
（D） ……
孪生题2 下列哪一项属于应用软件
（A） ……
（B） 财务管理软件
（C） ……
（D） ……
第25题 数据管理技术发展至今已经历三个阶段：人工管理阶段、文件系统阶段、数据库系统阶段。下列哪一项不是数据库系统的特点
（A） 局部数据结构化
（B） 数据共享性高、冗余度低、易扩充
（C） 数据独立性高
（D） 数据由数据库管理系统(DBMS)统一管理和控制
答案 A
知识点
① 数据管理技术发展至今已经历三个阶段：人工管理阶段、文件系统阶段、数据库系统阶段。
② 人工管理阶段的特点：
- 数据不保存
- 应用程序管理数据
- 数据不共享
- 数据不具有独立性
③ 文件系统阶段的特点：
- 数据可以长期保存
- 由文件系统管理数据
- 数据共享性差、冗余度大
- 数据独立性差
④ 数据库系统阶段的特点(要牢记)：
- 整体数据结构化
- 数据由数据库管理系统(DBMS)统一管理和控制
- 数据共享性高、冗余度低、易扩充
- 数据独立性高
孪生题1 数据管理技术发展至今已经历三个阶段：人工管理阶段、文件系统阶段、数据库系统阶段。下列哪一项不是数据库系统的特点
（A） ……
（B） 数据独立性差
（C） ……
（D） ……
孪生题2 数据管理技术发展至今已经历三个阶段：人工管理阶段、文件系统阶段、数据库系统阶段。下列哪个阶段的数据共享性最高
（A） ……
（B） 数据库系统阶段
（C） ……
孪生题3 数据管理技术发展至今已经历三个阶段：人工管理阶段、文件系统阶段、数据库系统阶段。数据库系统阶段的数据冗余度比文件系统阶段的
（A） 高
（B） 低
（C） 不确定
答案 B
第26题 在关系数据库系统中，关系是存储数据的
（A） 实体
（B） 属性
（C） 二维表
（D） 视图
答案 C
知识点
① 关系数据库管理系统(如SQL Server)在操作系统(如Windows Server)平台上运行，利用三级模式结构为采用结构化查询语言SQL(Structured Query Language)进行数据库应用开发的程序员提供一组视图或基本表(二维表)。在SQL应用程序或程序员看来，被操作的数据库呈现为一组视图或基本表，如下图。外模式包括若干视图和部分基本表，模式包括全体基本表，内模式包括全体存储文件。用户利用SQL对视图或基本表进行查询、插入、删除、更新等操作，视图和基本表一样，也是关系，也是二维表，但基本表是独立存在的表，一个或多个基本表对应一个存储文件，视图是封装一个或多个基本表的虚表，使数据库操作更灵活、方便、安全，并不被独立存储。
例如：设有一个简化的教务管理数据库系统，包含如下三个基本表(关系)，直观形式是二维表，不妨设学生关系S、课程关系C、选修关系SC的当前内容分别是：
随着教务管理数据库系统的运行，基本表的内容会不断变化更新。
关系是存储数据的二维表，其中，每一行称为元组、每一列称为属性。一个元组表示一个实体，如学生关系中的学生实体、课程关系中的课程实体；或者，一个元组表示两个实体间的联系，如学生与课程间的选课联系。实体是可相互区别的客观事物。表示同类实体的元组构成一个关系。
这些关系二维表，就像C语言的结构体、数组一样，是一种有结构的值，而这种值的类型，叫做关系模式，分别记作：
S（学号，姓名，性别，年龄，学院）
C（课程号，课程名，学分）
SC（学号，课程号，成绩）
可见，一个关系模式描述对应关系是由哪些属性组成的，关系模式描述数据的属性。
② 在实践中，一个关系数据库系统包含多个关系(基本表)，随着数据库系统的动态运行，关系的值，即基本表的内容会不断变化更新，但关系的类型，即关系模式却是恒定不变的。因此，关系是值，关系模式是关系的型，切勿混淆。
孪生题 在关系数据库系统中，关系模式描述数据的
（A） ……
（B） 属性
（C） ……
（D） ……
第27题 定义学生、课程、选课的关系模式分别是Student(S#，Sn，Ss，Sa，Colle，Dean)，其属性依次是学号、姓名、性别、年龄、所在学院、院长；Course(C#，Cname，Csc)，其属性依次是课程号、课程名、学分；SC(S#，C#，Gra)，其属性依次是学号、课程号、成绩，则这三个关系模式同属的最高级别范式为
（A） 第1范式
（B） 第2范式
（C） 第3范式
（D） BCNF范式
答案 B
解析 考查关系模式的级别，即判断给定关系模式属于第几范式。该题型需要初步的举一反三、比猫画虎能力。
知识点
① 关系的直观形式是二维表，关系二维表中的每一行称为元组、每一列称为属性。关系模式是关系的类型，指明关系包含哪些属性；关系是对应关系模式的实例(具体值)。随着数据库系统的运行，关系的值在不断变化。设与本题三个关系模式对应的三个关系的当前状态(当前值)如下图所示：
关系模式可简单理解为关系二维表的表头，于是，可将这三个关系模式分别记作：
Student(S#，Sn，Ss，Sa，Colle，Dean)
Course(C#，Cname，Csc)
SC(S#，C#，Gra)，
② 所谓″第几范式″原本是表示关系的某一种级别，所以常称某一关系模式R为第几范式，现在则把范式这个概念理解成符合某一种级别的关系模式的集合，即R属于第x范式，记作 R∈xNF，各种级别的范式集合之间的包含关系如下图所示：
注1：NF为Normal Form(范式)的缩写，BCNF是由Boyce和Codd两人共同提出的。
注2：高级范式一定也是低级范式，但反过来说是不行的！
③ 范式反映关系模式的优劣，一般而言，级别越高越好，但在设计关系模式时也要考虑实际情况。将低级关系模式分解、转换为高级关系模式的过程叫做规范化。
④ 对于二级考试而言，给定的关系模式中，有一个属性或两个属性的组合能够唯一标识一个元组，这一个属性或两个属性的组合叫做码，码内的属性叫主属性，码外的属性叫非主属性。任意两个元组的码值一定不同。例如：
学生模式 Student(S#，Sn，Ss，Sa，Colle，Dean) 的码是学号S#，任意两个学生元组的学号一定不同，S#是主属性；Sn、Ss、Sa、Colle、Dean都是非主属性。
课程模式 Course(C#，Cname，Csc) 的码是课程号C#，任意两课程元组的课程号一定不同，C#是主属性；Cname、Csc都是非主属性。
选课模式 SC(S#，C#，Gra) 的码是学号与课程号的二元组合{S#，C#}，任意两个选课元组的学号与课程号的组合一定不同，S#和C#是主属性；Gra是非主属性。
⑤ 第1范式1NF的定义：每一个属性值都是不可分的。因为学号S#、姓名Sn、性别Ss、年龄Sa、所在学院Colle、院长Dean、课程号C#、课程名Cname、学分Csc、成绩Gra等属性值都是不能拆分的、都是足够基本的值，所以学生模式Student、课程模式Course、选课模式SC都属于第1范式。二级考试给定的关系模式都属于第1范式。
⑥ 第2范式2NF的定义：码值能确定每一个非主属性的值。因为学号S#的值一旦给定，姓名Sn、性别Ss、年龄Sa、所在学院Colle、院长Dean等非主属性的值也就随之确定，所以学生模式Student属于第2范式。因为课程号C#的值一旦给定，课程名Cname、学分Csc等非主属性的值也就随之确定，所以课程模式Course也属于第2范式。因为学号与课程号的组合{S#，C#}的值一旦给定，成绩Gra这一非主属性的值也就随之确定，所以选课模式SC也属于第2范式。
⑦ 第3范式3NF的定义：码值不能传递(间接)确定任何非主属性。因为学号S#的值能确定(该学生)所在学院Colle的值，而所在学院Colle的值又能确定院长Dean的值，也就是说，学号S#的值能传递确定院长Dean的值，因此学生模式Student不属于第3范式。因为课程号C#的值能确定课程名Cname的值，而课程名Cname的值又能确定学分Csc的值，也就是说，课程号C#的值能传递确定学分Csc的值，因此课程模式Course也不属于第3范式。但在选课模式SC中，只有一个非主属性，即成绩Gra，学号与课程号的组合{S#，C#}的值不能传递确定成绩Gra，没有中介属性可用，无法形成传递，所以选课模式SC属于第3范式。
⑧ 综合⑤⑥⑦的结论可知，这三个关系模式同属的最高级别范式为第2范式。
⑨ BCNF范式的定义：非主属性只能由码来确定。因为所在学院Colle的值能确定院长Dean的值，但所在学院Colle并不是码，所以学生模式Student不属于BCNF范式。因为课程名Cname的值能确定学分Csc的值，但课程名Cname也不是码，所以课程模式Course也不属于BCNF范式。显然，选课模式SC属于BCNF范式。
⑩ 关系数据库的范式理论复杂费解，以上知识点都是简化说法，只适用于二级考试。因二级考试不涉及第4、5范式，故不再介绍。
孪生题 定义学生、课程、选课的关系模式分别是S(S#，Sn，Ss，Sa，Sdept，Dean)，其属性依次是学号、姓名、性别、年龄、所在系、系主任；Course(C#，Cname，P#)，其属性依次是课程号、课程名、先行课；SC(S#，C#，Grade)，其属性依次是学号、课程号、成绩，则这三个关系模式同属的最高级别范式为
（A） 第1范式
（B） 第2范式
（C） 第3范式
（D） BCNF范式
答案 B
第28题 算法的时间复杂度
（A） 与机器硬件的运行速度有关
（B） 与编译器所生成的代码质量有关
（C） 与运行算法时提供的特定输入有关
（D） 与程序设计语言的级别有关
答案 C
解析 考查算法时间复杂度的概念，哪些因素影响程序的执行时间，哪些因素影响算法的时间复杂度。
知识点
① 算法是指解题方案的准确而完整的描述。
② 算法必须用某种程序设计语言描述出来、变成程序，才能够在计算机上执行。算法不等于程序。
③ 算法的时间复杂度指执行算法所需要的计算工作量(即执行时间)。
④ 设算法采用高级语言来描述，则影响程序执行时间的因素有：
- 机器硬件的运行速度。
- 编译器所生成的代码质量。
- 程序设计语言的级别。如汇编语言程序比高级语言程序更快。
- 程序编制者的水平。
- 程序中的语句条数。
- 运行程序时提供的特定输入。如在顺序查找中，输入的待查找值在数组中的实际位置不同，查找时间也就不同。查找首元素最快，查找最后一个元素最慢。
- 问题的规模。如参与排序的元素个数，矩阵相乘的矩阵阶数。
- 基本运算的执行时间。程序的基本运算取决于具体问题，如矩阵相乘问题的乘法运算是基本运算、查找问题中的比较操作是基本运算。基本运算是耗时的主因。
⑤ 对于给定问题，通常存在多种算法策略。为了预先分析算法的执行效率，算法时间复杂度是在抛开机器硬件的运行速度、编译器所生成的代码质量、程序设计语言的级别、程序编制者的水平、程序中的语句条数这些具体的软、硬件因素，只考虑问题规模、基本运算和特定输入这三个更一般因素的基础上定义的。对于给定算法，记问题的规模为n，则基本运算的执行次数是问题规模n的函数f(n)。算法的时间复杂度记为
T(n) = O(f(n))
表示随问题规模n的增大，算法执行时间T(n)的增长率与f(n)的增长率相同。f(n)通常可转换成常数、n、n×log2n、n1.5、n2、n3、2n，相应就有了O(1)、O(n)、O(n×log2n)、O(n1.5)、O(n2)、O(n3)、O(2n)各种数量级的算法。记号Ο(*)为数量级符号，某排序算法的比较次数为Ο(n2)的含义是：比较次数与n2同数量级，或者说，比较次数的增长率与n2的增长率相同，于是，该排序算法的时间复杂度为Ο(n2)。
因此，影响算法时间复杂度的因素只有：
- 运行程序时提供的特定输入。
- 问题的规模。
- 基本运算的执行时间。
⑥ 本题命题思路就是把影响程序执行时间的因素与其中只影响算法时间复杂度的因素混合在一起，让考生分辨。
⑦ 当分析特定输入对算法的影响时，通常分析最坏情况下的时间复杂度和平均情况下的时间复杂度。
孪生题 下列关于算法时间复杂度的叙述中正确的是
（A） ……
（B） 与运行算法时提供的特定输入有关
（C） ……
（D） ……
第29题 在最坏情况下，时间复杂度居中的是
（A） 希尔排序
（B） 快速排序
（C） 堆排序
（D） 简单插入排序
答案 A
解析 解答此题需要牢记若干结论。
知识点
① 排序算法的时间复杂度分析很难理解，且不同教材给出的结论不完全一致。作为二级考生，应以教育部考试中心指定教材的结论为准，见下面的②③④⑤。
② 简单插入排序、简单选择排序、冒泡排序都是基本排序算法，在最坏情况下，这三种排序算法的比较次数均为Ο(n2)。
③ 希尔排序是对简单插入排序的改进，在最坏情况下，其比较次数为O(n1.5)。
④ 快速排序是对冒泡排序的改进，在最坏情况下，其比较次数为Ο(n2)，可见快速排序并非总是快的。
⑤ 堆排序是对简单选择排序的改进，在最坏情况下，其比较次数为O(n×log2n)，括号内是n与以2为底的n的对数的乘积。
⑥ 记号Ο(*)为数量级符号，如：比较次数为Ο(n2)的含义是：比较次数与n2同数量级，或者说，比较次数的增长率与n2的增长率相同。
⑦ 比较操作是排序算法的基本操作，比较操作的次数直接反映算法的执行时间。
⑧ n反映问题的规模，例如：n是被排序元素的个数。
⑨ 典型的数量级次序，务必牢记
O(n×log2n)＜O(n1.5)＜Ο(n2)
孪生题 在最坏情况下，时间复杂度最低的是
（A） ……
（B） 堆排序
（C） ……
（D） ……
第30题 已知栈的存储空间是S(1：30)，初始状态为top = 31，经过一系列正常入栈、出栈操作后，当前栈顶指针top = 30，那么当前栈中元素个数是
（A） 0
（B） 1
（C） 29
（D） 30
答案 B
解析 应理解或记住下面的知识点，该题型需要简单举一反三。
知识点
① 设有一端封闭竖直放置的圆柱形塑料筒，开口向上，直径刚好允许放进乒乓球，如下图所示：
显然，乒乓球呈现线性结构，用数据结构的话说，就是线性表。由于筒的一端封闭，乒乓球只能从一端进出，即按照″后进先出″的规则操作，用数据结构的话说，就是只能在线性表的一端，按照″后进先出″的规则插入、删除元素，这种操作受限的线性表叫做栈。栈在计算机技术领域中应用十分广泛，例如：在C语言中，函数的调用及返回(后调用的、先返回)的背后就有一个栈在工作。
② 栈的逻辑结构是操作受限的线性表，存储结构常用一维数组实现。
例如：设栈的存储空间是一维数组S(1：30)，可把栈顶指针top的初值设置为31，这就是栈的初始状态，也叫空栈，即栈中尚无元素。栈在工作过程中，依靠栈顶指针top进行元素的插入(进栈)或删除(出栈)，栈顶指针top总是指向当前的栈顶元素。进栈时， 先执行top减1，再将新元素赋值于S[top]；出栈时，先将当前栈顶元素S[top]取出，再执行top加1。当前栈中元素个数为31-top。如下图所示：
③ 也可把栈顶指针top的初值设置为0。进栈时，执行top加1；出栈时，执行top减1，其它操作与上面情况相同。当前栈中元素个数为top。如下图所示：
④ 综上所述，设栈的存储空间为数组S(1：n)，可把栈顶指针top的初值设置为n+1，即初始状态top = n+1；也可设置为0，即初始状态top = 0。若初始状态为top = n+1，则当前元素个数为n+1-top；若初始状态为top = 0，则当前栈中元素个数为top。
孪生题1 已知栈的存储空间是S(1：80)，初始状态为top = 0，经过一系列正常入栈、出栈操作后，当前栈顶指针top = 79，那么当前栈中元素个数是
（A） ……
（B） ……
（C） 79
（D） ……
孪生题2 已知栈的存储空间是S(1：40)，初始状态为top = 41，经过一系列正常入栈、出栈操作后，当前栈顶指针top = 1，那么当前栈中元素个数是
（A） ……
（B） ……
（C） 40
（D） ……
孪生题3 已知栈的存储空间是S(1：n)，初始状态为top = n+1，经过一系列正常入栈、出栈操作后，当前栈顶指针top的值也随之变化，那么当前栈中元素个数是
（A） ……
（B） ……
（C） n+1-top
（D） ……
第31题 在面向对象的程序设计中，下列陈述错误的是
（A） 继承具有传递性
（B） 多态性是指同一对象能够执行多种操作
（C） 消息传递是指对象之间的通信
（D） 对象是属性和方法的封装体
答案 B
知识点
① 在面向对象的程序设计实践中，对象是对客观世界中任何实体的抽象，根据编程需要，抽取客观实体的若干属性和一组相关操作。属性的具体值是刻画实体的数据，针对数据的各种操作称为方法。例如：Windows系统中的窗口是对象，其属性有位置、大小、标题等等，其方法有打开、关闭、最小化等等。
② 将刻画实体的各种数据(属性)和一组相关操作(方法)封装而成的统一体就是对象，因此对象是属性和方法的封装体。
③ 继承是指直接获得已有的性质和特征的机制。继承具有传递性，就像父亲继承了爷爷的财产，儿子又继承了父亲的财产，那么孙子通过父亲也继承了爷爷的财产。
④ 多态机制使得相同的消息被不同的对象接收时，产生完全不同的行为。也就是说，同样的消息被不同对象接收可执行完全不同的操作。
⑤ 对象之间的通信要依靠消息传递，类似函数之间的调用。
⑥ 根据实际需要，可在对象之间建立继承关系，但并非任何对象必须具有继承性。
⑦ ″同一对象能够执行多种操作″ 是正确的，但这不是多态性的含义。
孪生题1 在面向对象的程序设计中，下列陈述正确的是
（A） ……
（B） 对象之间的通信要依靠消息传递
（C） ……
（D） ……
孪生题2 在面向对象的程序设计中，下列陈述正确的是
（A） ……
（B） 多态是指同样的消息被不同对象接收可执行完全不同的操作
（C） ……
（D） ……
孪生题3 在面向对象的程序设计中，下列陈述错误的是
（A） ……
（B） 任何对象必须具有继承性
（C） ……
（D） ……
第32题 在软件设计中，衡量软件模块独立程度的标准是
（A） 低内聚、低耦合
（B） 低内聚、高耦合
（C） 高内聚、低耦合
（D） 高内聚、高耦合
答案 C
知识点
① 在软件设计中，模块化就是把复杂问题自顶向下逐层分解、把目标软件系统相应划分为若干模块的过程。
② 模块独立性是指模块只完成系统要求的独立子功能，与其它模块的联系最少且接口简单。
③ 内聚性是指一个模块内部各元素之间相互结合的紧密程度。
④ 耦合性是指各个模块之间相互结合的紧密程度。
⑤ 内聚性和耦合性是定性衡量模块独立程度的标准。若模块的内聚性越高、耦合性越低，则表明模块的独立性越好。
⑥ 高内聚、低耦合是划分模块应遵循的基本准则。
孪生题1 在软件设计中，划分模块要尽量做到
（A） ……
（B） 高内聚、低耦合
（C） ……
（D） ……
孪生题2 在软件设计中，划分模块是一项主要工作，应遵循下列哪一项准则
（A） 模块独立性只与内聚性有关
（B） 高内聚、低耦合
（C） 模块独立性只与耦合度有关
（D） 内聚与耦合无关
答案 B
孪生题3 下列陈述中错误的是
（A） 内聚性是指一个模块内部各元素之间相互结合的紧密程度
（B） 耦合性是指各个模块之间相互结合的紧密程度
（C） 提高内聚性、降低耦合性、有助于提高模块独立性
（D） 降低内聚性、提高耦合性、有助于提高模块独立性
答案 D
第33题 长期储存于计算机系统中的有组织、可共享的大量数据的集合是
（A） 数据
（B） 数据库
（C） 数据库管理系统
（D） 数据库系统
答案 B
知识点
① 数据是描述事物的符号记录。
② 数据库是长期储存于计算机系统中的有组织、可共享的大量数据的集合。
③ 数据库管理系统是介于用户和操作系统之间的一层数据管理软件。它和操作系统一样也是计算机的基础软件，是大型复杂的软件系统。
④ 数据库系统是由数据库、数据库管理系统、应用程序和数据库管理员组成的存储、管理、处理和维护数据的系统。
孪生题 数据库管理系统是
（A） ……
（B） 介于用户和操作系统之间的一层数据管理软件
（C） ……
（D） ……
第34题 设有关系数据库，学生关系S、课程关系C、选修关系SC：
学生关系S（学号，姓名，性别，年龄，学院）
课程关系C（课程号，课程名，学分）
选修关系SC（学号，课程号，成绩）
则选修关系SC的关键字(键或码)为
（A） 学号，课程号，成绩
（B） 学号，课程号
（C） 学号
（D） 学号，成绩
答案 B
解析 考查关键字(键或码)的概念，该题型需要初步的举一反三能力。
知识点
① 关系的直观形式是二维表，关系二维表中的每一行称为元组、每一列称为属性。关系模式是关系的类型，指明关系包含哪些属性；关系是对应关系模式的实例(具体值)。随着数据库系统的运行，关系的值在不断变化。设与本题三个关系模式对应的三个关系的当前状态(当前值)如下图所示：
关系模式可简单理解为关系二维表的表头，于是，可将这三个关系模式分别记作：
学生关系S（学号，姓名，性别，年龄，学院）
课程关系C（课程号，课程名，学分）
选修关系SC（学号，课程号，成绩）
② 对于二级考试而言，给定的关系模式中，有一个属性或两个属性的组合能够唯一标识一个元组，这一个属性或两个属性的组合叫做关键字(键或码)。任意两个元组的关键字值一定不同，例如：
学生关系S（学号，姓名，性别，年龄，学院）的关键字是学号，任意两个学生元组的学号一定不同。
课程关系C（课程号，课程名，学分）的关键字是课程号，任意两个课程元组的课程号一定不同。
选修关系SC（学号，课程号，成绩）的关键字是学号与课程号的组合，任意两个选修元组的学号与课程号的组合一定不同。
孪生题 设有关系数据库，公司关系、员工关系、聘用关系：
公司关系（公司号，公司名，办公地点，法人代表）
员工关系（员工号，姓名，性别，年龄，业绩）
聘用关系（员工号，公司号，聘期，年薪）
则聘用关系的关键字(键或码)为
（A） ……
（B） ……
（C） 员工号，公司号
（D） ……
注：二级考试总是考查这种由两个属性组合而成的关键字，其特点是两个号的组合，例如：″学号，课程号″、″员工号，公司号″、″商场号，职工号″等等
第35题 下列叙述中错误的是
（A） 空数据结构可能是线性结构，也可能是非线性结构
（B） 任一结点至多有一个前件、至多有一个后件的数据结构一定是线性结构
（C） 只有一个根结点的数据结构可能是线性结构，也可能是非线性结构
（D） 有两个根结点的数据结构一定是非线性结构
答案 B
解析 考查线性结构的定义。
知识点
① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构，二叉树是典型的非线性结构，如下图所示
其中，圆圈表示数据结点，有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点，没有后继的结点叫做终端结点或叶结点。在上图的线性表中，B是根结点，E是终端结点，X的前趋是U，X的后继是K。在上图的二叉树中，R是根结点，A、D、M、G都是叶结点，X的前趋是R，X的后继是C和D，结点C和D之间没有关系。任意两个结点之间要么没有关系，要么是前趋后继关系。
若一个数据结构只有一个根结点，其任一结点至多有一个前趋、至多有一个后继，则该数据结构称为线性结构。如果一个数据结构不是线性结构，就称为非线性结构。前趋后继关系也叫前件后件关系。
② 由线性结构的定义可知，有两个以上根结点的数据结构一定是非线性结构。
③ 只有一个根结点的数据结构可能是线性结构，如上图中的线性表；也可能是非线性结构，如上图中的二叉树。
④ 有且仅有一个根结点的数据结构可能是线性结构，如单结点的线性表；也可能是非线性结构，如单结点的二叉树。
⑤ 空数据结构不含任何数据结点，根据实际问题需要，可视为线性结构，也可视为非线性结构。
孪生题1 下列叙述中正确的是
（A） ……
（B） 有且仅有一个根结点的数据结构可能是线性结构，也可能是非线性结构
（C） ……
（D） ……
孪生题2 下列叙述中错误的是
（A） ……
（B） ……
（C） 有且只有一个根结点的数据结构一定是线性结构
（D） ……
第36题 下列叙述中错误的是
（A） 在单链表中，只能从头指针开始遍历所有结点
（B） 在循环链表中，无法做到从任意结点开始都能遍历所有结点
（C） 在双向链表中，能够从任意结点开始遍历所有结点
（D） 在二叉链表中，只能从根结点开始遍历所有结点
答案 B
知识点
① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构，二叉树是典型的非线性结构，如下图所示：
其中，圆圈表示数据结点，有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点，没有后继的结点叫做终端结点或叶结点。在上图的线性表中，B是根节点，E是终端结点，X的前趋是U，X的后继是K。在上图的二叉树中，R是根结点，A、D、M、G都是叶结点，X的前趋是R，X的后继是C和D，结点C和D之间没有关系。任意两个结点之间要么没有关系，要么是前趋后继关系。
若一个数据结构只有一个根结点，其任一结点至多有一个前趋、至多有一个后继，则该数据结构称为线性结构。如果一个数据结构不是线性结构，就称为非线性结构。
② 如上图所示，用结点和有向线段的图所表示的数据结构，称为逻辑结构。逻辑结构在机器内存中的表示形式，称为存储结构。一种逻辑结构可有多种不同的存储结构。
③ 在C语言中，若用结构体的数据域存储线性表的结点值，用结构体的指针域表示结点间的前趋后继关系，则这种存储结构叫做链表。
例如：①中的线性表可表示为多种线性链表，如下图所示：
例如：①中的二叉树可表示为二叉链表，如下图所示：
在二叉链表中，每个结点含有一个数据域和左、右两个指针域，分别指向左、右孩子结点。
④ 无论何种逻辑结构，设计存储结构的基本要求是：必须提供遍历所有结点的方法，所谓遍历，就是从某结点出发，能够访问所有的结点。遍历就是周游的意思。对于不同的存储结构，遍历的方便程度有很大不同，也是评判存储结构优劣的标准之一。
⑤ 在单链表中，只能从头指针开始遍历所有结点。由于指针的单向性，若从中间某结点出发，则无法到达左边的结点，如从U出发，只能沿着指针依次访问X、K、N、E，却无法到达D或B，如上图所示。
⑥ 在循环链表中，因为指针形成了一个封闭的环路，所以从任意结点出发都能沿着指针依次访问所有结点、最终回到出发点，如上图。
⑦ 在双向链表中，虽然不存在封闭的指针环路，但指针是双向的，因此从任意结点出发也能访问所有结点，沿着左向指针依次访问左边的结点、沿着右向指针依次访问右边的结点，如上图所示。
⑧ 在二叉链表中，只能从根结点开始遍历所有结点，如上图所示，从根结点出发，沿着指针能够到达任何一个结点。从根结点以外的任意结点出发，只能访问到它的子孙结点，却无法到达其父结点、祖父结点……等等。
孪生题 下列叙述中错误的是
（A） ……
（B） ……
（C） 在单向链表中，能够从任意结点开始遍历所有结点
（D） ……
第37题 在面向对象的程序设计中，下列哪一项不是对象的基本特征
（A） 唯一性
（B） 多态性
（C） 分类性
（D） 可移动性
答案 D
知识点
① 在面向对象的程序设计实践中，对象是对客观世界中任何实体的抽象，根据编程需要，抽取客观实体的若干属性和一组相关操作。属性的具体值是刻画实体的数据，针对数据的各种操作称为方法。例如：Windows系统中的窗口是对象，其属性有位置、大小、标题等等，其方法有打开、关闭、最小化等等。
② 由刻画实体的各种数据和一组相关操作封装而成的整体就是对象。
③ 继承是指直接获得已有的性质和特征的机制。
④ 多态机制使相同的消息被不同对象接收时，产生完全不同的行为。
⑤ 对象的基本特征(主要特征)包括唯一性、分类性(抽象性)、封装性、继承性、多态性。应付二级考试要以此为准，其它教材另有不同说法。要牢记。
⑥ 唯一性指任意两个对象都是可区分的(至少有一个属性是不同的)。
⑦ 分类性指将具有相同属性和操作的对象抽象成类，也叫抽象性。
孪生题 在面向对象的程序设计中，下列哪一项不是对象的主要特征
（A） ……
（B） ……
（C） ……
（D） ……
注：凡与⑤中所列特征对不上号的任何说法均可作为正确选项
第38题 在白盒测试中，设计测试用例的依据是
（A） 需求规格说明书
（B） 可行性研究报告
（C） 程序内部逻辑
（D） 使用说明书
答案 C
解析 此题宜考前强化记忆，二级考纲只要求软件工程的初步知识，考生往往基础知识不足，不易理解。
知识点
① 软件测试是为发现错误而执行程序的过程。或者说，是根据软件开发各阶段的规格说明和程序内部结构而精心设计一批测试用例(即输入数据及其预期的输出结果)，并利用这些测试用例去运行程序，以发现程序错误的过程。
② 白盒测试把测试对象看作透明的盒子，根据程序内部逻辑结构及有关信息来设计测试用例，对程序所有的逻辑路径进行测试 。
③ 黑盒测试把测试对象当成不透明的盒子，完全不考虑程序内部逻辑结构和特性，只依据程序的需求和规格说明，检查程序功能是否符合其功能说明。
④ 在白盒测试中，设计测试用例的依据是程序内部逻辑。
⑤ 在黑盒测试中，设计测试用例的依据是程序功能或者需求规格说明书。因为需求规格说明书的内容就是程序的功能，所以作为设计测试用例的依据，两种说法都对。
注：牢记④⑤这两句话，应对该题型就没问题。
⑥ 按是否需要执行被测试软件，软件测试分为静态测试和动态测试。
⑦ 静态测试包括代码检查、静态结构分析、代码质量度量等，不实际运行软件，主要靠人工进行。
⑧ 动态测试是为发现错误而执行程序的过程，是基于计算机的测试。
⑨ 软件测试是确保软件质量的重要手段之一。
⑩ 程序调试的任务是诊断和改正程序中的错误，而软件测试的任务是发现错误。
孪生题1 在黑盒测试中，设计测试用例的依据是
（A） ……
（B） 程序功能
（C） ……
（D） ……
孪生题2 在黑盒测试中，设计测试用例的依据是
（A） ……
（B） 需求规格说明书
（C） ……
（D） ……
孪生题3 关于软件测试，下列叙述正确的是
（A） 测试用例可随机选取
（B） 软件测试是为了发现错误和改正错误
（C） 软件测试是确保软件质量的重要手段之一
（D） 软件测试是指动态测试
答案 C
第39题 在数据库技术中，下列哪一项是逻辑模型
（A） E-R模型
（B） 概念模型
（C） 物理模型
（D） 关系模型
答案 D
解析 此题宜考前强化记忆，二级考纲只要求数据库系统的初步知识，考生往往基础知识不足，不易理解。
知识点
① 模型是对现实世界中某种对象特征的模拟和抽象。数据模型是对现实世界数据特征的抽象，是数据库系统的核心和基础。
② 按照模型应用的不同目的划分，存在三种模型：概念模型、逻辑模型、物理模型。
③ 概念模型是面向客观世界、面向用户的模型，比较有名的概念模型有：E-R模型、扩充的E-R模型、谓词模型等。E-R模型也叫实体-联系模型(Entity-Relationship)。
④ 逻辑模型是面向数据库系统的模型，主要包括层次模型、网状模型、关系模型等。
⑤ 物理模型是面向计算机物理表示的模型。
⑥ 该题型的命题特点是，将三种模型混在一起，让考生辨别。
孪生题1 在数据库技术中，下列哪一项是概念模型
（A） ……
（B） E-R模型
（C） ……
（D） ……
孪生题2 在数据库技术中，下列哪一项是概念模型
（A） ……
（B） 实体-联系模型
（C） ……
（D） ……
孪生题3 在数据库技术中，下列哪一项是概念模型
（A） ……
（B） 谓词模型
（C） ……
（D） ……
孪生题4 在数据库技术中，下列哪一项不是逻辑模型
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
孪生题5 在数据库技术中，数据的逻辑模型主要包括
（A） 大型、中型、小型、微型
（B） 层次模型、网状模型、关系模型
（C） 线性、非线性、混合型
（D） E-R模型、扩充的E-R模型、谓词模型
答案 B
第40题 设有关系A、B、C，如图所示：
则由关系A和B得到关系C的运算是
（A） 并
（B） 交
（C） 差
（D） 投影
答案 C
解析 考查差运算的运算规则，需要初步举一反三的能力。
知识点
① 关系的直观形式是一张二维表，给定关系A、B、C的内容是：
关系二维表的每一行称为元组、每一列称为属性。这些关系记作
A（X，Y，Z）
B（X，Y，Z）
C（X，Y，Z）
其中X、Y、Z为属性名。
② 执行A与B的差运算，记作A-B，就是逐一检查B的元组，凡在A中存在者，一律删除，最终剩下的元组构成一个新关系，就是A-B的结果，读作A减B。具体步骤为：先查元组（e，4，6），在A中不存在，不管它；再查元组（ c，3，2），在A中存在，删除它；后查元组（a，1，3），在A中存在，删除它；最终剩下元组（ b，2，2）和（d，4，6）组成一个新关系，就是A-B的结果，刚好是C，因此C是A与B的差。
③ 关系是元组的集合，关系的差运算就是集合的差运算。
孪生题 设有关系A、B、C，如图所示：
则由关系B和A得到关系C的运算是
（A） ……
（B） 差
（C） ……
（D） ……
分析如下：
执行B与A的差运算，记作B-A，就是逐一检查A的元组，凡在B中存在者，一律删除，最终剩下的元组构成一个新关系，就是B-A的结果，读作B减A。具体步骤为：先查元组（a，1，3），在B中存在，删除它；再查元组（ b，2，2），在B中不存在，不管它；再查元组（c，3，2），在B中存在，删除它；后查元组（d，4，6），在B中不存在，不管它；最终只剩下一个元组（ e，4，6）组成一个新关系，就是B-A的结果，刚好是C，因此C是B与A的差。
第41题 下列哪一个序列不是堆
（A） (93，90，88，89，84，80，71，59，50，44)
（B） (93，90，88，91，84，80，71，59，50，44)
（C） (93，90，88，89，84，85，71，59，50，44)
（D） (93，90，88，89，84，85，71，76，50，44)
答案 B
知识点
① 预备概念：完全二叉树和满二叉树是具有一定特点的二叉树，下图给出三层(根结点在第1层)的满二叉树以及所有可能的完全二叉树，并在每个结点的下方附着编号，编号从1开始，自上而下、自左而右依次编排：
满二叉树的特点是：各层结点数均达到其最大值，第k层结点数最大值为2k-1。完全二叉树的特点是：与满二叉树相比，只在最底层自右而左依次缺失若干结点。满二叉树也算作完全二叉树。试画出四层的满二叉树及其所有可能的完全二叉树。这里为了强调完全二叉树和满二叉树的结构特点，忽略了结点中的数据，结点中的数据要根据具体问题的需要确定。
② 完全二叉树使得堆的判别非常直观简单。
例如：选项A序列的判别，将选项A的序列
(93，90，88，89，84，80，71，59，50，44)
自上而下、自左而右填充完全二叉树，得到
编号6至10的结点均没有孩子，叫做叶结点。编号1至5的结点均有孩子，叫做非叶结点，其中编号为1的结点，也叫根结点。
若每一个非叶结点的值均大于其左、右孩子的值，则该序列是堆，也叫最大堆，因为根结点的值一定是序列的最大值；若每一个非叶结点的值均小于其左、右孩子的值，则该序列也是堆，也叫最小堆，因为根结点的值一定是序列的最小值。
下面依次考查每一个非叶结点，即编号1至5的结点，因为93>90且93>88，90>89且90>84，88>80且88>71，89>59且89>50，84>44，所以该序列是最大堆，93一定是序列的最大值。
③ 选项B序列的判别，将选项B的序列
(93，90，88，91，84，80，71，59，50，44)
自上而下、自左而右填充完全二叉树，得到
对于本序列，只考查编号为2的结点就可做出判断，因为90<91且90>84，也就是说，2号结点的值既不同时大于其左、右孩子的值，也不同时小于其左、右孩子的值，所以不符合堆的定义，既非最大堆，也非最小堆，即该序列不是堆。
④ 选项C序列的判别，将选项C的序列
(93，90，88，89，84，85，71，59，50，44)
自上而下、自左而右填充完全二叉树，得到
下面依次考查每一个非叶结点，即编号1至5的结点，因为93>90且93>88，90>89且90>84，88>85且88>71，89>59且89>50，84>44，所以该序列是最大堆，93一定是序列的最大值。
⑤ 选项D序列的判别，将选项D的序列
(93，90，88，89，84，85，71，76，50，44)
自上而下、自左而右填充完全二叉树，得到
下面依次考查每一个非叶结点，即编号1至5的结点，因为93>90且93>88，90>89且90>84，88>85且88>71，89>76且89>50，84>44，所以该序列是最大堆，93一定是序列的最大值。
⑥ 堆是一个形象化的术语，如果序列是堆，就能够确知序列的最大值或最小值。
⑦ 如果序列不是堆，可以把它调整成为堆，把序列调整成为最大堆的方法如下：
例如：设有非堆序列
(93，90，88，91，84，80，71，95，50，44)
将序列自上而下、自左而右填充完全二叉树，得到
对于每一个非叶结点，即编号1至5的结点，按倒序进行调整，即依次调整编号5至1的结点。对于5号结点，因84>44，故保持不变；对于4号结点，因91<95且91>50，故从左孩子值95和右孩子值50中挑选较大者95、并与4号结点值91交换位置，交换结果如下图所示：
对于3号结点，因88>80且88>71，故保持不变；对于2号结点，因90<95且90>84，故从左孩子值95和右孩子值84中挑选较大者95、并与2号结点值90交换位置，交换结果如下图所示：
至此，特别注意，因4号结点值变成了90、与8号、9号的关系也发生了变化，即90<91且90>50，故从左孩子值91和右孩子值50中挑选较大者91、并与4号结点值90交换位置，交换结果如下图所示：
对于1号结点，因93<95且93>88，故从左孩子值95和右孩子值88中挑选较大者95、并与1号结点值93交换位置，交换结果如下图所示：
至此，特别注意，虽然2号结点值变成了93、但与4号、5号的关系并未发生变化，即2号结点值仍然同时大于其左、右孩子的值，因此无需进一步交换。至此，给定序列被调整变成了最大堆，根结点的值95一定是序列的最大值。
注：在按倒序调整每一个非叶结点的过程中，存在三种情况：若当前非叶结点值同时大于左、右孩子值，则无需交换；若当前非叶结点值小于 一个或两个孩子的值，则从左、右孩子值中挑选较大者、与当前非叶结点交换位置，这种交换，可能只进行 一次、也可能引起连续多次交换的连锁反应，请结合上例仔细意会。
⑧ 把序列调整成为最小堆的方法可仿照⑦进行。
孪生题 下列哪一个序列是堆
（A） ……
（B） ……
（C） (93，90，88，89，84，85，71，59，50，44)
（D） ……
第42题 下列哪一项不是结构化程序设计的主要原则
（A） 自顶向下
（B） 逐步求精
（C） 可继承性
（D） 限制使用GOTO语句
答案 C
解析 考查结构化程序设计的原则。
知识点
① 结构化程序设计的主要原则包括自顶向下、逐步求精、模块化、限制使用GOTO语句。
孪生题 下列哪一项不是结构化程序设计的主要原则
（A） ……
（B） ……
（C） ……
（D） ……
注：凡与①中列出的原则对不上号的任何说法均可作为正确选项
第43题 在软件详细设计阶段，画出了下面的图：
这种图叫做
（A） 程序结构图
（B） 程序流程图
（C） N-S图
（D） PAD图
答案 B
解析 考查详细设计阶段所采用的主要工具。
知识点
① 软件详细设计的任务是为程序结构图中的每个模块设计算法和局部数据结构，采用特定工具表达算法和数据结构的细节，主要工具有程序流程图、N-S图、PAD图、PDL伪码。
② 程序结构图是在软件概要设计阶段采用的主要工具，描述软件系统的层次和模块结构关系。
孪生题 在软件详细设计阶段，画出了下面的图：
自己在此处随便画一张程序流程图
这种图叫做
（A） ……
（B） ……
（C） 程序流程图
（D） ……
第44题 实体-联系图(E-R图)可按一定原则转换为关系模型，多对多联系要转换为
（A） 新的关系模式
（B） 新的属性
（C） 与其它关系模式合并
（D） 新的属性组合
答案 A
解析 考查实体-联系图(E-R图)向关系模型转换的原则。
知识点
① 关系模型的逻辑结构是一组关系模式的集合。E-R图是由实体型、实体的属性和实体型之间的联系三个要素组成的。
② 将E-R图转换为关系模型就是要将实体型、实体的属性和实体型之间的联系转换为关系模式，遵循以下原则：
③ 一个实体型转换为一个关系模式，关系的属性就是实体的属性，关系的关键字就是实体的关键字。
④ 一对一(1:1)联系转换为一个新的关系模式，或与任意一端对应的关系模式合并。
⑤ 一对多(1:n)联系转换为一个新的关系模式，或与n端对应的关系模式合并。
⑥ 多对多(m:n)联系转换为一个新的关系模式。
⑦ 具有相同关键字的关系模式可以合并。
孪生题1 实体-联系图(E-R图)可按一定原则转换为关系模型，多对多联系要转换为
（A） ……
（B） 新的关系模式
（C） ……
（D） ……
孪生题2 实体-联系图(E-R图)可按一定原则转换为关系模型，实体和联系均可表示为
（A） 属性
（B） 元组
（C） 关系模式
（D） 关键字
答案 C
孪生题3 实体-联系图(E-R图)可按一定原则转换为关系模型，实体的属性转变为关系模式的
（A） 属性
（B） 元组
（C） 属性或元组
（D） 关键字
答案 A
注：在不严格的情况下，关系模式和关系可作为同义词
第45题 定义学生、课程、选课的关系模式分别是Student(S#，Sn，Ss，Sa，Colle，Dean)，其属性依次是学号、姓名、性别、年龄、所在学院、院长；Course(C#，Cname，Csc)，其属性依次是课程号、课程名、学分；SC(S#，C#，Gra)，其属性依次是学号、课程号、成绩，则下列哪一个关系模式包含对非主属性的部分函数依赖
（A） Student(S#，Sn，Ss，Sa，Colle，Dean)
（B） Course(C#，Cname，Csc)
（C） SC(S#，C#，Gra)
（D） 以上选项都不对
答案 A
解析 考查属性之间的函数依赖、完全函数依赖、部分函数依赖的概念。如果理解或记住了下面的知识点，就不难选择。该题型需要初步的举一反三的能力。
知识点
① 关系的直观形式是二维表，关系二维表中的每一行称为元组、每一列称为属性。关系模式是关系的类型，指明关系包含哪些属性；关系是对应关系模式的实例(具体值)。随着数据库系统的运行，关系的值在不断变化。设与本题三个关系模式对应的三个关系的当前状态(当前值)如下图所示：
关系模式可简单理解为关系二维表的表头，于是，可将这三个关系模式分别记作：
Student(S#，Sn，Ss，Sa，Colle，Dean)
Course(C#，Cname，Csc)
SC(S#，C#，Gra)
② 对于二级考试而言，给定的关系模式中，有一个属性或两个属性的组合能够唯一确定一个元组，这一个属性或两个属性的组合叫做码，码内的属性叫主属性，码外的属性叫非主属性。任意两个元组的码值一定不同。例如：
学生模式 Student(S#，Sn，Ss，Sa，Colle，Dean) 的码是学号S#，任意两个学生元组的学号一定不同，S#是主属性；Sn、Ss、Sa、Colle、Dean都是非主属性。
课程模式 Course(C#，Cname，Csc) 的码是课程号C#，任意两课程元组的课程号一定不同，C#是主属性；Cname、Csc都是非主属性。
选课模式 SC(S#，C#，Gra) 的码是学号与课程号的二元组合{S#，C#}，任意两个选课元组的学号与课程号的组合一定不同，S#和C#是主属性；Gra是非主属性。
③ 给定的关系模式中，若有一个属性或多个属性的组合X能够唯一确定另一个属性Y，则称X函数确定Y，或称Y函数依赖于X。
④ 若X函数确定Y，且X的任意非空真子集都不能函数确定Y，则称X完全函数确定Y，或称Y完全函数依赖于X。
⑤ 若X函数确定Y，且存在X的非空真子集也能函数确定Y，则称X部分函数确定Y，或称Y部分函数依赖于X。
⑥ 例如：Sn、Ss、Sa、Colle、Dean中的任一属性均完全依赖于单属性集{S#}，因为{S#}没有非空真子集。
属性Gra完全依赖于属性集{S#，C#}，因为{S#，C#}的非空真子集{S#}或{C#}都不能唯一确定属性Gra。
Ss、Sa、Colle、Dean中的任一属性均部分依赖于属性集{S#，Sn}，因为{S#，Sn}的真子集{S#}也能唯一确定Ss、Sa、Colle、Dean中的任一属性。
属性Dean部分依赖于属性集{Sn，Colle}，因为{Sn，Colle}的真子集{Colle}也能唯一确定属性Dean。对于本题还要清楚Sn和Colle都是非主属性。因此本题答案为A。
⑦ 唯一确定，就像数学中函数y = f(x)的x唯一确定y一样。
⑧ 码也叫关键字。
⑨ 对于此类题型，一般而言，属性最多的关系模式就是正确答案。
孪生题 定义学生、课程、选课的关系模式分别是Student(S#，Sn，Ss，Sa，Colle，Dean)，其属性依次是学号、姓名、性别、年龄、所在学院、院长；Course(C#，Cname，Csc)，其属性依次是课程号、课程名、学分；SC(S#，C#，Gra)，其属性依次是学号、课程号、成绩，则下列哪一个关系模式包含对非主属性的完全函数依赖
（A） ……
（B） Student(S#，Sn，Ss，Sa，Colle，Dean)
（C） ……
（D） ……
第46题 已知某二叉树的中序遍历序列为EDABC，后序遍历序列为EDABC，那么前序遍历序列为
（A） CBADE
（B） ABCDE
（C） ADEBC
（D） EDABC
答案 A
解析 考查二叉树的三种遍历方法，该题型需要举一反三能力。
知识点
① 所谓二叉树遍历，就是按一定次序访问每个结点一次且仅一次。
② 下图给出四棵简单二叉树的三种遍历序列：
中序遍历是按″左子树-根结点-右子树″的次序访问，也叫中根遍历。
前序遍历就是按″根结点-左子树-右子树″的次序访问，也叫前根或先根遍历。
后序遍历是按″左子树-右子树-根结点″的次序访问，也叫后根遍历。
对于Ⅰ，根结点为C，左子树为M，右子树为G。按″左子树-根结点-右子树″的次序访问，得中序序列MCG；按″根结点-左子树-右子树″的次序访问，得前序序列CMG；按″左子树-右子树-根结点″的次序访问，得后序序列MGC。
对于Ⅱ，根结点为S，左子树为A，右子树为空。按″左子树-根结点-右子树″的次序访问，得中序序列AS；按″根结点-左子树-右子树″的次序访问，得前序序列SA；按″左子树-右子树-根结点″的次序访问，得后序序列AS。
对于Ⅲ，根结点为C，左子树为空，右子树为D。按″左子树-根结点-右子树″的次序访问，得中序序列CD；按″根结点-左子树-右子树″的次序访问，得前序序列CD；按″左子树-右子树-根结点″的次序访问，得后序序列DC。
对于Ⅳ，只有一个根结点M，左、右子树均为空，无论采用哪种遍历方法，所得序列都是M。
③ 规定：对于空二叉树，无论哪种遍历方法，所得序列都是空序列。
④ 任意复杂的二叉树均可遍历，方法就是″化繁为简、分而治之″，即分解为根结点、左子树、右子树三个部分。左子树、右子树的遍历更为简单，并继续分解，直到左子树、右子树的序列已知，再用左、右子树的已知序列与根结点逐级拼接、逐级返回。
⑤ 下面用″化繁为简、分而治之″的思想，重新分析四种简单二叉树的遍历：
对于Ⅳ，只有一个根结点M，左、右子树均为空二叉树，按″左子树-根结点-右子树″的次序访问，得到中序序列(其中的+表示把两个序列拼接起来)
左子树中序序列 + 根结点 + 右子树中序序列
即
空序列 + M + 空序列
即
M
按″根结点-左子树-右子树″的次序访问，得到前序序列
根结点 + 左子树前序序列 + 右子树前序序列
即
M + 空序列 + 空序列
即
M
按″左子树-右子树-根结点″的次序访问，得到后序序列
左子树后序序列 + 右子树后序序列 + 根结点
即
空序列 + 空序列 + M
即
M
对于Ⅲ，根结点为C，左子树为空二叉树，右子树为D，按″左子树-根结点-右子树″的次序访问，得到中序序列
左子树中序序列 + 根结点 + 右子树中序序列
即
空序列 + C + D
即
CD
按″根结点-左子树-右子树″的次序访问，得到前序序列
根结点 + 左子树前序序列 + 右子树前序序列
即
C + 空序列 + D
即
CD
按″左子树-右子树-根结点″的次序访问，得到后序序列
左子树后序序列 + 右子树后序序列 + 根结点
即
空序列 + D + C
即
DC
对于Ⅱ，根结点为S，左子树为A，右子树为空二叉树，按″左子树-根结点-右子树″的次序访问，得到中序序列
左子树中序序列 + 根结点 + 右子树中序序列
即
A + S + 空序列
即
AS
按″根结点-左子树-右子树″的次序访问，得到前序序列
根结点 + 左子树前序序列 + 右子树前序序列
即
S + A + 空序列
即
SA
按″左子树-右子树-根结点″的次序访问，得到后序序列
左子树后序序列 + 右子树后序序列 + 根结点
即
A + 空序列 + S
即
AS
对于Ⅰ，根结点为C，左子树为M，右子树为G，按″左子树-根结点-右子树″的次序访问，得到中序序列
左子树中序序列 + 根结点 + 右子树中序序列
即
M + C + G
即
MCG
按″根结点-左子树-右子树″的次序访问，得到前序序列
根结点 + 左子树前序序列 + 右子树前序序列
即
C + M + G
即
CMG
按″左子树-右子树-根结点″的次序访问，得到后序序列
左子树后序序列 + 右子树后序序列 + 根结点
即
M + G + C
即
MGC
⑥ 下面用″化繁为简、分而治之″的思想，遍历下面的二叉树：
按″左子树-根结点-右子树″的次序访问，得到中序序列
左子树中序序列 + 根结点 + 右子树中序序列
即
即
即
AS + R + MCG + X + D
即
ASRMCGXD
按″根结点-左子树-右子树″的次序访问，得到前序序列
根结点 + 左子树前序序列 + 右子树前序序列
即
即
即
R + SA + X + CMG + D
即
RSAXCMGD
按″左子树-右子树-根结点″的次序访问，得到后序序列
左子树后序序列 + 右子树后序序列 + 根结点
即
即
即
AS + MGC + D + X + R
即
ASMGCDXR
⑦ 已知中序序列和后序序列可以确定前序序列；已知中序序列和前序序列可以确定后序序列。
⑧ 本题解答：
将后序序列
EDABC
与
左子树后序序列 + 右子树后序序列 + 根结点
比对，可知根结点是C
将中序序列
EDABC
与
左子树中序序列 + 根结点 + 右子树中序序列
比对，可知左子树中序序列是EDAB，右子树为空。既然右子树为空，再结合后序序列EDABC，进而可知，左子树后序序列是EDAB。
同理可知
左子树根结点是B。左子树的左子树中序序列是EDA，左子树的右子树为空，左子树的左子树后序序列是EDA。
左子树的左子树根结点是A。左子树的左子树的左子树中序序列是ED，左子树的左子树的右子树为空，左子树的左子树的左子树后序序列是ED。
于是，可画出该树，如下图所示：
再对该树进行前序遍历，可得前序序列为CBADE。
⑨ 推论1：若含有n个结点的二叉树的中序序列和后序序列相同，则这种树的形态如下图所示：
叫做左单分支树，深度为n。
⑩ 推论2：若含有n个结点的二叉树的中序序列和前序序列相同，则这种树的形态如下图所示：
叫做右单分支树，深度为n。
孪生题1 已知某二叉树的中序遍历序列为EDABC，前序遍历序列为EDABC，那么后序遍历序列为
（A） ……
（B） CBADE
（C） ……
（D） ……
解：根据推论2，此二叉树的形态如下图所示：
再对该树进行后序遍历，可得后序序列为CBADE。
孪生题2 给定二叉树，含有m个不同的结点，且中序序列和前序序列相同，那么该树的深度为(根结点为第1层)
（A） ……
（B） m
（C） ……
（D） ……
解：根据推论2可知，其深度为m。
孪生题3 已知某二叉树的中序遍历序列为DCBAGEF，后序遍历序列为DCBGFEA，那么该树的深度为(根结点为第1层)
（A） ……
（B） 4
（C） ……
（D） ……
解法1：
将后序序列
DCBGFEA
与
左子树后序序列 + 右子树后序序列 + 根结点
比对，可知根结点是A
将中序序列
DCBAGEF
与
左子树中序序列 + 根结点 + 右子树中序序列
比对，可知左子树中序序列是DCB，右子树中序序列是GEF。再结合后序序列DCBGFEA，进而可知，左子树后序序列是DCB，右子树后序序列是GFE。
将左子树的后序序列
DCB
与
左子树后序序列 + 右子树后序序列 + 根结点
比对，可知左子树的根结点是B
将左子树的中序序列
DCB
与
左子树中序序列 + 根结点 + 右子树中序序列
比对，可知左子树的左子树的中序序列是DC，左子树的右子树为空。再结合左子树的后序序列DCB，进而可知，左子树的左子树的后序序列是DC。
将左子树的左子树的后序序列
DC
与
左子树后序序列 + 右子树后序序列 + 根结点
比对，可知左子树的左子树的根结点是C
将左子树的左子树的中序序列
DC
与
左子树中序序列 + 根结点 + 右子树中序序列
比对，可知左子树的左子树的左子树的中序序列是D，左子树的左子树的右子树为空。
因此，可画出左子树的左子树如下图所示：
进而，可画出左子树如下图所示：
将右子树的后序序列
GFE
与
左子树后序序列 + 右子树后序序列 + 根结点
比对，可知右子树的根结点是E
将右子树的中序序列
GEF
与
左子树中序序列 + 根结点 + 右子树中序序列
比对，可知右子树的左子树的中序序列是G，右子树的右子树的中序序列是F。
因此，可画出右子树如下图所示：
综上，可画出整个二叉树如下图所示：
因此，其深度为4。
解法2：
因为中序序列为DCBAGEF，后序序列为DCBGFEA
所以中序序列分解为(DCB)A(GEF)，后序序列分解为(DCB)(GFE)A
所以中序序列分解为((DC)B())A((G)E(F))，后序序列分解为((DC)()B)((G)(F)E)A
所以中序序列分解为(((D)C())B())A((G)E(F))，后序序列分解为(((D)()C)()B)((G)(F)E)A
注：括号是分层嵌套的，分析根据是：从后序序列找出根结点(即后序序列的尾结点)，再结合对应中序序列找出左、右子树。
根据彻底分解的中序序列或后序序列，可画出整个二叉树如下图
因此，其深度为4。
孪生题4 已知某二叉树的中序遍历序列为DCBAEF，前序遍历序列为ABCDEF，那么该树的后序遍历序列为
（A） ……
（B） DCBFEA
（C） ……
（D） ……
解：
因为中序序列为DCBAEF，前序序列为ABCDEF
所以中序序列分解为(DCB)A(EF)，前序序列分解为A(BCD)(EF)
所以中序序列分解为((DC)B())A(()E(F))，前序序列分解为A(B(CD)())(E()(F))
所以中序序列分解为(((D)C())B())A(()E(F))，前序序列分解为A(B(C(D)())())(E()(F))
注：括号是分层嵌套的，分析根据是：从前序序列找出根结点(即前序序列的首结点)，再结合对应中序序列找出左、右子树。
根据彻底分解的中序序列或前序序列，可画出整个二叉树如下图
下面对这棵树进行后序遍历：
按″左子树-右子树-根结点″的次序访问，得到后序序列
左子树后序序列 + 右子树后序序列 + 根结点
即
即
即
DC + B + FE + A
即
DCBFEA
孪生题5 给定二叉树，含有26个不同的结点，且中序序列和后序序列相同，那么该树的深度为(根结点为第1层)
（A） 8
（B） 26
（C） 13
（D） 14
解：根据推论1可知，其深度为26。
第47题 下列叙述中错误的是
（A） 在循环队列中，队头指针和队尾指针不能确定队列长度
（B） 在链栈中，栈顶指针不能确定栈中元素个数
（C） 在顺序栈中，栈顶指针能够确定栈中元素个数
（D） 在链队列中，队头指针和队尾指针不能确定队列长度
答案 A
解析 考查队列长度和栈中元素个数的决定因素。
知识点
① 现实生活中的排队购票、买饭等服务活动，在程序设计中，通常采用队列来解决问题。队列的基本操作是入队操作和出队操作。若队列未满，则可执行入队操作；若队列未空，则可执行出队操作。队列逻辑结构是线性表，但只在前端删除(出队)、在后端插入(入队)，故称为先进先出、操作受限的线性表。在内存中，通常采用一维数组作为队列的存储结构。为了提高存储空间利用率，假想数组的首、尾元素也是相邻的，这就是循环队列，如下图所示：
② 对于循环队列Q(1：m)，存储结构的一维数组下标从1至m。初始空队列通常约定两种情况：front = rear = 1 或 front = rear = m。若队列非空，则规定变量front的值是队头元素的前面紧邻元素的下标，变量rear是队尾元素的下标。如下图所示：
入队操作：若队列未满，则先令rear加1(若rear加1后等于m+1则令rear为1)，再将入队新元素赋值于下标rear指示的元素，成为新队尾元素。
出队操作：若队列未空，则先令front加1(若front加1后等于m+1则令front为1)，再读取队头元素，即以front为下标的元素。
记非空队列的当前元素个数为n。若front < rear(上图状态1)，则n = rear – front；若front > rear(状态2)，则n = m – (front – rear)。m是数组总容量。
例如：对于上图的状态1(m = 12时)：n = rear – front = 10 – 3 = 7
对于上图的状态2：n = m – (front – rear) = 12 – (8 – 3) = 7
经过一系列的出队、入队操作后，若front = rear，则表明队列空或队列满。为了区分这两种状态，需要引入标志变量s，定义如下：
在队列操作过程中，要适时设置s的值。当检测到s=0时，表明队空；当检测到s=1且front = rear时，表明队满，这时循环队列Q(1：m)的元素个数为m。
可见，在循环队列中，队头指针和队尾指针能够确定队列长度。
③ 设有一端封闭竖直放置的圆柱形塑料筒，开口向上，直径刚好允许放进乒乓球，如下图所示：
显然，乒乓球呈现线性结构，用数据结构的话说，就是线性表。由于筒的一端封闭，乒乓球只能从一端进出，即按照″后进先出″的规则操作，用数据结构的话说，就是只能在线性表的一端，按照″后进先出″的规则插入、删除元素，这种操作受限的线性表叫做栈。栈在计算机技术领域中应用十分广泛，例如：在C语言中，函数的调用及返回(后调用的、先返回)的背后就有一个栈在工作。
栈的逻辑结构是操作受限的线性表，其存储结构常用一维数组实现，叫做顺序栈。
例如：设栈的存储空间是一维数组S(1：30)，可把栈顶指针top的初值设置为31，这就是栈开始工作之前的初始状态，或叫做空栈，即栈中尚无元素。栈在工作过程中，依靠栈顶指针top进行元素的插入(进栈)或删除(出栈)，栈顶指针top总是指向当前的栈顶元素。进栈时， 先执行top减1，再将新元素赋值于S[top]；出栈时，先将当前栈顶元素S[top]取出，再执行top加1。当前栈中元素个数为31-top。如下图
也可把栈顶指针top的初值设置为0。进栈时，执行top加1；出栈时，执行top减1，其它操作与上面情况相同。当前栈中元素个数为top。如下图所示：
综上所述，设栈的存储空间为数组S(1：n)，可把栈顶指针top的初值设置为n+1，即初始状态top = n+1；也可设置为0，即初始状态top = 0。若初始状态为top = n+1，则当前栈中元素个数为n+1-top；若初始状态为top = 0，则当前栈中元素个数为top。
可见，在顺序栈中，栈顶指针能够确定栈中元素个数。
④ 循环队列和顺序栈都以一维数组为存储结构，队头指针、队尾指针和栈顶指针都是数组下标，且数组元素是彼此物理邻接的，因此队头和队尾指针能够确定队列长度，栈顶指针能够确定栈中元素个数。
⑤ 队列也可采用链表作为存储结构，叫做链队列，如下图所示：
队头指针front指向队头结点，队尾指针rear指向队尾结点。入队时，将新结点链接至rear所指队尾结点之后，并用rear指向新的队尾结点。出队时，将front所指队头结点摘除，令front指向它后面的结点(成为新的队头)。因此，在出队、入队交错操作过程中，队头指针和队尾指针都在不断变化。
由于链表结点都是动态申请来的，front和rear的值具有动态随机性，因此，仅凭front和rear的值无法计算确定队列长度，只能另行设置专门的变量来跟踪记录队列长度。
可见，在链队列中，队头指针和队尾指针不能确定队列长度。
⑥ 栈也可采用链表作为存储结构，叫做链栈，如下图所示：
栈顶指针top指向栈顶结点，表尾的空指针表示栈底，是固定不变的，也叫栈底指针。入栈时，将新结点链接至top所指栈顶结点之前，并用top指向新的栈顶结点。出栈时，摘除top所指栈顶结点，令top指向它后面的结点(成为新的栈顶结点)。因此，在出栈、入栈交错操作过程中，栈顶指针不断变化，栈底指针固定不变。
与链队列同理，仅凭栈顶指针top的值无法计算确定栈中元素个数，只能另行设置专门的变量来跟踪记录栈中元素个数。
可见，在链栈中，栈顶指针不能确定栈中元素个数。
孪生题1 下列叙述中正确的是
（A） ……
（B） 在循环队列中，队头指针和队尾指针能够确定队列长度
（C） ……
（D） ……
孪生题2 下列叙述中正确的是
（A） 在链队列中，队头指针动态变化、队尾指针固定不变
（B） 在链队列中，队头指针和队尾指针都是动态变化的
（C） 在链栈中，栈底指针动态变化、栈顶指针固定不变
（D） 在链栈中，栈顶指针和栈底指针都是动态变化的
答案 B （参见知识点⑤⑥的叙述）
第48题 给定某软件系统的结构图如下：
那么，该结构图的最大扇入数为
（A） 1
（B） 2
（C） 3
（D） 4
答案 B
解析 考查结构图的扇入数、扇出数的概念。
知识点
① 结构图是表达软件模块结构的图形工具，反映模块之间的层次调用关系。
② 模块的扇出数是指被该模块直接调用的下层模块数目。例如：″系统主控″模块的扇出数为3，″功能1″模块的扇出数为2，″功能2″模块的扇出数为1，″功能3″模块的的扇出数为2。因此，该结构图的最大扇出数为3。
③ 模块的扇入数是指直接调用该模块的上层模块数目。例如：″功能1″模块的扇入数为1，″功能2″模块的扇入数为1，″功能3″模块的扇入数为1，″功能1.1″模块的扇入数为1，″功能1.2″模块的扇入数为2，″功能3.1″模块的扇入数为1，″功能3.2″模块的扇入数为1。因此，该结构图的最大扇入数为2。
④ 结构图的深度是结构图的层次数，在一定程度上反映软件结构的规模和复杂程度。
孪生题1 给定某软件系统的结构图如下：
那么，该结构图的最大扇出数为
（A） ……
（B） 3
（C） ……
（D） ……
孪生题2 给定某软件系统的结构图如下：
那么，该结构图的深度是
（A） ……
（B） 3
（C） ……
（D） ……
第49题 若将非负整数集定义为类T，则下列哪一个是类T的实例
（A） 6.25
（B） 625
（C） -625
（D） 6.25E-3
答案 B
解析 考查类的概念和实例的概念。
知识点
① 在面向对象程序设计中，类是类型概念的推广，类要么是自定义值的集合(一个或多个)，要么是自定义值的集合(一个或多个)及相关操作集合的封装。实例是值概念的推广，一个实例要么是一个自定义值，要么是自定义值及相关操作实现代码的封装体。
② 在C语言中，有char类型、int类型，′a′、′B′都是char类型的值，256、-379都是int类型的值。
③ 在面向对象程序设计中，例如本题，可将非负整数集定义为一个类，不妨命名为T，则625、0、23都是类T的实例。简而言之，类就是一种″型″，实例就是″型″的值。
④ 还可以将负整数集定义为一个类，不妨命名为R，则-625、-23都是类R的实例。
⑤ 为了应付这种题型，可以把类理解为类型，把实例理解为类型的具体值。
孪生题1 若将负整数集定义为类R，则下列哪一个是类R的实例
（A） 100
（B） -100
（C） 100.6
（D） -100.6
答案 B
孪生题2 若将整数集定义为类S，则下列哪一个是类S的实例
（A） 9.38
（B） 938
（C） -625.3
（D） 6.25E-4
答案 B
第50题 数据库系统由外模式、模式、内模式三级构成，模式由下列哪种语言来刻画
（A） 数据操纵语言
（B） 数据控制语言
（C） 数据定义语言
（D） 数据存储描述语言
答案 C
知识点
① 数据是描述事物的符号记录。
② 数据库是长期储存于计算机系统中的有组织、可共享的大量数据的集合。
③ 数据库管理系统是介于用户和操作系统之间的一层数据管理软件。它和操作系统一样也是计算机的基础软件，是大型复杂的软件系统。
④ 数据库管理系统的功能主要包括
- 数据定义
- 数据组织、存储和管理
- 数据操纵
- 数据库的事务管理和运行管理
- 数据库的建立和维护
⑤ 数据库管理系统提供多种语言来实现它的各种功能，语言包括：
- 数据定义语言，对数据库的模式和外模式进行定义。
- 数据操纵语言，对数据库进行基本操作，如查询、插入、删除、修改等。
- 数据控制语言，对数据库的安全性、完整性、并发性进行控制。
- 数据存储描述语言，对数据库数据进行分类组织、存储和管理。
⑥ 模式也叫逻辑模式或概念模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。一个数据库只有一个模式。数据库管理系统提供模式数据定义语言(模式DDL)来定义模式。
⑦ 外模式也叫子模式或用户模式，是数据库用户(应用程序员或最终用户)能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。一个数据库可以有多个外模式。数据库管理系统提供外模式数据定义语言(外模式DDL)来定义外模式。
⑧ 数据定义语言，简称DDL(Data Definition Language)；数据操纵语言，简称DML(Data Manipulation Language)；数据控制语言，简称DCL(Data Control Language)；数据存储描述语言，简称DSDL(Data Storage Description Language)。
孪生题1 数据库的模式(或逻辑模式或概念模式)，由下列哪种语言来刻画
（A） 数据操纵语言
（B） 数据控制语言
（C） 数据定义语言
（D） 数据存储描述语言
答案 C
孪生题2 数据库的外模式(或子模式或用户模式)，由下列哪种语言来刻画
（A） 数据操纵语言
（B） 数据控制语言
（C） 数据定义语言
（D） 数据存储描述语言
答案 C
第51题 设有关系A、B、C，如图所示：
则由关系A和B得到关系C的运算是
（A） 并
（B） 交
（C） 差
（D） 投影
答案 B
解析 考查交运算的运算规则，该题型需要初步举一反三。
知识点
① 关系的直观形式是一张二维表，给定关系A、B、C的内容是：
关系二维表的每一行称为元组、每一列称为属性。这些关系记作
A（X，Y，Z）
B（X，Y，Z）
C（X，Y，Z）
其中X、Y、Z为属性名。
② A与B的交运算，记作A∩B，读作A交B，A∩B的结果就是由同时属于A与B的元组构成的新关系。观察可知，元组（a，1，3）和元组（ c，3，2）同时属于A与B，它们组成的新关系就是A∩B的结果，刚好是C，因此C等于A∩B。
③ 关系是元组的集合，关系的交运算就是集合的交运算。
孪生题 设有关系A、B、C，如图所示：
则由关系A和B得到关系C的运算是
（A） ……
（B） 交
（C） ……
（D） ……
第52题 给定数据结构B = (D，R)，其中，数据结点集D = { a，b，c，d，e，f }，关系集R由下列选项给出，则下列哪一项是线性结构
（A） R = { (e，d)，(c，d)，(c，b)，(d，c)，(e，f) }
（B） R = { (a，b)，(b，c)，(c，d)，(d，e)，(f，e) }
（C） R = { (a，b)，(b，c)，(d，c)，(d，e)，(e，f) }
（D） R = { (a，b)，(b，f)，(f，e)，(d，c)，(e，d) }
答案 D
知识点
① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构，二叉树是典型的非线性结构，如下图所示：
其中，圆圈表示数据结点，有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点，没有后继的结点叫做终端结点或叶结点。在上图的线性表中，B是根结点，E是终端结点，X的前趋是U，X的后继是K。在上图的二叉树中，R是根结点，A、D、M、G都是叶结点，X的前趋是R，X的后继是C和D，结点C和D之间没有关系。任意两个结点之间要么没有关系，要么是前趋后继关系。
若一个数据结构只有一个根结点，其任一结点至多有一个前趋、至多有一个后继，则该数据结构称为线性结构。如果一个数据结构不是线性结构，就称为非线性结构。
② 如上图，用结点和有向线段的图表示的数据结构，称为逻辑结构。
逻辑结构包含两方面信息：数据结点的集合和有向线段的集合，有向线段的集合也叫前趋后继关系的集合，简称关系集，因此，一个数据结构可记作 B = (D，R)，其中，D为数据结点集，R为关系集。
于是，上面的线性表可记作
B1 = (D1，R1)
D1 = { B，D，U，X，K，N，E }
R1 = { (B，D)，(D，U)，(U，X)，(X，K)，(K，N)，(N，E) }
上面的二叉树可记作
B2 = (D2，R2)
D2 = { R，S，X，A，C，D，M，G }
R2 = { (R，S)，(R，X)，(S，A)，(X，C)，(X，D)，(C，M) ，(C，G)}
③ 要解答本题，先根据给定的结点集和关系集画出逻辑结构，再根据线性结构和非线性结构的定义判别。本题四个选项所对应的逻辑结构如下图所示：
参照这些直观的逻辑结构图，容易知道D是正确选项。例如：A有两个根结点a和e，B有两个根结点a和f，C有两个根结点a和d，仅凭这一点，就可排除A、B、C三个选项。
另外，A的结点e有两个后继，B的结点e有两个前趋，C的结点d有两个后继、C的结点c有两个前趋，据此，也可排除A、B、C三个选项。
④ 要能够完成逻辑结构图和符号表示B = (D，R)之间的相互转换。
孪生题 给定数据结构B = (D，R)，其中，数据结点集D = { 0，2，4，6，8 }，关系集R由下列选项给出，则下列哪一项是线性结构
（A） R = { (0，2)，(4，6)，(8，0) }
（B） R = { (0，4)，(6，0)，(4，2)，(8，6) }
（C） R = { (0，4)，(2，6)，(4，8) }
（D） R = { (0，2)，(2，4)，(6，8) }
解：先根据给定的结点集和关系集画出逻辑结构，再根据线性结构和非线性结构的定义判别。本题四个选项所对应的逻辑结构如下图：
参照这些直观的逻辑结构图，容易知道B是正确选项。例如：A有两个根结点4和8，C有两个根结点2和0，D有两个根结点6和0，据此，可以排除A、C、D三个选项。
第53题 在软件生命周期的各阶段都会产生相关文档，在软件设计阶段产生的文档是
（A） 软件测试计划
（B） 概要设计说明书
（C） 软件需求规格说明书
（D） 数据字典和数据流图
答案 B
解析 考查软件生命周期的各阶段都会产生哪些主要文档。
知识点
① 软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。在软件生命周期的各阶段都会产生相关文档，用以固定各阶段的工作成果。软件生命周期的主要阶段包括需求分析、概要设计、详细设计、测试。
② 在需求分析阶段产生的最重要文档是软件需求规格说明书。
③ 在概要设计阶段产生的最重要文档是概要设计说明书。
④ 在详细设计阶段产生的最重要文档是详细设计说明书。
⑤ 在测试阶段产生的最重要文档是软件测试计划。
⑥ 概要设计和详细设计统称软件设计阶段。
⑦ 数据字典和数据流图是需求分析阶段用到的主要工具。
⑧ 软件测试包括单元测试、集成测试、确认测试、系统测试，因此就有相应的软件单元测试计划、集成测试计划、确认测试计划、系统测试计划。
注：以上要点务必牢记！
孪生题 在软件生命周期的各阶段都会产生相关文档，在软件设计阶段产生的文档是
（A） ……
（B） 详细设计说明书
（C） ……
（D） ……
第54题 软件工程的三要素包括
（A） 方法、工具、过程
（B） 算法、流程图、程序
（C） 管理、技术、资金
（D） 管理、技术、人才
答案 A
知识点
① 软件工程的三要素：方法、工具、过程。
② 方法指完成软件开发项目的技术手段。
③ 工具指辅助软件的开发、管理、文档生成的各种工具。
④ 过程指完成各项开发任务的工作步骤。
注：以上要点务必牢记！
孪生题1 下列哪一项是软件工程的要素
（A） ……
（B） 过程
（C） ……
（D） ……
孪生题2 下列哪一项不是软件工程的要素
（A） 方法
（B） 算法
（C） 工具
（D） 过程
答案 B
第55题 设有关系A、B、C，如图所示：
则由关系A和B得到关系C的运算是
（A） 并
（B） 交
（C） 差
（D） 投影
答案 A
解析 考查并运算的运算规则，该题型需要初步举一反三。
知识点
① 关系的直观形式是一张二维表，给定关系A、B、C的内容是：
关系二维表的每一行称为元组、每一列称为属性。这些关系记作
A（X，Y，Z）
B（X，Y，Z）
C（X，Y，Z）
其中X、Y、Z为属性名。
② A与B的并运算，记作A∪B，读作A并B，A∪B的结果就是由属于A或属于B的元组构成的新关系。观察可知，C恰好等于A∪B。
③ 关系是元组的集合，关系的并运算就是集合的并运算。
孪生题 设有关系A、B、C，如图所示：
则由关系A和B得到关系C的运算是
（A） ……
（B） 并
（C） ……
（D） ……
第56题 关于链式存储结构，下列叙述中错误的是
（A）结点含有两个指针域的链式存储结构可能是线性结构，也可能是非线性结构
（B）在线性表的链式存储结构中，每个结点必须含有指向前趋和后继的两个指针
（C）在线性表的链式存储结构中，每个结点可以含有两个指针
（D）在线性表的链式存储结构中，叶结点的指针可空、也可不空
答案 B
解析 考查链式存储结构的特点。
知识点
① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构，二叉树是典型的非线性结构，如下图所示：
其中，圆圈表示数据结点，有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点，没有后继的结点叫做终端结点或叶结点。在上图的线性表中，B是根结点，E是终端结点，X的前趋是U，X的后继是K。在上图的二叉树中，R是根结点，A、D、M、G都是叶结点，X的前趋是R，X的后继是C和D，结点C和D之间没有关系。任意两个结点之间要么没有关系，要么是前趋后继关系。
若一个数据结构只有一个根结点，其任一结点至多有一个前趋、至多有一个后继，则该数据结构称为线性结构。如果一个数据结构不是线性结构，就称为非线性结构。
② 如上图所示，用结点和有向线段的图所表示的数据结构，称为逻辑结构。逻辑结构在机器内存中的表示形式，称为存储结构。一种逻辑结构可有多种不同的存储结构。
在C语言中，若用结构体的数据域存储结点值，用结构体的指针域表示结点间的前趋后继关系，则这种存储结构叫做链式存储结构。下图给出线性表的三种常见链式存储结构：单向链表、单向循环链表和双向链表。下图还给出二叉树的一种常见链式存储结构，即二叉链表。在其它语言中，也有类似结构体的类型，用于实现链式存储结构。
在单向链表中，每个结点含有一个指针域且指向其后继结点，叶结点的指针域为空。另设一个根指针指向根结点，通常叫做头指针。
在单向循环链表中，每个结点含有一个指针域且指向其后继结点，叶结点的指针域不再空闲，而是指向根结点，从而形成一个环。在某些情况下，会更方便。
在双向链表中，每个结点含有两个指针域，一个指向其前趋结点，一个指向其后继结点，叶结点的后继指针域为空，根结点的前趋指针域为空。
在二叉树的二叉链表中，每个结点含有两个指针域，一个指向左孩子结点，一个指向右孩子结点，叶结点的两个指针域为空。另设一个根指针指向根结点。
③ 双向链表和二叉链表的结点均含有两个指针，前者属线性结构，后者属非线性结构，所以选项A是正确的。
④ 双向链表的结点含有两个指针，所以选项C是正确的。
⑤ 在单向链表中，叶结点的指针域为空；在单向循环链表中，叶结点的指针域非空，所以选项D是正确的。
⑥ 在单向链表和单向循环链表中，结点均含一个指针，所以选项B是错误的。
注：前趋后继关系，也可叫做前件后件关系。
孪生题1 关于链式存储结构，下列叙述中错误的是
（A）若两个结点的同一指针域的值相等，则该结构一定是线性结构
（B）若有两个结点的同一指针域的值相等，则该结构一定是非线性结构
（C）结点含有两个指针域的链式存储结构可能是线性结构，也可能是非线性结构
（D） 在线性表的链式存储结构中，每个结点可以含有两个指针
答案 A
解：若有两个结点的同一指针域的值相等，则表明这两个结点指向同一结点，也说明被指结点具有两个前趋，不符合线性结构的定义，因此，一定是非线性结构，即选项A错误，选项B正确。
双向链表和二叉链表的结点均含有两个指针，前者属线性结构，后者属非线性结构，所以选项C是正确的。
双向链表的结点含有两个指针，所以选项D是正确的。
孪生题2 关于链式存储结构，下列叙述中正确的是
（A） ……
（B） ……
（C） 结点含有两个指针域的链式存储结构可能是线性结构，也可能是非线性结构
（D） ……
第57题 设有一个栈和一个队列，初始状态均为空。先将元素AKUXB依次进栈，再连续出栈4次(每次出栈的元素立即入队)，最后连续出队3次，则出队元素依次为
（A） BXU
（B） UXB
（C） AKU
（D） UKA
答案 A
解析 考查栈和队列的出入规则。
知识点
① 现实生活中的排队购票、买饭等服务活动，在程序设计中，通常采用队列来解决问题。队列的基本操作是入队操作和出队操作。若队列未满，则可执行入队操作；若队列未空，则可执行出队操作。队列逻辑结构是线性表，但只在前端删除(出队)、在后端插入(入队)，故称为″先进先出″的线性表。在内存中，通常采用一维数组作为队列的存储结构。为了提高存储空间利用率，假想数组的首、尾元素也是相邻的，这就是循环队列，如下图所示：
② 对于循环队列Q(1：m)，存储结构的一维数组下标从1至m。初始空队列通常约定两种情况：front = rear = 1 或 front = rear = m。若队列非空，则规定变量front的值是队头元素的前面紧邻元素的下标，变量rear是队尾元素的下标。如下图所示：
入队操作：若队列未满，则先令rear加1(若rear加1后等于m+1则令rear为1)，再将入队新元素赋值于下标rear指示的元素，成为新队尾元素。
出队操作：若队列未空，则先令front加1(若front加1后等于m+1则令front为1)，再读取队头元素，即以front为下标的元素。
记非空队列的当前元素个数为n。若front < rear(上图状态1)，则n = rear – front；若front > rear(状态2)，则n = m – (front – rear)。m是数组总容量。
例如：对于上图的状态1(m = 12时)：n = rear – front = 10 – 3 = 7
对于上图的状态2：n = m – (front – rear) = 12 – (8 – 3) = 7
经过一系列的出队、入队操作后，若front = rear，则表明队列空或队列满。为了区分这两种状态，需要引入标志变量s，定义如下：
在队列操作过程中，要适时设置s的值。当检测到s=0时，表明队空；当检测到s=1且front = rear时，表明队满，这时循环队列Q(1：m)的元素个数为m。
可见，在循环队列中，队头指针和队尾指针能够确定队列长度。
③ 设有一端封闭竖直放置的圆柱形塑料筒，开口向上，直径刚好允许放进乒乓球，如下图所示：
显然，乒乓球呈现线性结构，用数据结构的话说，就是线性表。由于筒的一端封闭，乒乓球只能从一端进出，即按照″后进先出″的规则操作，用数据结构的话说，就是只能在线性表的一端，按照″后进先出″的规则插入、删除元素，这种操作受限的线性表叫做栈。栈在计算机技术领域中应用十分广泛，例如：在C语言中，函数的调用及返回(后调用的、先返回)的背后就有一个栈在工作。
栈的逻辑结构是操作受限的线性表，其存储结构常用一维数组实现，叫做顺序栈。
例如：设栈的存储空间是一维数组S(1：30)，可把栈顶指针top的初值设置为31，这就是栈开始工作之前的初始状态，或叫做空栈，即栈中尚无元素。栈在工作过程中，依靠栈顶指针top进行元素的插入(进栈)或删除(出栈)，栈顶指针top总是指向当前的栈顶元素。进栈时， 先执行top减1，再将新元素赋值于S[top]；出栈时，先将当前栈顶元素S[top]取出，再执行top加1。当前栈中元素个数为31-top。如下图
也可把栈顶指针top的初值设置为0。进栈时，执行top加1；出栈时，执行top减1，其它操作与上面情况相同。当前栈中元素个数为top。如下图所示：
综上所述，设栈的存储空间为数组S(1：n)，可把栈顶指针top的初值设置为n+1，即初始状态top = n+1；也可设置为0，即初始状态top = 0。若初始状态为top = n+1，则当前栈中元素个数为n+1-top；若初始状态为top = 0，则当前栈中元素个数为top。
可见，在顺序栈中，栈顶指针能够确定栈中元素个数。
④ 循环队列和顺序栈都以一维数组为存储结构，队头指针、队尾指针和栈顶指针都是数组下标，且数组元素是彼此物理邻接的，因此队头和队尾指针能够确定队列长度，栈顶指针能够确定栈中元素个数。
⑤ 本题解答如下图所示(栈规则是后进先出，队列规则是先进先出)
Ⅰ 初始状态，栈和队列均为空
Ⅱ 将元素AKUXB依次进栈后，队列状态仍为空(见图Ⅰ)
Ⅲ 连续出栈4次(每次出栈的元素立即入队)后
Ⅳ 连续出队3次后，栈状态未变(见图Ⅲ)，出队元素依次为BXU
为便于初学者理解，图Ⅳ中未标出已出队的元素BXU，其实，它们仍然存在直到被将来的新入队元素覆盖。出队是逻辑上的出队，表现为front指针的移动。出栈也是逻辑上的出栈，表现为top指针的移动。
⑥ 栈的典型应用
- 编译技术中的表达式求值
- 在程序设计中，过程(函数、子程序)的调用与返回的实现
- 在程序设计中，递归的实现
⑦ 队列的典型应用
- 银行信息系统的排队服务
- 医院信息系统的排队候诊
- 操作系统中的作业调度
孪生题1 设有一个栈和一个队列，初始状态均为空。先将元素edcba依次进栈，再连续出栈3次(每次出栈的元素立即入队)，最后连续出队2次，则出队元素依次为
（A） ……
（B） ab
（C） ……
（D） ……
孪生题2 下列应用中，与栈有关的是
（A） 在程序设计中，过程(函数、子程序)的调用与返回的实现
（B） 医院信息系统的排队候诊
（C） 操作系统中的作业调度
（D） 程序执行中的循环控制
答案 A
孪生题3 下列应用中，与队列有关的是
（A） 在程序设计中，过程(函数、子程序)的调用与返回的实现
（B） 编译技术中的表达式求值
（C） 操作系统中的作业调度
（D） 程序执行中的循环控制
答案 C
第58题 需求分析属于下列软件生命周期的哪个阶段
（A） 维护阶段
（B） 定义阶段
（C） 开发阶段
（D） 以上都不对
答案 B
解析 考查软件生命周期各阶段的主要工作。
知识点
① 软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件生命周期分为三个阶段，如下图所示(牢记此图)：
孪生题 在软件生命周期的定义阶段，有两项主要工作，其中之一是
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
第59题 下列哪一项属于非线性结构
（A） 单向链表
（B） 循环链表
（C） 二叉链表
（D） 顺序栈
答案 C
知识点
① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构，二叉树是典型的非线性结构，如下图所示：
其中，圆圈表示数据结点，有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点，没有后继的结点叫做终端结点或叶结点。在上图的线性表中，B是根结点，E是终端结点，X的前趋是U，X的后继是K。在上图的二叉树中，R是根结点，A、D、M、G都是叶结点，X的前趋是R，X的后继是C和D，结点C和D之间没有关系。任意两个结点之间要么没有关系，要么是前趋后继关系。
若一个数据结构只有一个根结点，其任一结点至多有一个前趋、至多有一个后继，则该数据结构称为线性结构。如果一个数据结构不是线性结构，就称为非线性结构。
② 如上图所示，用结点和有向线段的图所表示的数据结构，称为逻辑结构。逻辑结构在机器内存中的表示形式，称为存储结构。一种逻辑结构可有多种不同的存储结构。
③ 在C语言中，若用结构体的数据域存储线性表的结点值，用结构体的指针域表示结点间的前趋后继关系，则这种存储结构叫做线性链表。例如：①中的线性表可表示为多种线性链表，如下图所示，但它们都是线性表的存储结构，都属于线性结构。
因此，单向链表、循环链表、双向链表都是线性结构。
④ 现实生活中的排队购票、买饭等服务活动，在程序设计中，通常采用队列来解决问题。队列的基本操作是入队操作和出队操作。若队列未满，则可执行入队操作；若队列未空，则可执行出队操作。队列逻辑结构是线性表，但只在前端删除(出队)、在后端插入(入队)，故称为先进先出、操作受限的线性表。在内存中，通常采用一维数组作为队列的存储结构。为了提高存储空间利用率，假想数组的首、尾元素也是相邻的，这就是循环队列，如下图所示：
因此，循环队列是线性结构。
⑤ 设有一端封闭竖直放置的圆柱形塑料筒，开口向上，直径刚好允许放进乒乓球，如下图所示：
显然，乒乓球呈现线性结构，用数据结构的话说，就是线性表。由于筒的一端封闭，乒乓球只能从一端进出，即按照″后进先出″的规则操作，用数据结构的话说，就是只能在线性表的一端，按照″后进先出″的规则插入、删除元素，这种操作受限的线性表叫做栈。栈在计算机技术领域中应用十分广泛，例如：在C语言中，函数的调用及返回(后调用的、先返回)的背后就有一个栈在工作。
栈的逻辑结构是操作受限的线性表，其存储结构常用一维数组实现，叫做顺序栈。
例如：设栈的存储空间是一维数组S(1：30)，可把栈顶指针top的初值设置为31，这就是栈开始工作之前的初始状态，或叫做空栈，即栈中尚无元素。栈在工作过程中，依靠栈顶指针top进行元素的插入(进栈)或删除(出栈)，栈顶指针top总是指向当前的栈顶元素。进栈时， 先执行top减1，再将新元素赋值于S[top]；出栈时，先将当前栈顶元素S[top]取出，再执行top加1，如下图所示：
因此，顺序栈是线性结构。
⑥ 循环队列和顺序栈都以一维数组为存储结构。队列也可采用链表作为存储结构，这种队列叫做链队列，如下图所示：
队头指针front指向队头结点，队尾指针rear指向队尾结点。
因此，链队列是线性结构。
⑦ 栈也可采用链表作为存储结构，这种栈叫做链栈，如下图所示：
栈顶指针top指向栈顶结点，表尾的空指针表示栈底，是固定不变的，也叫栈底指针。
因此，链栈是线性结构。
⑧ 任何二叉树都可以采用二叉链表存储结构，如下图所示：
在二叉链表中，每个结点含有一个数据域和左、右两个指针域，分别指向左、右孩子结点。注意：这里在二叉树的逻辑结构中用无向线段代替有向线段，这是因为树的上下层次反映了前趋后继关系，是允许的，也是习惯表示法。
因此，二叉链表是非线性结构。
⑨ 综上所述，单向链表、循环链表、双向链表、循环队列、链队列、顺序栈、链栈都属于线性结构；二叉链表是非线性结构。记住这句话，应付该题型足矣！
孪生题 下列哪一项属于非线性结构
（A） ……
（B） 二叉链表
（C） ……
（D） ……
第60题 有些关系运算要求满足一定的前提条件。要求关系R和S含有一个或多个共有的属性是下列哪种运算的前提条件
（A） 选择
（B） 投影
（C） 笛卡尔积
（D） 自然连接
答案 D
解析 考查自然连接的前提条件。
知识点
① 关系R和S进行自然连接的前提条件是要求关系R和S含有一个或多个共有的属性。
② 关系的直观形式是一张二维表，不妨设学生关系S、课程关系C、选修关系SC的内容分别是：
关系二维表中的每一行称为元组、每一列称为属性。将这三个关系的模式分别记作：
S（学号，姓名，性别，年龄，学院）
C（课程号，课程名，学分）
SC（学号，课程号，成绩）
③ 不妨对关系S和SC执行自然连接运算
它要求S和SC具备相同属性列，否则无法进行运算。这里S和SC的相同属性列是学号。自然连接的操作过程是：对于S的每一个元组，在SC中找出与之学号相同的各个元组(剔除相同属性学号列)并逐一与之拼接成新的元组，这样得出的全体新元组构成一个新关系，就是自然连接的结果，如下图所示：
孪生题 两个关系进行自然连接的前提条件是
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
第61题 设深度为6的二叉树共有63个结点，那么下列哪一项是错的
（A） 该树是满二叉树
（B） 该树是完全二叉树
（C） 该树有31个叶结点
（D） 该树不含度为1的结点
答案 C
解析 考查满二叉树和完全二叉树的特点。
知识点
① 满二叉树和完全二叉树具有一定特点，下图给出三层(根结点在第1层)的满二叉树以及所有可能的完全二叉树：
满二叉树的特点是：各层结点数均达到其最大值，第k层结点数最大值为2k-1。完全二叉树的特点是：与满二叉树相比，只在最底层自右而左依次缺失若干结点。满二叉树也算作完全二叉树。深度就是二叉树的总层次数，上图中二叉树的深度为3。
② 结点的度是孩子结点的个数，例如，在上图完全二叉树(3)中，结点R、S的度均为2，结点X的度为1，结点A、M、C的度均为0。度为0的结点叫叶结点。
③ 推论
- 满二叉树不含度为1的结点
- 深度为n的满二叉树共有2n-1个叶结点
- 深度为n的满二叉树的结点总数 N = 1 + 2 + 4 + … +2n-1
孪生题1 设深度为8的二叉树共有255个结点，那么下列哪一项是错的
（A） 该树是满二叉树
（B） 该树是完全二叉树
（C） 该树有128个叶结点
（D） 该树含有度为1的结点
答案 D
孪生题2 设深度为7的二叉树共有127个结点，下列哪一项是正确的
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
第62题 设有关系A、B、C，如图所示：
则由关系A和B得到关系C的运算是
（A） 除法
（B） 交
（C） 差
（D） 投影
答案 A
解析 考查除法运算的运算规则，该题型需要初步举一反三。
知识点
① 关系的直观形式是一张二维表，给定关系A、B、C的内容是：
关系二维表中的每一行称为元组、每一列称为属性。这些关系记作
A（X，Y，Z，U）
B（X，Y）
C（Z，U）
其中X、Y、Z，U为属性名。
② A与B的除法运算，记作A/B或A÷B，读作A除以B。
③ 对于二级考试而言，可采用如下方法验证：
若A/B = C，则C包含所有在A但不在B中的属性及其值，且B的元组与C的元组的所有可能的组合元组均在A中。
关于本题的验证如下：
因为B的元组（a，1）与C的元组（m，3）和（n，5）的组合元组
（a，1，m，3）
（a，1，n，5）
都在A中，且B的元组（b，3）与C的元组（m，3）和（n，5）的组合元组
（b，3，m，3）
（b，3，n，5）
也都在A中，所以，C恰好等于A/B。
孪生题1 设有关系A、B、C，如图所示：
则由关系A和B得到关系C的运算是
（A） ……
（B） 除法
（C） ……
（D） ……
孪生题2 设有关系如下图所示：
那么关系运算表达式
表示
（A） 全部课程号
（B） 全部学号
（C） 学号关系S中所有学生都选修的课程号
（D） 选课人数最少的课程号
答案 C
解：投影运算
的结果和先投影再相除运算
的结果如下图所示：
执行投影运算
即把选课关系SC的学号、课程号这两个属性列挑出来构成一个新关系。所谓投影，可设想用灯光照射指定的属性列而得到的影像。
再根据关系除法的含义可知选项C正确，本题要求充分理解！
孪生题3 设有关系如下图所示：
那么关系运算表达式
表示
（A） 全部课程号
（B） 全部学号
（C） 选修了关系C中所有课程的学生学号
（D） 选课人数最少的课程号
答案 C
第63题 数据库的物理设计不包括
（A） 索引设计
（B） 视图设计
（C） 集簇设计
（D） 分区设计
答案 B
解析 考查数据库设计各阶段的主要工作。
知识点
① 数据库设计分为四个阶段，如下图所示：
② 概念设计的主要工作包括选择局部应用、视图设计、视图集成。
③ 逻辑设计的主要工作包括：
- 从E-R图向关系模式转换
- 逻辑模式规范化及调整、实现
- 关系视图设计
④ 物理设计的主要工作包括索引设计、集簇设计、分区设计。
孪生题1 索引设计属于数据库设计的哪个阶段
（A） ……
（B） ……
（C） 物理设计
（D） ……
孪生题2 分区设计属于数据库设计的哪个阶段
（A） ……
（B） ……
（C） 物理设计
（D） ……
第64题 软件测试过程通常按四个步骤进行，第1步要进行的是
（A） 单元测试
（B） 集成测试
（C） 确认测试
（D） 系统测试
答案 A
解析 考查软件测试过程的四个步骤。
知识点
① 软件测试过程通常按四个步骤进行，如下图所示：
注：要牢记先后次序！
② 单元测试也叫模块测试，对软件设计的最小单位(即程序模块)进行测试，旨在发现模块内部的错误。
③ 集成测试也叫组装测试或联合测试，在单元测试的基础上，把程序模块按设计要求组装起来进行测试，旨在发现与模块之间接口有关的错误。
④ 确认测试也叫有效性测试，根据软件需求规格说明书，验证软件的功能和性能是否符合用户要求。
⑤ 系统测试把通过确认测试的软件作为整个计算机系统的一个元素，与计算机硬件、外设、某些支持软件、数据和人员等其它系统元素结合起来，在实际运行环境下，对计算机系统进行一系列的组装测试和确认测试。
孪生题1 软件测试过程通常按四个步骤进行，第2步要进行的是
（A） 单元测试
（B） 集成测试
（C） 确认测试
（D） 系统测试
孪生题2 软件测试过程通常按四个步骤进行，第3步要进行的是
（A） 单元测试
（B） 集成测试
（C） 确认测试
（D） 系统测试
第65题 在软件项目管理的进度管理中，用于表示工作进度计划以及工作实际进度情况的工具是
（A） 数据流图
（B） 甘特图(Gantt chart)
（C） 系统结构图
（D） PAD图
答案 B
解析 考查软件工程中的几个工具。
知识点
① 甘特图(Gantt chart)是在软件项目管理的进度管理中，用于表示工作进度计划以及工作实际进度情况的工具。
② 数据流图、数据字典是在需求分析阶段进行结构化分析的工具。
③ 结构图也叫程序结构图或系统结构图，是在概要设计阶段进行结构化设计的工具。
④ 程序流程图、N-S图、PAD图，是在详细设计阶段进行过程设计的工具。
⑤ 概要设计和详细设计合称软件设计。
注：任意混合上述工具，要求辨别属于哪个阶段，是一种典型题型！
孪生题1 下列哪一项不属于软件设计工具
（A） 程序流程图
（B） 系统结构图
（C） 数据流图
（D） N-S图
答案 C
孪生题2 下列哪一项是结构化需求分析工具
（A） 系统结构图
（B） 数据字典
（C） 甘特图
（D） 程序流程图
答案 B
孪生题3 下列哪一项是软件设计工具
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
孪生题4 下列哪一项是软件概要设计工具
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
孪生题5 下列哪一项是软件详细设计工具
（A） ……
（B） ……
（C） ……
（D） ……
（请自拟选项）
第66题 长度为20的线性表进行冒泡排序的比较次数是
（A） 380
（B） 190
（C） 400
（D） 200
答案 B
解析 理解下面的知识点，就不难选择，需要举一反三。
知识点
① 长度为n的一维数组的冒泡排序过程如下图所示，以n = 8为例：
长度为n的一维数组进行冒泡排序，需要n-1趟。因为上图中n = 8，所以共需7趟。为了直观显示冒泡的意义，将数组竖直画出，排序结果自上而下、从小到大排列。
对每一趟，均将数组元素自下而上两两分组，图中每个圆弧对应一组、圆圈数字代表组号。第1趟分成n-1组、第2趟分成n-2组、…、第i趟分成n-i组、第n-1趟只含1组。
对每一趟，自下而上、按组两两比较，若下面元素小于上面元素，则交换位置，否则保持不变，这样，较小的元素就像气泡一样逐级往上冒。每趟结束后，参与比较的所有元素中的最小值必定冒泡至顶端。
例如：上图第1趟，首先67与06比较，因67>06故不交换，然后06与18比较，因06<18故交换位置，即06上冒一个位置，接着06与94比较，因06<94故交换位置，即06再上冒一个位置，如此不断比较、不断上冒，最后06与44比较，因06<44故交换位置，即06再上冒一个位置到达顶端，用红色表示。这样，第1趟找出最小值06，第2趟找出次小值12，第3趟找出第三小值18，…，第7趟找出第七小值67、剩下最大值94，至此，冒泡排序过程结束。
从上可见，第1趟比较7次，第2趟比较6次，…，第7趟比较1次，于是
总的比较次数 = 7 + 6 + 5 + 4 + 3 + 2 + 1 = 8×7÷2 = 28
对于长度为n的数组，在任何情况下，归纳可得一般公式：
总的比较次数 = n(n-1) / 2
务必牢记该公式！
孪生题 长度为n的线性表进行冒泡排序，任何情况下，比较次数都是
（A） ……
（B） ……
（C） n(n-1) / 2
（D） ……
答案 C