二级公共基础知识(学生版)

第一部分 数据结构(5-6个题目，占10分)

*1.所谓算法是指解题方而完整的描述。严格来说，一个算法必须具有以下五个主要特征：

 有穷性 确定性 可行性 输入 输出（或说成：拥有足够的情报 ）

2.算法的组成要素

 算法中对数据的运算和操作及算法的控制结构

3.算法设计基本方法

 列举法 归纳法 递推 递归 减半递推 回溯法

*4.算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。

（1）算法的时间复杂度：算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法的时间复杂度为算法中的基本操作重复执行的次数。是问题规模n的某个函数f(n)。

（2）算法的空间复杂度：算法的空间负杂度是指执行这个算法所需要的内存空间。 5.数据结构的定义

是指相互有关联的数据元素的集合。（一定要注意是数据元素的集合，不是数据的集合） *6. 数据结构主要研究三个方面的问题：

1) 逻辑结构是各数据元素之间的逻辑关系。它与在计算机中的存储位置无关，是于计算机的。 2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。 3)对各种数据结构进行的运算。 7.常见的存储结构：

 顺序存储结构 链式存储结构 索引存储结构 散列存储结构  一般分为：线性存储和非线性存储

8.线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“存储，表中第一个元素的存储位置作称作线性表的基地址。 所有数据元素的存储位置均可由第一个数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)×C ↑ ↑ 基地址 一个数据元素所占存储量 9. 线性表的插入和删除运算最坏的时间复杂度为O(n-1),最好为O(o). 10. 栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。栈是一种后进先出的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。

11. 栈的操作有：

 入栈：在栈顶位置插入一个新元素，栈顶指针top加1。

 退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。

 取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针不变。

12. 如果某栈的入栈顺序是ABCDEF，则出栈顺序不可能是哪个（C） （此类型的题目一定要会推导）

A、DCEFBA B、ABCDEF C、EDFCAB D、CBAEDF

13. 队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。

14. 循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。容量的计算：

*当rear>front时，元素个数＝rear－front ；

*当rear15. 单链表是用一组任意的存储单元(可以连续，也可以不连续)存储数据元素，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，除了存储其本身的信息(数据域)之外，还需要存储其后继元素的

存储位置信息(指针域)。

16．N个结点链接成一个链表，为线性表的链式存储结构。由于结点中只包含一个指针域，故称为单链表。 17. 增加头指针是为了方便操作。必须从头指针开始(顺序存取)才能访问整个链表，从链表中的任一结点是不能访问整个链表的。最后一个数据元素没有直接后继，其指针域为空。 18.链表中插入和删除结点（数据）是不需要移动其他结点的。

19. 在双向链表中的结点包含两个指针域，其中一个指向直接后继，另一个指向直接前驱。

20.循环链表的特点是表中最后一个结点的指针域指向第一个结点，整个链表为一个由链指针相链接的环。 21. 树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。

树是(n≥0)个结点的有限集合，集合为空的树简称为空树；树中的元素称为结点。在任意一棵非空树中： (1)有且仅有一个特定的结点称为根结点。 (2)当n>1时，其余的结点可分为m个互不相交的子集T1,T2,„Tm，其中每个有限子集本身又是一棵树。 *22. 树的的几个重要术语：（不明白的自己看书）

树的度 叶节点 双亲、孩子和兄弟 层次 深度

*23. 二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。几个重要的性质：

性质1 在二叉树的第i层上至多有2i-1个结点（i≥1）

性质2 深度为k的二叉树至多有2k -1个结点（k≥1）

性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2 ，则：n0 =n2+1 性质4 具有n个结点的二叉树，其深度至少为[log2n] +1

24.满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。

**25.完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为[log2n] +1。（一定要会计算结点的个数）

26. 二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。

**27. 二叉树的遍历指不重复地访问二叉树的所有结点。分为：先序、后序和中序遍历。一定要明白由先序和中序推出后序，和由后序和中序推出先序！！！！

28. 顺序查找是指在一个给定的数据结构中查找某个指定的元素。最好情况查找长度为1，最坏为n，所以平均查找长度为（n+1)/2。时间复杂度为O(n)。

