《数据结构辅导七.docx》由会员分享，可在线阅读，更多相关《数据结构辅导七.docx（7页珍藏版）》请在课桌文档上搜索。
1、数据结构辅导七-一查找的辅导练习题及解答(一)单项选择题1 .若查找每一个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找 长度为()。A n B n+1 C (n-l)2 D (n+l)22 .对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8,查找 后面5个元素的概率相同，均为3/40,则查找任一元素的平均查找长度为()oA 5.5 B 5C 39/8 D 19/43 .对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2,查找第二个元素 的概率为1/3,查找第三个元素的概率为1/6,则查找任一元素的平均查找长度为()oA 5/3B2C7/3D4/34
2、 .对长度为n的单链有序表，若查找每一个元素的概率相等，则查找任一元素的平均 查找长度为()oA n/2B(n+1)/2C(n-l)2Dn/45 .对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长 度为()的值的向上取整。Alog (n+1) B log Cn/2 D (+l)26 .对于长底为n的顺序存储的谒序表，若采用二分查找，则对所有元素的最长查找长 度为()的值的向下取整加UA Llog (n+1)J B Llog nJ C Ln2j D L(n+l)2j7 .对于长版为9的顺序存储的着序表，若采用二分查找，在等概率情况下的平均查找 长度为()的9分之一。A 2
3、0 B 18 C 25 D 228 .对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找 长度为()。A 3B 4C 5I) 69 .对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用二分查找，则查找元 素26的查找长度为()。A 2B 3C 4D 510 .对具有n个元素的有序表采用二分查找，则算法的时间复杂性为()。A O(n) B O(2) C O(I) D O(log n)11 .在索引查找中，若用于保存数据元素的主表的长屋为n,它被均分为k个子表，每 个子表的长度均为nk,则索引查找的平均查找长度为()。A n+k B k+n/
4、k C (k+nk)2 D (k+nk)2+l12 .在索引查找中，若用于保存数据元素的主表的长度为n,它被均分为若干个子表， 每一个子表的长度均为s,则索引查找的平均查找长度为()。A (n+s)/2 B (ns+s)2+l C (n+s)2+l D (ns+s)213 .在索引查找中，若用于保存数据元素的主表的长度为144,它被均分为12子表， 每一个子表的长度均为12,则索引查找的平均查找长度为()。 13B 24 C 12 D 7914 .在索引查找中，若用于保存数据元素的主表的长度为117,它被均分为9子表，则索引查找的平均查找长度为()。 11B 12 C 13 D 915 .在一
5、棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为 ()oA nB log n C (h+l)2 D h16 .从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂性大致 为()。A 0(n) B 0(1) C O(log n) DOg)17 .从具有n个结点的二叉搜索树中查,一个元素时，在最坏情况下的时间复杂性为 ( )。A 0(n) B 0(1) C O(log n) D 0(m)18 .向具有个结点的二叉搜索树中插入二个元素时，其时间复杂性大致为()。A 0(1) B O(log n ) C 0(n) D O(nlog n)19 .根据n个元素建立一展二叉
6、搜索树时，其时间复杂性大致如 )。A 0(n) B O(log n ) C O(n2) D O(nlog n)20 .在一棵平衡二叉排序树-中，每一个结点的平衡因子的取值虚围是()。A -1-1 B -2-2 C 1-2 D 0121 .若根据查找表(23, 44, 36, 48, 52, 73, 64, 58)建立开散列表，采用h(K)=K%13计算散 列地址，则元素64的散列地址为()。A 4B 8 C 12 D 1322 .若根据查找表(23, 44, 36,48, 52, 73, 64, 58)建立开散列表，采用h(K)=K%7计算散列 地址，则散列地址等于3的元素个数()。 1B 2
7、 C 3 D 423 .若根据查找表(23, 44, 36,48, 52, 73, 64, 58)建立开散列表，采用h(K)=K%7计算散列 地址，则同义词元素个数最多为()oA 1B 2 C 3 D 424 .若根据查找表建立长度为m的闭散列表，采用线性探测法处理冲突，假定对一个元 素第一次计算的散列地址为d,则下一次的散列地址为()。A dB d+1 C (d+l)m D (d+l)%m25 .若根据查找表建立长度为m的闭散列表，采用二次探测法处理冲突，假定对一个元 素第一次计算的散列地址为d,则第四次计算的散列地址为()。A (d+l)%m B (d-l)%m C (d+4)%m D (
8、d-4)%m26 .在采用线性探测法处理冲突的闭散列表上，假定装填因子a的值为0.5,则查找任 一元素的平均查找长度为()。A 1B 1.5 C 2 D 2.527 .在采用链接法处理冲突的开散列表上，假定装填因子a的值为4,则查找任一元素 的平均查找长度为()。A 3 B 3.5 C 4 D 2.528 .在散列查找中，平均查找长度主要与()有关。A散列表长度B散列元素的个数C装填因子D处理冲突方法(二)填空题1 .以顺序查找方法从长度为n的顺序表或者单链表中查找一个元素时，平均查找长度 为.，时间复杂性为_O2 .对长度为n的查找表进行查找时，假定查找第i个元素的概率为P ,查找长度(即在
9、 查找过程中挨次同有关元素比较的总次数)为C j则在查找成功情况下的辛均查找长度的计 算公式为一。3 .假定一个顺序表的长度为40,并假定查找每一个元素的概率都相同，则在查找成功 情况下的平均查找长度，在查找不成功情况下的平均查找长度o4 .以二分查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于 的向上取整减1,时间复杂性为。5 .以二分查找方法从长度为50的有序表中查找一个元素时，其查找长度不超过6 .以二分查找方法在一个查找表上进行查找时，该查找表必须组织成 存储的表。7 .从有序表(12, 18, 30,43, 56, 78,82, 95)中分别二分查找43和56元素时，其
10、查找长度 分别为 和o8 .二分查找所对应的判定树，既是一棵又是一棵9 .假定对长度n=50的有序表进行二分查找，则对应的判定树高度为最后一层的结点数为10 .假定在索引查找中，查找表长度为n,每一个子表的长度相等，设为s,则进行成 功查找的平均查找长度为一。11 .在索引查找中，假定查找表(即主表)的长度为96,被等分为8个子表，则进行 索引查找的平均查找长度为。12 .假定对长度n的主表进行索引查找，并假定每一个子表的长度均为n ,则进行索 引查找的平均查找长度为，时间复杂性为。13 .在一棵二叉排序树中，每一个分支结点的左子树上所有结点的值一定一该结点的值，右子树上所有结点的值一定.该结
11、点的值。14 .对一棵二叉排序树进行中序遍历时，得到的结点序列是一个15 .从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明,若元素的值小于根结点的值，则继续向查找，若元素的值大于根结点的值，则继续向查找。16 .向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结 点的插入，若元素的值大于根结点的值，则接着向根结点的 插入。17 .从一棵具有n个结点的二叉排序树中查找和插入元素的时间复杂性大致分别为 和 O18 .根据n个元素建立一棵二叉排序树的时间复杂性大致为19 .在一棵平衡二叉排序树中，每一个结点的左子树高度与右子树高度之差的绝对值不 超过 O20
12、 .假定对线性表(38, 25, 74, 52, 48)进行散列存储，采用H(K)=K % 7作为散列函数, 采用线性探测法处理冲突，则在建立闭散列表的过程中，将会碰到 次存储冲突。21 .假定对线性表(38, 25, 74, 52,48)进行散列存储,采用H(K)=K % 7作为散列函数, 采用线性探测法处理冲突，则平均查找长度为 一。22 .假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度 m=20的开散列表，每一个散列地址的单链表的长度平均为o23 .在线性表的散列存储中，装填因子C又称为装填系数，若用m表示散列表的长度， n表示线性表中的元素的个数，则。等于
13、 。24 .在开散列表中，处理冲突的方法为法，在闭散列表中，处理冲突的方法为法。25 .对线性表(18, 25, 63, 50,42, 32, 90)进行散列存储时,若选用H(K)=K % 9作为散列 函数，则散列地址为0的元素有个，散列地址为5的元素有一个。26 .在开散列表中插入一个元素的时间复杂性为，查找一个元素的时间复杂性为，假定装填因子为a。27 .在采用线性探测法处理冲突的闭散列表中，假定装填因子为，则进行成功查找的 平均查找长度为。28 .在采用二次探测法处理冲突的长度为m的闭散列表中，假定根据散列函数求出一 个元素的散列地址为d,则第五个后继散列地址为 o(三)应用题1 .已知
14、一个顺序存储的有序表为(15, 26, 34, 39, 45, 56, 58, 63, 74, 76),试画出对应的二 分查找判定树，求出其平均查找长度。2 .已知一个顺序存储的有序表为(15, 26, 34, 39, 45, 56, 58, 63, 74, 76),根据二分查找每 个元素的比较次数填写下表。123456789103 .假定一个线性表为(38, 52, 25, 74, 68, 16,30,54,90,72),画出按线性表中元素的次序 生成的一棵二叉排序树，求出其平均查找长度。4 .已知一个二叉排序树的广义表表示为38(25(16), 52(, 74(68(, 72), 90),
15、试根据查 找每一个元素的比较次数填写下表。123456785 .假定一个待散列存储的线性表为(32, 75,29,63, 48, 94, 25, 46, 18, 70),散列地址空间 为HT13,若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素在闭 散列表中的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。12345678910元素 32 75 29 63 48 94 25 46 18 70初始散列地址初始散列地址12345678910 11 12散列表平均查找长度：6.假定一个待散列存储的线性表为(32, 75, 29, 63, 48, 94, 25, 3
16、6, 18, 70, 49, 80),散列地 址空间为HT11,若采用除留余数法构造散列函数和链接法处理冲突，试画出最后得到的 开散列表，并求出平均查找长度。(四)算法设计题1 .假定在一个类型为sqtable的结构变量R中保存着一个有序表，编写一个进行二分 查找的递归算法。int binsearch(sqtab1e& R, int low, int high, keytype K)2 .假定在一个类型为sqtable的结构变量R中保存着一个有序表，编写一个进行二分 查找的非递归算法。int binsearchi(sqtable& R, keytype K)3 .假定在一个类型为bitrept
17、r的指针变量t指向一棵二叉排序树，编写一个从中查找 键值为K的结点的递归算法。bitreptr searchbstl(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的指
18、针变量T指向一棵二叉排序树，编写一个向其插入 键值为K的结点的非递归算法。int insert_bst2(bitreptr T, keytype K)练习题参考解答(一)单项选择题1. D2. C3. A4.B5.A6. B7. A8, B9. C10.D11.D12. B13. A14. B15. D16.C17.A18. B19. D20. A21. C22.B23.C24. D25. C26. B27. A28.C(二)填空题1. (n+l)2 0(n)2.Epc I ji=13. 20.5 414.log (n+l) 0(log n) 225. 66.顺序有序7. 1 38.二叉排序树
19、理想平衡树9. 6 1910.(ns+s)2+l11. 1112.n +1 o( n )13.小于大于14.有序序列15.查找成功左子树右子树16.左子树右子树17. O(log n) O(log n) 2218.O(nlog n)219. 120. 521. 223. n/m25. 3 227. (l+l(l-q)222. 524.链接开放定址26. 1 l+228. (d+9)%m（三）应用题1.二分查找判定树如图7-1所示,平均查找长度等于2910o7892.此题答案如下表。12345610图7-24 .此题答案如下表所示。123456785 .平均查找长度为14/10,其余解答如下。7891025 46 18 70123456元素 32 75 29 63 48 94初始散列地址初始散列地址11 12散列表6 .得到的开散列表如图73所示，平均查找长度43o（四）算法设计题每一个算法设计题解答从略。
