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

《第八章查找习题_数据结构.doc》由会员分享，可在线阅读，更多相关《第八章查找习题_数据结构.doc（16页珍藏版）》请在三一文库上搜索。

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

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

3、2):A.结点太多复杂。B. 结点的多少 C. 树型B. 完全二叉树D. 结C. 呈单枝树 D. 结点太8. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采 用 （） 查找法。A. 分快查找B. 顺序查找C. 折半查找D. 基于属性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 ,

4、120, 130, 110)10.下图所示的4棵二叉树,（）是平衡二叉树。(A)(C)A. 1B. 2C. 3D. 4(B)(D)11. 散列表的平均查找长度（）。A. 与处理冲突方法有关而与表的长度无关B. 与处理冲突方法无关而与表的长度有关C. 与处理冲突方法有关且与表的长度有关D. 与处理冲突方法无关且与表的长度无关12. 设有一组记录的关键字为19, 14, 23, 1, 68, 20, 84, 27, 55, 11,10, 79，用链地址法构造散列表，散列函数为 H（key） =key MOD 13,散列地址为 1的链中有（）个记录。13. 关于杂凑查找说法不正确的有几个（ ）（1）

5、采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素 的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集A. 1 B. 2 C. 3 D. 414. 设哈希表长为 14，哈希函数是 H（key）=key%11, 表中已有数据的关键字为 15，38，61，84 共四个，现要将关键字为 49的结点加到表中，用二次探测再散列 法解决冲突，则放入的位置是 （ ）A8B 3C5D915. 将 10 个元素散列到 100000个单元的哈希表中，则（）产生冲突。A. 一定会 B. 一定不会 C. 仍可能会二、填空题

6、1. 顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为 _ _ 次；当使用监视哨时，若查找失败，则比较关键字的次数为 _ _ 。2. 在顺序表（ 8,11,15,19,25,26,30,33,42,48,50 ）中，用二分（折半）法 查找关键码值 20，需做的关键码比较次数为 .3一个无序序列可以通过构造一棵 _ _ _ _ 树而变成一个有序序 列，构造树的过程即为对无序序列进行排序的过程。4. 哈希表是通过将查找码按选定的 _ _ 和_ ，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_ _和 _ _ 。一个好的哈希函数其转换地址应 尽可能 _ ，而且函数运算应

7、尽可能 _ _5. 平衡二叉树又称 ，其定义是 。6. 在哈希函数H( key) =key%p中，p值最好取。7假定有 k 个关键字互为同义词，若用线性探测再散列法把这k 个关键字存入散列表中，至少要进行 次探测。8. 法构造的哈希函数肯定不会发生冲突。9. 动态查找表和静态查找表的重要区别在于前者包含有 和运算，而后者不包含这两种运算。10. 在散列存储中，装填因子 a的值越大，则_； a的值越小，则11. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算 法是用对分(折半)查找方法统计成绩大于或等于 X分的学生人数，请填空使之完 善。#define N /* 学生人数 */i

8、nt uprx(int aN,int x )/* 函数返回大于等于 X 分的学生人数 */ int head=1,mid,rear=N;do mid=(head+rear)/2;if(x<=amid) _(1)_ else_(2)_;while(_(3)_);if (ahead<x) return head-1;return head; 三、应用题1. HASF方法的平均查找路长决定于什么？是否与结点个数N有关？处理 冲突的方法主要有哪些？2. 设有一组关键字 9,01,23,14,55,20,84,27 ，采用哈希函数： H( key) =key mod 7 ，表长为 10，用开

9、放地址法的二次探测再散列方法 Hi=(H(key)+di) mod 10(di=12,22,32,)解决冲突。要求：对该关键字序列构造哈希表，并计算 查找成功的平均查找长度。3. 选取哈希函数H( key) =key mod 7,用链地址法解决冲突。试在0 - 6的散列地址空间内对关键字序列 31,23,17,27,19,11,13,91,61,41构造哈希表，并计算在等概率下成功查找的平均查找长度。4. 输入一个正整数序列( 53,17,12,66,58,70,87,25,56,60 )，试完成下列 各题(1) 按次序构造一棵二叉排序树BS(2) 依此二叉排序树，如何得到一个从大到小的有序序

10、列？(3) 画出在此二叉排序树中删除“ 66”后的树结构5. 直接在二叉排序树中查找关键字 K与在中序遍历输出的有序序列中查找关 键字K,其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此 树进行查找，其效率如何？为什么？6. 一棵二叉排序树结构如下，各结点的值从小到大依次为1-9，请标出各结 点的值。7. 假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试 回答下列问题:(1) .画出描述折半查找过程的判定树;(2) .若查找元素54,需依次与那些元素比较？(3) . 若查找元素 90，需依次与那些元素比较 ?(4) . 假定每个元

