1 / 14
数据结构第 5 次作业
知识范畴：查找；排序
提交截止日期：2022 年 12 月 22 日
作业内容：
一、查找
1. 算法设计题 ：已知 n 元顺序表 a
0
, a
1
, … , a
n-1
按关键字递增有序存储。给定关键字值 key，
编写算法用对分查找求下标 i，满足 a
i-1
<key 且 a
i
�key。
2. 编程题：输入 n 个两两互不相等的整数，以这些整数为关键字建立平衡的二叉排序树。判
断该二叉树是否为平衡的，输出判断结果；输出该二叉树的中序遍历关键字访问次序。
3. 从空树起连续插入以下 20 个关键字构建 m=4 的 B-树。
50, 15, 09, 18, 03, 85, 33, 72, 48, 22,
91, 88, 11, 99, 06, 56, 68, 77, 43, 36。
4. 16 个关键字组成的 5 阶 B-树如下图所示，请按关键
字递减的次序删除所有结点至空树，画出每删除 1 个关键字后得到 B-树，直至空树。
5. 12 个关键字如本电子教案例 1 所示，设 H(K)=K mod 13，地址空间范围 0~15，用二次探测
再散列解决冲突。画出哈希表；若各元素等概率查找，求成功查找时的平均查找长度。
二、内部排序
1. 算法设计与分析题：将直接插入排序的内循环改造为使用对分查找实现元素插入，请写
出基于对分查找的插入排序算法并给出其时间复杂度分析。
2. 算法设计：将教案给出的非递归直接插入排序和冒泡排序算法用递归算法实现。
3. 算法设计：带附加头结点单链表将各数据结点按关键字升序连接。
4. 编程题：键盘输入 n 个无符号整数，用链式基数排序实现由小到大排序，输出排序结果。
提示：对于 C 语言 32bit 宽的 unsigned 类型，可以采用 16 进制形式来实现基数排序，
即 32bit 共有 8 个 16 进制位，每个 16 进制位进行一趟分配和收集，共 8 趟。
一、1
40 50 60 70
12 20 25 28 43 46 51 57 63 66 74 79
评分
满分—3 分
剩余13页未读，继续阅读
资源评论
