江大18秋《数据结构》第三次离线作业
江南大学现代远程教育 第三阶段练习题考试科目:《数据结构》第九章至第十二章（总分100分）______________学习中心（教学点） 批次： 层次：
专业： 学号： 身份证号：
姓名： 得分： 一、选择题（每题3分，共30分）
1、若查找每个元素的概率均相等，则在具有n个元素的静态查找表中采用顺序查找法查找一个记录，其平均查找长度ASL为（ ）。
Ａ、(n-1)/2 Ｂ、n/2 Ｃ、(n+1)/2 Ｄ、n
2、适用于折半查找的表的存储方式及元素排列要求为（ ）。
Ａ、链接方式存储，元素无序 Ｂ、链接方式存储，元素有序
Ｃ、顺序方式存储，元素无序 Ｄ、顺序方式存储，元素有序
3、对二叉排序树进行（ ）序遍历所得的遍历序列中，关键字值是按升序排列的。
Ａ、前序 Ｂ、中序 Ｃ、后序 Ｄ、层序
4、下面关于m阶B树说法正确的是（ ）。
①每个结点至少有两棵非空子树； ②树中每个结点至多有m-1个关键字；
③所有叶子在同一层上； ④当插入一个数据项引起B树结点分裂后，树长高一层。
Ａ、①②③ B、②③ C、②③④ D、③
5、下面给出的四种排序法中（ ）排序法是不稳定的排序法。
Ａ、插入 Ｂ、冒泡 Ｃ、二路归并 Ｄ、堆
6、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
Ａ、快速排序 Ｂ、堆排序 Ｃ、归并排序 Ｄ、直接插入排序
7、在待排元素序列基本有序的前提下，效率最高的排序方法是（ ）。
Ａ、插入 Ｂ、选择 Ｃ、快速 Ｄ、归并
8、设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（ ）。
Ａ、79,46,56,38,40,84 Ｂ、84,79,56,38,40,46
Ｃ、84,79,56,46,40,38 Ｄ、84,56,79,40,46,38
9、下列排序算法中（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A、快速排序 B、shell排序 C、堆排序 D、冒泡排序
10、下列关于文件的说法，错误的是（ ）。
Ａ、选择文件的组织方式时应考虑外存的性质和容量
Ｂ、不定长文件指的是总长度可变的文件
Ｃ、对文件的操作主要是维护和检索
Ｄ、文件的存储结构指的是文件在外存上的组织方式二、（10分）
设给定关键字序列（68, 55, 27, 43, 58, 12），试构造平衡的二叉查找树。三、（10分）
设有3阶B-树如下，试画出对其依次执行下列操作后的结果。
(1)插入52；(2)删除11；(3)删除74。四、（15分）
设哈希函数H(key)=key%13，用公共溢出区法处理冲突，试在长度为18的散列地址空间中对关键字序列（71，28，46，14，2，20，85，58）构造哈希表，要求画出哈希表存储结构示意图，并求等概率下查找成功时的平均查找长度。五、（15分）
设有关键字序列（87,43,28,91,12,62,55,26），用快速排序法进行排序，要求写出每趟排序结束时的关键字序列。六、（20分）
设以带头结点的单链表为存储结构，设计算法，实现简单选择排序。
关于答案可以联系QQ 1647861640
页:
[1]