二级公共基础知识考点.doc

第一章 数据结构与算法
笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。
详细重点学习知识点：
1．算法的概念、算法时间复杂度及空间复杂度的概念
2．数据结构的定义、数据逻辑结构及物理结构的定义
3．栈的定义及其运算、线性链表的存储方式
4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历
5．二分查找法
6．冒泡排序法
考点1 算法的基本概念
考试链接：
考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。
考点2 算法复杂度
考试链接：
考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。
疑难解答：算法的工作量用什么来计算？
算法的工作量用算法所执行的基本运算次数来计算，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f（n），其中n是问题的规模。
考点3 数据结构的定义
考试链接：
考点3在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为识记内容，读者还应该识记数据的逻辑结构和存储结构的概念。
考点4 线性结构与非线性结构
考试链接：
考点4在笔试考试中，虽然说不是考试经常考查的内容，但读者还是对此考点有所了解，在笔试考试中出现的几率为30%，主要是以填空题出现的形式出现，分值为2分，此考点为识记内容。
疑难解答：空的数据结构是线性结构还是非线性结构？
一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的算法是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。
考点5 栈及其基本运算
考试链接：
考点5在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100%，主要是以选择的形式出现，分值为2分，此考点为重点掌握内容，读者应该掌握栈的运算 。
小技巧：栈是按照"先进后出"或"后进先出"的原则组织数据，但是出栈方式有多种选择，在考题中经常考查各种不同的出栈方式。
考点6 线性链表的基本概念
考试链接：
考点6在笔试考试中出现的几率为30%，主要是以选择的形式出现，分值为2分，此考点为识记内容。重点识记结点的组成。
疑难解答：在链式结构中，存储空间位置关系与逻辑关系是什么？
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
考点7 树与二叉树及其基本性质

考试链接：
考点7在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100%，主要是以选择的形式出现，有时也有出现在填空题中，分值为2分，此考点为重点掌握内容。重点识记树及二叉树的性质。
误区警示：
满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。应该注意二者的区别。

小技巧：在二叉树的遍历中，无论是前序遍历，中序遍历还是后序遍历，二叉树的叶子结点的先后顺序都是不变的。
考点8 二叉树的遍历
考试链接：
考点8在笔试考试中考核几率为30%，分值为2分，读者应该熟练掌握各种遍历的具体算法，能由两种遍历的结果推导另一种遍历的结果。
疑难解答：树与二叉树的不同之处是什么？
在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。
考点9 顺序查找
考试链接：
考点9在笔试考试中考核几率在30%，一般出现选择题中，分值为2分，读者应该具体掌握顺序查找的算法。
考点10 二分法查找
考试链接：
考点10在笔试考试中考核几率为30%，一般出现填空题中，分值为2分，考核比较多查找的比较次数，读者应该具体掌握二分查找法的算法。
疑难解答：二分查找法适用于哪种情况？
二分查找法只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。
这个过程一直进行到查找成功或子表长度为0为止。
对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。
考点11 交换类排序法
考试链接:
考点11属于比较难的内容，一般以选择题的形式考查，考核几率为30%，分值约为2分，读者应该熟练掌握几种排序算法的基本过程。
冒泡排序法和快速排序法都属于交换类排序法。
疑难解答：冒泡排序和快速排序的平均执行时间分别是多少？
冒泡排序法的平均执行时间是O（n2），而快速排序法的平均执行时间是O（nlog2n）。

1.7 例题详解
一、选择题
【例1】算法的时间复杂度取决于_______。（考点2）