29．二分查找法只适用于顺序存储的有序表。查找过程为：给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间” 或 “后半个区间” 之后继续进行查找。平均查找长度小于等于 ┍log2 (n+1)┑ ，时间复杂度为O(log2n)。 *30. 排序方法有：插入排序：包括简单插入排序法和希尔排序法等

交换排序：包括冒泡排序和快速排序法等 选择排序：包括简单选择排序和堆排序等

31. 冒泡排序最坏情况下运算的次数为：n*(n-1)/2（即时间复杂度）。最好情况下为：n-1。 *32.排序部分应该掌握的几点：

1.当原表有序或基本有序时,直接插入排序和冒泡排序最好，时间复杂度可降至O(n)。（也就是最好情

况下） 。如果选择快速排序则相反，达到最坏时间复杂度。

2.空间复杂度最坏的是归并排序O（n) ，其次是基数排序O（rd) 。 3.平均时间最好的是快速、堆、归并排序O（nlgn)。 4.稳定排序和不稳定排序（希尔、堆、直接选择，快速）。 5.最坏情况下，时间复杂度最小的是：堆和归并排序。

第一部分典型例题

1：已知一组数据原先采用顺序存储，现改为散列存储，则（B）不变。 A.存储结构 B.逻辑结构 C.数据间的顺序 D.不确定 2：常见的线性结构有__线性表_,_队列___,_栈____

3：在线性表中删除第5个节点，则原第6个节点的位置（B），如果单链表则（C）

A.6 B.5 C.不变 D.不确定

4：已知栈的头指针front当前位置为5，从栈中读取一个数据，则front指向（A） A.5 B.6 C.不变 D.不确定

5：如果某栈的入栈顺序是123456，则出栈顺序不可能是哪个（C） A、435621 B.123456 C、6312 D、6321

6:容量为25的循环队列中，若front=16，rear=9，有 _18_ 个元素

7： 一棵二叉树有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 ( B) A）221 B）219 C）231 D）229 8：一棵含18个结点的二叉树的高度至少为(5)

A）3 B）4 C）5 D）6 9： 在一棵二叉树上第5层的结点数最多是 (B)

A）8 B）16 C）32 D）15 10：在深度为5的满二叉树中，叶子结点的个数为(C)

A）32 B）31 C）16 D）15

11：深度为4的二叉树中，编号为7的节点，它的右孩子节点为（D）该树为满二叉树；如果该树是完全二叉树，但不是满二叉树，则它的最大节点编号为（A）

A）14 B）8 C）9 D）15

12：设树T的度为4，其中度为1，2，3，4的结点个数分别人4，2，1，1.则T中的叶子结点数为(A) A)8 B)7 C)6 Ｄ）５ 13．（3）线性表L=（a1,a2,a3,„ai，„an），下列说法正确的是（D）

A）每个元素都有一个直接前件和直接后件 B）线性表中至少要有一个元素 C）表中诸元素的排列顺序必须是由小到大或由大到小

D）除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 14．3）链表不具有的特点是（B）

A）不必事先估计存储空间 B）可随机访问任一元素

C）插入删除不需要移动元素 D）所需空间与线性表长度成正比 15、1）由两个栈共享一个存储空间的好处是（B）

A）减少存取时间，降低下溢发生的机率 B）节省存储空间，降低上溢发生的机率 C）减少存取时间，降低上溢发生的机率 D）节省存储空间，降低下溢发生的机率 16、设有两个串p和q，求q在p中首次出现位置的运算称作（B）

A）连接 B）模式匹配 C）求子串 D）求串长 17. n个顶点的连通图中边的条数至少为（C）

A）0 B）1 C）n-1 D）n 18、 n个顶点的强连通图中边的条数至少为（D）

A）0 B）1 C）n-1 D）n 19. （2）非空的循环单链表head的尾结点（由p所指向），满足

A）p->next==NULL B）p==NULL C）p->next=head D）p=head 20、已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是（B） A）堆排序 B）直接插入排序 C）快速排序 D）直接选择排序 21、最简单的交换排序方法是（D）

A）快速排序 B）选择排序 C）堆排序 D）冒泡排序 22、栈和队列通常采用的存储结构是 【链式存储和顺序存储】。

23、冒泡排序算法在最好的情况下的n个元素交换次数为 【0】次，但比较次数为【n-1】 24、当线性表采用顺序存储结构实现存储时，其主要特点是 【存储位置相邻】 25、用链表表示线性表的突出优点是 【插入、删除操作方便】

