江南大学现代远程教育2015数据结构第3阶段测试题3b

1、江南大学现代远程教1第三阶段测试卷考试科目：数据结构第五章至第七章（总分100分） 时间：90分钟 习中心（教学点）批次：层次：专业：学号：姓名：身份证号：得分：一、选择题（每题3分，共30分）1、m阶B树中的一个分支结点最多含（C）个关键字。A、m-1 B、m C、m+1 D、m/2-1E、m/2F、m/2+12、设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（B）次探测。A、k-1 E、k C、k+1 D、k（k-1）/23、 设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（A）。A、50 E、25 C、10 D、74、 设哈希表地址范围

2、为 019，哈希函数H（key）=key%17 ,使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（）。A、2 E、3 C、4 D、7 E、8 F、以上都不对5、 直接插入排序在最好情况下的时间复杂度为（D）。2A、O（logn）B O（n） C、O（n*logn）D、O（n）6、 将两个各有n个元素的有序表归并成一个有序表，最少进行（B）次比较。A、n B、2n-1 C、2n D、n-17、 设有一组关键字值 （46,79,56,38,40,84）,则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（D）

3、。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,56,79,84D、40,38,46,84,56,798、外部排序是指（B）。A、在外存上进行的排序方法B、不需要使用内存的排序方法C、数据量很大，需要人工干预的排序方法D、排序前后数据在外存，排序时数据调入内存的排序方法9、 下述文件中适合于磁带存储的是（C）。A、顺序文件B、索引文件 C、散列文件D、多关键字文件10、ISAM文件和 VSAM文件属于（A）。A、索引非顺序文件E、索引顺序文件C、顺序文件D、散列文件二、（10 分） 设用堆排序法对给定关键字序列（8 5,61, 序进行排序，试

4、画出初始堆。答：96,85, 43,24, 15,三、（10分）画出对长度为17的有序表进行折半查找的判定树,15,33,24,96,76,43）按升6,并求等概率下查找成功时的平均查找长度。17四、（15分）设内存有大小为5个记录的区域可供内部排序之用，文件的关键字序列为：（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,

5、11, 15, 19, 21, 36, 52, 63, 73, 82, 87 初始归并段3: 4五、(15分)设哈希函数 H(key)=(3*key)%11 ，用开放定址法处理冲突，di =i*(7*key)%10+1), i=1,2,3试在01 0的散列地址空间中对关键字序列(22,41,53,46,30,13,01,6 7)造哈希表，并求等概率下查找成功时的平均查找长度。01234567891022674?30531346平均查找长度：=(1 + 1 + 1+2+2+1+6+3) /8= 1701六、(20分)设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于x的数据元素。Viod OutputNLT(BiTreeKeyType X)if (!T) return;if (!LT(T-data.key,x) /Output(T-rchild); /Prin tf(T-data); /根结点及右子树中所有结点的关键字值俊不小于x按关键字值从大到小的顺序输出右子树中所有结点输出p所指结点处理左子树OutputNLT(T-lchild,x); /else OutputNLT(T-lc