搜索
作业5.查找、排序非编程作业：1．对下标为1～9的有序表进行折半查找，画出折半查找的判定树；并计算在等概率情况下查找成功的平均查找长度ASL。参考答案：2．设有关键字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算。参考答案：线性探查再散列处理冲突：链地址法处理冲突：3．已知待排序序列为{50，86，72，41，45，93，57，46}，请写出按下列排序方法进行升序排序时的第一趟排序结果：①直接插入排序；②冒泡排序；③简单选择排序；0123456789101133126625472272409458758查找时比较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.8333662225477294408701234567891011^^^^^^^^^12^58^5^33336666222225254747727294944040878701234567891011^^^^^^^^^1212^5858^55^查找成功的ASL=(1*7+2*3+3*2)/12≈1.58④堆排序初建堆序列。参考答案：第一趟直接插入排序：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