《习题9查找及其答案.pdf》由会员分享，可在线阅读，更多相关《习题9查找及其答案.pdf（5页珍藏版）》请在三一文库上搜索。
1、习题习题 9 一、单项选择题一、单项选择题 1. 若查找每个元素的概率相等，则在长度为 n 的顺序表上查找任一元素的平均查找长 度为( )。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2. 对于长度为 9 的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找 长度为( )的 9 分之一。 A. 20 B. 18 C. 25 D. 22 3. 对于长度为 18 的顺序存储的有序表，若采用折半查找，则查找第 15 个元素的比较 次数为( )。 A. 3 B. 4 C. 5 D. 6 4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，
2、若采用折半查找，则查找元 素 26 的比较次数为( )。 A. 2 B. 3 C. 4 D. 5 5. 对具有 n 个元素的有序表采用折半查找，则算法的时间复杂度为( )。 A. O(n) B. O(n 2) C. O(1) D. O(log2n) 6. 在索引查找中，若用于保存数据元素的主表的长度为 n，它被均分为 k 个子表，每个 子表的长度均为 n/k，则索引查找的平均查找长度为( )。 A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+1 7. 在索引查找中，若用于保存数据元素的主表的长度为 144，它被均分为 12 子表，每 个子表的长度均为 12，
3、则索引查找的平均查找长度为( )。 A. 13 B. 24 C. 12 D. 79 8. 从具有 n 个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致 为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n 2) 9. 从具有 n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为 ( )。 A. O(n) B. O(1) C. O(log2n) D. O(n 2) 10. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( )。 A. -11 B. -22 C. 12 D. 01 11. 若根据查找表(23,44,36,48,52,
4、73,64,58)建立哈希表，采用 h(K)=K%13 计算哈希 地址，则元素 64 的哈希地址为( )。 A. 4 B. 8 C. 12 D. 13 12. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表， 采用 h(K)=K%7 计算哈希地 址，则哈希地址等于 3 的元素个数( )。 A. 1 B. 2 C. 3 D. 4 13. 若根据查找表建立长度为 m 的哈希表，采用线性探测法处理冲突，假定对一个元素 第一次计算的哈希地址为 d，则下一次的哈希地址为( )。 A. d B. d+1 C. (d+1)/m D. (d+1)%m 二、填空题 1. 以顺序查找方法
5、从长度为 n 的顺序表或单链表中查找一个元素时，平均查找长度为 _，时间复杂度为_。 2. 对长度为 n 的查找表进行查找时，假定查找第 i 个元素的概率为 pi,查找长度（即在 查找过程中依次同有关元素比较的总次数） 为 ci， 则在查找成功情况下的平均查找长度的计 算公式为_。 3. 假定一个顺序表的长度为 40，并假定查找每个元素的概率都相同，则在查找成功情 况下的平均查找长度_，在查找不成功情况下的平均查找长度_。 4. 以折半查找方法从长度为 n 的有序表中查找一个元素时，平均查找长度约等于 _的向上取整减 1，时间复杂度为_。 5. 以折半查找方法在一个查找表上进行查找时，该查找表
6、必须组织成_存储的 _表。 6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找 43 和 56 元素时，其比较次数 分别为_和_。 7. 假定对长度 n=50 的有序表进行折半查找，则对应的判定树高度为_，最后一 层的结点数为_。 8. 假定在索引查找中，查找表长度为 n，每个子表的长度相等，设为 s，则进行成功查 找的平均查找长度为_。 9. 在索引查找中，假定查找表（即主表）的长度为 96，被等分为 8 个子表，则进行索 引查找的平均查找长度为_。 10. 在一棵二叉排序树中， 每个分支结点的左子树上所有结点的值一定_该结点 的值，右子树上所有结点的值一定_该结
7、点的值。 11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个_。 12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 _，若元素的值小于根结点的值，则继续向_查找，若元素的值大于根结点的 值，则继续向_查找。 13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结 点的_插入，若元素的值大于根结点的值，则接着向根结点的_插入。 14. 根据 n 个元素建立一棵二叉排序树的时间复杂度大致为_。 15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超 过_。 16. 假定对线性表(38,25,74,52,48)进
8、行哈希存储，采用 H(K)=K % 7 作为哈希函数， 采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到_次存储冲突。 17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用 H(K)=K % 7 作为哈希函数， 采用线性探测法处理冲突，则平均查找长度为_。 18. 在线性表的哈希存储中，装填因子又称为装填系数，若用 m 表示哈希表的长度， n 表示线性表中的元素的个数，则等于_。 19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用 H(K)=K % 9 作为哈希 函数，则哈希地址为 0 的元素有_个，哈希地址为 5 的元素有_个。 三、
9、应用题 1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)， 试画出对应的折 半查找判定树，求出其平均查找长度。 2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序 生成的一棵二叉排序树，求出其平均查找长度。 3. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)， 哈希地址空间 为 HT13，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈 希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。 元素 32
10、 75 29 63 48 94 25 46 18 70 初始哈希地址 最终哈希地址 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 4. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地 址空间为 HT12，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的 哈希表，并求出平均查找长度。 四、算法设计题 1. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存 储结构，且树中结点的关键字均不同。 2. 试将折半查找的算法改写成递归算法。 习题习题 9 参考参考答案答案 一、单项选择
11、题 1. D 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. A 10. A 11. C 12. B 13. D 二、填空题 1. (n+1)/2, O(n) 2. n i iic p 1 3. 20.5, 41 4. log2(n+1)，O(log2n) 5. 顺序 有序 6. 1，3 7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于 11. 有序序列 12. 查找成功，左子树，右子树 13. 左子树，右子树 14. O(nlog2n) 15. 1 16. 5 17. 2 18. n/m 19. 3， 2 三、应用题 1. 折半查找判
12、定树如图 7-3 所示，平均查找长度等于 29/10。图 7-3 中的结点与有序表中元 素的对应关系如下表所示。 图 7-3 10 9 4 5 6 7 8 1 2 3 2. 二叉排序树如图 7-4 所示，平均查找长度等于 32/10。 3. H(K)=K % 13 平均查找长度为 14/10，其余解答如下。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 6 10 3 11 9 3 12 7 5 5 最终哈希地址 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 4
13、8 75 63 25 4. H(K)=K % 11，哈希表如图 7-5 所示，平均查找长度 17/12。 四、算法设计题 1. 设计思路：进入判别算法之前，pre 取初值为 min(小于树中任一结点值)，fail=FALSE, 即认为 bt 是二叉排序树。按中序遍历 bt，并在沿向根结点，与前趋比较，若逆序，则 fail 为 TRUE,则 bt 不是二叉排序树。 void bisorttree(bitree bt,keytype pre, bool /判断左子树 if (bt-data_keydata_key; bisorttree(bt-rchild,pre,fail); /判断右子树 /bisorttree 说明：较为直观的方法，可套用中序遍历非递归算法。 2. int search_bin(SeqTable st , keytype k , int low , int high) if (lowhigh) return (0); /不成功 else mid=(low+high)/2; if (k= =st.elemmid.key) return (mid) ; /成功 else if (kst.elemmid.key) return (st,k,low,mid-1); else return(st,k,mid+1,high); /search-bin