数据结构作业：查找与排序实践

本次数据结构第5次作业主要涵盖了查找和内部排序两个核心主题，涉及多项具体任务和理论分析。 在查找部分，作业要求学生掌握高级搜索算法的应用： 1. **对分查找**（二分查找）是用于有序列表中高效查找的关键算法。设计题要求设计一个算法，在递增有序的顺序表中找到指定关键字的插入位置。提供的代码片段展示了如何通过设置两个指针h和a，每次取中间值b，比较关键字，逐步缩小查找范围，直到找到合适的位置。这种方法的时间复杂度为O(log n)，大大提高了查找效率。 2. **平衡二叉排序树**的构建和判断是另一个重点。编程题要求输入一组互不相等的整数，构建一棵平衡二叉排序树，并检查其是否平衡（左右子树高度差不超过1），最后输出中序遍历的序列。这涉及到树的性质理解和遍历算法的实践。 3. **B-树操作**包括从空树开始插入关键字和逐步删除结点以重构B-树。学生需理解B-树的结构和插入/删除操作，以及在递减关键字顺序下删除结点的过程。 4. **哈希表**设计中，学生需用二次探测再散列解决冲突，并计算等概率查找情况下成功查找的平均查找长度。这涉及哈希函数的设计和性能分析。 在内部排序部分，作业强调了排序算法的改进和实现： 1. **对分查找插入排序**要求将直接插入排序中的内循环替换为对分查找，这会改变原有的插入策略，提高排序效率。学生需编写新的插入排序算法，并分析其时间复杂度。 2. **递归排序算法**设计则涉及到非递归直接插入排序和冒泡排序的递归版本，让学生熟悉递归思想在排序中的应用。 3. **单链表排序**要求设计一个带有附加头结点的单链表，其中的数据结点按照关键字升序排列。这涉及链表操作和排序算法的具体实现。 4. **链式基数排序**是最后一个编程题，涉及无符号整数的排序，利用16进制表示每个数字，通过多趟分配和收集实现基数排序，要求学生能够熟练掌握这一排序方法。 这些题目综合考察了学生的算法设计、分析能力，以及对查找、排序、数据结构（如B-树、哈希表、链表）和排序算法（如对分查找、递归、基数排序）的深入理解。完成这些作业有助于巩固和提升学生在数据结构领域的核心技能。