大连理工大学算法1练习

一.对60，40，120，85，20，35，150，130，45按非减序排序。请分别给出下列5种排序的第一趟排序的结果:a.插入排序b.冒泡排序c.快速排序d.堆排序e.归并排序。二.如果在一种排序方法中,相等的元素间的相互位置在排序前后保持不变,则称这种排序方法为稳定的。第2题所列的5种排序方法中,哪些是稳定的？为每一种不稳定的排序方法举出两个相等的元素间的相互位置在排序前后被改变的实例。三.按照以下次序输入关键字的值建立2-3树(3阶B-树):(68,54,82,35,75,90，103，22)。(1)请画出所建的2-3树。(2)如果此后依次删除22,75，画出每一步执行后的2-3树的状态。四.已知键值序列为{38,17,59，4，40,25,20,22}。(1)按照给定的顺序输入构造一棵二叉排序树，画出所建的二叉排序树;并计算在等概率的情况下查找成功的平均查找长度;(2)画出在所建的二叉排序树中删除17后的二叉排序树;(3)针对给定的8个键值，按照不同的顺序输入可以建立不同形态的二叉排序树，画出一棵最好情况下所建的二叉排序树(即最佳二叉排序树)。五.设哈希表表长m=9，键值集合为{90,48,66,50,87,111,134,152}，哈希函数为h(k)=k%9，用线性探测法解决冲突，请画出相应的哈希表;查找111，152各要比较多少次?计算在等概率的条件下查找成功的平均检索长度?六.设有序顺序表(4,18，30,56,78,82,95，128，145)，用二分法查找。1.画出相应的二分查找判定树。2.查找56，128时分别需要和哪些数据比较?3.计算在等概率的条件下查找成功的平均查找长度。七.请构造一棵8个节点的红-黑树,其关键字序列为1,5,2,6,3,7,4,8。八.设字符a,b,c,d,e的使用频度分别为8，12，15，30，35。求a,b,c,d,e的哈夫曼编码，并给出相应的哈夫曼树，同时计算其带权路径长度。九.请给出一个有效的对n个正整数重排的内置算法，使得所有偶数位于奇数之前。你的算法有多快？十.请给出在最坏情况下只需7次元素比较的对5个元素排序的算法。