数据结构练习第八章 查找

《数据结构练习第八章 查找》由会员分享，可在线阅读，更多相关《数据结构练习第八章 查找（51页珍藏版）》请在金锄头文库上搜索。

1、1数据结构练习数据结构练习 第八章第八章 查找查找1.若有 18 个元素的有序表存放在一维数组 A19中，第一个元素放 A1中，现 进行二分查找，则查找 A3的比较序列的下标依次为( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，3 2设二叉排序树中有 n 个结点，则在二叉排序树的平均平均查找长度为（ ） 。A. O(1) B. O(log2n) C. O(n) D. O(n2) 3在二叉排序树中插入一个结点的时间复杂度为（ ） 。 A. O(1) B. O(n) C. O(log2n) D. O(n2) 4设有序顺序表中有 n 个数据元素，则利用二分查找法查找数

2、据元素 X 的最多 比较次数不超过（ ） 。 A. log2n+1 B. log2n-1 C. log2n D. log2(n+1) 5设有序表中有 1000 个元素，则用二分查找查找元素 X 最多需要比较（ ） 次。 A. 25 B. 10 C. 7 D. 1 6顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ） 。 A. O(n) B. O(n2) C. O(n1/2) D. O(1og2n) 7设二叉排序树上有 n 个结点，则在二叉排序树上查找结点的平均时间复杂度 为（ ） 。 A. O(n) B. O(n2) C. O(nlog2n) D. O(1og2n) 8 （ ）二

3、叉排序树可以得到一个从小到大的有序序列。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 9设一组初始记录关键字序列为 (13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关 键字 90 需要比较的关键字个数为（ ） 。 A. 1 B. 2 C. 3 D. 4 10设某散列表的长度为 100，散列函数 H(k)=k % P，则 P 通常情况下最好选 择（ ） 。 A. 99 B. 97 C. 91 D. 93 11在二叉排序树中插入一个关键字值的平均时间复杂度为（ ） 。 A. O(n) B. O(1og2n) C. O(nlog2n) D

4、. O(n2) 12设一个顺序有序表 A1:14中有 14 个元素，则采用二分法查找元素 A4的 过程中比较元素的顺序为( )。 A. A1，A2，A3，A4B.A1，A14，A7，A4 C.A7，A3，A5，A4 D. A7，A5 ，A3，A4 13设散列表中有 m 个存储单元，散列函数 H(key)= key % p，则 p 最好选择 （ ） 。 A. 小于等于 m 的最大奇数B. 小于等于 m 的最大素数 C. 小于等于 m 的最大偶数 D. 小于等于 m 的最大合数 14设顺序表的长度为 n，则顺序查找的平均比较次数为（ ） 。 A. n B. n/2 C. (n+1)/2 D. (n

5、-1)/2215设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分 法查找值为 24 的元素需要经过（ ）次比较。 A. 1 B. 2 C. 3 D. 4 16设顺序线性表的长度为 30，分成 5 块，每块 6 个元素，如果采用分块查找， 则其平均查找长度为（ ） 。 A. 6 B. 11 C. 5 D. 6.5 17设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这 组记录关键字生成的二叉排序树的深度为（ ） 。 A. 4 B. 5 C. 6 D. 7 18二叉排序树中左子树上所有结点的值均（ ）根结点的值。 A. C. = D.

6、!= 19设有 n 个关键字具有相同的 Hash 函数值，则用线性探测法把这 n 个关键字 映射到 HASH 表中需要做（ ）次线性探测。 A. n2 B. n(n+1) C. n(n+1)/2 D. n(n-1)/2 20用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得 到相同散列函数值的冲突现象。可用于解决上述问题的是( ) A.线性探测法B.除留余数法 C.平方取中法 D.折叠法 21 22在线性表的散列存储中，若用 m 表示散列表的长度，n 表示待散列存储的 元素的个数，则装填因子等于（ ） 。 An/m Bm/n Cn/(n+m) Dm/(n+m) 23从一棵 B_树

7、删除元素的过程中，若最终引起树根结点的合并，则新树高度 是（ ） 。 A原树高度加 1 B原树高度减 1 C原树高度 D不确定 24向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ） 。 .O（log2n） B. O(n) C. O(1) D. 0(nlog2n) 255 阶 B 树中，每个结点最多有（）个关键码。 A2 B3 C4 D5 26对一棵二叉排序树采用中根遍历进行输出的数据一定是（ ） A.递增或递减序列B.递减序列 C.无序序列 D.递增 序列 27一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100， 当二分查找值为 82 的结点时，查找成功

8、时的比较次数为（ ） A.1 B.2C.4C.4 D.8 28若构造一棵具有 n 个结点的二叉排序树，最坏的情况下其深度不超过( )A. B. n C. D. n+12n 21n 29闭散列表中由于散列到同一个地址而引起的“堆积”现象，是( ) A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 3D.由散列表“溢出”引起的 30在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素 插入到集合中。这种方式主要适合于( ) A.静态查找表B.动态查找表 C.静态查找表与动态查找表 D.静态查找表或动态查找表 31设一组记录的

9、关键字 key 值为62，50，14，28，19，35，47，56，83， 散列函数为 H(key)=key modmod 13，则它的开散列表中散列地址为 1 的链中的结 点个数是（ ） A1 B.2 C3 D.4 32已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134） ， 当二分检索值为 90 的元素时，检索成功需比较的次数是（ ） A.1 B.2 C.3 D.4 33闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（ ） A.同义词之间发生冲突引起的 B.非同义词之间发生冲突引起的 C.同义词与非同义词之间发生冲突引起的 D.散列地址“溢出”

10、引起的 34在最坏的情况下，查找成功时二叉排序树的平均查找长度（ ） A小于顺序表的平均查找长度B大于顺序表的平均查找长度 C与顺序表的平均查找长度相同D无法与顺序表的平均查找长度比较 35闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（ ） A同义词之间发生冲突引起的 B非同义词之间发生冲突引起的 C同义词之间或非同义词之间发生冲突引起的 D散列表“溢出”引起的 36设有 100 个元素，用二分法查找时，最大比较次数是（ ） 。 A25 B7 C10 D1 37设有 1000 个元素，用二分法查找时，最小比较次数为（ ） A0 B1 C10 D500 38在一个长度为 n 的顺序线

11、性表中顺序查找值为 x 的元素时，查找成功时的 平均查找长度（即 x 与元素的平均比较次数，假定查找每个元素的概率都相等） 为 ( )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 39对有 14 个数据元素的有序表 R14进行折半搜索，搜索到 R3的关键码等 于给定值，此时元素比较顺序依次为（ ） 。 AR0，R1，R2，R3 BR0，R13，R2， R3 CR6，R2，R4，R3 DR6，R4，R2， R3 40在一个有 N 个元素的有序单链表中查找具有给定关键字的结点，平均情况 下的时间复杂性为( B ) A.O(1) B.O(N) C.0（N2） D.O(Nlo

12、gN)441对线性表进行二分查找时，要求线性表必须（B ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 42下列二叉排序树中查找效率最高的是( A ) A.平衡二叉树 B.二叉查找树 C.没有左子树的二叉排序树 D.没有右子树的二叉排序树 43如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采 用下列哪一种查找方法。A A. 分块 B. 顺序 C. 折半 D. 哈希 44分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的 是( C ) A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C.(100,60,80,90, 20,110,130) D.(100,80,60,90,120,130,110) 45下面关于 B 和 B+树的叙述中，不正确的是(C ) A. B 树和 B+树都是平衡的多叉树。 B. B 树和 B+树都可用于文件的索引 结构。 C. B 树和 B+树都能有效地支持顺序检索。 D. B 树和 B+树都能有效地支持随 机检索。 46m 阶 B-树是一棵( B ) A. m 叉排序树 B. m 叉平衡排序树 C. m-1