第八章查找习题_数据结构

1、习题八査找一、单项选择题1 顺序查找法适合于存储结构为（ A.散列存储C.压缩存储）的线性表。B.顺序存储或链式存储D.索引存储2. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL%（A（nT）/2B. n/2C. （n+l）/23. 适用于折半查找的表的存储方式及元素排列要求为（A.链接方式存储，元素无序 B.链接方式存储，C.顺序方式存储，元素无序 D.顺序方式存储，)oDn）元素有序 元素有序4. 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但 前者比后者的查找速度（）A.必定快 B.不一定 C.在

2、大部分情况卞要快D.取决于表递增还是递减5. 当采用分块查找时，数据的组织方式为（）A. 数据分成若干块，B. 数据分成若干块，的数据组成索引块C. 数据分成若干块，D. 数据分成若干块，每块内数据有序每块内数据不必有序，但块间必须有序，每块内最大（或最小）每块内数据有序，每块内最人（或最小）的数据组成索引块 每块（除最后一块外）中数据个数需相同6. 二叉树为二叉排序树的充分必要条件是其任一结点的值均人于其左孩子的值.小于其右 孩子的值。这种说法（A.正确B.错误7. 二叉查找树的查找效率与二叉树的（1）（1）： A.高度B.结点的多少（2）: A.结点太多 B.完全二叉树)o）有关，在（2）

3、C.树型D.C.呈单枝树D.）时其查找效率最低。 结点的位置 结点太复杂。则可采用（8. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，法。A.分快查找B.顺序查找C.折半查找D.9. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（A. （100, 80, 90, 60, 120, 110, 130） B.C. （100, 60, 80, 90, 120, 110, 130） D.10下图所示的4棵二叉树，（）是平衡二叉树。基于属性）查找90,60,80,90,)。60,90)(100, 120, 110, 130, 80,(100, 80,60,90,120

4、, 130, 110)（A）11散列表的平均查找长度（与处理冲突方法有关而与表的长度无关 与处理冲突方法无关而与表的长度有关 与处理冲突方法有关且与表的长度有关 与处理冲突方法无关且与表的长度无关)oA.B.C.D.20, 84, 27, 55, 11, 10, 79,用链13,散列地址为1的链中有（）个设有一组记录的关键字为19, 14, 23, 1, 68, 地址法构造散列表,散列函数为H （key）二key MOD记录。A1B2C3D412. 关于杂凑查找说法不正确的有几个（）（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插

5、入任一个元素的时间是 相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A. 1B2C3D413. 设哈希表长为14,哈希函数是H（key）=key%U,表中己有数据的关键字为15, 38, 61, 84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的 位置是（）A. 8B3C5D914. 将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A. 一定会B. 一定不会C.仍可能会二、填空题1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为次：当使用监视哨时，若查找失败，则比较关键字的次数为。2. 在顺序表（8,11

6、,15,19,25,26,30,33,42,48, 50）中，用二分（折半）法査找关键码值 20,需做的关键码比较次数为.3. 一个无序序列可以通过构造一棵_ 树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。4. 哈希表是通过将查找码按选定的.一和.把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是-和一一个好的哈希函数其转换地址应尽可能.，而且函数运算应尽可能5. 平衡二叉树又称,其定义是°6. 在哈希函数H （key） =key%p中，p值最好取。7. 假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行次探测。8. 法构

7、造的哈希函数肯定不会发生冲突。9. 动态查找表和静态查找表的重要区别在于前者包含有和运算，而后者不包含这两种运算。10. 在散列存储中，装填因子a的值越大，则.；a的值越小，则._11. 已知N元整型数组a存放N个学生的成绩，已按由人到小排序，以下算法是用对分（折 半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。#define N /*学生人数*/int uprx（int aN, int x ）/*函数返回大于等于X分的学生人数*/ int head二 1, mid, rear二N;do mid二（head+rear）/2;if (x<=a mid) 一_ else _(2

8、)_while(=/3)_);if (aheadx) return head-1;return head; 三、应用题1. HASH方法的平均查找路长决定于什么？是否与结点个数N有关？处理冲突的方法主要 有哪些？2. 设有一组关键字9,01,23, 14, 55, 20, 84, 27,采用哈希函数：H (key) =key mod 7 ,表 长为10,用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=f, 2 3：,-,)解 决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。3. 选取哈希函数H (key)二key mod 7,用链地址法解

9、决冲突。试在0 - 6的散列地址空间内 对关键字序列31,23,17,27, 19,11,13,91,61,41构造哈希表,并计算在等概率下成功查 找的平均查找长度。4. 输入一个正整数序列(53, 17, 12, 66, 5& 70,87,25,56,60)，试完成下列各题。(1) 按次序构造一棵二叉排序树BSo(2) 依此二叉排序树，如何得到一个从人到小的有序序列？(3) 画出在此二叉排序树中删除“66”后的树结构。5. 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K,其效 率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如 何

