数据结构练习第八章查找
1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
2．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。
A. O(1)
B. O(log
2
n) C. O(n) D. O(n2) 3．在二叉排序树中插入一个结点的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(log
2
n) D. O(n2) 4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。
A. log
2n+1 B. log
2
n-1 C. log
2
n D. log
2
(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(1og
2
n) 7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。
A. O(n)
B. O(n2)
C. O(nlog
2n) D. O(1og
2
n)
8．（）二叉排序树可以得到一个从小到大的有序序列。
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(1og
2n) C. O(nlog
2
n) D. O(n2)
12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。
A. A[1]，A[2]，A[3]，A[4]
B.A[1]，A[14]，A[7]，A[4]
C.A[7]，A[3]，A[5]，A[4]
D. A[7]，A[5] ，A[3]，A[4]
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-1)/2
15．设有序表中的元素为(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 . < B. > C. = D. !=
19．设有n 个关键字具有相同的Hash 函数值，则用线性探测法把这n 个关键字映射到HASH 表中需要做（ ）次线性探测。
A. n 2
B. n(n+1)
C. n(n+1)/2 D . n(n-1)/2
20．用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( )
A.线性探测法
B.除留余数法
C.平方取中法
D.折叠法
21．
22．在线性表的散列存储中，若用m 表示散列表的长度，n 表示待散列存储的元
素的个数，则装填因子α等于（ ）。
A ．n/m
B ．m/n
C ．n/(n+m)
D ．m/(n+m)
23．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度
是（ ）。
A ．原树高度加1
B ．原树高度减1
C ．原树高度
D ．不确定
24．向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。 Ａ.O （log 2n ） B. O(n) C. O(1) D. 0(nlog 2n) 25．5阶B 树中，每个结点最多有（）个关键码。
A ．2
B ．3
C ．4
D ．5
26．对一棵二叉排序树采用中根遍历进行输出的数据一定是（ ）
A.递增或递减序列
B.递减序列
C.无序序列
D.递增
序列
27．一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（ ）
A.1
B.2
C.4
D.8
28．若构造一棵具有n 个结点的二叉排序树，最坏的情况下其深度不超过( ) A. 2n B. n C. 2
1n + D. n+1 29．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是( )
A.由同义词之间发生冲突引起的
B.由非同义词之间发生冲突引起的
C.由同义词之间或非同义词之间发生冲突引起的
D.由散列表“溢出”引起的
30．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( )
数据结构课程（本科）第七章试题 一、单项选择题 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的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向下取整加一。 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.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。 A. n B. log2n C. (h+1)/2 D. h+1 11.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为 （）。 A. O(n) B. O(1) C. O(log2n) D. O(n2)
习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个
第八章查找 重点难点 要求理解"查找表"的结构特点以及各种表示方法的适用性；熟练掌握顺序查找和折半查找的方法；熟悉描述折半查找过程的判定树的构造方法；熟练掌握二叉排序树的构造和查找方法；理解二叉平衡树的构造过程；理解B-和B+树的特点、基本操作和二者的区别。熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握各种不同查找方法之间的区别和各自的适用情况，能按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 典型例题 1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度： (1)查找不成功，即表中无关键字等于给定值K的记录； (2)查找成功，即表中有关键字等于给定值K的记录。 【解】查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。 查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。 2.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 【解】 等概率情况下，查找成功的平均查找长度为： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 3.为什么有序的单链表不能进行折半查找?
【解】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 4.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 【解】此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。 但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。 新结点总是作为叶子插入在二叉排序树中的。 5.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字? 【解】在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。 若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。6.设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 答： (1)拉链法如下图： T[0..10] ┌──┐ 0││→ 33 → 22 →∧ ├──┤ 1││→ 1 → 12 →34→ ∧ ├──┤ 2││→ 13 →∧ ├──┤ 3│ ∧ │ ├──┤ 4│ ∧ │ ├──┤ 5││→ 38 → 27 →∧ ├──┤ 6│ ∧ │ ├──┤ 7│∧ │
数据结构练习第八章查找 1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 2．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A. O(1) B. O(log 2 n) C. O(n) D. O(n2) 3．在二叉排序树中插入一个结点的时间复杂度为（）。 A. O(1) B. O(n) C. O(log 2 n) D. O(n2) 4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 A. log 2n+1 B. log 2 n-1 C. log 2 n D. log 2 (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(1og 2 n) 7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 A. O(n) B. O(n2) C. O(nlog 2n) D. O(1og 2 n) 8．（）二叉排序树可以得到一个从小到大的有序序列。 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(1og 2n) C. O(nlog 2 n) D. O(n2) 12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 A. A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5] ，A[3]，A[4] 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-1)/2 15．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4
第9章查找自测卷姓名班级 一、填空题（每空1分，共10分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结 点数为；比较四次查找成功的结点数为；平均查找长度为。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n 第8章 查找 测试题 及答案 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n 第八章查找 习题 9．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。( ) (2)查找成功与否的关键在于是否按主关键字查找。( ) (3)顺序文件必须用一片地址连续的存储空间来存放。( ) (4)只有在顺序存储结构上才能采用顺序查找方法。( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。( ) (8)建立稠密索引的优点是节省存储空间。( ) (9)分块查找的效率与文件中的记录被分成多少块有关。( ) (10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。( ) (11)B-树和B十树都是用来实现动态索引的。( ) (12)在B-树上可以进行顺序查找。( 1 (13)在B+树上可以进行顺序查找。／ 1 (14)采用散列方法存储线性表，不能存储数据元素之间的关系。( ) (15)在散列文件中进行查找不涉及关键字的比较。( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。( ) (18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。( ) (19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。 (20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。( ) 9．2单项选择题。 (1)衡量查找算法性能好坏的主要标准是。 A．参加比较的关键字值的多少 B．被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D．关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是—。· A．对于被查找对象几乎没有限制B．适合排序连续顺序文件的查找 C.适合链接顺序文件的查找D．查找时间效率高 (3)对线性表采用折半查找，该线性表必须。 A．元素按值有序排列B．采用顺序结构 C．元素按值有序排列，并且采用顺序存储结构 n元素按值有序排列，并且采用链式存储结构 (4)下面的说法中，不正确的是——。 A．折半查找方法不适用于按值有序链接的链表的查找 B．折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D．折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1，k2，…，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。 第8章查找测试题及答案一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。 2. 线性有序表（a，a，a，…，a)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相123256等的元素，在 查找不成功的情况下，最多需要检索8 次。设有100个结点，用二分法查找时，最大比较次 数是7。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1； 比较两次查找成功的结点数为 2；比较四次查找成功的结点数为 8；平均查找长度为 3.7。 5解：显然，平均查找长度＝O（logn）<5次（2）。但具体是多少次，则不应当按照公式2m来计算（即 （21×log21）/20＝4.6次并不正确！）。因为这是在假设n＝2-1的情况下22n推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！4．【计研 题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20， 它将依次与表中元素 28，6，12，20比较大小。 5. 在各种查找方法中，平均查找长度与结 点个数n无关的查找方法是散列查找。 6. 散列法存储的基本思想是由关键字的值决定数 据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n 一、单选题 1．下列查找方法中，不属于动态的查找方法是( )。 A ．二叉排序树法 B ．平衡树法 C ．散列法 D ．二分查找法 2．适用于静态的查找方法为( )。 A ．二分查找、二叉排序树查找 B ．二分查找、索引顺序表查找 C ．二叉排序树查找、索引顺序表查找 D ．二叉排序树查找、散列法查找 3．静态查找表与动态查找表二者的根本差别在于( )。 A ．它们的逻辑结构不一样 B ．施加在其上的操作不同 C ．所包含的数据元素的类型不一样 D ．存储实现不一样 4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。 A ．5.5 B ．5 C ．39/8 D ．19/4 5．( )存储方式适用于折半查找。 A ．键值有序的单链表 B ．键值有序的顺序表 C ．键值有序的双链表 D ．键值无序的顺序表 6．对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B ．以链接方式存储 C ．顺序存储，且结点按关键字有序排序 D ．链式存储，且结点按关键字有序排序 7．在索引顺序表中查找一个元素，可用的且最快的方法是( )。 A ．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B ．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C ．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D ．用二分查找法确定元素所在块，再用二分查找法在相应块中查找 8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。 A ．13 B ．24 C ．12 D ．79 9．由同一关键字集合构造的各棵二叉排序树( )。 A ．形态和平均查找长度都不一定相同 B ．形态不一定相同，但平均查找长度相同 C ．形态和平均查找长度都相同 D ．形态相同，但平均查找长度不一定相同 10．对二叉排序树进行( )，可以得到各结点键值的递增序列。 A ．先根遍历 B ．中根遍历 C ．层次遍历 D ．后根遍历 11．下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？ A ．2，25，40，39，53，34，35 B ．25，39，2，40，53，34，35 C ．53，40，2，25，34，39，35 D ．39，25，40，53，34，2，35 12．在A VL 树中，每个结点的平衡因子的取值范围是( )。 A ．-1~1 B ．-2~2 C ．1~2 D ．0~1 13．在AVL 树中，任一结点的( )。 A ．左、右子树的高度均相同 B ．左、右子树高度差的绝对值不超过1 C ．左、右子树的结点数均相同 D ．左、右子树结点数差的绝对值不超过1 14．下面关于B 树和B +树的叙述中，不正确的是 A ．都是平衡的多叉树 B ．都是可用于文件的索引结构 C ．都能有效地支持顺序检索 D ．都能有效地支持随机检索 15．右图是一棵( )。 2822221915100528 2610数据结构第8章 查找 答案
数据结构练习8
数据结构第8章 查找 答案
数据结构第8章查找练习题
相关主题
文本预览