江南大学现代远程教20育12年上半年第三阶段测试卷考试科目:《数据结构》第九章至第十二章（总分100分）时间：90分钟一、选择题（每题3分，共30分）1、若查找每个元素的概率均相等，则在具有n个元素的静态查找
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
中采用顺序查找法查找一个记录,其平均查找长度ASL为（C）。A、（n-1）/2B、n/2C、（n+1）/2D、n2、适用于折半查找的表的存储方式及元素排列要求为（D）。A、链接方式存储，元素无序B、链接方式存储，元素有序C、顺序方式存储，元素无序D、顺序方式存储，元素有序3、对二叉排序树进行（B）序遍历所得的遍历序列中，关键字值是按升序排列的。A、前序B、中序C、后序D、层序4、下面关于m阶B树说法正确的是（B）。①每个结点至少有两棵非空子树；②树中每个结点至多有m-1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。A、①②③B、②③C、②③④D、③5、下面给出的四种排序法中（D）排序法是不稳定的排序法。A、插入B、冒泡C、二路归并D、堆6、若需在O^log^）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C）。A、快速排序B、堆排序C、归并排序D、直接插入排序7、在待排元素序列基本有序的前提下，效率最高的排序方法是（A）。A、插入B、选择C、快速D、归并8、设有一组关键字值（46,79,56,38,40,84）,则用堆排序的方法建立的初始堆为（B）。A、79,46,56,38,40,84B、84,79,56,38,40,46C、84,79,56,46,40,38D、84,56,79,40,46,389、下列排序算法中（B）不能保证每趟排序至少能将一个元素放到其最终的位置上。A、快速排序B、shell排序C、堆排序D、冒泡排序10、下列关于文件的说法，错误的是（B）A、选择文件的组织方式时应考虑外存的性质和容量B、不定长文件指的是总长度可变的文件C、对文件的操作主要是维护和检索D、文件的存储结构指的是文件在外存上的组织方式二、（10分）设给定关键字序列（68,55,27,43,58,12），试构造平衡的二叉查找树。三、(10分)设有3阶B-树如下，试画出对其依次执行下列操作后的结果。答;四、(15分)设哈希函数H(key)=key%13，用公共溢出区法处理冲突，试在长度为18的散列地址空间中对关键字序列(71，28，46，14，2，20，85，58)构造哈希表，要求画出哈希表存储结构示意图，并求等概率下查找成功时的平均查找长度。答：H(71)=6H(2®)=2H(46)=7H(14)=lH(2)=2H(20)=7H(85)=7H(58)=6011422834571746891013214151617208558ASL=(1+1+1+1+2+3+4+5)/8=9/4五、(15分)设有关键字序列(87,43,28,91,12,62,55,26)，用快速排序法进行排序，要求写出每趟排序结束时的关键字序列。第一趙：26.43.28,5542^2,87.91第二遹：忆囱■强殂羽厲田戲弟三趟：厲扯给爼帕坨的.91諾四趟：忆恥2辭玄◎仏87.9】六、(20分)设以带头结点的单链表为存储结构，设计算法，实现简单选择排序。voidSelectSort(IjnkL-i5t&L){獰链表L带头结点p=L,while(p->next)(mn=p>ne^//minffiU指向本趟排序中黄键芋值最小的结点q=niinFe减while(q){ifLT(q->data.key,min->data.key)mm=q..//q所指结点关键字值更小<^=q->iiext;)//whilep=p->ne5i;if(minl=p)imZ删ta~fp.珂al出ff当前关键字值最小的记录到拉)//whiIe)//SelectSort
浙公网安备 33021202002483