10、？为什么？6. 一棵二叉排序树结构如下,各结点的值从小到人依次为1-9,请标出各结点的值。7. 假定对有序表：(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95)进行折半查找，试回答下列问题:(1) .画出描述折半查找过程的判定树；(2) 若查找元素54,需依次与那些元素比较？(3) 若查找元素90,需依次与那些元素比较？(4) .假定每个元素的查找概率相等，求查找成功时的平均查找长度。四、算法设计题1. 设记录Rl,R2,-,Rn按关键字值从小到人顺序存储在数组:rln中，在rn+l处设立一 个监督哨,其关键字值为+8；试写一查找给定关键字k的算法;并画出

11、此查找过程的判 定树，求出在等概率情况下查找成功时的平均查找长度。2. 试编写算法求出指定结点在给定的二叉排序树中所在的层数。写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指 针P所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。第九章查找一、单项选择题1. B2. C3. D4. C5. B6. B7. C C8. A9. C10. B11. A12. D13. B14. D15. C二填空题1. n n+12. 43. 二叉排序_4. (1)哈希函竅解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6) 简单5. AVL树(高

12、度平衡树，高度平衡的二叉排序树)或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于lo6. 小于等于表长的最大素数或不包含小于20的质因子的合数7. k(k+l)/28. 直接定址法9. 插入删除10. 存取元素时发生冲突的可能性就越人存取元素时发生冲突的可能性就越小11. (l)rear=mid-l (2)head二mid+1 (3)head>rear三、应用题1. 哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比)，它反映了 哈希表的装满程度，该值一般取0.65P.9。散列表存储中解决碰撞的基本方法： 开放定址法形成地址序列的公式是：Hi= (

13、H (key) +dJ % m,其中m是表长，d是增量。根据&取法不同，又分为三种：a. d：二1, 2,，m-1称为线性探测再散列，其特点是逐个探测表空间，只要散列表 中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一 散列地址。b. d =f, -f, 2：, -22,，±k2 (kWm/2)称为二次探测再散列，它减少了聚集， 但不容易探测到全部表空间，只有当表长为形如4j+3 (j为整数)的素数时才有可能。c. d二伪随机数序列，称为随机探测再散列。 再散列法 HfRH, (key) i=l, 2,，k,是不同的散列函数，即在同义词产生 碰

14、撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生''聚集”，但增加 了计算时间。 链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用HO.m-1表示，分量初始值为空指针。凡散列地址为i (OWiWm-1)的记录均插在以Hi 为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但 增加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是 元素个数受表长限制。 建立公共溢出区 设HO.m-1为基本表，凡关键字为同义词的记录，都填入溢出 区OO ml o2.散列地址0123456789关键字140192384

15、275520比较次数11123412平均查找长度：ASL*二(1+1+1+2+3+4+1+2) /8二 15/8以关键字 27 为例：H (27) =27%7=6 (冲突) H：= (6+1) %10=7 (冲突)H:= (6+22) $10二0 (冲突)Hs= (6+33) %10=5 所以比较了 4 次。3. 表略ASL唉=15/104. 略5. 在二叉排序树上查找关键字K,走了一条从根结点至多到叶子的路径，时间复杂度是 O(logn),而在中序遍历输出的序列中查找关键字K,时间复杂度是0(n)。按序输入建立的 二叉排序树，蜕变为单枝树，其平均查找长度是(n+1) /2,时间复杂度也是0

16、(n)o6. 略7. 略四、算法设计题1 int Search (rec typ 己 r int n, key type k)/在n个关键字从小到犬排列的顺序表中，查找关键字为k的结点。rn+l.key二MAXINT： /在高端设置监视哨i=l;while (rij. key<k) i+；if (rn+1. key=k) return (i% (n+1 )；else return (0)/算法search结束查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有序，但进行 顺序查找，查找成功的平均查找长度亦为(n+1) /2。2. 解答：.分析：采用递归方法，从根结点开始查找

17、结点p,若查询结点是所要找的结点， 返回其深度h0。否则，到左、右子树上去找，查找深度加1。int findl ( birtreptr T , p , int hO )/*在二叉树排序树T中查找结点p的层次，若不在时返回空值。hO为根结点T的层次*/ if ( p = NULL ) return ( 0 ) ;/* 没找到，返回 0 */if( p =T)return( hO ) ;/* 找到 */else if (p -data < T data ) return( findl ( T >lchild, p, hO) +1) ; /* 到左子树去找*/else return ( f indl ( T -> rchild, p, hO) + 1) ;/* 到右子树去找*/int f ind2 ( birtrp tr T, p ) :ret urn ( f indl ( T, p, 1 ) ) ; 3. void Delete (BSTree t, p)/在二叉排序树t中，删除f所指结点的右孩子(由P所指向)的算法if (p"> 1 chi 1 d=nul 1) f>rchild=p">rch