A）问题的规模 B）待处理的数据的初态
C）问题的难度 D）A）和B）
解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。
答案：D）
【例2】在数据结构中，从逻辑上可以把数据结构分成_______。（考点3）
A）内部结构和外部结构 B）线性结构和非线性结构
C）紧凑结构和非紧凑结构 D）动态结构和静态结构
解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。
答案：B）
【例3】以下_______不是栈的基本运算。（考点5）
A）判断栈是否为素空 B）将栈置为空栈
C）删除栈顶元素 D）删除栈底元素
解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。
答案：D）
【例4】链表不具备的特点是_______。（考点6）
A）可随机访问任意一个结点 B）插入和删除不需要移动任何元素
C）不必事先估计存储空间 D）所需空间与其长度成正比
解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所以答案为A）
答案：A）
【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是_______。（考点8）
A）ACBED B）DEABC
C）DECAB D）EDBAC
解析：后序遍历的顺序是"左子树－右子树－根结点"；中序遍历顺序是"左子树－根结点－右子树"；前序遍历顺序是"根结点－左子树－右子树"。根据各种遍历算法，不难得出前序遍历序列是EDBAC。所以答案为D）。
答案：D）
【例6】设有一个已按各元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，s和b的关系是_______。（考点9）
A）s=b B）s>b C）s［log2n］+1。
答案：B）
【例7】在快速排序过程中，每次划分，将被划分的表（或子表）分成左、右两个子表，考虑这两个子表，下列结论一定正确的是_______。（考点11）
A）左、右两个子表都已各自排好序
B）左边子表中的元素都不大于右边子表中的元素
C） 左边子表的长度小于右边子表的长度
D）左、右两个子表中元素的平均值相等
解析：快速排序基本思想是：任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。
答案：B）
二、填空题
【例1】问题处理方案的正确而完整的描述称为_______。（考点1）
解析：计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。
答案：算法
【例2】一个空的数据结构是按线性结构处理的，则属于_______。（考点4）
解析：一个空的数据结构是线性结构或是非线性结构，要根据具体情况而定。如果对数据结构的运算是按线性结构来处理的，则属于线性结构，否则属于非线性结构。
答案：线性结构
【例3】设树Ｔ的度为４，其中度为１、２、３和４的结点的个数分别为４、２、１、１，则Ｔ中叶子结点的个数为_______。（考点7）
解析：根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和加１。
因此树的结点数为１×４＋２×２＋３×１＋４×１＋１＝16。叶子结点数目等于树结点总数减去度不为０的结点数之和，即16－（４＋２＋１＋１）＝８。
答案：8
【例4】二分法查找的存储结构仅限于_______且是有序的。（考点10）
解析：二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可）。
答案：顺序存储结构

第二章 程序设计基础
经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是结构化程序设计的原则、面向对象方法的基本概念，读者应对此部分进行重点学习。
详细重点学习知识点：
1．结构化程序设计方法的四个原则
2．对象、类、消息、继承的概念、类与实例的区别
考点1 结构化程序设计的原则
考试链接：
考点1在笔试考试中出现的几率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该识记结构化程序设计方法的四个主要原则。
疑难解答：如何进行自顶向下设计方法？
程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标；不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。
考点2 面向对象方法的基本概念
考试链接：
考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以填空题的形式出现，分值为2分，此考点为重点识记内容，读者应该识记几个基本要素的定义、对象的特征以及消息、继承、类的定义。
误区警示：
当使用"对象"这个术语时，既可以指一个具体的对象，也可以泛指一般的对象，但是当使用"实例"这个术语时，必须是指一个具体的对象。
疑难解答：能举一下现实中的对象及其属性和操作吗？
一辆汽车是一个对象，它包含了汽车的属性（如颜色、型号等）及其操作（如启动、刹车等）。一个窗口是对象，它包含了窗口的属性（如大小、颜色等）及其操作（如打开、关闭等）。

2.3 例题详解
一、选择题
【例1】结构化程序设计方法提出于_______。（考点1）
A）20世纪50年代 B）20世纪60年代
C）20世纪70年代 D）20世纪80年代
解析：20世纪70年代提出了"结构化程序设计（structured programming）"的思想和方法。结构化程序设计方法引入了工程化思想和结构化思想，使大型软件的开发和编程得到了极大的改善。
答案：C）
【例2】结构化程序设计方法的主要原则有下列4项，不正确的是_______。（考点1）
A）自下向上 B）逐步求精
C）模块化 D）限制使用goto语句
解析：结构化程序设计方法的主要原则为：
（1）自顶向下：即先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。
（2）逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。
（3）模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。
（4）限制使用goto语句。
答案：A）
【例3】面向对象的开发方法中，类与对象的关系是_____考点2）
A）抽象与具体 B）具体与抽象
C）部分与整体 D）整体与部分
解析：现实世界中的很多事物都具有相似的性质，把具有相似的属性和操作的对象归为类，也就是说类是具有共同属性、共同方法的对象的集合，是对对象的抽象。它描述了该对象类型的所有对象的性质，而一个对象则是对应类的一个具体实例。所以本题正确答案为A）项。
答案：A）

