《数据结构练习第八章-查找》由会员分享，可在线阅读，更多相关《数据结构练习第八章-查找（80页珍藏版）》请在金锄头文库上搜索。
1、数据构造练习 第八章查找1.若有8个元素的有序表寄存在一维数组19中,第一种元素放A1中，现进行二分查找,则查找A3的比较序列的下标依次为（ )A. 1，2，B. 9，5,3.9，5,3D. 9，4，2,32.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ )。A. (1) B.O(og2n) C. O(n) D. O(n2）3.在二叉排序树中插入一种结点的时间复杂度为(）。. O（) B. O（n) . O（lo) D. O（n2)4设有序顺序表中有n个数据元素,则运用二分查找法查找数据元素X的最多比较次数不超过( ）。A.lg2n+1 B.gn-1 o2n D log2(n
2、+1)5.设有序表中有100个元素，则用二分查找查找元素最多需要比较（ ）次。A5 B0 C.7 D16顺序查找不管在顺序线性表中还是在链式线性表中的时间复杂度为（ )。A. （n） B O（2) C.(n1/2) .O(1og2n).设二叉排序树上有个结点,则在二叉排序树上查找结点的平均时间复杂度为（ ）。A. O(n） B. O（n） C.O(lo2n） D. (1og2）8.（ )二叉排序树可以得到一种从小到大的有序序列。.先序遍历 B.中序遍历 C. 后序遍历 D. 层次遍历9设一组初始记录核心字序列为（1，18，24，35，4，5，62,3,0,115,13),则运用二分法查找核心字
3、需要比较的核心字个数为（ )。A. . 2 C. 3 D. 40设某散列表的长度为100,散列函数H(k)% P,则P一般状况下最佳选择( ）。A.99 . 7 C91 D. 31.在二叉排序树中插入一种核心字值的平均时间复杂度为( ）。A. （n) B (1o2n) C. O(nog2n） D.O（n2).设一种顺序有序表A1：1中有个元素,则采用二分法查找元素A4的过程中比较元素的顺序为（)。. A1，2,A3，4BA1，A14,A7，4C.A7，A3,A5,A4 D. A7,5 ，A,A41设散列表中有m个存储单元,散列函数(y）= ky% p,则p最佳选择( ）。A不不小于等于m的最大
4、奇数B. 不不小于等于的最大素数C. 不不小于等于m的最大偶数 D不不小于等于m的最大合数14.设顺序表的长度为，则顺序查找的平均比较次数为( )。. n Bn2 (+1）/ . (n-1）21设有序表中的元素为(13，18，24，35，7，50，62），则在其中运用二分法查找值为24的元素需要通过( )次比较。A. 1 B 2 . D. 46设顺序线性表的长度为0,提成块,每块个元素,如果采用分块查找，则其平均查找长度为( )。A6 B. 1 C D.65设有一组初始记录核心字序列为(34，6，5,1，5,2),则由这组记录核心字生成的二叉排序树的深度为（ )。A. . 5 C.6 . 71
5、.二叉排序树中左子树上所有结点的值均( )根结点的值。A . = D. !=.设有个核心字具有相似的ash函数值，则用线性探测法把这n个核心字映射到HASH表中需要做（ ）次线性探测。A 2 . n(n+） C.n(+)/2 D. n(n-1）/0用散列函数求元素在散列表中的存储位置时,也许会浮现不同的核心字得到相似散列函数值的冲突现象。可用于解决上述问题的是( ）A线性探测法B.除留余数法C.平方取中法 D.折叠法21.22在线性表的散列存储中，若用m表达散列表的长度,表达待散列存储的元素的个数，则装填因子a等于（ ）。n/m .m/ C/(+) /（n+m）23从一棵B_树删除元素的过程中
6、,若最后引起树根结点的合并,则新树高度是（ ）。A原树高度加 .原树高度减1 C.原树高度 D.不拟定24.向二叉搜索树中插入一种元素时,其时间复杂度大体为（ )。A.O（lon） B. O(n) C.O(1） D. (nogn)255阶B树中，每个结点最多有(）个核心码。A.2 B.3 .4 D.26对一棵二叉排序树采用中根遍历进行输出的数据一定是（ )A.递增或递减序列B.递减序列 C.无序序列 .递增序列2一种有序表为1，3,9,12,32,41，45，62,75,77，8,95,0,当二分查找值为82的结点时,查找成功时的比较次数为（ ）A.1 B.C.4 .若构造一棵具有n个结点的二
7、叉排序树，最坏的状况下其深度不超过( )A. Bn . D n+12闭散列表中由于散列到同一种地址而引起的“堆积”现象,是( )A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表“溢出”引起的30在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插入到集合中。这种方式重要适合于（ )A.静态查找表B.动态查找表C.静态查找表与动态查找表 D静态查找表或动态查找表31.设一组记录的核心字ky值为2，0，14，28,19，3，,6,散列函数为H（key)=ky md 1，则它的开散列表中散列地址为1的链中的结点个
8、数是（ ）A.1 B. 3 .43已知一种有序表为（1,18，2,47，0，2,83,90，11,134),当二分检索值为90的元素时,检索成功需比较的次数是( ）.1 B.2 C.343.闭散列表中由于散列到同一种地址而引起的“堆积”现象，是由( )A.同义词之间发生冲突引起的B.非同义词之间发生冲突引起的C.同义词与非同义词之间发生冲突引起的.散列地址“溢出”引起的34.在最坏的状况下,查找成功时二叉排序树的平均查找长度（ ).不不小于顺序表的平均查找长度B.不小于顺序表的平均查找长度C与顺序表的平均查找长度相似D.无法与顺序表的平均查找长度比较5闭散列表中由于散列到同一种地址而引起的“堆
9、积”现象，是由（ ).同义词之间发生冲突引起的非同义词之间发生冲突引起的C同义词之间或非同义词之间发生冲突引起的.散列表“溢出”引起的36.设有100个元素,用二分法查找时,最大比较次数是(）。A5 B.7 0 D.137.设有0个元素,用二分法查找时,最小比较次数为( )A0 B C.1 D538.在一种长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数,假定查找每个元素的概率都相等）为 ( )。A. B. n2 C. (n+1)/2 (n-)/23对有14个数据元素的有序表R14进行折半搜索，搜索到R3的核心码等于给定值,此时元素比较顺序依次为
10、（ ）。.R0,1，R2,3 B.R0,，R2，RC.R6,R，R4,3 6,4,R2，R30在一种有N个元素的有序单链表中查找具有给定核心字的结点，平均状况下的时间复杂性为(B )A.O（1） BO(N） (N) D.O（NlogN）4.对线性表进行二分查找时,规定线性表必须（B ）A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 .以链接方式存储,且数据元素有序4.下列二叉排序树中查找效率最高的是（ A ) A平衡二叉树 B二叉查找树C.没有左子树的二叉排序树 D.没有右子树的二叉排序树.如果规定一种线性表既能较快地查找,又能适应动态变化的规定，可以采用下列哪一种查找措施。A. 分块 B. 顺序 C.折半 D. 哈希44.分别如下列序列构造二叉排序树，与用其他三个序列所构造的成果不同的是( C ) A.（10,80,90，60，120，11,10) .(00，12,110,130,80,60,90)C.(10，60,80,0, 2，10,30) D.(10,0，60,9,1,130,10)5下面有关B和+树的论述中，不对的的是(C )A. B树和B+树都是平衡的多叉树。 .B树和B树都可用于文献的索引构造。C. 树和B树都能有效地支持顺序检索。 DB树和+树都能有效地支持随机检索。46m阶B树是一棵( B ) A. 叉排序树 B 叉平衡排序
