试卷详情
-
数据库系统工程师-数据结构与算法(二)
-
[单项选择]
在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是 (16) 。
16()
从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为 (17) 。设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好选用 (18) 排序法。
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
-
[单项选择]
哈希存储的基本思想是根据 (36) 来决定 (37) ,冲突(碰撞)指的是 (38) , (39) 越大,发生冲突的可能性也越大。处理冲突的两种主要方法是 (40) 。
36()
A. 存储地址
B. 元素的序号
C. 元素个数
D. 关键码值
-
[单项选择]综合局部er图生成总体er图过程中,下列说法错误的是()
A. 不同局部er图中出现的相同实体,在总体er图中只能出现一次。
B. 在总体er图中可以添加属于不同局部er图实体间的联系。
C. 在总体er图中可以添加局部er图中不存在的联系。
D. 在总体er图中不可以删除任何实体间的联系。
-
[单项选择]
二叉树的前序、中序和后序遍历法最适合采用 (1) 来实现。
1()
查找树中,由根结点到所有其他结点的路径长度的总和称为 (2) ,而使上述路径长度总和达到最小的树称为 (3) 。它一定是 (4) 。
在关于树的几个叙述中,只有 (5) 是正确的。
A. 递归程序
B. 迭代程序
C. 队列操作
D. 栈操作
-
[单项选择]
一棵查找二叉树,其结点A、B、C、D、E、F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中,每个结点占4个字节:前二个字节存放结点值,后二个字节依次放左指针、右指针。若该查找二叉树的根结点为E,则它的一种可能的前序遍历为 (6) ,相应的层次遍历为 (7) 。在以上两种遍历情况下,结点 C的左指针Lc的存放地址为 (8) ,Lc的内容为 (9) 。结点A的右指针Ra的内容为 (10) 。
6()
A. EAFCBD
B. EFACDB
C. EABCFD
D. EACBDF
-
[单项选择]
二叉树 (31) 。在完全二叉树中,若一个结点没有 (32) ,则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里,一个结点N的左子树是N在原树里对应结点的 (33) ,而N的右子树是它在原树里对应结点的 (34) 。二叉排序树的平均检索长度为 (35) 。
31()
A. 是特殊的树
B. 不是树的特殊形式
C. 是两棵树的总称
D. 是只有两个根结点的树状结构
-
[单项选择]
设二维数组F的行下标为1~5,列下标为0~8,F的每个数据元素均占4个字节。在按行存储的情况下,已知数据元素F[2,2]的第一个字节的地址是1044,则F[3,4]和F[4,3]的第一个字节的地址分别为 (41) 和 (42) ,而数组的第一个数据元素的第一个字节和数组最后一个元素的最后一个字节的地址分别为 (43) 和 (44) 。
41()
对一般的二维数组G而言,当 (45) 时,其按行存储的G[i,j]的地址与按列存储的G[j,i]的地址相同。
A. 1088
B. 1084
C. 1092
D. 1120
-
[单项选择]
哈希存储的基本思想是根据(61)来决定(62),冲突(碰撞)指的是(63),(64)越大,发生冲突的可能性也越大。处理冲突的两种主要方法是(65)。
61()
A. 存储地址
B. 元素的序号
C. 元素个数
D. 关键码值
-
[单项选择]
某顺序存储的表格,其中有90000个元素,已按关键字递增有序排列,现假定对各个元素进行查找的概率是相同的,并且各个元素的关键字皆不相同。
46()
用顺序查找法查找时,平均比较次数约为 (46) ,最大比较次数为 (47) 。
现把90000个元素按排列顺序划分成若干组,使每组有g个元素(最后一组可能不足 g个)。查找时,先从第一组开始,通过比较各组的最后一个元素的关键字,找到欲查找的元素所在的组,然后再用顺序查找法找到欲查找的元素。在这种查找法中,使总的平均比较次数最小的g是 (48) ,此时的平均比较次数是 (49) 。当g的值大于等于 90000时,此方法的查找速度接近于 (50) 。
A. 25000
B. 30000
C. 45000
D. 90000
-
[单项选择]下列聚合函数中不忽略空值(null)的是()
A. sum(列名)
B. max(列名)
C. count(*)
D. avg(列名)
-
[单项选择]
对于给定的一组关键字(12,2,16,30,8,28,4,10,20,6,18),按照下列算法进行递增排序,写出每种算法第一趟排序后得到的结果:希尔排序(增量为5)得到 (11) ,快速排序(选第一个记录为基准元素)得到 (12) ,基数(基数为10)排序得到 (13) ,二路归并排序得到 (14) ,堆排序得到 (15) 。
11()
A. 2,4,6,8,10,12,16,18,20,28,30
B. 6,2,10,4,8,12,28,30,20,16,18
C. 12,2,10,20,6,18,4,16,30,8,28
D. 30,10,20,12,2,4,16,6,8,28,18
-
[单项选择]
用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下。
19()
①25,84,21,47,15,27,68,35,20 ②20,15,21,25,47,27,68,35,84
③5,20,21,25,35,27,47,68,84 ④15,20,21,25,27,35,47,68,84
则所采用的排序方法是 (19) 。不稳定的排序是 (20) 。外排序是指 (21) 。
A. 选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
-
[单项选择]
在内部排序中,通常要对被排序数据进行多次扫描。各种排序方法有不同的排序实施过程和时间复杂性。对给定的整数数列(541,132,984,746,518,181,946,314,205, 827)进行从小到大的排序时,采用冒泡排序和简单选择排序时,若先选出大元素,则第一次扫描结果分别是 (22) ,采用快速排序(以中间元素518为基准)的第一次扫描结果是 (23) 。
22()
设被排序的序列有n个元素,冒泡排序和简单选择排序的时间复杂度是 (24) ;快速排序的时间复杂度是 (25) 。
A. (181,132,314,205,541,518,946,827,746,984)和(541,132,827,746,518,181,946,314,205,984)
B. (132,541,746,518,181,946,314,205,827,984)和(541,132,827,746,518,181,946,314,205,984)
C. (205,132,314,181,518,746,946,984,541,827)和(132,541,746,518,181,946,314,205,827,984)
D. (541,132,984,746,827,181,946,314,205,518)和(132,541,746,518,181,946,314,205,827,984)
-
[单项选择]
给定结点的关键字序列(F,B,J,G,E,A,I,D,C,H),对它按字母的字典顺序进行排列,采用不同方法,其最终结果相同,但中间结果是不同的。
26()
Shell排序的第一趟扫描(步长为5)结果应为 (26) 。
冒泡排序(大数下沉)的第一趟冒泡的效果是 (27) 。
快速排序的第一次扫描结果是 (28) 。
二路归并排序的第一趟结果是 (29) 。
若以层次序列来建立对应的完全二叉树后,采用筛选法建堆,其第一趟建的堆是 (30) 。
A. (B, F, G, J, A, D, I, E, H,)
B. (B, F, G, J, A, E, D, I, C,)
C. (A, B, D, C, E, F, I, J, G,)
D. (C, B, D, A, E, F, I, G, J,)
-
[单项选择]在关系数据库中,通过()来表示概念记录之间的关系。
A. 外来关键字
B. 关键字
C. 数据字典
D. 元组
-
[单项选择]如果一个系统定义为关系系统,则它必须()
A. 支持关系数据库
B. 支持选择、投影和连接运算
C. A和B均成立
D. A、B都不需要
-
[单项选择]在数据库设计中,超类实体与子类实体的关系是()
A. 前者继承后者的所有属性
B. 后者继承前者的所有属性
C. 前者只继承后者的主键
D. 后者只继承前者的主键