数据结构第九章查找习题及答案.docx

《数据结构第九章查找习题及答案.docx》由会员分享，可在线阅读，更多相关《数据结构第九章查找习题及答案.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章查找一、选择题1 .若查找每一个记录的概率均等，则在具有D个记录的连续顺叙文件中采用顺序查找法查找 个记录，其平均查找长度ASL为（）。A. （n-l）/2 B. n/2C. （n+l）/2D. n2 .下面关于二分查找的叙述正确的是（）A.表必须有序，表可以顺序方式存储，也可以链表方式存储C,表必须有序，而且只 能从小到大罗列B.表必须有序且表中数据必须是整型，实型或者字符型 D.表必须有序，且表 只 能以顺序方式存储 3.用二分（对半）查找表的元素的速度比用顺序法（）A.必然快 B.必然慢 C,相等 D.不能确定4 .具有12个关键字的有序表，折半查找的平均查找长度（）A. 3. 1

2、B. 4C. 2.5D. 55 .当采用分块查找时，数据的组织方式为（）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或者最小） 的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或者最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同6 .二叉查找树的查找效率与二叉树的（1）有关，在（2）时其查找效率最低（1）：A.高度B.结点的多少C.树型D.结点的位置（2）:A.结点太多B.彻底二叉树C.呈单枝树D.结点太复杂。7 .对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找

3、失 败，它们的平均查找长度是（D）,对于查找成功，他们的平均查找长度是（2）供选择 的答案：A.相同的B.不同的9 .分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A. （100, 80,90,60,120, 110, 130） B. （100, 120, 110, 130, 80,60,90）C. （100, 60,80,90,120, 110, 130） D. （100, 80,60,90,120, 130, 110）10 .在平衡二叉树中插入一个结点后造成为了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1,则应作（）型调整以使

4、其平衡。A. LLB. LRC. RLD. RR11 .下面关于m阶B-树说法正确的是（）每一个结点至少有两棵非空子树；树中每一个结点至多有m 1个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后，树长高一层。A. B. C. D.12 . m阶B-树是一棵（）A. m叉排序树B. m叉平衡排序树C. m-1叉平衡排序树D. m+1叉平衡排序树15 .设有一组记录的关键字为19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79）,用链 地址法构造散列表，散列函数为H （key）二key MOD 13,散列地址为1的链中有（） 个记录。A. 1B

5、. 2C. 3D. 416 .关于哈希查找说法不正确的有儿个（）（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是 相同的（3）用链地址法解决冲突易引起会萃现象（4）再哈希法不易产生会萃A. 1B. 2C. 3D. 417 .设哈希表长为14,哈希函数是H（key）二key%ll,表中已有数据的关键字为15, 38, 61, 84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突， 则放入的位置是（）A . 8 B . 3 C . 5 D . 918 .假定哈希查找中k个关键字具有同一哈希值，若

6、用线性探测法把这k个关键字存入散列 表中，至少要进行多少次探测？（）A. k-1 次 B. k 次 C. k+1 次 D. k （k+1） /2 次19 .好的哈希函数有一个共同的性质，即函数值应当以（）取其值域的每一个值。A.最大概率 B.最小概率 C.平均概率D.同等概率20 .将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A. 一定会B. -*定不会C.仍可能会二、判断题1 .采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所 在位置置空，因为这会影响以后的查找。（）2 .在散列检索中，“比较”操作普通也是不可避免的。（）3 . Hash表的平

7、均查找长度与处理冲突的方法无关。（）4 .散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（ ）5 .在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元 素个数有关，而且与每块中元素个数有关。（）6 .就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（）7 .最佳二叉树是AVL树（平衡二叉树）。（）8 .在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。（）9 .二叉树中除叶结点外，任一结点X,其左子树根结点的值小于该结点（X）的值；其右子 树根结点的值2该结点（X）的值，则此二叉树一定是二叉排序树。（）10

8、.有n个数存放在一维数组AL,n中，在进行顺序查找时，这n个数的罗列有序或者无 序其平均查找长度不同。（）11 . N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（）12 .在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排 序叉树相同。（）13 . B-树中所有结点的平衡因子都为零。（）14 .在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（）三、填空题1,顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为次；当使用监视哨时，若查找失败，则比较关键字的次数为 。2 .在有序表AL.12中，采用二分查找算法查