第二部分 程序设计基础（1-2题）和软件工程（4-5题）

 1. 程序设计主要经历了结构化的程序设计和面向对象的程序设计阶段。在程序设计中，通常采用

“自顶向下，逐步求精”的方法。结构化程序设计由三种基本控制结构组成：顺序结构、选择结构和循环结构。

2.程序风格也是非常重要的。良好的程序设计风格概括起来包括以下4个方面：  源程序文档化

（1） 标识符的命名:要有一定的实际含义。

（2）程序的注释：分为序言性注释和功能性注释。 （3）程序的视觉组织：一定要层次清晰

 数据说明的方法

（1）数据说明的次序应该规范化

（2）说明语句中变量的安排有序化：如多个变量出现在同一个说明语句中，要按顺序排列。 （3）使用注释说明复杂的数据结构

 语句的结构（几个重要的方面）

（1）除非对效率有特殊要求，程序编写要做到清晰第一，效率第二

（2）尽可能使用库函数，且避免使用复杂的条件语句

(3)要模块化，且要利用信息隐蔽，确保每一个模块的性

 输入和输出

对所有输入数据检验合法性和输入数据时，应允许使用自由格式

*3. 对象是面向对象程序设计中的基本单位。对象可以表示客观世界中的任何实体，是对问题域中某个实体的抽象。对象通常由对象名、属性和操作三部分组成。

4. 类是对一组具有共同属性和相似行为的对象的一种抽象，类是对象的抽象，而对象是类的具体实例。

类是抽象的，不占用内存，而对象是具体的，占用存储空间。

5. 对象的特点: 标识唯一性、分类性、封装性、模块性、多态性和继承（分为单重基础和多重继承）。 6. 方法也可称为操作或服务，它描述了对象执行的功能，它是对象的动态属性。

*7. 消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的。消息由三部分组成： 消息标识符、零个或多个参数、接受消息对象的对象名

8. 面向对象程序设计的特点：稳定性好、可重用性好、易于开发大型软件、可维护性好。

9. 计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。 10. 所谓软件危机是指在计算机软件开发和维护过程中所遇到的一系列严重问题。

11. 为了消除软件危机，提出了软件工程学。软件工程是应用于计算机软件定义、开发和维护的一整套方法、工具、文档、实践标准和工序。

*12. 软件工程的三要素：方法、工具、过程。

13. 软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列工程活动。包括四种基本活动：P(Plan)：软件规格说明、D(Do)：软件开发、C(Check)：软件确认、A(Action)：软件演进。 14. 软件工程的基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。 *15. 软件工程的理论和技术性研究的内容包括：

 软件开发技术：软件开发方法学、开发过程、开发工具和软件工程环境  软件工程管理：软件管理学、软件工程经济学、软件心理学 *16. 衡量软件的指标：高内聚（模块内）、低耦合（模块间）。

17. 计算机辅助软件工程(CASE):是一组工具和方法集合。包括5个方面的集成：平台集成、数据集成、表示集成、控制集成、过程集成。

*18.软件的生命周期是软件从提出、实现、使用、维护到停止使用的过程，一般包括以下几个阶段：

 可行性研究：其实质是要进行一次简化、压缩了的需求分析

 需求分析：任务就是导出目标系统的逻辑模型，解决“做什么”的问题（即系统功能）。  软件设计：包括概要设计和详细设计。

 软件实现：把软件设计转换成计算机可以接受的程序代码。  软件测试:为发现错误而进行的活动。

 运行和维护：软件生命周期中所花费最多的阶段是软件运行维护阶段。

19. 需求分析阶段的主要工作：需求获取、需求分析、编写需求规格说明书(SRS)和需求评审。 20. 需求规格说明书是需求分析应交付的主要文档，也是需求分析的最后成果。需求规格说明书的特点是：

（1）正确性（2）无岐义性（3）完整性 （4）可验证性 （5）一致性 （6）可理解性（7）可追踪性。 *21. 结构化分析方法是一种建模技术。其实质着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。