二、填空题
【例1】在面向对象方法中，使用已经存在的类定义作为基础建立新的类定义，这样的技术叫做_______。（考点2）
解析：继承是面向对象方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。
答案：继承
【例2】对象的基本特点包括_______、分类性、多态性、封装性和模块独立性好等5个特点。（考点2）
解析：对象具有如下的基本特点：
（1）标识惟一性。对象是可区分的，并且由对象的内在本质来区分；
（2）分类性。可以将具有相同属性和操作的对象抽象成类；
（3）多态性。同一个操作可以是不同对象的行为；
（4）封装性。只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法；
（5）模块独立性。面向对象是由数据及可以对这些数据施加的操作所组成的统一体。
答案：标识惟一性
【例3】对象根据所接收的消息而做出动作，同样的消息被不同的对象所接收时可能导致完全不同的行为，这种现象称为_______。（考点2）
解析：对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性。
答案：多态性
第三章 软件工程基础
经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是软件生命周期、软件设计的基本原理，软件测试的目的、软件调试的基本概念，读者应对此部分进行重点学习。
详细重点学习知识点：
1．软件的概念、软件生命周期的概念及各阶段所包含的活动
2．概要设计与详细设计的概念、模块独立性及其度量的标准、详细设计常用的工具
3．软件测试的目的、软件测试的4个步骤、
4．软件调试的任务

3.1软件工程基本概念
考点1 软件定义与软件特点
考试链接：
考点1在笔试考试中，是一个经常考查的内容，考核的几率为70%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该识记软件的定义，特点及其分类。
小提示：应用软件是为解决特定领域的应用而开发的软件；系统软件是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件；支撑软件是介于两者之间，协助用户开发软件的工具性软件。
考点2 软件工程过程与软件生命周期
考试链接：
考点2在笔试考试中，在笔试考试中出现的几率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该识记软件生命周期 的定义，主要活动阶段及其任务。
考点3 软件设计的基本概念
考试链接：
考点3在笔试考试中，是一个经常考查的内容，考核中几率为70%，主要是以选择题的形式出现，分值为2分，此考点为重点掌握内容，读者应该识记模块独立性中的耦合性和内聚性。
误区警示：
在程序结构中，各模块的内聚性越强，则耦合性越弱。软件设计应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。
小提示：上面仅是对耦合机制进行的一个分类。可见一个模块与其他模块的耦合性越强则该模块独立性越弱。原则上讲，模块化设计总是希望模块之间的耦合表现为非直接耦合方式。但是，由于问题所固有的复杂性和结构化设计的原则，非直接耦合是不存在的。
考点4 详细设计
考试链接：
考点4在笔试考试中，在笔试考试中出现的几率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该识记过程设计包括哪些常用工具。
疑难解答：程序流程图，N-S图，PAD图的控制结构的异同点是什么？
相同点是三种图都有顺序结构，选择结构和多分支选择，并且N-S图和PAD图还有相同的WHILE重复型、UNTIL重复型；不同点是程序流程图没有WHILE重复型、UNTIL重复型而有后判断重复型和先判断重复型。
考点5 软件测试的目的

