数据结构-第三阶段练习

第1页/共6页江南大学网络教育第三阶段练习题 一单选题(共10题，总分值20分，下列选项中有且仅有一个选项符合题目要1.下面给出的四种排序法中()排序法是不稳定的排序法。(2分)A.插入B.冒泡C.二路归并D.堆2.若需在0(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法A.快速排序B.堆排序C.归并排序D.直接插入排序3.在待排元素序列基本有序的前提下，效率最高A.插入B.选择C.快速D.归并4.下面关于m阶B树说法正确的是()。①每个结点至少有两棵非空子树；②树中每个结点至多有m-1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。(2分)A.①②③B.②③D.③第2页/共6页A.选择文件的组织方式时应考虑外存的性质和容量B.不定长文件指的是总长度可变的文件C.对文件的操作主要是维护和检索D.文件的存储结构指的是文件在外存上的组织方式8.设有一组关键字值(46,79,56,38,40,84),则用堆排序的方法建立的初始堆为()。(29.适用于折半查找的表的存储方式及元素排列要求为()。(2分)A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序10.对二叉排序树进行()遍历所得的遍历序列中，关键字值是按升序排列的。A.前序B.中序C.后序D.层序二多选题(共5题，总分值10分，下列选项中至少有2个或2个以上选项符合11.下列说法中错误的是()。(2分)A.A.在二叉排序树中，根结点的值都小于孩子结点的值；C.哈希法的查找效率主要取决于哈希表构造时选择的哈希函数；C.哈希法的查找效率主要取决于哈希表构造时选择的哈希函数；D.查找表是以集合为查找结构的12.在排序过程中，关键字比较次数与记录的初始排列顺序无关的是()。(2分)14.下列叙述正确的是()。(2分)C.快速排序是对起泡排序的改进，通过一趟排序将待排序记录分割成两部分；第3页/共6页E.基数排序是通过若干次分配和收集来实现排序的15.下列叙述中正确的是()。(2分)三判断题(共9题，总分值9分正确的填涂“A”,错误的填涂“B”。)16.在有序列{1,3,9,12,32,41,62,75,77,82,95,100}上进行折半查找关键字为82的数据元素四简答题(共2题，总分值20分)25.设给定关键字序列(68,55,27,43,58,12),试构造平衡的二叉查找树。(10分)第4页/共6页五综合题(共3题，总分值41分)第5页/共6页28.设以带头结点的单链表为存储结构，设计算法，实现简单选择排序。(13分)//单链表L//单链表L带头结点min=p->next;//min用以指向本趟排序中关键字值最小的结点ifLT(q->data.key,min->data.key)min=q;//q所指结点关键字值更小p=p->nextp=p->nextif(min!=p)min->data*→p->data;//当前关键字值最小的记录到位29.设哈希函数H(key)=key%13,用公共溢出区法处理冲突，试在长度为18的散列地址空间中对关键字序列(71,28,46,14,2,20,85,58)构造哈希表，要求画出哈希表存储结构示意图，并求等概率下查找成功时的平均查找长度。(1