*22. 结构化分析常用的工具：数据流图DFD， 数据字典DD ，判定树，判定表。（有时也用结构化语言） *23. 数据流图（DFD）：就是采用图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程。数据流图的基本元素有：数据源（终点) 、 数据流、 处理(加工) 、 数据存储。

 处理（加工）过程至少有一个输入数据流和一个输出数据流。  数据流程图上的每个元素都必须有名字。

*24. 数据字典（DD）是对数据流图中的各个元素进行完整的定义和说明，本质是一个数据库。作用是对数据流图中出现的被命名的图形元素的确切解释。

 数据字典通常包含5个部分：数据项、数据结构、数据流、数据存储和处理过程 。  数据字典是结构化分析的核心。

*25. 从技术角度出发软件设计包括：软件结构设计、数据设计、接口设计、过程设计。（每个设计的含义一定要记住，见“内部资料“P6！)

*26．从结构化设计角度看，软件设计分概要设计和详细设计两步完成。

 概要设计，即总体设计。将需求分析得到的DFD转化为转化为软件系统结构和全局数据结构、

确定数据库模式（即概要设计的功能）。

 概要设计的工具是结构图(SC)，结构图基本组成成分：模块、数据和调用.。

 详细设计即过程设计。功能是为软件结构图（SC）中的每一个模块确定采用的算法，模块内数

据结构，用某种选定的表达工具（如N-S图等）给出清晰的描述。

27. 需求分析的工具：（不要与方法弄混了，也不要与结构化分析工具弄混！！！） 问题分析图 （ PAD ）、程序流程图 （PFD ）、 N-S 图（盒图）

 程序流程图（PFD）中的箭头代表的是：控制流  数据流图中的箭头代表：数据的流向  结构图（sc):箭头代表模块的调用

*28. 软件测试是为了发现错误而执行程序的过程。（有时也解决存在的问题）测试的分类：

 从是否需要执行被测试软件的角度，可将测试分为静态测试和动态测试。  按照功能划分，可将软件测试分为黑盒测试和白盒测试。（有时也称白箱和黑箱测试）

29. 测试用例包括合理的和不合理的输入条件。好的测试用例指可能找到迄今为止尚未发现的错误的用例。 30. 静态测试主要包括代码检查、静态结构分析、代码质量度量等，它可以由人工进行 。

31．动态测试是通常意义上的测试，也就是运行和使用软件。是根据软件开发的各个阶段的规格说明和程序的内部结构而精心设计的一批测试用例，并利用这些测试用例去运行程序，以发现程序错误的过程。 *32. 黑盒测试将测试对象看作一个黑盒，不考虑程序内部的逻辑结构和内部特性，只依据程序的需求规格说明书，检查程序的功能是否符合它的功能说明。这种测试又称为功能测试或数据驱动测试。

 黑盒测试的方法：等价类划分法、边界值分析法、错误推测法、因果图法等。

*33. 白盒测试把测试对象看作一个透明的盒子，利用程序内部逻辑机构及有关信息，设计或选择测试用例，对程序的所有逻辑路径进行测试，确定实际的状态是否与预期的一致。又称为结构测试或逻辑驱动测试。

 白盒测试的方法：逻辑覆盖、基本路径测试等。

*34．软件测试按四个步骤（不同阶段）进行：单元测试、集成测试、确认测试、系统测试  单元测试：对软件设计的最小单位－模块进行正确性的测试，其目的是发现各模块内部可能

存在的各种错误。是在代码编写阶段可进行的测试，它是整个测试工作的基础。

 确认测试是验证软件的功能和性能是否满足需求规格说明中得各种需求，以及软件配置是否

完全、正确。

*35、程序调试的任务是诊断和修正程序中的错误。调试的方法：强行排错法、回溯法、原因排除法 *36、软件维护主要是指根据需求变化或硬件环境的变化对应用程序进行部分或全部的修改。 分类： 1.适应性维护 2.改善性维护 3.纠错性维护 4.预防性维护 （备注：每样维护要明白什么意思） 37、维护的副作用有编码副作用、数据副作用、文档副作用三种。

本部分典型例题：

1、程序设计语言的基本成分是数据成分、运算成分、控制成分和（D）

A）对象成分 B）变量成分 C）语句成分 D）传输成分 2、结构化程序设计主要强调的是 （D）

