2022年江南大学现代远程教育数据结构第3阶段测试题3b.pdf
学习资料收集于网络，仅供参考学习资料江南大学现代远程教育 第三阶段测试卷考试科目 :数据结构第五章至第七章（总分 100分）时间： 90分钟_学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择题（每题 3 分，共 30 分）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、设哈希表地址范围为019，哈希函数H(key)=key%17 ，使用二次探测再散列法处理冲突。若表中已存放有关键字值为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） 。、在外存上进行的排序方法、不需要使用内存的排序方法、数据量很大，需要人工干预的排序方法、排序前后数据在外存，排序时数据调入内存的排序方法精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 4 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料9、下述文件中适合于磁带存储的是（C） 。、顺序文件、索引文件、散列文件、多关键字文件10、ISAM 文件和 VSAM 文件属于（ A） 。、索引非顺序文件、索引顺序文件、顺序文件、散列文件二、 （10 分）设用堆排序法对给定关键字序列（，）按升序进行排序，试画出初始堆。答： 9 6， 8 5，4 3， 2 4，1 5，7 6，3 3 三、 （10 分）画出对长度为的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。平均查找长度：17599 4 13 2 6 11 15 1 3 5 7 12 10 14 16 8 17 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 4 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料四、 （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)%11 ，用开放定址法处理冲突，di=i*(7*key)%10+1)，i=1,2,3 。试在 0 的散列地址空间中对关键字序列（，）造哈希表，并求等概率下查找成功时的平均查找长度。L 0 22 1 67 2 41 3 30 4 5 53 6 13 7 8 46 9 10 01 平均查找长度=（1+1+1+2+2+1+6+3 ）/8=817精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 4 页 - - - - - - - - - - 学习资料收集于网络，仅供参考学习资料六、 （20 分）设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于的数据元素。Viod OutputNLT(BiTree T,KeyType X) if (!T) return; if (!LT(T-data.key,x) /根结点及右子树中所有结点的关键字值俊不小于x Output(T-rchild); /按关键字值从大到小的顺序输出右子树中所有结点Printf(T-data); /输出 p 所指结点OutputNLT(T-lchild,x); /处理左子树 else OutputNLT(T-lchild,x); /OutputNLT Void Output(BiTree T) Output(T-rchild); printf(T-data); Output(T-lchild); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 4 页 - - - - - - - - - -
