1、数据结构与算法练习试卷 2-3 及答案解析(总分：70.00，做题时间：90 分钟)一、选择题(总题数：16，分数：70.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_哈希存储的基本思想是根据(1)来决定(2)，冲突(碰撞)指的是(3)，(4)越大，发生冲突的可能性也越大。处理冲突的两种主要方法是(5)。（分数：10.00）A.存储地址B.元素的序号C.元素个数D.关键码值A.存储地址B.元素的序号C.元素个数D.关键码值A.两个元素具有相同序号B.两个元素的关键码值不同，而非码属性相同C.不同关键码值对应
2、到相同的存储地址D.数据元素过多A.非码属性B.平均检索长度C.负载因子D.哈希表空间A.线性探查法和双散列函数法B.建溢出区法和不建溢出区法C.除余法和折叠法D.拉链法和开放地址法设二维数组 F 的行下标为 15，列下标为 08，F 的每个数据元素均占 4 个字节。在按行存储的情况下，已知数据元素 F2，2的第一个字节的地址是 1044，则 F3，4和 F4，3的第一个字节的地址分别为(1)和(2)，而数组的第一个数据元素的第一个字节和数组最后一个元素的最后一个字节的地址分别为(3)和(4)。对一般的二维数组 G 而言，当(5)时，其按行存储的 Gi，j的地址与按列存储的 Gj，i的地址相同
3、。（分数：10.00）A.1088B.1084C.1092D.1120A.1092B.1088C.1120D.1124A.1004B.1044C.1000D.984A.1183B.1179C.1164D.1187A.G 的列数与行数相同B.G 的列的上界与 G 的行的上界相同C.G 的列的上界与 G 的行的下界相同D.G 的列的上下界与 G 的行的上下界相同某顺序存储的表格，其中有 90000 个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。 用顺序查找法查找时，平均比较次数约为(1)，最大比较次数为(2)。 现把 90000 个元素按排列
4、顺序划分成若干组，使每组有 g 个元素(最后一组可能不足 g 个)。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的 g 是(3)，此时的平均比较次数是(4)。当 g 的值大于等于 90000 时，此方法的查找速度接近于(5)。（分数：10.00）A.25000B.30000C.45000D.90000A.25000B.30000C.45000D.90000A.100B.200C.300D.400A.100B.200C.300D.400A.快速分类法B.斐波那契查找法C.二分法D.
5、顺序查找法已知无向图的邻接表如图 2-35 所示。 （分数：10.00）A.B.C.A.FGILJMKHB.FGILJKHMC.FGILJKMHD.FGHMILJKA.FGILJKMHB.FGHMILJKC.FGHILJKMD.FGHMKILJA.B.C.A.B.C.图 2-36 是带权的有向图 G 的邻接表。以结点 V1 出发深度遍历图 G 所得的结点序列为(1)；广度遍历图 G所得的结点序列为(2)；G 的一种拓扑序列是(3)；从结点 V1 到 V8 结点的最短路径是(4)；从结点 V1 到 V8结点的关键路径是(5)。 （分数：10.00）A.V1，V2，V3，V4，V5，V6，V7，V
6、8B.V1，V2，V3，V8，V4，V5，V6，V7C.V1，V2，V3，V8，V4，V5，V7，V6D.V1，V2，V3，V8，V5，V7，V4，V6A.V1，V2，V3，V4，V5，V6，V7，V8B.V1，V2，V4，V6，V5，V3，V7，V8C.V1，V2，V4，V6，V3，V5，V7，V8D.V1，V2，V4，V6，V7，V3，V5，V8A.V1，V2，V3，V4，V5，V6，V7，V8B.V1，V2，V4，V6，V5，V3，V7，V8C.V1，V2，V4，V6，V3，V5，V7，V8D.V1，V2，V4，V6，V7，V3，V5，V8A.(V1，V2，V4，V5，V3，V8)B.(
7、V1，V6，V5，V3，V8)C.(V1，V6，V7，V8)D.(V1，V2，V5，V7，V8)A.(V1，V2，V4，V5，V3，V8)B.(V1，V6，V5，V3，V8)C.(V1，V6，V7，V8)D.(V1，V2，V5，V7，V8)2.在一棵完全二叉树中，其根的序号为 1，_可判定序号为 p 和 q 的两个结点是否在同一层。（分数：2.00）A.log 2 p=log 2 qB.log 2 p=log 2 qC.log 2 p+1=log 2 qD.log 2 p=log 2 q+13.堆是一种数据结构，_是堆。（分数：2.00）A.(10,50,80,30,60,20,15,18)B
8、.(10,18,15,20,50,80,30,60)C.(10,15,18,50,80,30,60,20)D.(10,30,60,20,15,18,50,80)4._从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。（分数：2.00）A.二叉排序树B.大顶堆C.小顶堆D.平衡二叉树5.若广义表 L=(1,2,3)，则 L 的长度和深度分别为_。（分数：2.00）A.1 和 1B.1 和 2C.1 和 3D.2 和 26.若对 27 个元素只进行 3 趟多路归并排序，则选取的归并路数为_。（分数：2.00）A.2B.3C.4D.57.循环链表的主要优点是_。（分数：2.0
9、0）A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表8.表达式 a*(b+c)-d 的后缀表达形式为_。（分数：2.00）A.abcd*+-B.abc+*d-C.abc*+d-D.-+abcd9.若二叉树的先序遍历序列为 ABDECF，中序遍历序列 DBEAFC，则其后序遍历序列为_。（分数：2.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA10.无向图中一个顶点的度是指图中_。（分数：2.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数D
10、.与该顶点连通的顶点数11.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后，查找元素 30 要进行_次元素间的比较。（分数：2.00）A.4B.5C.6D.7数据结构与算法练习试卷 2-3 答案解析(总分：70.00，做题时间：90 分钟)一、选择题(总题数：16，分数：70.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_解析：哈希存储的基本思想是根据(1)来决定(2)，冲突(碰撞)指的是(3)，(4)越大，发生冲突的可能性也越大。处理冲突的两种主要
11、方法是(5)。（分数：10.00）A.存储地址B.元素的序号C.元素个数D.关键码值 解析：A.存储地址 B.元素的序号C.元素个数D.关键码值解析：A.两个元素具有相同序号B.两个元素的关键码值不同，而非码属性相同C.不同关键码值对应到相同的存储地址 D.数据元素过多解析：A.非码属性B.平均检索长度C.负载因子 D.哈希表空间解析：A.线性探查法和双散列函数法B.建溢出区法和不建溢出区法C.除余法和折叠法D.拉链法和开放地址法 解析：设二维数组 F 的行下标为 15，列下标为 08，F 的每个数据元素均占 4 个字节。在按行存储的情况下，已知数据元素 F2，2的第一个字节的地址是 1044
12、，则 F3，4和 F4，3的第一个字节的地址分别为(1)和(2)，而数组的第一个数据元素的第一个字节和数组最后一个元素的最后一个字节的地址分别为(3)和(4)。对一般的二维数组 G 而言，当(5)时，其按行存储的 Gi，j的地址与按列存储的 Gj，i的地址相同。（分数：10.00）A.1088 B.1084C.1092D.1120解析：A.1092B.1088C.1120 D.1124解析：A.1004B.1044C.1000 D.984解析：A.1183B.1179 C.1164D.1187解析：A.G 的列数与行数相同B.G 的列的上界与 G 的行的上界相同C.G 的列的上界与 G 的行的
13、下界相同D.G 的列的上下界与 G 的行的上下界相同 解析：某顺序存储的表格，其中有 90000 个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。 用顺序查找法查找时，平均比较次数约为(1)，最大比较次数为(2)。 现把 90000 个元素按排列顺序划分成若干组，使每组有 g 个元素(最后一组可能不足 g 个)。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的 g 是(3)，此时的平均比较次数是(4)。当 g 的值大于等于 90
14、000 时，此方法的查找速度接近于(5)。（分数：10.00）A.25000B.30000C.45000 D.90000解析：A.25000B.30000C.45000D.90000 解析：A.100B.200C.300 D.400解析：A.100B.200C.300 D.400解析：A.快速分类法B.斐波那契查找法C.二分法D.顺序查找法 解析：已知无向图的邻接表如图 2-35 所示。 （分数：10.00）A.B.C. 解析：A.FGILJMKHB.FGILJKHM C.FGILJKMHD.FGHMILJK解析：A.FGILJKMHB.FGHMILJK C.FGHILJKMD.FGHMKIL
15、J解析：A. B.C.解析：A.B. C.解析：图 2-36 是带权的有向图 G 的邻接表。以结点 V1 出发深度遍历图 G 所得的结点序列为(1)；广度遍历图 G所得的结点序列为(2)；G 的一种拓扑序列是(3)；从结点 V1 到 V8 结点的最短路径是(4)；从结点 V1 到 V8结点的关键路径是(5)。 （分数：10.00）A.V1，V2，V3，V4，V5，V6，V7，V8B.V1，V2，V3，V8，V4，V5，V6，V7C.V1，V2，V3，V8，V4，V5，V7，V6D.V1，V2，V3，V8，V5，V7，V4，V6 解析：A.V1，V2，V3，V4，V5，V6，V7，V8B.V1，
16、V2，V4，V6，V5，V3，V7，V8C.V1，V2，V4，V6，V3，V5，V7，V8 D.V1，V2，V4，V6，V7，V3，V5，V8解析：A.V1，V2，V3，V4，V5，V6，V7，V8B.V1，V2，V4，V6，V5，V3，V7，V8 C.V1，V2，V4，V6，V3，V5，V7，V8D.V1，V2，V4，V6，V7，V3，V5，V8解析：A.(V1，V2，V4，V5，V3，V8)B.(V1，V6，V5，V3，V8)C.(V1，V6，V7，V8)D.(V1，V2，V5，V7，V8) 解析：A.(V1，V2，V4，V5，V3，V8)B.(V1，V6，V5，V3，V8) C.(V1，
17、V6，V7，V8)D.(V1，V2，V5，V7，V8)解析：2.在一棵完全二叉树中，其根的序号为 1，_可判定序号为 p 和 q 的两个结点是否在同一层。（分数：2.00）A.log 2 p=log 2 q B.log 2 p=log 2 qC.log 2 p+1=log 2 qD.log 2 p=log 2 q+1解析：3.堆是一种数据结构，_是堆。（分数：2.00）A.(10,50,80,30,60,20,15,18)B.(10,18,15,20,50,80,30,60) C.(10,15,18,50,80,30,60,20)D.(10,30,60,20,15,18,50,80)解析：4.
18、_从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。（分数：2.00）A.二叉排序树B.大顶堆C.小顶堆 D.平衡二叉树解析：5.若广义表 L=(1,2,3)，则 L 的长度和深度分别为_。（分数：2.00）A.1 和 1B.1 和 2 C.1 和 3D.2 和 2解析：6.若对 27 个元素只进行 3 趟多路归并排序，则选取的归并路数为_。（分数：2.00）A.2B.3 C.4D.5解析：7.循环链表的主要优点是_。（分数：2.00）A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都
19、能遍历整个链表 解析：8.表达式 a*(b+c)-d 的后缀表达形式为_。（分数：2.00）A.abcd*+-B.abc+*d- C.abc*+d-D.-+abcd解析：9.若二叉树的先序遍历序列为 ABDECF，中序遍历序列 DBEAFC，则其后序遍历序列为_。（分数：2.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA 解析：10.无向图中一个顶点的度是指图中_。（分数：2.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数 D.与该顶点连通的顶点数解析：11.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后，查找元素 30 要进行_次元素间的比较。（分数：2.00）A.4B.5 C.6D.7解析：