A）程序的规模 B）程序的效率 C）程序设计语言的先进性 D）程序易读性 3、对建立良好的程序设计风格，下面描述正确的是（A）

A）程序应简单、清晰、可读性好 B）符号名的命名只要符合语法 C）充分考虑程序的执行效率 D）程序的注释可有可无 4、NULL是指（C）

A）0 B）空格 C）未知的值或无任何值 D）空字符串

5、在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（C）

A）安全性 B）一致性 C）可理解性 D）合理性

6、子程序通常分为两类： 【过程】 和函数，前者是命令的抽象，后者是为了求值。 7、.在面向对象方法中，类之间共享属性和操作的机制称为 【继承】 。

8、一个类可以从直接或间接的祖先中继承所有属性和方法，提高了软件的 【可重用性】 9.软件的可行性研究中不包括（D）

Ａ、法律可行性 Ｂ、技术可行性 Ｃ、经济可行性 Ｄ、政治可行性 10.软件生产过程中，需求信息由（D ）给出。

A、程序员 B、项目管理者 C、软件分析设计人员 D、软件用户 11．可行性研究要进行一次（C）需求分析。

A．详细的 B．全面的 C．简化的、压缩的 D．彻底的 12、需求分析的任务不包括（B）

A问题分析 B系统设计 C 需求描述 D 需求评审。

13、1.对在数据流图中每一个命令的图形元素均给以定义是（B） Ａ、条目定义Ｂ、数据字典 Ｃ、数据定义Ｄ、数据说明

14. 结构化程序设计理论认为，实现良好的程序结构要应用（ A ）的分析方法。 A、自顶向下 B、自底向上 C、面向对象 D、基于组件

15.从事物的组成部件及每个部件的属性、功能来认识事物。这种方法被称为（A）的方法。 A、面向对象 B、面向数据 C、面向过程 D、面向属性 16.（D）工具在软件详细设计过程中不采用。 A．判定表 B．IPO图 C．PDL D．DFD图 17．程序的三种基本控制结构的共同特点是（:D）

A．不能嵌套使用 B．只能用来写简单程序 C．已经用硬件实现D．只有一个入口和一个出口 18.从工程管理的角度软件设计可分为概要设计和【详细】设计两大步骤。

19.流程图也称为程序框图是最常用的一种表示法，它有顺序、分支和【循环】三个基本控制构件。 20.软件可靠性是指在给定的时间间隔内，程序成功运行的【概率】 21. 软件工程时代的生产方式是【工程】化。

22. 结构化设计以（数据结构）为基础映射成软件结构。软件结构是以【模块】为基础而组成的一种控制层次结构。

23.在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是_(C)____ A. 循环的集合 B. 地址的集合 C. 路径的集合 D. 目标的集合 24.在设计测试用例时，应当包括（C）

Ａ、合理的输入条件 Ｂ、不合理的输入条件Ｃ、合理的和不合理的输入条件Ｄ、部分条件 25、与设计测试数据无关的文档是（D ）。

A、需求说明书 B、设计说明书 C、源程序 D、项目开发设计

26.对于软件测试分类，下列各项都是按照不同阶段来进行的划分，除了（C）。 A、单元测试 B、集成测试 C、黑盒测试 D、系统测试

27、为了进一步改善软件系统的可维护性和可靠性，并为以后的改进奠定基础的软件维护称为（D）。 A。纠错性维护 B适应性维护 C 改善性维护 D预防性维护

28. 为适应软件运行环境的变化而修改软件的活动称为（B）。 A.纠错性维护 B适应性维护 C 改善性维护 D预防性维护

29、根据用户在软件使用过程中提出的建设性意见而进行的维护活动称为（C）。 A纠错性维护 B适应性维护 C改善性维护 D预防性维护 30、为改正软件系统中潜藏的错误而进行的维护活动称为（A）。 A错性维护 B适应性维护 C 改善性维护D 预防性维护 31、以下不属于白盒测试技术的是（D）

A 逻辑覆盖 B基本路径测试 C循环覆盖测试 D等价类划分 32．产生软件维护的副作用，是指（C）

A．开发时的错误 B．隐含的错误 C．因修改软件而造成的错误 D．运行时误操作 33. 软件测试方法中（ D ）属于静态测试。

