西南交通大学-zhy-数据结构第5次作业.zip

西南交大;西南交通大学;数据结构;赵宏宇;一、查找 1. 算法设计题 ：已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值key，编写算法用对分查找求下标i，满足ai-1<key且ai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趟。