江南大学现代远程教第育三阶段测试卷
考试科目:《数据结构
______________
专业： 姓名：
一、选择题（每题 3 分，共 30 分
》第五章至第七章（总分 100 分） 时间：90 分钟
批次：
层次：
身份证号： 得分：
学习中心（教学点）
学号：
）
1、m 阶Ｂ树中的一个分支结点最多含（C）个关键字。
Ａ、m-1 Ｂ、m Ｃ、m+1 Ｄ、[m/2]-1 Ｅ、[m/2] Ｆ、[m/2]+1
2、设 有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入散列表，至少要进行（B） 次探测。
Ａ、k-1 Ｂ、k Ｃ、k+1 Ｄ、k(k-1)/2
3、设表中含 100 个数据元素，用折半查找法进行查找，则所需最大比较次数为（A）。 Ａ、50 Ｂ、25 Ｃ、10 Ｄ、7
4、设哈希表地址范围为 0~19，哈希函数 H(key)=key，使用二次探测再散列法处理冲突。 若表中已存放有关键字值为 6、22、38、55 的记录，则再放入关键字值为72 的记录时，其存放 地址应为（）。
Ａ、2 Ｂ、3 Ｃ、4 Ｄ、7 Ｅ、8 Ｆ、以上都不对 5、直接插入排序在最好情况下的时间复杂度为（D）。 Ａ、O(logn) Ｂ、O(n) Ｃ、O(n*logn) Ｄ、O(n2)
6、将两个各有 n 个元素的有序表归并成一个有序表，最少进行（B）次比较。 Ａ、n Ｂ、2n-1 Ｃ、2n Ｄ、n-1
7、设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得到的 一次划分结果为（D）。
Ａ、38,40,46,56,79,84 Ｂ、40,38,46,79,56,84 Ｃ、40,38,46,56,79,84 Ｄ、40,38,46,84,56,79 8、外部排序是指（B）。 Ａ、在外存上进行的排序方法 Ｂ、不需要使用内存的排序方法
Ｃ、数据量很大，需要人工干预的排序方法
Ｄ、排序前后数据在外存，排序时数据调入内存的排序方法 9、下述文件中适合于磁带存储的是（C）。
Ａ、顺序文件 Ｂ、索引文件 Ｃ、散列文件 Ｄ、多关键字文件
10、ISAM 文件和 VSAM 文件属于（A）。
Ａ、索引非顺序文件 Ｂ、索引顺序文件 Ｃ、顺序文件 Ｄ、散列文件
二、（10 分 ）
设用堆排序法对给定关键字序列（８５，６１，１５，３３，２４，９６，７６，４３）按升 序进行排序，试画出初始堆。
答：9 6， 8 5，4 3， 2 4，1 5，7 6，3 3
三、（10 分 ）
画出对长度为１７的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。
9
4
2
6
3
5
7
8 10
12
14
16
1
17
平均查找长度：17
59
四、（15 分 ）
设内存有大小为５个记录的区域可供内部排序之用，文件的关键字序列为：（18，32，56，40，
23，11，8，99，58，36，21，7，4，15，19，87，73，52，82，63），要求用置换－选择排序 求初始归并段。
初始归并段 1：18，23，32，40，56，58，99；
初始归并段 2：7，8，11，15，19，21，36，52，63，73，82，87 初始归并段 3：4 五、（15 分 ）
设哈希函数 H(key)=(3*key)，用开放定址法处理冲突，d =i i*((7*key)+1)，i=1,2,3…。试 在０～１0 的散列地址空间中对关键字序列（２２，４１，５３，４６，３０，１３，０１， ６７）造哈希表，并求等概率下查找成功时的平均查找长度。
L 0 1 2 3 4 5 6 7 8 9 10
01 46 53 13 22 67 41 30
17
平均查找长度=（1+1+1+2+2+1+6+3）/8=
8
六、（20 分 ）
设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于ｘ的数据元素。 Viod OutputNLT(BiTree T,KeyType X){ if (!T) return;
江南大学现代远程教育 2015数据结构第3阶段测试题3b
