2013年上半年软考《数据库系统工程师》上午模拟试卷一

1: (70)

A．n+4
B．n+8
C．n+12
D．n+16

查看答案

2: (69)

A．n+4
B．n+8
C．n+12
D．n+16

查看答案

3: (67)

A．EAFCBD
B．EFACDB
C．EABCFD
D．EACBDF

查看答案

4: (68)

A．n+9
B．n+10
C．n+12
D．n+13

查看答案

5: 一棵查找二叉树，其结点A，B，C，D，E，F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中，每个结点占4个字节：前2个字节存放结点值，后2个字节依次放左指针、右指针。若该查找二叉树的根结点为万，则它的一种可能的前序遍历为(54)，相应的层次遍历为(55)。在以上两种遍历情况下，结点C的左指针L_C的存放地址为(56)，　L_C的内容为(57)。结点A的右指针凡的内容为(58)。

A．EAFCBD
B．EFACDB
C．EABCFD
D．EACBDF

查看答案

6: (65)

A．用指针方式存储有n个结点的二叉树，至少要有n+1个指针
B．m阶B树中，每个非叶子结点的后件个数大于等于<IMG src="//img1.yqda.net/question-name/7f/de8d756316f3b9f72bfc21dd30612b.jpg">
C．m阶B树中，具有k个后件的结点，必含有k-1个键值
D．平衡树一定是丰满树

查看答案

7: (63)

A．B树
B．B+树
C．丰满树
D．穿线树

查看答案

8: (64)

A．B树
B．平衡树
C．非平衡树
D．穿线树

查看答案

9: (62)

A．路径和
B．内部路径长度
C．总深度
D．深度和

查看答案

10: (60)

A．顺序
B．链接
C．散列
D．索引

查看答案

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

A．递归程序
B．迭代程序
C．队列操作
D．栈操作

查看答案

12: (57)

A．无向树
B．无向图
C．有向图
D．有向树

查看答案

13: (58)

A．转移矩阵
B．邻接矩阵
C．状态矩阵
D．优先矩阵

查看答案

14: (59)

A．顺序
B．链接
C．散列
D．分块

查看答案

15: 给定数据结构(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)上存储的关系表(又称边表)。

A．<IMG src="//img1.yqda.net/question-name/29/02936a3db5e4416b2c8afb376f8b55.jpg">
B．<IMG src="//img1.yqda.net/question-name/cf/002b63291a7b1d24deb3233f0060b1.jpg">
C．<IMG src="//img1.yqda.net/question-name/52/c6338faacafeaabf71d786e8da662d.jpg">
D．<IMG src="//img1.yqda.net/question-name/b7/1c1c4a275c3af49f54e35996aa678c.jpg">

查看答案

16: (55)

查看答案

17: (54)

查看答案

18: (52)

查看答案

19: (53)

查看答案

20: (50)

A．PBQHCJ
B．PBHCJQ
C．BCHJPQ
D．CJHBQP
E．BHCJQP

查看答案

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

查看答案

22: (48)

A．1003
B．1004
C．100A
D．1009
E．1006

查看答案

23: (49)

A．PBQHCJ
B．PBHCJQ
C．BCHJPQ
D．CJHBQP
E．BHCJQP

查看答案

24: (47)

A．1003
B．1004
C．100C
D．1009
E．1006

查看答案

25: 一棵二叉排序树可顺序存放在一组物理上相邻的存储区中，每个结点及左、右指针依次分别放在该存储区的3个连续单元中。现对一棵结点按字母的字典顺序构成的二叉排序树从根结点户开始顺序放在一个存储区中，结果如图4-13所示。其中Li为第i个结点的左指针，Ri为第i个结点的右指针，则L2应为(34)，L4应为(35)，R1应为(36)。该二叉排序树的前序遍历序列为(37)，后序遍历序列为(38)。

A．1006
B．1004
C．100A
D．1009
E．1006

查看答案

26: (45)

A．O(1)
B．O(nlog2n)
C．O(n)
D．O(n2)
E．O(log2n)

查看答案

27: (43)

A．O(1)
B．O(nlog2n)
C．O(n)
D．O(n2)
E．O(n(log2n)2)

查看答案

28: (44)

A．O(1)
B．O(nlog2n)
C．O(n)
D．O(n2)
E．O(n(log2n)2)

查看答案

29: (42)

A．O(1)
B．O(nlog2n)
C．O(n)
D．O(n2)
E．O(n(log2n)2)

查看答案

30: 对由n个记录所组成的有序关键码排序时，下列各常用排序算法的平均比较次数分别是：二路归并排序为(29)，冒泡排序(30)，快速排序为(31)。其中，归并排序和快速排序所需要的辅助存储分别是(32)和(33)。

A．O(1)
B．O(nlog2n)
C．O(n)
D．O(n2)
E．O(n(log2n)2)

查看答案

31: (40)

A．F，H，C，D，P，A，M，Q，R，S，Y，X
B．P，A，C，S，Q，D，F，X，R，H，M，Y
C．A，D，C，R，F，Q，M，S，Y，P，H，X
D．H，C，P，A，M，S，R，D，F，X，Y
E．H，Q，C，Y，A，P，M，S，D，R，F，X