A 黑盒法 B 路径覆盖 C 错误推测 D 人工检测 34.黑盒测试主要是测试软件是否满足【功能】需求 。

35.程序设计语言的【可维护】性通常指这种语言编写的程序被理解，被修改及调整和改进的难易程度。 36.软常【单元测试】是在代码编写阶段可进行的测试，它是整个测试工作的基础。

37.若按功能划分，软件测试的方法通常分为白盒测试方法和【黑盒】测试方法。 按软件是否被执行，软件测试分为【动态测试】和【静态测试】。 38.维护的副作用有编码副作用、【数据副作用】、文档副作用三种。 39、软件按功能可以分为：应用软件、系统软件、和【工具软件】。 40、软件工程的出现是由于 【软件危机】。为了解决软件危机，人们提出了【软件工程学】的原理来设计软件，这就是软件工程诞生的基础。

41、在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为【消息】 42、需求分析中开发人员要从用户那里了解【软件做什么】。即需求分析任务是确定【软件系统功能】。 43、详细设计的结果基本决定了最终程序的【质量】。

44、开发大型软件时，产生困难的根本原因是【大型系统的复杂性】。

45、开发软件时对提高开发人员工作效率至关重要的是【先进的软件开发工具和环境】，而【计算机辅助软件工程】（或CASE）是一组工具和方法集合是软件开发全过程的软件工具集合。

第三部分 数据库设计基础（2-4题）

3.1 数据库系统的基本概念

1、数据、数据库、数据管理系统

（1）数据：实际上就是描述事物的符号记录。

（2）数据库（DB）：是有组织的相互关联数据的集合，具有集成与共享的特点。

（3）数据库管理系统（DBMS）：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。数据库管理系统功能：

1）数据模式定义。2）数据存取的物理构建。3）数据操纵。4）数据的完整性、安生性定义与检查。 5）数据库的并发控制与故障恢复。6）数据的服务。

（4）数据库管理员（DBA）：对数据库进行规划、设计、维护、监视等的专业管理人员。

（5）数据库系统（DBS）：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。

（6）数据库应用系统：由数据库系统、应用软件及应用界面三者组成。

*：数据库技术的根本目标是解决数据的共享问题。

*2、数据库系统的发展经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。 3、数据库系统的基本特点

（1）数据的高集成性。 （2）数据的高共享性与低冗余性。

*：数据库系统可以减少数据冗余，但无法避免一切冗余。

*（3）数据性：数据性一般分为物理性与逻辑性两级。

1）物理性：物理性即是数据的物理结构（包括存储结构，存取方式等）的改变，如存储设备的更换、物理存储的更换、存取方式改变等都不影响数据库的逻辑结构，从而不致引起应用程序的变化。 2）逻辑性：数据库总体逻辑结构的改变，如修改数据模式、增加新的数据类型、改变数据间联系等，不需要相应修改应用程序，这就是数据的逻辑性。 *4、数据库系统的三级模式：

1）概念模式：数据库系统中全局数据逻辑结构的描述，是全体用户（应用）公共数据视图。

2）外模式：也称用户模式，它是用户的数据视图，用户所见到的数据模式，它由概念模式推导而出。 3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。 5、数据库系统的两级映射：

1）概念模式/内模式的映射：保证数据具有很高的物理性。 2）外模式/概念模式的映射：保证数据具有较高的逻辑性。 *3.2 数据模型

1、数据模型是数据特征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示与操作提供一个抽象的框架。

 数据模型所描述的内容有三个部分，它们是数据结构、数据操作与数据约束。  数据模型分为概念模型、逻辑数据模型和物理模型三类：

2、概念数据模型：简称概念模型，是对客观世界复杂事物的结构描述及它们之间的内在联系的刻画。概念模型主要有：E-R模型(实体联系模型)、扩充的E-R模型、面向对象模型及谓词模型等。

3、逻辑数据模型：又称数据模型，是一种面向数据库系统的模型，该模型着重于在数据库系统一级的实现。逻辑数据模型主要有：层次模型、网状模型、关系模型、面向对象模型等。 4、物理数据模型：又称物理模型，给出了数据模型在计算机上物理结构的表示。 5、E-R模型的基本概念：

1）实体：现实世界中的事物。 2）属性：事物的特性。

3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。 *：E-R模型的基本成分是实体和联系。

