1.【全国专升本题】对分(折半)查找适不适合链表结构的序列,为什么?用二分查找的查找速度必然比 线性查找的速度快,这种说法对吗? 答:不适合!虽然有序的单链表的结点是按从小到大(或从大到小)顺序排列,但因其存储结构为单链表 查找结点时只能从头指针开始逐步搜索,故不能进行折半查找 分查找的速度在一般情况下是快些,但在特殊情况下未必快。例如所查数据位于首位时,则线性查找快; 而二分查找则慢得多。 2.【计研题1999假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试 回答下列问题: (1)画出描述折半查找过程的判定树; (2)若查找元素54,需依次与哪些元素比较? (3)若查找元素90,需依次与哪些元素比较? (4)假定每个元素的查找概率相等,求查找成功时的平均查找长度 解 (1)先画出判定树如下(注:mid(1+12)/2}6): 95 (2)查找元素54,需依次与30,63,42,54等元素比较; (3)查找元素90,需依次与30,63,87,95,72等元素比较; (4)求ASL之前,需要统计每个元素的查找次数。判定树的前3层共查找1+2×2+4×3=17次; 但最后一层未满,不能用8×4,只能用5×4=20次 所以ASL=1/12(17+20)=37/12≈3.08 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是 什么?如果要求时间复杂度更小,你采用什么方法?此方法的时间复杂度是多少? 答:查找某个元素的时间复杂度下限,如果理解为最短查找时间,则当关键字值与表头元素相同时,比较 1次即可。要想降低时间复杂度,可以改用Hash查找法。此方法对表内每个元素的比较次数都是0(1) 4.【计研题1999】设哈希(Hash)表的地址范围为0~17,哈希函数为:H(K)=KMOD16 K为关键字,用线性探测法再散列法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49) 造出Hash表,试回答下列问题 (1)画出哈希表的示意图 (2)若查找关键字63,需要依次与哪些关键字进行比较? (3)若查找关键字60,需要依次与哪些关键字比较? (4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度 :(1)画表如下: 01234567891011|121314151617 32176349 244010 303146474 1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比 线性查找的速度快，这种说法对吗？ 答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表， 查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。 二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快； 而二分查找则慢得多。 2.【计研题 1999】假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试 回答下列问题： （1） 画出描述折半查找过程的判定树； （2） 若查找元素 54，需依次与哪些元素比较？ （3） 若查找元素 90，需依次与哪些元素比较？ （4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解： （1） 先画出判定树如下（注：mid=(1+12)/2=6）： 30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素 54，需依次与 30, 63, 42, 54 等元素比较； (3) 查找元素 90，需依次与 30, 63,87, 95, 72 等元素比较； （4） 求 ASL 之前，需要统计每个元素的查找次数。判定树的前 3 层共查找 1＋2×2＋4×3=17 次； 但最后一层未满，不能用 8×4，只能用 5×4=20 次， 所以 ASL＝1/12（17＋20）＝37/12≈3.08 3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是 什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少? 答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较 1 次即可。要想降低时间复杂度，可以改用 Hash 查找法。此方法对表内每个元素的比较次数都是 O（1）。 4. 【计研题 1999】设哈希（Hash）表的地址范围为 0～17，哈希函数为：H（K）＝K MOD 16。 K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出 Hash 表，试回答下列问题： （1） 画出哈希表的示意图； （2） 若查找关键字 63，需要依次与哪些关键字进行比较？ （3） 若查找关键字 60，需要依次与哪些关键字比较？ （4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47