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