数据库系统工程师基础知识（选择题）模拟试卷8

数据库系统工程师基础知识（选择题）模拟试卷8

中文选择题（含3小题）

在图4-14中，(39)是非简单图，(40)是完全图，(41)和(42)都是哈密尔顿图，其中(41)又是欧拉图，(43)是树。

1.

A

解析：

2.

A

解析：

3.

B

解析：

4.

D

解析：本题主要考查一些特殊图的概念，下面分别进行介绍。

非简单图：既无平行边也无环的无向图称为简单无向图，有平行边或有环的图是非简单图。在本题中，只有B有环，其余的5个图都既无平行边也无环，因而(26)的答案应为B。

完全图：每个顶点度数都等于n-1的n阶无向简单图称为n阶无向完全图，并记为 kn。在给定的6个图中，只有A图满足要求，它是k5，所以(27)的答案为A。

哈密尔顿图：通过连通图中所有结点一次且仅一次的回路称为哈密尔顿回路，具有哈密尔顿回路的图称为哈密尔顿图。一个图是哈密尔顿图的必要条件(注意：不是充分条件)是图的连通性和图中不存在度数为1的顶点。在本题中，E图是分离的k3，即E是非连通图，而C、D、F均有度数为1的顶点，所以C、D、E、F都不是哈密尔顿图。 A、B中均存在哈密尔顿回路，因而A、B均为哈密尔顿图。所以(28)、(29)的答案可以为A、B。

欧拉图：通过连通图(有向图或无向图)中每条边一次且仅一次遍历图中所有顶点的回路，称为欧拉回路，存在欧拉回路的图称为欧拉图。设G是连通图，则G是欧拉图，当且仅当G的所有顶点都是偶顶点(度数为偶数的顶点)。在本题中，只有A连通且无奇度顶点，因而A为欧拉图，在其余各图中，E无奇度顶点，但它不连通，所以不是欧拉图。而B、C、D、F中都有奇度顶点，因而它们也不是欧拉图，所以(28)的答案为A，(29)的答案为B。

树：连通且无回路的无向图称为无向树。在本题中，只有D满足要求，其余5个图中均有回路，因而都不是树，(30)的答案为D。

另外，还有一些特殊的图，我们也简单介绍一下。

平面图：平面图是指一个图能画在平面上，除顶点之外，再没有边与边相交。在本题中，B、C、D、F为平面图。

二部图：若能将无向图的顶点集V划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图(也称为偶图)。在本题中， D为二部图。

给定数据结构(V，E)，V为结点的有限集合，V＝{V1，V2，V3，V4，V5，V6，V7，V8)，E是V上关系的集合。E＝{＜V1，V2＞，＜V3，V4＞，＜V5，V8＞，＜V5，V6＞，＜V1，V3＞，＜V4，V7＞，＜V4，V5＞，＜V2，V4＞，＜V4，V6＞)，它所对应的图形是(44)，这是(45)。

图的存储结构主要有邻接表和(46)，若用邻接表来存储一个图，则需要保存一个(47)存储的结点表和若干个(48)上存储的关系表(又称边表)。

5.(B)

A. 无向树

B. 无向图

C. 有向图

D. 有向树

解析：

6.(B)

A. 转移矩阵

B. 邻接矩阵

C. 状态矩阵

D. 优先矩阵

解析：

7.(A)

A. 顺序

B. 链接

C. 散列

D. 分块

解析：

8.(B)

A. 顺序

B. 链接

C. 散列

D. 索引

解析：题目第一问是求原题所给数据结构表示的图。我们可以先在纸上画出V1～V8这8个顶点，然后看边关系召，召集合的第一个元素是：＜V1，V2＞，这表示在V1和V2之间有一条边，如图4-20所示。

接下来是＜V3，V4＞，所以在V3和V4之间也有一条边，如图4-21所示。

二叉树的前序、中序和后序遍历法最适合采用(49)来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为(50)，而使上述路径长度总和达到最小的树称为(51)，它一定是(52)。在关于树的几个叙述中，只有(53)是正确的。

9.(B)

A. 路径和

B. 内部路径长度

C. 总深度

D. 深度和

解析：

10.(C)

A. B树

B. B+树

C. 丰满树

D. 穿线树

解析：

11.(B)

A. B树

B. 平衡树

C. 非平衡树

D. 穿线树

解析：

12.(C)

A. 用指针方式存储有n个结点的二叉树，至少要有n+1个指针

B. m阶B树中，每个非叶子结点的后件个数大于等于C. m阶B树中，具有k个后件的结点，必含有k-1个键值

D. 平衡树一定是丰满树

解析：由于二叉树的前序、中序和后序遍历方法都是递归定义的，所以最适合采用递归程序来实现。此外，递归程序的实现基础是栈操作，所以二叉树的遍历也可以使用栈操作来完成，但是用栈操作来实现遍历的程序逻辑结构没有递归程序那么清晰，而且用栈来实现的二叉树遍历代码比较难懂，其优点是代码的机器执行效率较高。

在查找二叉树中，由根结点到所有其他结点的路径长度总和称为内部路径长度。具有最小内部路径长度的树称为丰满树，对丰满查找树进行插入或者删除操作后，会产生一棵非丰满树。

为了保证查找二叉树的高度为log₂n，从而保证在查找二叉树上实现的插入、删除和查找等基本操作的平均时间为O(log₂n)，往树中插入或删除结点时，要调整树的形态来保持树的“平衡”，使之既保持查找二叉树性质不变，又保证树的高度在任何情况下均为O(log₂n)，从而确保树上的基本操作在最坏情况下的时间均为O(log₂n)。

平衡二叉树是指树中任一结点的左、右子树的高度大致相同，即平衡树上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近，但是在插入或者删除结点时，平衡树能动态地调整保持平衡的特点。

如果任一结点的左、右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(log₂n)，就可看做是平衡的。平衡二叉树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的平衡二叉树的高度约为1.44log₂n。而完全平衡的二叉树高度约为log₂n，平衡二叉树是接近最优的。

根据丰满树和平衡树的定义可知，丰满树一定是平衡树，但平衡树不一定是丰满树。

本文档预览：3600字符，共10667字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载