查看答案

32: (39)

A．F，H，C，D，P，A，M，Q，R，S，Y，X
B．P，A，C，S，Q，D，F，X，R，H，M，Y
C．A，D，C，R，F，Q，M，S，Y，P，H，X
D．H，C，P，A，M，S，R，D，F，X，Y
E．H，Q，C，Y，A，P，M，S，D，R，F，X

查看答案

33: (38)

A．F，H，C，D，P，A，M，Q，R，S，Y，X
B．P，A，C，S，Q，D，F，X，R，H，M，Y
C．A，D，C，R，F，Q，M，S，Y，P，H，X
D．H，C，P，A，M，S，R，D，F，X，Y
E．H，Q，C，Y，A，P，M，S，D，R，F，X

查看答案

34: (37)

A．F，H，C，D，P，A，M，Q，R，S，Y，X
B．P，A，C，S，Q，D，F，X，R，H，M，Y
C．A，D，C，R，F，Q，M，S，Y，P，H，X
D．H，C，P，A，M，S，R，D，F，X，Y
E．H，Q，C，Y，A，P，M，S，D，R，F，X

查看答案

35: (35)

A．O(1)
B．O(log2n)
C．O(log2n2)
D．O(nlog2n)
E．O(n)

查看答案

36: 在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列{Q，H，C，Y，P，A，M，S，R，D，F，　X}中的关键码按字母的升序重新排列，则(24)是冒泡排序一趟扫描的结果，(25)是初始步长为4的希尔排序一趟扫描的结果，(26)是两路归并(合并)排序一趟扫描的结果，(27)是以第一个元素为分界元素的快速排序一趟扫描的结果，(28)是堆排序初始建堆的结果。

A．F，H，C，D，P，A，M，Q，R，S，Y，X
B．P，A，C，S，Q，D，F，X，R，H，M，Y
C．A，D，C，R，F，Q，M，S，Y，P，H，X
D．H，C，P，A，M，S，R，D，F，X，Y
E．H，Q，C，Y，A，P，M，S，D，R，F，X

查看答案

37: (34)

A．O(1)
B．O(log2n)
C．O(log2n2)
D．O(nlog2n)
E．O(n)

查看答案

38: (32)

A．O(1)
B．O(log2n)
C．O(log2n2)
D．O(nlog2n)
E．O(n)

查看答案

39: (33)

A．O(1)
B．O(log2n)
C．O(log2n2)
D．O(nlog2n)
E．O(n)

查看答案

40: 在查找算法中，可用平均查找长度(记为ASL)来衡量一个查找算法的优劣，其定义为：

此处P_i为表中第i个记录被查找的概率，C_i为查找第i个记录时同关键字比较的次数，n为表中记录数。
以下叙述中均假定每一个记录被查找的概率相等，即P_i=//n(i=1，2，…，n)。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19)，折半查找时的ASL为(20)。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为(21)。当二叉排序树是一棵平衡树时，ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形下需(23)次旋转。

A．O(1)
B．O(log2n)
C．O(log2n2)
D．O(nlog2n)
E．O(n)

查看答案

41: (30)

A．<IMG src="//img1.yqda.net/question-name/af/e8068f5ebe3bb79bef47bf5ae6e7d0.jpg">
B．<IMG src="//img1.yqda.net/question-name/b5/8de2a782f092bcf517cfb66132d391.jpg">
C．<IMG src="//img1.yqda.net/question-name/94/1e396fca2f7a3920e38aa545c1c985.jpg">

查看答案

42: (27)

A．FGILJMKH
B．FGILJKHM
C．FGILJKMH
D．FGHMILJK
E．FGHILJKM

查看答案

43: (28)

A．<IMG src="//img1.yqda.net/question-name/61/36e02b31d7432b4c1c5b214a0eb0a2.jpg">
B．<IMG src="//img1.yqda.net/question-name/91/320ee38b41f3cd6c3c96c2395f65ab.jpg">
C．<IMG src="//img1.yqda.net/question-name/3c/edd5a82c4989987f15a0fcd731f3eb.jpg">

查看答案

44: (29)

A．FGILJMKH
B．FGILJKHM
C．FGILJKMH
D．FGHMILJK
E．FGHILJKM

查看答案

45: (25)

A．2.8
B．3.4
C．3.8
D．4.2

查看答案

46: 已知某图的邻接表如图4-12所示。

①此邻接表所对应的无向图为(14)。
②此图由F开始的深度优先遍历为(15)。
③此图由9开始的深度优先遍历的支撑树为(16)。
④此图由F开始的广度优先遍历为(17)。
⑤此图由9开始的广度优先遍历的支撑树为(18)。

A．<IMG src="//img1.yqda.net/question-name/e1/f24b5cf8cf40e41128c86d673e1147.jpg">
B．<IMG src="//img1.yqda.net/question-name/34/e1bfea50144c43d4e1828d7a5cfd52.jpg">
C．<IMG src="//img1.yqda.net/question-name/1b/df3a9911bcd3f49eca961512d014ed.jpg">

查看答案