发布时间 : 星期四 文章《数据结构》习题集：第9章查找(第1次更新2019-5)更新完毕开始阅读
结点数为（ ），比较五次查找成功的结点数为（ ）。总平均查找长度为（ ）。【＊＊】 23. 折半查找方法仅适用于这样的表：表中的记录必须（ ），其存储结构必须是（ ）。【＊】
24. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等
于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9.1所示的二叉树中，并使之满足上述性质。（圆圈旁边的数字表示插入结点的序号）【＊，★】
25. 设线性表L=（a1，a2，…，an）（n>2），表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查
找和折半查找与k相等的元素，比较次数为s和b，若检索不成功，则s和b的数据关系是（）。（注：大于、小于或等于）【＊】
26. 某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相
同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为（ ），最大比较次数为（ ）。现把10000个元素按排列顺序划分成若干组，使得每一组中有g个元素（最后一组可能小于g）。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的g是（ ），此时的平均比较次数是（ ）。【＊＊，★】
27. 长度为225的表，采用分块查找法，每块的最佳长度是（ ），应分（ ）块，若每块的长度为10，
则平均查找长度为（ ）。【＊＊，★】
28. 已知有序表为（13，17，20，32，48，54，65，79，86，91，97），当采用折半查找法查找86时需进行
（ ）次比较可确定查找成功。查找48时需进行（ ）次比较可确定查找成功，查找100时需进行（ ）次比较才能确定查找不成功。【＊＊】
四、 简答题
1. 简述顺序查找、折半查找和分块检索法对被检索表中元素中的要求。若检索表中每个元素概率相同，则对一
个长度为n的表，用上面三种方法检索时平均查找长度为多少？【＊＊，★】
2. 画出长度为10的有序表进行折半查找的一棵判定树，并求其等概率下的平均查找长度。【＊＊】
3. 有一个10000项线性表，若采用分区查找，问分成多少块较理想？平均查找长度为多少？若每块为40，则平
均查找长度为多少？【＊＊】
4. 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key，采
用开放地址法的线性探测再散列方法解决冲突，试在0到8的Hash地址空间中对该关键字序列构造Hash表。【＊＊】
2
5. 若哈希表的地址范围为0到9，Hash函数为H(key)=(key+2) mod 9，并采用链地址法处理冲突，画出元素7，
4，5，3，6，2，8，9依次插入哈希表以后该哈希表的状态。【＊＊，★】
6. 假定有n个关键字，它们具有相同的哈希函数值，用线性探测方法把这n个关键字存入到哈希表中要做多少
次探测？【＊＊】
7. 地址空间为0-14的散列表中，对关键字序列（JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，
DEC）构造哈希函数：H(key)=floor(i/2)，其中i为关键字中第一个字母在字母表中的序号。用如下两种处理冲突的方法：（1）线性探测法，（2）链地址法。分别求出这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。【＊＊，★】
8. 有一个400项的表，欲采用索引顺序查找方法进行查找，问：
1) 分成多少块最为理想？ 2) 每块的理想长度是什么？
3) 平均查找长度是多少？【＊＊】
9. 设有一组关键字（19，05，21，24，45，20，68，27，70，11，10），采用哈希函数：H(key)=key，采用
线性探测再散列方法解决冲突，试在0到14的散列地址空间中对该关键字序列构造哈希函数。并求查找成功和不成功时的平均查找长度。【＊＊】
10. 线性表的关键字集合（47，26，120，08，39，68，96，23，70，63，57），已知散列函数为：
11. 12. 13.
14. 15.
H(key)=key，采用拉链法处理冲突。设计出这种链表结构，并计算该表的查找成功和不成功的平均查找长度。【＊＊】
建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各是多少？【＊＊】
分别画出在线性表（06，10，19，24，37，42，50，83）中进行折半查找，查找关键字10和30的过程。【＊】
设二叉排序树中的关键字由1到100内的整数构成，现要查找关键字为63的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列？【＊，★】 1) 12，25，71，68，33，34，37，63 2) 92，20，91，24，88，25，36，63 3) 95，22，91，24，94，25，63
4) 21，89，77，29，36，38，41，47，63
给定表（25，18，48，07，76，52，81，70，92，15）。试按元素在表中的次序将它们依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树。【＊】
二叉树序树中关键字互不相同，则其中最小元无左孩子，最大元无右孩子，此命题是否正确？最小元和最大元一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？【＊，★】