《T8-查找(练习)课件.ppt》由会员分享，可在线阅读，更多相关《T8-查找(练习)课件.ppt（28页珍藏版）》请在三一文库上搜索。
1、practice,1,下面关于二分查找的叙述，正确的是( )。 A表必须有序，表可以顺序方式存储，也可以链表方式存储 B表必须有序且表中数据必须是整型、实型或字符型 C表必须有序，而且只能从上到大排列 D表必须有序，而且只能以顺序方式存储,D,2,有一组元素为11,2, 33, 21, 34,10, 42， 已知哈希表大小为， 散列函数hf（x）x10， 冲突时采用线性探查法查找“下一个”位置， 则元素的桶地址（） A B C D,D,3,当采用索引表有序查找时，数据的组织方式为( ) A数据分成若干块，每块内数据有序 B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)
2、的数据组成索引块 C数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块 D数据分成若干块，每块(除最后一块)中数据个数需相同,B,4,假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到( )次存储冲突。 A4 B5 C6 D7,B,5,从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明找到该元素，若元素的值小于根结点的值，则继续向( )查找，若元素的值大于根结点的值，则继续向( )查找。 A左子树，左子树 B左子树，右子树 C右子树，左子树 D右子树，右子树,
3、B,6,单若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为( ) Ad Bd+1 C(d+1)/m D(d+1)%m,D,7,在长度为100的顺序表R0100中，R0作为监视哨，那么查找失败时，需进行( )次关键字比较。 A99 B100 C101 D以上答案都错啦,C,8,对一棵二叉排序树进行( )时，得到的结点序列是一个有序序列。 A前序遍历 B中序遍历 C后序遍历 D层序遍历,B,9,*有一组元素为 11,2, 33, 21, 23，存放于一个大小为的哈希表中，散列函数hf（x）x10;冲突时采用线性探查法查找“下一个
4、”位置， 则查找各个数平均查找长度为（） A（） B（） C（）,C,10,若采用链地址法处理冲突，则哈希表是将( )和( )组合在一起的数据结构 A数组和表 B数组和堆栈 C表和队列 D堆栈和队列,A,11,在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（ ）。 An Blog2n(以2为底) C(h+1)/2 Dh+1,D,12,对元素(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有( )个 A2 B3 C4 D5,B,13,假设对长度为n=50的有序表进行二分查找，则对应的判断树高度和
5、最后一层的结点数分别为( )。 A8， 13 B6， 13 C8， 19 D6， 19,D,14,散列法的主要问题在于( )。 A散列函数难以计算 B散列表的存取速度慢 C会发生冲突 D散列表占很多内存,C,15,对于一个大小为m含有n项的散列表，它的装填因子为( )。 Am-n Bm+n Cm/n Dn/m,D,16,二叉搜索树重新平衡算法中常用的工具为( ) A结点的旋转变换 B将结点插入到堆栈中 C将结点插入到队列中 D散列技术,A,17,顺序查找方法适合于存储结构为( )的线性表。 A顺序存储结构或链式存储结构 B散列存储结构 C索引存储结构 D压缩存储结构,A,18,若每个记录的查找
6、概率相等，则在有n个数据的序列中采用顺序查找方法，平均查找长度ASL=( )。 An Bn/2 C(n-1)/2 D(n+1)/2,D,19,从具有n个结点的AVL树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为（ ）。 AO(n) BO(1) CO(log2n)（以2为底） DO(n2),C,20,散列查找时，解决冲突的方法有( )。 A除留余数法 B数字分析法 C直接地址法 D链地址法,D,21,在相等搜索概率的情形下，高度为h+1的最优的二叉排序树中，上面 h (h是高度) 层都是( )的，第 h+1层( )。 A满，不满 B不满，不满 C满，满 D不满，满,A,22,假
7、定一个线性表为(12, 23, 74, 55, 63, 40, 82, 36)，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为_、_和_,12， 63， 36 55， 40， 82 23， 74,23,在有序表A112中，采用二分查找算法查找等于A12的元素，所比较的元素下标依次为( )。,6-9-11-12,24,对于长度为n的线性表，若采用顺序查找法进行查找，则时间复杂度为( )；若采用二分查找法进行查找，则时间复杂度为( )。,O(n) O(log2n),25,在散列函数H(key)=key%p，p应取( )。,小于或等于key的最大素数,26,长度为100和1000的散列表中分别存放有50和500个数据，采用链地址解决冲突，那么散列查找的平均查找长度分别近似为( )、( )。,1.5 1.5,27,假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按次序插入每个对象生成一棵AVL树（高度平衡的二叉搜索树），请回答以下问题: (1) 在插入16时需要进行_操作, 使树保持平衡. (2) 在插入50时需要进行 _操作, 使树保持平衡. (3) 在插入32时需要进行_操作, 使树保持平衡.,右单旋 先右后左双旋转 先右后左双旋转,