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

江南大学现代远程教育 第三阶段测试卷考试科目:数据结构第五章至第七章（总分100分） 时间：90分钟_学习中心（教学点） 批次： 层次： 专业： 学号： 身份证号： 姓名： 得分： 一、选择题（每题3分，共30分）1、m阶树中的一个分支结点最多含（C）个关键字。、m-1、m、m+1、m/2-1、m/2、m/2+12、设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（B）次探测。、k-1、k、k+1、k(k-1)/23、设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（A）。、50、25、10、74、设哈希表地址范围为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-17、设有一组关键字值（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,798、外部排序是指（B）。、在外存上进行的排序方法、不需要使用内存的排序方法、数据量很大，需要人工干预的排序方法、排序前后数据在外存，排序时数据调入内存的排序方法9、下述文件中适合于磁带存储的是（C）。、顺序文件、索引文件、散列文件、多关键字文件10、ISAM文件和VSAM文件属于（A）。、索引非顺序文件、索引顺序文件、顺序文件、散列文件二、（10分）设用堆排序法对给定关键字序列（，）按升序进行排序，试画出初始堆。答：96，85，43，24，15，76，33三、（10分）画出对长度为的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。9134151162161412105713178平均查找长度：四、（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的散列地址空间中对关键字序列（，）造哈希表，并求等概率下查找成功时的平均查找长度。 L0221672413304553613784691001平均查找长度=（1+1+1+2+2+1+6+3）/8=六、（20分）设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于的数据元素。Viod OutputNLT(BiTree T,KeyType X) if (!T) return; if (!LT(T-data.key,x) /根结点及右子树中所有结点的关键字值俊不小于xOutput(T-rchild); /按关键字值从大到小的顺序输出右子树中所有结点Printf(T-data); /输出p所指结点OutputNLT(T-lchild,x); /处理左子树 else OutputNLT(T-lchild,x);/OutputNLTVoid Output(BiTree T) Output(T-rchild); printf(T-data); Output(T-lchild);