数据结构作业5查找、排序 参考答案
作业5. 查找、排序
非编程作业参考答案：
1．设有关键字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列表长12，散列函数为h(key)=key，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算在等概率情况下的查找成功的平均查找长度。
线性探查再散列处理冲突：
0 1 2 3 4 5 6 7 8 9 10 1133 12 66 25 47 22 72 40 94 5 87 58查找时比较1次能够成功的有：25、40、33、12、72、87比较2次能够成功的有：47比较3次能够成功的有：66、94比较5次能够成功的有：5比较6次能够成功的有：22比较9次能够成功的有：58查找成功的ASL=(1*6+2+3*2+5+6+9)/12≈2.83
链地址法处理冲突：
22^33660 112^ 2^47253 58^4^
5^5
7294^6
740^ 8^ 9^87^ 1011^ 查找成功的ASL=(1*7+2*3+3*2)/12≈1.58
数据结构作业5查找、排序 参考答案
2．已知待排序序列为{50，86，72，41，45，93，57，46}，请写出按下列排序方法进行升序排序时的第一趟排序结果：
① 冒泡排序； ② 二路归并排序；
③ 以第一个元素为枢轴的快速排序； ④ 堆排序初建堆序列； ⑤ 取d1=4时的希尔排序； ⑥ 简单选择排序。
冒泡排序： 50，72，41，45，86，57，46，93 二路归并排序：50，86，41，72，45，93，46，57 快速排序： 46，45，41，50，72，93，57，86 初建堆： 41，45，57，46，50，93，72，86 希尔排序： 45，86，57，41，50，93，72，46 简单选择排序：41，86，72，50，45，93，57，46
3．设计一种方法，以少于2n-3次的比较在顺序存储的n(n>=2)个数中同时找出最大和最小值。
方法1：从n个数中找出最大值放在下标为0的位置——(n-1)次比较； 再在剩余的n-1个数中找到最小值——(n-2)次比较； 总比较次数为2n-3。
方法2：将n个数两两比较，比较的过程中将小的数放在前面，大的数放
在后面——(0.5n)次比较；
之后在偶数下标的数中找到最小值（下标从0开始）——(0.5n-1)
次比较；
在奇数下标的数中找到最大值——(0.5n-1)次比较； 总比较次数为1.5n-2，当n>=2时小于2n-3。