数据结构作业：查找与排序算法分析

"这是西南交通大学数据结构课程的一份第5次作业，涵盖了查找和排序两个主题。作业包括理论问题、算法设计以及编程实践。学生需要完成对分查找算法的编写，构建并判断平衡二叉排序树，以及实现链式基数排序。" 在查找部分，作业涉及了对分查找算法。对分查找是一种在有序数组中查找特定元素的有效方法。它通过不断将查找区间减半来快速定位目标值。给定一个n元顺序表，已按照关键字递增有序存储，学生需要编写算法找到满足ai-1<key且ai≥key的下标i。对分查找的效率很高，其时间复杂度为O(log n)。 排序部分则包含内部排序的习题和编程题目。习题集中的问题可能涉及各种排序算法的分析，如计算平均查找长度(ASL)。而编程题目要求学生实现链式基数排序，这是一种非比较型整数排序算法，特别适用于处理大量无符号整数。对于C语言的32位无符号整数，可以按16进制位进行8次分配和收集，从而实现排序。链式基数排序的时间复杂度为O(kn)，其中k是数字的最大位数，n是数字的数量。 此外，作业还涉及到平衡二叉排序树的构建和分析。平衡二叉排序树，如AVL树或红黑树，确保了树的高度保持平衡，从而保证了查找、插入和删除操作的平均时间复杂度为O(log n)。学生需要输入n个两两互不相等的整数，建立这样的树，并判断其是否平衡，同时输出中序遍历的结果，中序遍历可以得到排序后的序列。 这份作业考察了学生对数据结构基础概念的理解，包括查找算法、排序算法以及平衡二叉树的实现和分析。完成这些任务需要扎实的算法基础和编程能力。