发布时间 : 星期二 文章软件技术基础总复习题及参考答案更新完毕开始阅读
1q->front->next=lq->rear 。
58、 设高度为 h 的二又树只有度为 O 和 2 的结点，则此类二叉树的结点数至少为
（ 2h-1 ），至多为（ 2n-1 ）。
59、 在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等
于该顶点的 度
；对于有向图来说等于该顶点的_ 出度
。
60、 在有序表 A[1..20]中，按二分查找方法进行查找，查找长度为 5 的元素个数是
5 。 61、 若以{4，5，6，7，8}作为叶
子节点的权值构造哈夫曼树，则该 Huffman 树的根
结点权值为 30 。
62、 当 待排数据本身已排好序 时，快速排序算法的时间复杂性最差。
63、 n(n>0)个结点构成的二叉树，若二叉树有 m 个叶结点，则度为 2 的结点有 m-1 个64、 直接插入排序，起泡排序和快速排序三种方法中， 快速排序 所需的平均执 行时
间最小。 65、 若对序列（7，3，1，8，6，2，4，5）按从小到大排序，请写出冒泡排序的第
一趟结果 3 1 7 6 2 4 5 8 。
66、 栈的特点是 先进后出 ，队列的特点是 后进先出 。 67、 在一棵完全二叉树中，若编号为 i 的结点有右孩子，则该右孩子结点的编号为
2i+1 。 68、 已知 8 个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点
的方法生成一棵二叉排序树，则该树的深度为 5 。 69、 在二叉树的第 i 层上至多有 2i-1 结点
70、 数据的存储结构被分为顺序结构、链接结构、 索引结构 、 散列结构 四 种。 71、 线性结构反映结点间的逻辑关系是 一对一 的，图中的数据元素之间的关系 是
多对多 的，树形结构中数据元素间的关系是 一对多 的。 72、 栈、队列逻辑上都是 线性存储 结构。
73、 在一个无向图中，所有顶点的度数之和等于所有边数的 ２ 倍。在一个 具有 n
个顶点的无向完全图中，包含有 n(n-1)/2 条边，在一个具有 n 个顶 点的有向完全图中，包含有 n(n-1) 条边。
74、 在插入和选择排序中，若初始数据基本正序，则选择 插入排序 ，若初始数 据基
本反序，则最好选择 选择排序 。 75、 35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其
进行归并排序的过程中，第二趟排序后的结果是 ［３８ ４６ ５６ ７９］ ［４０ ８０］ 。
76、 实体完整性要求主属性不能取空值，这一点可以通过 定 义主 码 来保证。 77、 关系模型的基本数据结构是 关系（或二维表 ，其数据库存储时的基
本组织方式是 文件 。
参照完整性规则是对 外码 78、 实体完整性规则是对 主码_ 的约束， 的约束。
。 79、 关系代数的理论基础是 集合论（或集合代数）_ 80、 关系的并、差、交操作，要求两个关系具有 相同的关系模式（或相同的结构）
。
81、 数据库是长期存储在计算机内、有组织的、可_ 共享 _的数据集合。
82、 已知系（系编号，系名称，系主任，电话，地点）和学生（学号，姓名，性别，
入日期，专业，系编号）两个关系，学生关系的关键字是 学号 ，外关 键字是 系编号 。 83、 SQL 语言提供数据库定义、 数据操纵_ 、数据控制等功能。
84、 数据库保护问题包括：
多方面。
安全性保护 、完整性、故障恢复和并发控制等
85、 关系代数中专门的关系运算包括：选择、投影、连接和
除法 。
86、 若关系中的某一属性组（或单个属性）的值能惟一标识一个元组，则称该属性
组（或属性）为 候选码
。
87、 数据库的 完整性 是指数据的正确性和相容性。
88、 在关系数据模型中，两个关系 R1 与 R2 之间存在 1 ∶ M 的联系，可以通过
在一个关系 R2 中的 中外部关键字值 检索相对应的记录。
89、 数据库的逻辑模型设计阶段，任务是将
在相关联的另一个关系 R1
E-R 模型 转换成关系模型。
90、 关系中主码的取值必须唯一且非空，这条规则是 实体 完整性规则。
91、 在关系代数中，交操作可由 差 操作组合而成。 92、 设一个关系 A 具有 a1 个属性和 a2 个元组，关系 B 具有 b1 个属性和 b2 个元组， 则关系 A×B 具有 a1+b1 个属性和 a2*b2 个元组。 93、
关系的完整性包括 实体 、 参照 和 用户定义 三个
方面的完整性
94、 数据库系统的三级模式结构由 外模式 、 概念模式 和 内模式
组成。 95、 关系中主码的取值必须唯一且非空，这条规则是 实体 完整性规则。 96、 构成数据模型的三大要素是 数据结构 、数据操作和数据完整性约束。 97、 专门的关系运算包括 选择 、 投影 、 连接 和除四种。
三、 简答题
1、 简述一个算法具有哪些重要特性？
参考答案：
有穷性：执行有穷步后结束； 确定性：具有一条惟一的执行路径； 可行性：算法实施后能得到预期的解； 输入：有零个或多个输入； 输出：应有一个或多个输出。
2、 简述算法设计有哪些要求？
参考答案：
正确性：能满足具体问题的需求； 可读性：利于理解；
健壮性：对非法输入也能作出适当反应；
效率高与低在存储量需求：执行时间短，最大存储空间要求低
3、 在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？
参考答案： 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元， 因此叫假溢出； 解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。
4、 线性结构与非线性结构有何差别？
参考答案： 线性结构的前驱与后继之间为一对一关系，非线性结构的前驱与后继之间通常为一 对多或多对多关系。
5、 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
参考答案： 1)从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表 作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因 此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序 存储结构。
2)从时间上看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用 顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。
6、 说明在图的遍历中，设置访问标志数组的作用。
参考答案： 图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。
7、 简述顺序表和链表存储方式的特点。
参考答案： 顺序表的优点是可以随机访问数据元素；
缺点是大小固定，不利于增减结点（增减操作需要移动元素）。 链表的优
点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动 结点）。
其缺点是不能进行随机访问，只能顺序访问； 另外，每个结点上增加指针域，造成额外存储空间增大。
8、 设教学数据库中，有两个基本表：
学生表：S（S#，SNAME，AGE，SEX） 学习表：SC（S#，C#，GRADE） 现有一个 SQL 语句：
SELECT SEX，AGE，AVG（GRADE） FROM S，SC
WHERE S.S# = SC.S# GROUP BY SEX，AGE ORDER BY 3 DESC；
试写出与此语句等价的汉语查询语句。
参考答案：
检索每一性别每一年龄的学生的平均成绩； 显示时，按平均成绩降序排列。
9、 设教学数据库中，有两个基本表：
学生表：S（S#，SNAME，AGE，SEX） 学习表：SC（S#，C#，GRADE） 现有一个 SQL 语句： SELECT S# FROM S
WHERE S# NOT IN （SELECT S#