数据结构--查找-习题及答案

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

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, 8 0, 9 0,6 0, 12 0, 110, 1 3 0） B（100, 120, 1 1 0,13 0,80,60,90）C（1 0 0, 6 0,80, 9 0,120, 1 1 0, 1 3 0） D（1 0 0, 80, 60, 9 0,12 0 ,1 30, 11 0）10在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知 A的左孩子的平衡因子为0右孩子的平衡因子为1 ,

4、则应作（）型调整以使英平衡。A LLB LRCRLD RR11. 下而关于m阶B-树说法正确的是（）每个结点至少有两棵非空子树；树中每个结点至多有m一1个关键字；所有叶子在同一层上；当插入一个数据项引起B树结点分裂后,树长髙一层。A.B.C. D.12. m阶B-树是一棵（ ）A. m叉排序树 B. m叉平衡排序树Cm-1叉平衡排序树 D. m+1叉平衡排序树15. 设有一组记录的关键字为1 9, 1 4, 23,1,68, 20,84, 27,5 5, 11, 10, 7 9,用链 地址法构造散列表，散列函数为H （key ） =key MOD 13,散列地址为1的链中有 （ ）个记录。D.

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

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

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

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

9、12 0中，按二分查找方法进行查找，查找长度为5的元素个数是4髙度为4（含叶子结点层）的3阶b-树中.最多有个关键字。5. 在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是;若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是O6 .在哈希函数H ( k ey) = k e y %p中，p值最好取8. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为O9. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树中没有出现的关键码依次插入到二叉排序树中，则对

10、这样的二叉排序树检索时，平均比 较次数为o (提示：此时二叉排序树与折半查找的二叉判立树一样了)10 平 衡 因 子 的 定 义 是 _1 1.查找是非数值程序设计的一个重要技术问题，基本上分成(1)_查找,_(2). 查找和' (3 )查找。处理哈希冲突的方法有_(4)一 .5 ) _ 、和 _(7)°1 2具有N个关键字的B树的查找路径长度不会大于.在一棵有N个结点的非平衡二叉树中进行查找，平均时间复杂度的上限(即最坏情况平均时间复杂度)为1 3 .髙度为5 (除叶子层之外)的三阶B树至少有个结点。14.可以唯一的标识一个记录的关键字称为c1 5.动态査找表和静态查找表的

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

12、w二 1, mid, h ig h =N：do mid= ( 1 ow+hi g h ) /2;if (x<=a mid) 二 e 1 se 二(2 )二： wh i 1 e( _i f (a low<x) re t u rn low- 1 ;retu r n low; 四、应用题1.名词解释：哈希表叙述B-树左义，主要用途是什么？平衡二叉树(AVL树)平衡因子平均査找长度(ASL)3. 设有一组关键字9,0b 23, 1 4, 5 5, 2 0, 84, 2 7,采用哈希函数:H( k e y) =key mod 7，表长为10,用开放地址法的二次探测再散列方法解决冲突Hi=(H

13、(key) +di) mod 1 0 (di二讥31要求:对该关键字序列构造哈希表，并确左其装填因子,查找成功所需 的平均探査次数。4. 设一组数据为1, 1 4, 2 7, 29, 55, 6 8,10,1 1 ,23，现采用的哈希函数是H (key) =ke y MOD 13,即关键字对13取模，冲突用链地址法解决，设哈希表的大小为1 3 (0. . 1 2),试画出插入上述数据后的哈希表。7. 设有一棵空的3阶B树，依次插入关键字3 0,2 0,10, 4 0, 8 0,58,47,5 0, 2 9 , 22, 5 6,98, 9 9请画出该树。9.已知2棵2-3 B-树如下(省略外结点

14、)：(1)对树G),请分别画出先后插入2 6, 8 5两个新结点后的树形：（2）对树（b）,请分别画出先后删除53, 37两个结点后的树形。10输入一个正整数序列（5 3,17, 1 2,66, 5 8,70,87 , 25, 56, 60）,试完成下列各题。（1）按次序构造一棵二叉排序树BSo（2）依此二叉排序树，如何得到一个从大到小的有序序列？（3）假左每个元素的查找概率相等试计算该二叉排序树的平均查找长度（4）画出在此二叉排序树中删除“ 6 6”后的树结构。11 给泄关键词输入序列CAP,AQU,PIS,ARI,TAU, G EM,CAN,L I B, V 1 R,LEOt SCO, 假

15、左关键词比较按英文字典序，试画岀从一棵空树开始，依上述顺序（从左到右）输入 关键词，用平衡树的查找和插入算法生成一棵平衡树的过程，并说明生成过程中采用了 何种转动方式进行平衡调整，标出树中各结点的平衡系数匚12 假泄对有序表：（ 3,4, 5,7, 24, 30,4 2,54, 6 3, 72, 8 7, 95）进行折半查找. 试回答下列问题：（1）.画出描述折半查找过程的判圧树；（2）.若查找元素54,需依次与那些元素比较？（3）.若查找元素9 0 ,需依次与那些元素比较？（4）假泄每个元素的查找概率相等，求查找成功时的平均查找长度。第9章查找一.选择题1.C2D3D4. A5.B6. 1C

16、6. 2C71 B7. 2A9.C10.C11. B12. B15. D16. B17.D18. D19. D20. C二.判断题1. J2. J3X4. J5. J6. X7. V8. X9. X10X11J12.X13.1 4. X三填空题I . n n+12 6, 9, 11, 123 54. 2 6(第4层是叶子结点，每个结点两个关键字)5 . m-1, m / 2 119. 2, 4, 36 .小于等于表长的最大素数或不包含小于20的质因子的合数8. (n+l)/29. (n+1)/n* log： (n+ 1 )- 110 .结点的左子树的高度减去结点的右子树的髙度II .(1)静态

17、查找表(2)动态查找树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈 希(7)建立公共溢出区n + 112. 1 ogr，51( 2 )+1, (n+l)/2(最坏情况是每个结点只要一个孩子结点的情况，这时的平均时间复杂度为(n + 1 ) /2,而log。(詰(” + 1) 2是通常情况下的ASL)1 3.3114. 主关键字15. 插入 删除16( 1 ) low=mid+ 1(2)high二m i d1( 3 )high>=low四.应用题1.概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。3.散列地址0123456789关键字14019

18、238427L L0020比较次数11123412查找成功平均査找长度：ASLsucc=(l+l 4-1+2+34-4+1 + 2) /8=1 5 /8 以关键字 27 为例:H (27) =27%7 =6(冲突)lh= (6+1)%1 0=7(冲突)Hc=(6+2:) %1 0=0 (冲突)Ho=(6 +33) %1 0=5 所以比较了 4 次。注意：计算查找失败时的平均査找长度，必须计算不在表中的关键字，当其哈希地址为i( 0 WiWm-1)时的查找次数。如下例中m=10 o对于关键字集30, 15,21,4 0 , 25, 26, 36, 37 若査找表的装填因子为0.&哈希函数为H (key)二key % 7采用线性探测再散列方法解决冲 突，则哈希表如下：散列地址0123456789关键字2 115303625402637比较次数11131126故查找失败时的平均查找长度为:ASLs/(4+8+7+6 + 5+4 + 3+2+1+1)/1 0二464.27A&81A551423| 101 41 11I A|ATA1AAAAAAIA290123456789 0 121X 1XASL査找成功=18/137.如下图：9. (1)当插入2 6后的树形为:(2 )删除5 3后为:删除37后:1 0(1)构造的二