2013数据结构作业5-查找排序-参考答案

数据结构练习题以及答案,非常有用

作业5. 查找、排序

非编程作业：

1．对下标为1～9的有序表进行折半查找，画出折半查找的判定树；并计算在等

概率情况下查找成功的平均查找长度ASL。

参考答案：

2．设有关键字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列

表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算。

参考答案：

线性探查再散列处理冲突：

查找时比较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

链地址法处理冲突：

查找成功的ASL=(1*7+2*3+3*2)/12≈1.58

3．已知待排序序列为{50，86，72，41，45，93，57，46}，请写出按下列排序

方法进行升序排序时的第一趟排序结果：

① 直接插入排序；

② 冒泡排序；

③ 简单选择排序；

数据结构练习题以及答案,非常有用

④ 堆排序初建堆序列。

参考答案：

第一趟直接插入排序：50，86，72，41，45，93，57，46 第一趟冒泡排序： 50，72，41，45，86，57，46，93 第一趟简单选择排序：41，86，72，50，45，93，57，46 堆排序初建堆序列 ： 41，45，57，46，50，93，72，86