查找的输导练习愿及解答 (一)单项选释题 1,若查找每个元素的概率相等，则在长度为的顺序表上查找任一元素的平均查找长 度为()。 An B ntl C(m-l)/2Dn+1)/2 2对长度为10的顺序表选行查找。若查找前面5个元素的概率相同，均为1/8，查找 后面5个元素的概率相同。均为3/40。则查找任一元素的平均查找长度为( A55B5 C39/8D19/4 及对长度为3的顺序表进行查找。若查找第一个元素的概率为1/2，查找第二个元素 的概率为1/3。查找第三个元素的概率为1/6，则直找任一元素的平均查找长度为()。 A5/3 B2 C7/3 D/3 4对长度为■的单随有序表，若查找每个元素的顺率相等，则查找任一元素的平均查 找长度为()。 A n/2 B(n+l)/2c(n-l)/2Dn/4 5对干长度为的顺序存储的有序表，若采用二分查找。则对所有元素的最长查找长 度为( )的值的向上取整 Af1o%(n+1)门 B「1ogm1c「n/2] D「m*1)/21 6对于长度为的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长 度为{ )的植的向下取整加1， A Llog(n+1)] B Llogin] c Ln/2] D L(m+1)/2] T,。对于长度为9的顺序存储的有序表，若采用二分查找。在等概率情况下的平均查找 长度为( 》的9分之一. A20 B18 C25 022 8对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找 长度为(》。 A3 B4 C 5 9.对于顺序存储的有序表(612,20.26,37.42.650,64)，若采用二分查找，则查找元 素26的查找长度为()： A2 B3 C4 D 5
1 查找的辅导练习题及解答 （一）单项选择题 1．若查找每个元素的概率相等，则在长度为 n 的顺序表上查找任一元素的平均查找长 度为( )。 A n B n+1 C (n-1)/2 D (n+1)/2 2. 对长度为 10 的顺序表进行查找，若查找前面 5 个元素的概率相同，均为 1/8，查找 后面 5 个元素的概率相同，均为 3/40，则查找任一元素的平均查找长度为( )。 A 5.5 B 5 C 39/8 D 19/4 3. 对长度为 3 的顺序表进行查找，若查找第一个元素的概率为 1/2，查找第二个元素 的概率为 1/3，查找第三个元素的概率为 1/6，则查找任一元素的平均查找长度为( )。 A 5/3 B 2 C 7/3 D 4/3 4. 对长度为 n 的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查 找长度为( )。 A n/2 B (n+1)/2 C (n-1)/2 D n/4 5. 对于长度为 n 的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长 度为( )的值的向上取整。 A log2(n+1) B log2n C n/2 D (n+1)/2 6. 对于长度为 n 的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长 度为( )的值的向下取整加 1。 A log2(n+1) B log2n C n/2 D (n+1)/2 7. 对于长度为 9 的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找 长度为( )的 9 分之一。 A 20 B 18 C 25 D 22 8. 对于长度为 18 的顺序存储的有序表，若采用二分查找，则查找第 15 个元素的查找 长度为( )。 A 3 B 4 C 5 D 6 9. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用二分查找，则查找元 素 26 的查找长度为( )。 A 2 B 3 C 4 D 5
10,对具有个元素的有序表采用二分查找，则算法的时间复杂性为()。 A D(m) B 0(n')C 0(1)D 0(logn) 1山，在素引查我中，若用于保存数据元素的主表的长度为，它被均分为k个子表，每 个子表的长度均为n/k,则索引查找的平均查找长度为()。 A nek B k*n/k C (k+m/k)/2 D (k*n/k)/2+1 12,在素引查找中。若用于保存数据元素的主表的长度为■，它被均分为若干个子表， 每个子表的长度均为s,则索引查找的平均查找长度为()， A (mts)/2 B (n/s+s)/2+1 C(n*s)/2+1D(n/s*s)/2 13,在素引查找中，若用于保存数据元素的主表的长度为144。它被均分为12子表： 每个子表的长度均为12，则索习查找的平均查找长度为( 0. A13 B24 C12 D79 14,在黎引查找中。若用于保存数据元素的主表的长度为117，它被均分为9子表，则 索引查找的平均查找长度为(》。 A11 B12 C13 D9 1点，在一棵深度为的具有■个元素的二叉排序树中，查找所有元素的最长查找长度为 ()。 An B logn C0+10/2Dh 16.从具有个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复桑性大致 为( ）. A 0(n) B 0(1) C 0(log:n) D0(n) 17.从具有个结点的二又搜素横中查找一个元素封，在最坏情况下的时间复杂性为 A 0(m) B0) C 0(logn) D0(n9 18.向具有口个结点的二义搜索树中插入一个元素时，其时间复杂性大政为( A0(I) B0logn）C0(n) D 0(nlogn) 19.根据n个元素建立一保二义瘦索树时，其时间复杂性大致为()。 A0) B01ogm）C0(n) D 0(mlog) 0.在一棵平衡二叉挂序树中，每个结点的平衡因子的取值范围是( A-1-1 B-2-2 C1-2 D 0-t 21,若根据查找表(23.4H.36,48,52.73,64,58)建立开散列表。采用h0=13计算散
2 10. 对具有 n 个元素的有序表采用二分查找，则算法的时间复杂性为( )。 A O(n) B O(n2 ) C O(1) D O(log2n) 11. 在索引查找中，若用于保存数据元素的主表的长度为 n，它被均分为 k 个子表，每 个子表的长度均为 n/k，则索引查找的平均查找长度为( )。 A n+k B k+n/k C (k+n/k)/2 D (k+n/k)/2+1 12. 在索引查找中，若用于保存数据元素的主表的长度为 n，它被均分为若干个子表， 每个子表的长度均为 s，则索引查找的平均查找长度为( )。 A (n+s)/2 B (n/s+s)/2+1 C (n+s)/2+1 D (n/s+s)/2 13. 在索引查找中，若用于保存数据元素的主表的长度为 144，它被均分为 12 子表， 每个子表的长度均为 12，则索引查找的平均查找长度为( )。 A 13 B 24 C 12 D 79 14. 在索引查找中，若用于保存数据元素的主表的长度为 117，它被均分为 9 子表，则 索引查找的平均查找长度为( )。 A 11 B 12 C 13 D 9 15. 在一棵深度为 h 的具有 n 个元素的二叉排序树中，查找所有元素的最长查找长度为 ( )。 A n B log2n C (h+1)/2 D h 16. 从具有 n 个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂性大致 为( )。 A O(n) B O(1) C O(log2n) D O(n2 ) 17. 从具有 n 个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂性为 ( )。 A O(n) B O(1) C O(log2n) D O(n2 ) 18. 向具有 n 个结点的二叉搜索树中插入一个元素时，其时间复杂性大致为( )。 A O(1) B O(log2n ) C O(n) D O(nlog2n) 19. 根据 n 个元素建立一棵二叉搜索树时，其时间复杂性大致为( )。 A O(n) B O(log2n ) C O(n2 ) D O(nlog2n) 20．在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( )。 A -11 B -22 C 12 D 01 21. 若根据查找表(23,44,36,48,52,73,64,58)建立开散列表，采用 h(K)=K%13 计算散
列地址。则元素4的散列地址为()： A4 B8 C12 D13 22.若根据查线表(23.44,36.48,52.73,64.8)建立开收列表.采用0=7计算收列 地址，则散列地址等于3的元素个数( ）. AI B2 C3 D4 23.若根据查找表(23.44,38.48,52.73,64.8)建立开收列表.采用h)=7计算收列 地址，则同文司元素个数最多为()。 AI B2 C3 D4 24。若根据查找表建立长度为■的闭散列表，采用线性探测法处理冲突，假定对一个元 素第一次计算的散列地址为d,则下一次的散列地址为()。 Ad Bd+1C(d+1)/mD(d+1)%a 25.若根据查找表建文长度为■的闭散列表，采用二次探测法处理冲突，假定对一个元 素第一次计算的列地址为d,则第四次计算的散列地址为()。 A《d+1)知 B (d-1)% C (d+4)%n D (d-d)%a 2.在采用线性深测法处理冲突的闭散列表上，假定装填因子的值为0.5，则查找任 一元素的平均查找长度为( AI B1.5 C2 D25 红，在采用益接法处理冲突的开散列表上，假定装填因子的值为4，则查钱任一元素 的平均查找长度为()。 A3 B3.5 C4 D2.5 然，在散列查找中，平均查找长度主要与( )有关。 A散列表长度B散列元素的个数C转填因子D处理冲突方法 (二)填空题 1.以顺序查找方法从长度为的顺序表或单链表中查找一个元素时，平均查找长度为 一，时间复桑性为一· 2对长度为■的查找表进行查找时，假定查找第1个元素的概率为，查找长度（即在 查找过程中依次同有关元素比较的总次数)为C,则在董找成功情况下的平均董找长度的计 算公式为一· 3.假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情 况下的平均查找长度 ·在查找不成功情况下的平均查找长度
3 列地址，则元素 64 的散列地址为( )。 A 4 B 8 C 12 D 13 22. 若根据查找表(23,44,36,48,52,73,64,58)建立开散列表，采用 h(K)=K%7 计算散列 地址，则散列地址等于 3 的元素个数( )。 A 1 B 2 C 3 D 4 23. 若根据查找表(23,44,36,48,52,73,64,58)建立开散列表，采用 h(K)=K%7 计算散列 地址，则同义词元素个数最多为( )。 A 1 B 2 C 3 D 4 24. 若根据查找表建立长度为 m 的闭散列表，采用线性探测法处理冲突，假定对一个元 素第一次计算的散列地址为 d，则下一次的散列地址为( )。 A d B d+1 C (d+1)/m D (d+1)%m 25. 若根据查找表建立长度为 m 的闭散列表，采用二次探测法处理冲突，假定对一个元 素第一次计算的散列地址为 d，则第四次计算的散列地址为( )。 A (d+1)%m B (d-1)%m C (d+4)%m D (d-4)%m 26. 在采用线性探测法处理冲突的闭散列表上，假定装填因子的值为 0.5，则查找任 一元素的平均查找长度为( )。 A 1 B 1.5 C 2 D 2.5 27. 在采用链接法处理冲突的开散列表上，假定装填因子的值为 4，则查找任一元素 的平均查找长度为( )。 A 3 B 3.5 C 4 D 2.5 28. 在散列查找中，平均查找长度主要与( )有关。 A 散列表长度 B 散列元素的个数 C 装填因子 D 处理冲突方法 （二）填空题 1．以顺序查找方法从长度为 n 的顺序表或单链表中查找一个元素时，平均查找长度为 ________，时间复杂性为________。 2. 对长度为 n 的查找表进行查找时，假定查找第 i 个元素的概率为 pi,查找长度（即在 查找过程中依次同有关元素比较的总次数）为 ci，则在查找成功情况下的平均查找长度的计 算公式为________。 3．假定一个顺序表的长度为 40，并假定查找每个元素的概率都相同，则在查找成功情 况下的平均查找长度________，在查找不成功情况下的平均查找长度________
4。以二分查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于 的向上取参减1，时间复条性为 5.以二分查找方法从长度为50的有序表中查找一个元素时，其查找长度不超过 6.以二分查找方法在一个查找表上进行查找时，该查找表必须组织成存他的 表 7.从有序表(12,18.30,43,66,78.82,95)中分别二分查找43和阅元素时，其查找长度 分别为和 8.二分查找所对应的判定树，低是一棵一，又是一棵 9,假定对长度=50的有序表进行二分查找，则对应的判定树高度为 一，最后一 层的结点数为一· 10.假定在索引查找中，查找表长度为，每个子表的长度相等，设为s,则进行成功 查找的平均查找长度为 11,在素引查找中，假定查找表（即主表》的长度为9%，被等分为8个子表，则进行 索引查找的平均查找长度为一· 12。假定对长度的主表进行素引查我。并假定每个子表的长度均为√：，则选行素引 查找的平均查找长度为，时间复桑性为一· 13。在一绿二夏排序树中，每个分支结点的左子树上所有结点的值一定 该结点 的值，右子树上所有结点的值一定一该结点的值。 14.对一裸二义排序树进行中序遍历时，得到的结点序列是一个 15.从一棵二义排序树中查找一个元素时，若元素的值等于根结点的值，则表明 若元素的值小于根结点的值，则继续向查找，若元煮的值大子根结点的值，则继续 向查找。 16.向一探二叉排序树中插入一个元素封，若元素的值小于根结点的值，则接着向根结 点的插入，若元素的值大于根结点的值，则接着向根结点的 插入。 17.从一棵具有个结点的二叉持序树中查找和插入元素的时闻复象性大致分别为 和 18。根据n个元素建立一棵二义排序树的时间复杂性大致为一。 19在一保平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超 4
4 4．以二分查找方法从长度为 n 的有序表中查找一个元素时，平均查找长度约等于 ________的向上取整减 1，时间复杂性为________。 5．以二分查找方法从长度为 50 的有序表中查找一个元素时，其查找长度不超过 ________。 6．以二分查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的 ________表。 7．从有序表(12,18,30,43,56,78,82,95)中分别二分查找 43 和 56 元素时，其查找长度 分别为________和________。 8．二分查找所对应的判定树，既是一棵_______，又是一棵________。 9．假定对长度 n=50 的有序表进行二分查找，则对应的判定树高度为________，最后一 层的结点数为________。 10．假定在索引查找中，查找表长度为 n，每个子表的长度相等，设为 s，则进行成功 查找的平均查找长度为____________。 11. 在索引查找中，假定查找表（即主表）的长度为 96，被等分为 8 个子表，则进行 索引查找的平均查找长度为________。 12．假定对长度 n 的主表进行索引查找，并假定每个子表的长度均为 n ,则进行索引 查找的平均查找长度为________，时间复杂性为________。 13. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点 的值，右子树上所有结点的值一定________该结点的值。 14．对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。 15．从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_______， 若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的值，则继续 向________查找。 16．向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结 点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。 17．从一棵具有 n 个结点的二叉排序树中查找和插入元素的时间复杂性大致分别为 ________和________。 18．根据 n 个元素建立一棵二叉排序树的时间复杂性大致为________。 19. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超
过 20.假定对线性表(3825,74,52,48)进行散列存储，采用目()=K7作为散列函数： 采用找性探测法处理冲突，则在建立闭散列表的过程中，将会碰到 次存储冲突。 21,假定对线性表(3825,74,52,48)进行散列存错，采用日（保）=K年7作为散列函数， 采用线性探测法处理冲突，则平均查找长度为 2.假定要对长度=1的的线性表遗行散列存储，并采用链接法处理冲突。则对于长度 一20的开散列表，每个散列地址的单统表的长度平均为一· 23.在线性表的散列存储中，装填因子又称为装填系数，若用■表示散列表的长度， n表示线性表中的元素的个数，x等于 2L。在开散列表中，处理冲突的方法为法，在用散列表中，处理冲突的方法为 法。 25.对线性表(18,2563,50,42,32,90)进行散列存储时，若选用日)=9作为散列 函数，则散列地址为0的元素有个，胜列地址为5的元素有 个。 6.在开散列表中插入一个元素的时间复条性为一，查找一个元素的时间复条 性为，假定装填因子为加 7。在采用线性深测法处理冲突的闭散列表中，假定装填因子为和，则进行成功查找的 平均查找长度为 8。在深用二次探测法处理冲突的长度为■的用散列表中，假定根据散列函数求出一个 元素的胜列地址为d,则第五个后雅酸列陆址为 (三)应用思 1.已知一个顺序存储的有序表为(15.25,34.3的，45.56,58.6374.76)，试面出对应的二 分查找列定树，求出其平均查找长度。 2己知一个顺序存精的有序表为(16,28,34,39,45,56,58,6总，74,76，鼠据二分查找每 个元素的比较次数填写下表。 1 3 5 8 10 15 28343945 56 5863 74 76 3假定一个线性表为38,52.25,74,68,1630,54,90,72)，画出按线性表中元煮的次序 生成的一棵二义排序树，求出其平均查找长度， 4,己知一个二叉持序树的广义表表示为38(25(16,52(，74(68(.72)，90)，试根据查
5 过________。 20．假定对线性表(38,25,74,52,48)进行散列存储，采用 H(K)=K % 7 作为散列函数， 采用线性探测法处理冲突，则在建立闭散列表的过程中，将会碰到________次存储冲突。 21．假定对线性表(38,25,74,52,48)进行散列存储，采用 H(K)=K % 7 作为散列函数， 采用线性探测法处理冲突，则平均查找长度为________。 22．假定要对长度 n=100 的线性表进行散列存储，并采用链接法处理冲突，则对于长度 m=20 的开散列表，每个散列地址的单链表的长度平均为________。 23．在线性表的散列存储中，装填因子又称为装填系数，若用 m 表示散列表的长度， n 表示线性表中的元素的个数，则等于________。 24. 在开散列表中，处理冲突的方法为________法，在闭散列表中，处理冲突的方法为 ____________法。 25．对线性表(18,25,63,50,42,32,90)进行散列存储时，若选用 H(K)=K % 9 作为散列 函数，则散列地址为 0 的元素有________个，散列地址为 5 的元素有________个。 26．在开散列表中插入一个元素的时间复杂性为__________，查找一个元素的时间复杂 性为________，假定装填因子为。 27．在采用线性探测法处理冲突的闭散列表中，假定装填因子为，则进行成功查找的 平均查找长度为___________。 28．在采用二次探测法处理冲突的长度为 m 的闭散列表中，假定根据散列函数求出一个 元素的散列地址为 d，则第五个后继散列地址为___________。 （三）应用题 1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的二 分查找判定树，求出其平均查找长度。 2. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，根据二分查找每 个元素的比较次数填写下表。 1 2 3 4 5 6 7 8 9 10 15 26 34 39 45 56 58 63 74 76 3. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序 生成的一棵二叉排序树，求出其平均查找长度。 4．已知一个二叉排序树的广义表表示为 38(25(16),52(,74(68(,72),90)))，试根据查
找每个元素的比较次数填写下表。 2 34 5 5.假定一个特散列存铺的线性表为(32.75,29.63,8.94,25.46,18,70)，散列地址空间为 T[13】,若采用除面余数法构造散列函数和线性深测法处理冲突，试求出每一元素在闭散列 表中的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。 23456 78910 元素 327629 63489426461870 初始散列地址 初始散列地址 123456789101112 散列表 平均查找长度： 6假定一个特散列存储的线性表为32,7529,63,48,94.25,3就，18,70,49,80)，散列地 址空何为T[11】,若采用除留余数法构造散列函数和醚接法处理冲突。试酒出最后得到的 开散列表，并求出平均查找长度。 (四)算法设计思 1.假定在一个类型为s幻tb】e的结构变量R中保存着一个有序表，编写一个进行二分 查找的速归算法。 int binsearch(sqtable&R.int low.int high,keytype K) 2假定在一个类型为sqtb1e的结构变量R中保存着一个有序表，编写一个进行二分 查找的非递白算法。 int binsearchl(sqtablek R.keytype K) 3.假定在一个类型为bitreptr的指针变量t指向一棵二义排序树，编写一个从中查找 健值为K的结点的递归算法。 bitreptr search_bstl(bitreptr t,keytype K) 4.假定在一个类型为hitreptr的指针变量t指向一棵二义排序树，编写一个从中查找 健值为K的结点的非通归算法。 6
6 找每个元素的比较次数填写下表。 1 2 3 4 5 6 7 8 38 25 52 16 74 68 90 72 5. 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为 HT[13]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素在闭散列 表中的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。 1 2 3 4 5 6 7 8 9 10 元素 32 75 29 63 48 94 25 46 18 70 初始散列地址 初始散列地址 1 2 3 4 5 6 7 8 9 10 11 12 散列表 平均查找长度： 6. 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，散列地 址空间为 HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试画出最后得到的 开散列表，并求出平均查找长度。 （四）算法设计题 1. 假定在一个类型为 sqtable 的结构变量 R 中保存着一个有序表，编写一个进行二分 查找的递归算法。 int binsearch(sqtable& R, int low, int high, keytype K) 2. 假定在一个类型为 sqtable 的结构变量 R 中保存着一个有序表，编写一个进行二分 查找的非递归算法。 int binsearch1(sqtable& R, keytype K) 3．假定在一个类型为 bitreptr 的指针变量 t 指向一棵二叉排序树，编写一个从中查找 键值为 K 的结点的递归算法。 bitreptr search_bst1(bitreptr t, keytype K) 4．假定在一个类型为 bitreptr 的指针变量 t 指向一棵二叉排序树，编写一个从中查找 键值为 K 的结点的非递归算法
bitreptr search_bst2(bitreptr t.keytype K) 5.假定在一个类型为bitreptr的指针变量T指向一保二叉排序树，编写一个向其插入 健值为K的结点的递自算法。 int insert_bstl(bitreptr&T.keytype K) 6.假定在一个类型为bitreptr的指针变量T指向一保二叉排序树，编写一个向其插入 健值为K的结点的非递归算法。 int insert_hst2(bitreptr&T.keytype K)
7 bitreptr search_bst2(bitreptr t, keytype K) 5．假定在一个类型为 bitreptr 的指针变量 T 指向一棵二叉排序树，编写一个向其插入 键值为 K 的结点的递归算法。 int insert_bst1(bitreptr& T, keytype K) 6．假定在一个类型为 bitreptr 的指针变量 T 指向一棵二叉排序树，编写一个向其插入 键值为 K 的结点的非递归算法。 int insert_bst2(bitreptr& T, keytype K)
然习团参考师答 (一)单选择题 1.D 2.c 3.A 4.B 5.A 6.B 7.A8.B 9.C 10.011.D 12.B 13.A14.B15.D 18.C17.A 18.B 19.D20.A21.C 22.B23.C 24.D 25.C26.B 27.A 28.C (二)填空题 1.(n+1)/20 2上pe 3.20.541 4.「1c2(m+1)10(1ond 56 6顺序有序 7.13 8.二叉排序树理想平衡树 9.619 10./s+s)/2+1 11.11 12.√n+10(Nn) 13.小于大于 14。有序序列 15,查找成功左子树右子树 16左子树右子树 17.0(1oenl 0(logn) 18.0(nlogan) 19.1 20.5 21.2 22.5 23.n/a 24.绒接开放定址 25.32 28.11+n/2 27.(1+1/(1-a)/2 28.d+9)a (三)应用题 1.二分查找判定树如图7-1所示，平均查找长度等干29/10. 46 63 16 3 56 14 39 76
8 练习题参考解答 （一）单项选择题 1. D 2. C 3. A 4. B 5. A 6. B 7. A 8. B 9. C 10. D 11. D 12. B 13. A 14. B 15. D 16. C 17. A 18. B 19. D 20. A 21. C 22. B 23. C 24. D 25. C 26. B 27. A 28. C （二）填空题 1. (n+1)/2 O(n) 2. = n i i i p c 1 3. 20.5 41 4. log2(n+1) O(log2n) 5. 6 6. 顺序 有序 7. 1 3 8. 二叉排序树 理想平衡树 9. 6 19 10. (n/s+s)/2+1 11. 11 12. n +1 O( n ) 13. 小于 大于 14. 有序序列 15. 查找成功 左子树 右子树 16. 左子树 右子树 17. O(log2n) O(log2n) 18. O(nlog2n) 19. 1 20. 5 21. 2 22. 5 23. n/m 24. 链接 开放定址 25. 3 2 26. 1 1+/2 27. (1+1/(1-))/2 28. (d+9)%m （三）应用题 1. 二分查找判定树如图 7-1 所示，平均查找长度等于 29/10
图7-1 2.此题答案如下表。 1 4 7 9 10 15 26 34 39 45 56 58 63 74 76 3 4 34 3,二义排序树如图7-2所示，平均查找长度等于32/10。 38 25 52 16 90 6 2 图7-2 4,此题容案知下表所示 2 3 5 38 25 52 16 74 68 90 72 2 2 3 5 5.平均查找长度为1/10，其余解答如下。 2 3 4 5 6 7 8 910 元素 32 7529 634894256 1870 初始散列地址 初始散列地灶 6 8 2 3 4 5 6 7 8 9 1011 12 散列表 29941832467048756325 6。得到的开散列表如图7-3所示，平均查找长度4/3。 9
9 图 7-1 2．此题答案如下表。 1 2 3 4 5 6 7 8 9 10 15 26 34 39 45 56 58 63 74 76 3 2 3 4 1 3 4 2 3 4 3．二叉排序树如图 7-2 所示，平均查找长度等于 32/10。 图 7-2 4．此题答案如下表所示。 1 2 3 4 5 6 7 8 38 25 52 16 74 68 90 72 1 2 2 3 3 4 4 5 5．平均查找长度为 14/10，其余解答如下。 1 2 3 4 5 6 7 8 9 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 1 2 3 4 5 6 7 8 9 10 11 12 散列表 29 94 18 32 46 70 48 75 63 25 6．得到的开散列表如图 7-3 所示，平均查找长度 4/3
1 234567891011 A 南中离离奥卤离 南画 离 南 图7-3 (四)算法设计题 每个算法设计题解答从略
10 图 7-3 （四）算法设计题 每个算法设计题解答从略