6、数据库管理系统常见的数据模型有层次模型、网状模型和关系模型三种。 7、关系模型的一些概念和特征：（自己再看看！！）

 关键字（不能取空值）、属性、元组、外部关键字、域、关系模式  一些约束（特征）：不能有相同元组、列不可分解等等。

8、关系中的数据约束：1）实体完整性约束。2）参照完整性约束 3）用户定义的完整性约束 9、关系操纵（即数据操纵）是建立在关系上的数据操纵，一般有查询、增加、删除和修改四种操作。 10、传统的集合运算（1）并（∪） （2）差（－）（3）交（∩）

专门的关系运算：选择、投影、连接运算 广义笛卡尔积（×） *3.3 数据库设计方法和步骤

1）需求分析阶段：这是数据库设计的第一个阶段，任务主要是收集和分析数据。

2）概念设计阶段：分析数据间内在语义关联，在此基础上建立一个数据的抽象模型，即形成E-R图。

*：数据库概念设计的过程包括选择局部应用、视图设计和视图集成。 3）逻辑设计阶段：将E-R图转换成指定RDBMS中的关系模式。

4）物理设计阶段：对数据库内部物理结构作调整并选择合理的存取路径。

本部分典型例题

1、关系中属性个数称为“元数”，元组个数称为（ C ）。

A、行数 B、列数 C、基数 D、超键 2、SQL的主码子句和外码子句属于DBS的 A 。

A、完整性措施 B、安全性措施 C、恢复措施 D、并发控制措施 3、概念设计结果是（ B ）。

A、一个与DBMS相关的概念模式 B、一个与DBMS无关的概念模式 C、数据库系统的公用视图 D、数据库系统的数据字典

4、关系模型的完整性规则不包括（ D ）。

A、实体完整性规则 B、参照完整性规则 C、用户自定义的完整性规则 D、数据操作性规则

5、关系R，S和T如下。关系T是由关系R和S经过哪种操作得到的？( A )

A、R S B、R－S C、R×S D、R∪S

6、设关系R、S、W各有10个元组，那么这3关系的自然联接的元组个数为（ D ）。 A、10 B、30 C、1000 D、不确定（与计算结果有关） 7、数据管理的三个阶段中，由应用程序管理数据的阶段是 D A、数据库系统阶段 B、人工管理阶段、文件系统阶段和数据库系统阶段 C、人工管理阶段和文件系统阶段 D、只有人工管理阶段

8、在概念模型中，一个实体相对于关系数据库中一个关系中的一个 B 。

A、属性 B、元组 C、列 D、字段 9、三级模式间存在两种映像，它们是 D 。

A、内模式与子模式之间，模式与内模式之间 B、子模式与内模式之间，外模式与内模式之间 C、子模式与外模式之间，模式与内模式之间 D、模式与内模式之间，模式与外模式之间 10、ER方法的三要素是（ C ）。

A、实体、属性、实体集 B、实体、键、属性 C、实体、属性、联系 D、实体、域、联系 11、设关系R和S的结构相同,且各有10个元组,那么这两个关系的并操作结果的元组个数为（ B ）。

A、20 B、≤20 C、10 D、≤10

12、概念结构设计主要目标是产生数据库的概念结构，该结构主要反映 （ D ）。

A、应用程序员的编程需求 B、DBA的管理信息需求 C、数据库系统的维护需求 D、企业组织的信息需求

13、设一关系模式为：运货路径（顾客姓名，顾客地址，商品名，供应商姓名，供应商地址），则该关系

模式的主键是（ C ）。

A、顾客姓名，供应商姓名，供应商地址 B、顾客姓名，商品名 C、顾客姓名，商品名，供应商姓名 D、顾客姓名，顾客地址 14、在关系模型中，关系的“基数”是指（ B ）。

A、属性个数 B、元组个数 C、关系个数 D、列数 15、在关系模型中,下列说法正确的是（ D ）。

A、关系中存在可分解的属性值 B、关系中允许出现相同的元组

C、考虑元组的顺序 D、元组中理论上属性是无序的,但使用时按习惯考虑列的顺序 17、数据库恢复的重要依据是（ D ）。

A、DBA B、DD C、文档 D、事务日志 18、关系模型的完整性规则不包括（ D ）。