11、素的查找概率相等，求查找成功时的平均查找长度。四、算法设计题1. 设记录R1,R2,Rn按关键字值从小到大顺序存储在数组r1.n中,在rn+1处设立一个监督哨,其关键字值为+x;试写一查找给定关键字k的算法;并 画出此查找过程的判定树 , 求出在等概率情况下查找成功时的平均查找长度。2试编写算法求出指定结点在给定的二叉排序树中所在的层数。3. 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设 删除结点由指针 p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结 点的右孩子。第九章 查找一、单项选择题1 B2C3D4C5B6B7. C C8A9C10B11A12. D

12、13. B14. D15. C二、填空题1. n n+12. 43 二叉排序4. (1) 哈希函数 (2) 解决冲突的方法 (3) 选择好的哈希函数 (4) 处理冲突的方 法 (5) 均匀 (6) 简单5. AVL 树(高度平衡树，高度平衡的二叉排序树)或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小 于等于 1。6. 小于等于表长的最大素数或不包含小于 20 的质因子的合数7k(k+1)/28. 直接定址法9. 插入 删除10 存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能 性就越小11(1)rear=mid-1 (2)head=mid+1(3)head>

13、rear三、应用题1哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之 比)，它反映了哈希表的装满程度，该值一般取 0.650.9 。散列表存储中解决碰撞的基本方法： 开放定址法形成地址序列的公式是：Hi= (H(key) +di) % m其中m是表长，di是增量。根据di取法不同，又分为三种：a. di =1，2,，m-1称为线性探测再散列，其特点是逐个探测表空间，只 要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词 的关键字争夺同一散列地址。b. di =12 , -12 , 22, -22，k2 (k<m 称为二次探测再散列，它减少了聚集，但不

14、容易探测到全部表空间，只有当表长为形如4j+3 (j为整数)的素数时才有可能。c. di =伪随机数序列，称为随机探测再散列。 再散列法 Hi=RHi (key) i=1，2,，k，是不同的散列函数，即在 同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产 生“聚集”，但增加了计算时间。 链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H0.m-1表示，分量初始值为空指针。凡散列地址为i (0<i <m-1 )的记录均插在以Hi为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为

15、开散列 表，而中的散列表称闭散列表，含义是元素个数受表长限制。 建立公共溢出区设H0.m-1为基本表，凡关键字为同义词的记录，都填入溢出区O0.m-1。2.散列地址0123456789关键字140192384275520比较次数11123412平均查找长度：ASLsucc=（ 1+1+1+2+3+4+1+2 /8=15/8以关键字27为例：H（27） =27%7=6（冲突）H仁（6+1） %10=7（冲突）H2= (6+22) %10=0(冲突)H3= (6+33) %10=5 所以比较了 4 次。3. 表略ASLsucc =15/104. 略5. 在二叉排序树上查找关键字K,走了一条从根结点

16、至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K,时间复杂度是0(n)。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是( n+1) /2 ，时间复杂度也是 0( n)。6. 略7. 略四、算法设计题1. int Search ( rectype r ， int n ， keytype k )/在n个关键字从小到大排列的顺序表中，查找关键字为k的结点。rn+1.key=MAXINT ；/ 在高端设置监视哨i=1 ；while ( ri. key<k ) i+ ；if (rn+1.key=k) return( i%(n+1)；else return

17、 (0)/ 算法 search 结束查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有 序，但进行顺序查找，查找成功的平均查找长度亦为(n+1)/2 。2 解答：分析：采用递归方法，从根结点开始查找结点p,若查询结点是所要找的结点，返回其深度hO。否则，到左、右子树上去找，查找深度加1。int find1 ( birtreptr T , p , int h0 )/*在二叉树排序树T中查找结点p的层次，若不在时返回空值。hO为根结点T的层次*/ if ( p = NULL ) return ( O ) ;/* 没找到，返回 O */if( p =T)return( hO ) ;/

18、* 找到 */else if (p -> data < T -> data ) return( find1( T ->lchild,p,hO)+1) ; /* 到左子树去找 */else return ( find1 ( T -> rchild,p,hO) +1);/* 到右子树去找 */int find2( birtrptr T, p ) return ( find1 ( T, p,1 ) ) ; 3. void Delete ( BSTree t ， p)/在二叉排序树t中，删除f所指结点的右孩子(由p所指向)的算法女else / 用 p 左子树中的最大值代替 p 结点的值q=p->lchild ； s=q；while (q->rchild )s=q ；q=q->rchild ；/ 查 p 左子树中序序列最右结点if (s=p->lchild ) /p 左子树的根结点无右子女p->data=s->data ；p->lchild=s->lchild；free (s)； elsep->data=q->data ； s->rchild=q->lchild ；free (q)； /Delete