问答题
解答下面的问题：
问答题
画出在递增有序表A[1．．21]中进行折半查找的判定树。
【正确答案】正确答案：图中，结点中的数字为元素在有序表中的下标。
【答案解析】
问答题
当实现插入排序过程时，可以用折半查找来确定第I个元素在前I-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度?为什么?
【正确答案】正确答案：插入排序中，用折半查找确定待插入元素位置，比直接插入排序减少了比较次数，但数据移动次数没有改变，排序的时间复杂度也未改变。
【答案解析】
问答题
折半查找的平均查找长度是多少?【西安电子科技大学2000计算机应用八(10分)】
【正确答案】正确答案：折半查找的平均查找长度是((n+1)n)log
2
(n+1)一1≈log(n+1)一1。本例ASL=79／21。
【答案解析】