A、实体完整性规则 B、参照完整性规则 C、用户自定义的完整性规则 D、数据操作性规则

19、把E→R图转换成关系模型的过程，属于数据库设计的 B 。

A、概念设计 B、逻辑设计 C、需求分析 D、物理设计 20、下列实体类型的联系中，属于一对多联系的是（ B ）。

A、学生对课程的所属联系 B、父亲对孩子的亲生联系 C、省对省会的所属联系 D、商店对顾客之间的联系 21、对表进行水平方向的分割用的运算是 C 。

A、交 B、投影 C、选择 D、连接 22、逻辑数据性是指（ A ）。

A、概念模式改变，外模式和应用程序不变 B、概念模式改变，内模式不变 C、内模式改变，概念模式不变 D、内模式改变，外模式和应用程序不变 23、层次模型只能表示1：m联系，对表示m：n联系则很困难，而且层次顺序严格，这是该模型的 C 。

A、严格性 B、复杂性 C、缺点 D、优点

24、设F是基本关系R的一个或一组属性，但不是关系R的码。如果F与基本关系S的主码Ks相对应，则称F是基本关系R的 D 。

A、候选码 B、主码 C、全码 D、外码 25. 分布式数据库系统不具有的特点是（D）

A）数据分布性和逻辑整体性 B）位置透明性和复制透明性 C）分布性 D）数据冗余 26、.在基本SQL语言中，不可以实现( D)

A.定义视图 B.定义基表 C.查询视图和基表 D.并发控制 27.下列四项中，必须进行查询优化的是 (A )

A.关系数据库 B.网状数据库 C.层次数据库 D.非关系模型 28．关系数据库中的视图属于4个数据抽象级别中的 （A） A 外部模型 B 概念模型 C 逻辑模型 D 物理模型

29．关系数据库中，实现实体之间的联系是通过表与表之间的（D） A 公共索引 B 公共存储 C 公共元组 D 公共属性

30．为了防止一个用户的工作不适当地影响另一个用户，应该采取（C） A 完整性控制 B 安全性控制 C 并发控制 D 访问控制 31．有一关系：学生（学号，姓名，系别），规定学号的值域是8个字符，这一规则属于（C） A 实体完整性约束 B 参照完整性约束 C 用户自定义完整性约束 D 关键字完整性约束 32、下列数据模型中，具有坚实理论基础的是（C）

A）层次模型 B）网状模型 C）关系模型 D）以上3个都是 33、）数据库的故障恢复一般是由（C）

A）数据流图完成的 B）数据字典完成的 C）DBA完成的 D）PAD图完成的 34、下列说法中，不属于数据模型所描述的内容的是（C）

A）数据结构 B）数据操作 C）数据查询 D）数据约束

35、在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有（A） A）特定的数据模型 B）数据无冗余 C）数据可共享 D）专门的数据管理软件 36、下列关系运算的叙述中，正确的是（C）

A）投影、选择、连接是从二维表行的方向进行的运算B）并、交、差是从二维表的列的方向来进行运算 C）投影、选择、连接是从二维表列的方向进行的运算 D）以上3种说法都不对 37、一个关系中属性个数为1时，称此关系为（C）

A）对应关系 B）单一关系 C）一元关系 D）二元关系 38、为用户与数据库系统提供接口的语言是（C）

A）高级语言 B）数据描述语言（DDL）C）数据操纵语言（DML） D）汇编语言 39、相对于数据库系统，文件系统的主要缺陷有数据关联差、数据不一致性和（D） A）可重用性差 B）安全性差 C）非持久性 D）冗余性 40、下列叙述中，正确的是（C）

A)用E-R图能够表示实体集间一对一的联系、一对多的联系和多对多的联系 B)用E-R图只能表示实体集之间一对一的联系 C)用E-R图只能表示实体集之间一对多的联系

D)用E-R图表示的概念数据模型只能转换为关系数据模型 41、“年龄在18～25之间”这种约束是属于数据库当中的（C）

A)原子性措施 B)一致性措施 C)完整性措施 D)安全性措施 42、【数据模型】 是数据库设计的核心。

43、关系操作的特点是 【集合】 操作。

44、数据库恢复是将数据库从 【错误】 状态恢复到某一已知的正确状态。