考试链接：
考点5在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择题的形式出现，分值为2分，此考点为理解内容，读者应该理解测试是为了发现错误。
考点6 软件测试的实施
考试链接：
考点6在笔试考试中出现的几率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该识记软件测试过程的4个步骤，单元测试的两种测试方式。
考点7 软件调试的基本概念
考试链接：
考点7在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择题的形式出现，分值为2分，此考点为重点识记内容，读者应该识记软件调试的概念。
误区警示：
程序经调试改错后还应进行再测试，因为经调试后有可能产生新的错误，而且测试是贯穿生命周期的整个过程。
疑难解答：软件测试与软件调试有何不同？
软件测试是尽可能多地发现软件中的错误，而软件调试的任务是诊断和改正程序中的错误。软件测试贯穿整个软件生命周期，调试主要在开发阶段。
3.5 例题详解
一、选择题
【例1】对软件的特点，下面描述正确的是_______。（考点1）
A）软件是一种物理实体
B）软件在运行使用期间不存在老化问题
C）软件开发、运行对计算机没有依赖性，不受计算机系统的限制
D）软件的生产有一个明显的制作过程
解析：软件在运行期间不会因为介质的磨损而老化只可能因为适应硬件环境以及需求变化进行修改而引入错误，导致失效率升高从而软件退化，所以本题正确答案为B）。
答案：B）
【例2】以下哪项是软件生命周期的主要活动阶段？_______（考点2）
A）需求分析 B）软件开发
C）软件确认 D）软件演进
解析：B）、C）、D）项都是软件工程过程的基本活动，还有一个是软件规格说明。
答案：A）
【例3】从技术观点看，软件设计包括_______。（考点3）
A）结构设计、数据设计、接口设计、程序设计
B）结构设计、数据设计、接口设计、过程设计
C）结构设计、数据设计、文档设计、过程设计
D）结构设计、数据设计、文档设计、程序设计
解析：技术角度，要进行结构、接口、数据、过程的设计。结构设计是定义系统各部件关系，数据设计是根据分析模型转化数据结构，接口设计是描述如何通信，过程设计是把系统结构部件转化为软件的过程性描述。
答案：B）
【例4】以下哪个是软件测试的目的？_______（考点5）
A）证明程序没有错误 B）演示程序的正确性
C）发现程序中的错误 D）改正程序中的错误
解析：关于测试目的的基本知识，IEEE的定义是：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求，或是弄清预期结果与实际结果之间的差别，所以正确答案是C）。
答案：C）
【例5】以下哪个测试要对接口测试？_______。（考点6）
A）单元测试 B）集成测试
C）验收测试 D）系统测试
解析：检查对测试实施各阶段的了解，集成测试时要进行接口测试、全局数据结构测试、边界条件测试和非法输入的测试等，所以正确答案是B）。
答案：B）
【例6】程序调试的主要任务是_______。（考点7）
A）检查错误 B）改正错误
C）发现错误 D）以上都不是
解析：程序的调试任务是诊断和改正程序中的错误。调试主要在开发阶段进行。
答案：B）
【例7】以下哪些不是程序调试的基本步骤？_______（考点7）
A）分析错误原因 B）错误定位
C）修改设计代码以排除错误 D）回归测试，防止引入新错误
解析：程序调试的基本步骤：
（1）错误定位。从错误的外部表现形式入手，研究有关部分的程序，确定程序中出错位置，找出错误的内在原因。
（2）修改设计和代码，以排除错误。
（3）进行回归测试，防止引进新的错误。
答案：A）
【例8】在修改错误时应遵循的原则有_______。（考点7）
A）注意修改错误本身而不仅仅是错误的征兆和表现
B）修改错误的是源代码而不是目标代码
C）遵循在程序设计过程中的各种方法和原则
D）以上3个都是
解析：修改错误原则：
(1）在出现错误的地方，很可能有别的错误；
2）修改错误的一个常见失误是只修改了这个错误的征兆或这个错误的表现，而没有修改错误本身；
(3）注意修正一个错误的同时有可能会引入新的错误；
(4）修改错误的过程将迫使人们暂时回到程序设计阶段；
(5）修改源代码程序，不要改变目标代码。
答案：D）

二、填空题
【例1】软件设计是软件工程的重要阶段，是一个把软件需求转换为_______的过程。（考点3）
解析：软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。其基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。
答案：软件表示
【例2】_______是指把一个待开发的软件分解成若干小的简单的部分。（考点3）
解析：模块化是指把一个待开发的软件分解成若干小的简单的部分。如高级语言中的过程、函数、子程序等。每个模块可以完成一个特定的子功能，各个模块可以按一定的方法组装起来成为一个整体，从而实现整个系统的功能。
答案：模块化

【例3】数据流图采用4种符号表示_______、数据源点和终点、数据流向和数据加工。（考点4）
解析：数据流图可以表达软件系统的数据存储、数据源点和终点、数据流向和数据加工。其中，用箭头表示数据流向，用圆或者椭圆表示数据加工，用双杠表示数据存储，用方框来表示数据源点和终点。
答案：数据存储
第四章 数据库设计基础
经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是数据库管理系统，数据库基本特点，数据库系统的三级模式及二级映射，E-R模型，关系模型和关系代数，读者应对此部分进行重点学习。
详细重点学习知识点：
1．数据的概念、数据库管理系统提供的数据语言、数据管理员的主要工作、数据库系统阶段的特点、数据的物理独立性及逻辑独立性、数据统一管理与控制、三级模式及两级映射的概念
2．数据模型3个描述内容、E-R模型的概念及其E-R图表示法、关系操纵、关系模型三类数据约束
3．关系模型的基本操作、关系代数中的扩充运算
4．数据库设计生命周期法的4个阶段

考点1 数据、数据库、数据库管理系统
考试链接：
考点1在笔试考试中，是一个经常考查的内容，在笔试考试中出现的机率为70%，主要是以选择题的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记数据语言所包括的数据定义语言、数据操纵语言和数据控制语言。
考点2 数据库系统的发展
考试链接：
考点2在笔试考试中出现的机率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者还应该注意各个阶段的特点。
考点3 数据库系统的基本特点
考试链接：
考点3在笔试考试中出现的机率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该理解物理独立性和逻辑独立性的定义。
考点4 数据库系统的内部结构体系
考试链接：
考点4在笔试考试中出现的机率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者还应该理解三级模式及两级映射的定义。
误区警示：
一个数据库只有一个概念模式。一个概念模式可以有若干个外模式。三级模式都有几种名称，读者应该熟记每个模式的另一些名称。
疑难解答：数据库应用系统的结构是什么样的？
数据库应用系统的7个部分以一定的逻辑层次结构方式组成一个有机的整体，它们的结构关系是：应用系统工、应用开发工具软件、数据库管理系统、操作系统、硬件。
考点5 数据模型的基本概念
考试链接：
考点5在笔试考试中是一个经常考查的内容，出现的机率为70%，主要是以填空形式出现，分值为2分，此考点为重点识记内容，读者应该识记数据模型的3个部分。
考点6 E-R模型
考试链接：
考点6在笔试考试中出现的机率为30%，主要是以选择题的形式出现，分值为4分，此考点为理解内容，读者应该理解实体间三种函数关系，识记实体、属性、联系各用什么图形来表示。
考点7 层次模型
考试链接：
考点7在笔试考试中出现的机率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者应该理解层次模型的定义。它的基本结构是树形结构。
考点8 关系模型
考试链接：
考点8笔试考试中，是一个经常考查的内容，在笔试考试中出现的机率为70%，主要是以选择题的形式出现，分值为2分，此考点重点掌握为理解内容，读者应该理解二维表的7个性质，识记三类数据约束。
误区警示：
当对关系模型进行查询运算，涉及到多种运算时，应当注意它们之间的先后顺序，因为有可能进行投影运算时，把符合条件的记录过滤，产生错误的结果。
小提示：关系模式采用二维表来表示，一个关系对应一张二维表。可以这么说，一个关系就是一个二维表，但是一个二维表不一定是一个关系。
疑难解答：E-R图是如何向关系模式转换的？
从E-R图到关系模式的转换是比较直接的，实体与联系都可以表示成关系，E-R图中属性也可以转换成关系的属性。实体集也可以转换成关系。
考点9 关系代数
考试链接：
考点9在笔试考试中出现的机率为30%，主要是以选择题的形式出现，分值为2分，此考点重点掌握理解内容，读者应该理解关系模型的基本操作以及关系代数的几种运算。
误区警示：
当对关系模型进行查询运算，涉及到多种运算时，应当注意它们之间的先后顺序，因为有可能进行投影运算时，把符合条件的记录过滤，产生错误的结果。
小提示：当关系模式进行笛卡尔积运算时，读者应该注意运算后的结果是n+m元关系，元组个数是p×q，这是经常混淆的。
疑难解答：连接与自然连接的不同之处在什么？
一般的连接操作是从行的角度进行运算，但自然连接还需要取消重复列，所以是同时从行和列的角度进行运算。
考点10 数据库设计概述
考试链接：
考点10在笔试考试中出现的机率为30%，主要是以选择题的形式出现，分值为2分，此考点为识记内容，读者还应识记数据库设计的前4个阶段以及它们相应的任务。
疑难解答：数据库设计的前4个阶段的成果分别是什么？
数据库设计中一般采用前4个阶段，它们的成果分别是需求说明书、概念数据模型、逻辑数据模型和数据库内模式。
4.4 例题详解
一、选择题
【例1】对于数据库系统，负责定义数据库内容，决定存储结构和存取策略及安全授权等工作的是_______。（考点1）
A）应用程序员 B）用户
C）数据库管理员 D）数据库管理系统的软件设计员
解析：数据库管理员（简称DBA），具有如下的职能：设计、定义数据库系统；帮助用户使用数据库系统；监督与控制数据库系统的使用和运行；改进和重组数据库系统；转储和恢复数据库；重构数据库。所以，定义数据库内容，决定存储结构和存取策略及安全授权等是数据库管理员（DBA）的职责。
答案：C）
【例2】在数据库管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是_______。（考点2）
A）数据库系统 B）文件系统
C）人工管理 D）数据项管理
解析：在人工管理阶段，数据无法共享，冗余度大，不独立，完全依赖于程序。在文件系统阶段，数据共享性差，冗余度大，独立性也较差。所以B）选项和C）选项均是错误的。
答案：A）
【例3】在数据库系统中，当总体逻辑结构改变时，通过改变_______，使局部逻辑结构不变，从而使建立在局部逻辑结构之上的应用程序也保持不变，称之为数据和程序的逻辑独立性。（考点3）
A）应用程序 B）逻辑结构和物理结构之间的映射
C）存储结构 D）局部逻辑结构到总体逻辑结构的映射
解析：模式描述的是数据的全局逻辑结构，外模式描述的是数据的局部逻辑结构。当模式改变时，由数据库管理员对外模式/模式映射做相应改变，可以使外模式保持不变。应用程序是依据数据的外模式编写的，从而应用程序也不必改变。保证了数据与程序的逻辑独立性，即数据的逻辑独立性。
答案：D）
【例4】数据库系统依靠_______支持数据的独立性。（考点4）
A）具有封装机制
B）定义完整性约束条件
C）模式分级，各级模式之间的映射
D）DDL语言和DML语言互相独立
解析：。数据库的三级模式结构指数据库系统由外模式、模式和内模式3级构成。数据库管理系统在这3级模式之间提供了两层映射：外模式/模式映射，模式/内模式映射。这两层映射保证了数据库系统中的数据能够具有较高的逻辑独立性和物理独立性。
答案：C）
【例5】将E-R图转换到关系模式时，实体与联系都可以表示成______考点6）
A） 属性 B） 关系
C） 键 D） 域
解析：E-R图由实体、实体的属性和实体之间的联系3个要素组成，关系模型的逻辑结构是一组关系模式的集合，将E-R图转换为关系模型：将实体、实体的属性和实体之间的联系转化为关系模式。
答案：B）
【例6】用树形结构来表示实体之间联系的模型称为_______。（考点7）
A）关系模型 B）层次模型
C）网状模型 D）数据模型
解析：满足下面两个条件的基本层次联系的集合为层次模型：
（1）有且只有一个结点没有双亲结点，这个结点称为根结点；
（2）根以外的其它结点有且仅有一个双亲结点。
层次模型的特点：
（1）结点的双亲是惟一的；
（2）只能直接处理一对多的实体联系；
（3）每个记录类型定义一个排序字段，也称为码字段；
（4）任何记录值只有按其路径查看时，才能显出它的全部意义；
（5）没有一个子女记录值能够脱离双亲记录值而独立存在。
答案：B）
【例7】对数据库中的数据可以进行查询、插入、删除、修改（更新），这是因为数据库管理系统提供了_______。（考点8）
A） 数据定义功能 B） 数据操纵功能
C） 数据维护功能 D） 数据控制功能
解析：数据库管理系统包括如下功能：
（1）数据定义功能：DBMS提供数据定义语言（DDL），用户可以通过它方便地对数据库中的数据对象进行定义；
（2）数据操纵功能：DBMS还提供数据操作语言（DML），用户可以通过它操纵数据，实现对数据库的基本操作，如查询、插入、删除和修改；
（3）数据库的运行管理：数据库在建立、运用和维护时由数据库管理系统统一管理，统一控制以保证数据的安全性、完整性、多用户对数据的并发使用及发生故障后的系统恢复；
（4）数据库的建立和维护功能：它包括数据库初始数据的输入、转换功能，数据库的转储、恢复功能，数据库的重组、功能和性能监视等等。
答案：B）
【例8】设关系R和关系S的属性元数分别是3和4，关系T是R与S的笛卡儿积，即T=R×S，则关系T的属性元数是_______（考点9）
A） 7 B） 9
C） 12 D） 16
解析：笛卡儿积的定义是设关系R和S的元数分别是r和s，R和S的笛卡儿积是一个（r+s）元属性的集合，每一个元组的前r个分量来自R的一个元组，后s个分量来自s的一个元组。所以关系T的属性元数是3+4＝7。
答案：A）
【例9】下述_______不属于数据库设计的内容。（考点10）
A） 数据库管理系统 B） 数据库概念结构
C） 数据库逻辑结构 D） 数据库物理结构
解析：数据库设计是确定系统所需要的数据库结构。数据库设计包括概念设计、逻辑设计和建立数据库（又称物理设计）。
答案：A）
二、填空题

【例1】一个数据库的数据模型至少应该包括以下3个组成部分，_______、数据操作和数据的完整性约束条件。（考点5）
解析：数据模型是严格定义的一组概念的集合。这些概念精确地描述了系统的静态特性、动态特性和完整性约束条件。因此，数据模型通常由数据结构、数据操作和完整性约束3部分组成。其中，数据结构是对系统静态特性的描述，数据操作是对系统动态特性的描述，数据的完整性约束用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确性、有效性和相容性。
答案：数据结构
【例2】在关系数据模型中，二维表的列称为属性，二维表的行称为_____。（考点8）
解析：一个关系是一张二维表。表中的行称为元组，一行对应一个元组，一个元组对应存储在文件中的一个记录值。
答案：元组

例题
第一章
1．算法的时间复杂度是指_____C__。
A）执行算法程序所需要的时间
B）算法程序的长度
C）算法执行过程中所需要的基本运算次数
D）算法程序中的指令条数
2．数据结构在计算机存储空间的存放形式称为____A___。
A）数据的存储结构 B）数据结构
C）数据的逻辑结构 D）数据元素之间的关系
3．设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列____B___序列是不可能通过栈产生的。
A）1，2，3，4，5 B）5，3，4，1，2
C）4，3，2，1，5 D）3，4，5，2，1
4．在一棵二叉树的前序遍历、中序遍历和后序遍历所产生的序列中，所有的叶子结点的先后顺序____A___。
A）完全相同 B）不相同
C）前序与中序相同 D）后序与中序相同
5．一棵二叉树的前序遍历序列为ABDGCFK，中序遍历序列为DGBAFCK，则结点的后序遍历序列是__B_____。
A）ACFKDBG B）GDBFKCA
C）KCFAGDB D）ABCDFKG
6．顺序查找适合于存储结构为____B___的线性表。
A）散列存储 B）顺序存储或链式存储
C）压缩存储 D）索引存储
1．算法的复杂度主要包括时间复杂度和空间复杂度。
2．在一棵二叉树中，叶子结点的个数为n0，度为2的结点的个数为n2，则有n0=__n2+1_____。
3．设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深和最小树深分别是__99__和 _6__。
4．在顺序表（8，12，16，20，26，27，31，34，43，49，51）中，用二分法查找关键值为21，需做的比较次数为____4___。
5．对n个元素的序列进行冒泡排序时，最少的比较次数是__n－1___。

第二章
1．严格控制goto语句的使用，意思是指____C___。
Ⅰ. 用一个非结构化的程序设计语言去实现一个结构化的构造
Ⅱ. 若不使用goto语句会使功能模糊
Ⅲ. 在某种可以改善而不是损害程序可读性的情况下
Ⅳ.取消goto语句的使用
A）Ⅰ、Ⅱ和Ⅳ B）Ⅱ、Ⅲ和Ⅳ
C）Ⅰ、Ⅱ和Ⅲ D）Ⅰ和Ⅳ
2．以下_____D__不是面向对象的特征。
A）封装性 B）继承性 C）多态性 D）过程调用
3．下面对对象概念描述不正确的是___B____。
A）对象是属性和方法的封装体
B）任何对象都必须有继承性
C）操作是对象的动态属性
D）对象间的通信靠消息传递
1．结构化程序设计方法的主要原则包括自顶向下、逐步求精、___模块化____和