数据结构第3阶段练习题20年江大考试题库及答案一科共有三个阶段,这是其中一个阶段答案在最后

1、江南大学网络教育第三阶段练习题考试科目：数据结构第章至第章（总分100分）学习中心（教学点）批次：层次:专业：学号：身份证号：姓名：得分:一单选题（共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。）1 .m阶B树中的一个分支结点最多含（）个关键字。（）（2分）D.m/2+1）次比较。（2分）A.m-1B.mC.m/22 .将两个各有n个元素的有序表归并成一个有序表，最少进行（C. 2n（2分）C.散列文件D. n-1D.多关键字文件A.nB.2n-13 .下述文件中适合于磁带存储的是（A.顺序文件B.索引文件4 .外部排序是指（）。（2分）A.在外存上进行

2、的排序方法B.不需要使用内存的排序方法C.数据量很大，需要人工干预的排序方法D.排序前后数据在外存，排序时数据调入内存的排序方法5 .设哈希表地址范围为019,哈希函数H（key）=key%17,使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（）。（2分）A.2B.3C.7D.86 .ISAM文件和VSAM：件属于（）。（2分）A.索引非顺序文件C.顺序文件B.索引顺序文件D.散列文件第1页/共7页）。（2分）7 .设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为A.50B.258 .设有一组

3、关键字值（46,79,56,38,40,84）到的一次划分结果为（）。（2分）A.38,40,46,56,79,84C.40,38,46,56,79,849 .直接插入排序在最好情况下的时间复杂度为（A.O（logn）B.O（n）10 .设有k个关键字互为同义词，次探测。（2分）A. k-1B.k若用线性探测法把这C.10D.7,则用快速排序的方法，以第一个记录为基准得B. 40,38,46,79,56,84D.40,38,46,84,56,79）。（2分）C. O（n*logn）D. O（n2）k个关键字存入散列表，至少要进行（）C.k+1D.k（k-1）/2二简答题（共2题，总分值20分）

4、11 .设用堆排序法对给定关键字序列（85,61,15,33,24,96,76,43）按升序进行排序，试画出初始堆。（10分）12 .画出对长度为17的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。（10分）三综合题（共3题，总分值60分）13 .设哈希函数H（key）=（3*key）%11，用开放定址法处理冲突，dj=i*（7*key）%10+1）,i=1,2,3。试在。10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率下查找成功时的平均查找长度。（20分）14 .设内存有大小为5个记录的区域可供内部排序之用，文件的关键

5、字序列为：（18,32,56,40,23,11,8,99,58,36,21,7,4,15,19,87,73,52,82,63）,要求用置换选择排序求初始归并段。（20分）15.设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于x的数据元素。（20分）第2页/共7页第3页/共7页一单选题（共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。）1 .答案：A解析过程：2 .答案：A解析过程：3 .答案：A解析过程：4 .答案：D解析过程：5 .答案：D解析过程：6 .答案：A解析过程：7 .答案：A解析过程：8 .答案：C解析过程：9 .答案：B解析过程：10 .答案：D解析过程：二简答题（共2题，总分值20分）第4