9、等于A12的元素，所比较的元素下标挨次 为 O3 .在有序表AL.20中，按二分查找方法进行查找，查找长度为5的元素个数是4 .高度为4 （含叶子结点层）的3阶b-树中，最多有 个关键字。5 .在一棵ni阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有 的关键字的个数是；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个薮是 o6 .在哈希函数H （key）二key%p中，p值最好取。8 .如果按关键码值递增的顺序挨次将关键码值插入到二叉排序树中，则对这样的二叉排序 树检索时，平均比较次数为 o9 .如果关键码按值排序，而后用二分法挨次检索这些关键码，

10、并把检索中遇到的在二叉树 中没有浮现的关键码挨次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为 O (提示：此时二叉排序树与折半查找的二叉判定树一样了)10 .平衡因子的定义是11 .查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和 查找。处理哈希冲突的方法有(4)_(5) _ (61和_(7L o12 .具有N个关键字的B树的查找路径长度不会大于 o在一棵有N个结点的非平衡二叉树中进行查找，平均时间复杂度的上限(即最坏情况平均时间复杂度)为13 .高度为5 (除叶子层之外)的三阶B-树至少有 个结点。14 .可以惟一的标识一个记录的关键字称为 o15

11、 .动态查找表和静态查找表的重要区别在于前者包含有 和 运算，而后者不包含这两种运算。16 .已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分(折 半)查找方法统计成绩大于或者等于X分的学生人数，请填空使之完善。(提示：这时需 要找的是最后一个大于等于X的下标，若查找成功其下标若为m,则有m个学生成绩大 于或者等于X,若查找不成功，若这时low所指向的值小于X,则有lowT个学生成绩 大于或者等于X,注意这时表中可能不止一个数值为X的值，这时我们要查找的是下标 最大的) define N /*学生人数*/int uprx(int aN, int x )/*函数返回大于等

12、于X分的学生人数*/ int low=l, mid, high=N;do mid=(low+high)/2;if (x=amid) else (2);while(_ (3) _);if (alow=low四.应用题1 .概念是基本知识的主要部份，要坚固掌握。这里只列出一部份，目的是引起重视，解答 略。散列地址0123456789关键字140192384275520比较次数11123412查找成功平均查找长度：ASL = (1 + 1 + 1+2+3+4+1+2) /8=15/8 SUCC 以关键字 27 为例：11 (27)=27%7二6 (冲突) H =(6+1) %10=7 (冲突) II

13、 =(6+22)%10=0 (冲突) H =(6+33) %10=5 1所以比较了 4 次。 23注意：计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i (0 WiWm-1)时的查找次数。如下例中m=10o对于关键字集30, 15, 21, 40, 25, 26, 36, 37若查 找表的装填因子为0.8,哈希函数为H (key)=key % 7采用线性探测再散列方法解决冲突， 则哈希表如下：散列地址0123456789关键字2115303625402637比较次数11131126故查找失败时的平均查找长度为：ASL =(4+8+7+6+5+4+3+2+1 + 1) /

14、10=4. 6unsucc111201234567891011A23AASL查找成功二18/137.如下图：9. (1)当插入26后的树形为:插入85后树形为:删除53后为:删除37后:(1)构造的二叉排序树为：(4)删除结点66后;(2)对于一个二叉排序树，想得到一个从大到小的序列只要先读右子树再读根结点，最后 读左子树的遍历这颗二叉树就可以了。如果是要从小到大的序列，则只需中序遍历这颗 二叉树就可。(3)该二叉树的平均查找长度为：ASL= (1*1+2*2+3*4+4*3) /10=2.910. (1)二叉判定树为(2)若要查找54,则需要查找：30, 63, 42, 54(3)若要查找90,则需查找：30, 63, 87, 95,空(4)假定每一个元素的查找概率相等，则查找成功时的平均查找长度为 ：ASL= (1*1+2*2+4*3+5*4) /12=37/12