一、单项选择题
————————————————————
————————————————————
解析：顺序查找是指从表的一端开始向另一端查找。它不要求查找表具有随机存取的特性，可以是顺序存储结构或链式存储结构。
正确答案：
————————————————————
————————————————————
解析：对于顺序查找，不管线性表是有序的还是无序的，成功查找第一个元素的比较次数为1，成功查找第二个元素的比较次数为2，以此类推，即每个元素查找成功的比较次数只与其位置有关(与是否有序无关)。因此查找成功的平均时间两者相同。
正确答案：
————————————————————
————————————————————
解析：在有序单链表上做顺序查找，查找成功的平均查找长度与在无序顺序表或有序顺序表上做顺序查找的平均查找长度相同，都是(n+ 1)/2。
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：二分查找通过下标来定位中间位置元素，所以应采用顺序存储，且二分查找能够进行的前提是查找表是有序的，但具体是从大到小还是从小到大的顺序则不做要求。
正确答案：
————————————————————
————————————————————
解析：折半查找的快体现在一般情况下，在大部分情况下要快，但是对于某些特殊情况，顺序查找可能会快于折半查找。例如，查找一个含1000个元素的有序表中的第一个元素时，顺序查找的比较次数为1次，而折半查找的比较次数却将近10次。
正确答案：
————————————————————
————————————————————
解析：A显然排除。对于选项C，考点精析示例中的判定树就不是完全二叉树。由选项C也可排除选项D，且满二叉树对结点数有要求。只可能选B。事实上，由折半查找的定义不难看出，每次把一个数组从中间结点分割时，总是把数组分为结点数相差最多不超过1的两个子数组，从而使得对应的判定树的两棵子树高度差的绝对值不超过1，所以应是平衡二叉树。
正确答案：
————————————————————
————————————————————
解析：折半查找的性能分析可以用二叉判定树来衡量,平均查找长度和最大查找长度都是O(logzn);二叉排序树的查找性能与数据的输入顺序有关，最好情况下的平均查找长度与折半查找相同，但最坏情况即形成单支树时，其查找长度为O(n)。
正确答案：
————————————————————
————————————————————
解析：依据折半查找算法的思想，第一次mid=L(1+11)/2]=6，第二次mid=L[ (6+1)+11]/2]=9,第三次mid=L[ (9+1)+11]/2]=10，第四次mid= 11。
正确答案：
————————————————————
————————————————————
解析：开始时low指向13，high 指向134，mid指向50，比较第一次90>50，所以将low指向62，high指向134,mid指向90，第二次比较找到90。
正确答案：
————————————————————
————————————————————
解析：在折半查找算法中，mid取值的方式是确定的，要么采用向上取整，要么采用向下取整，而不能出现两种情况。对于A，第Ⅰ次比较的元素是f，为向下取整;第2次比较的元素是c，为向下取整;第3次比较的元素是b，为向下取整，查找成功，符合二分查找。对于B，第1次比较的元素是f，为向下取整;第⒉次比较的元素是d，为向上取整，两次mid取值的方式不同，不符合二分查找。对于C，第1次比较的元素是g，为向上取整;第2次比较的元素是c，为向下取整，不符合二分查找。对于D，第1次比较的元素是g，为向上取整;第2次比较的元素是d,为正中间元素;第3次比较的元素为b，为向下取整，不符合二分查找。
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：折半查找法不仅要求数据元素有序，而且要求必须为顺序存储，A错误。折半查找法在最坏情况下的时间性能为O(logzn)，二叉查找树在最坏情况下的时间性能为O(n)，B错误。在每个元素查找概率不同的情况下，折半查找法的平均查找长度可能大于顺序查找法，C错误。
正确答案：
————————————————————
————————————————————
解析：通常情况下，在分块查找的结构中，不要求每个索引块中的元素个数都相等。
正确答案：
————————————————————
————————————————————
解析：设块长为b，索引表包含n/b项，索引表的ASL=(n/b+1)/2，块内的ASL=(b+1)/2，总ASL=索引表的ASL＋块内的ASL=(b+n/b+2)/2，其中对于b+n/b，由均值不等式知b=n/b时有最小值，此时b=√n。则最理想块长为√2500 = 50 。
正确答案：
————————————————————
————————————————————
解析：平均查找长度为(2＋3+4+…＋42＋3+4+5+…+43＋4+5+6+…＋44)123=23。
正确答案：
————————————————————
————————————————————
解析：为使查找效率最高，每个索引块的大小应是√65025=255，为每个块建立索引，则索引表中索引项的个数为255。若对索引项和索引块内部都采用折半查找，则查找效率最高，为 [ log2(255+1)]+[log2(255+1)]= 16。
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：该程序采用跳跃式的顺序查找法查找升序数组中的x。显然，x越靠前，比较次数越少。
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：
正确答案：
二、综合应用题
————————————————————
————————————————————
解答：
————————————————————
————————————————————
解答：
————————————————————
————————————————————
解答：
