客观题测试-第7章查找

第1关：查找客观题测试（一）

1、关键字可以唯一地标识一个数据元素。

A、对

B、错

2、二叉排序树是一个动态查找表。

A、对

B、错

3、如果顺序表中各元素的查找概率相同，在顺序查找时，查找不成功的平均查找长度因元素有序排列或无序排列情况的不同而不同。

A、对

B、错

解：在有序排列的情况下，查找不成功的概率会比无序排列时要高。因为有序排列时，每个元素都有其固定的位置，所以查找不成功时，需要检查的元素数量会更多。因此，在有序排列的情况下，查找不成功的平均查找长度会比无序排列时要长。

相反，在无序排列的情况下，查找不成功的概率会相对较低。因为无序排列时，元素的位置是随机的，所以查找不成功时，需要检查的元素数量会相对较少。因此，在无序排列的情况下，查找不成功的平均查找长度会相对较短。

4、任意一棵二叉排序树的平均查找时间都小于用顺序查找法找到同样元素的顺序表的平均查找时间。

A、对

B、错

5、二叉排序树用中序遍历得到的一定是关键字的升序序列

A、对

B、错

6、m阶B树中每个非终端结点至少有m/2个子树。

A、对

B、错

7、若二叉排序树有n个结点，其关键字互不相等，则不论其形态如何，都必然有n种查找成功的情形和n+1种查找失败的情形。

A、对

B、错

8、二叉排序树删除一个结点时，如果该结点有左右子树，就用左子树的最右侧结点替换之，再处理该结点的删除问题。

A、对

B、错

9、二叉排序树的形态和输入无关。

A、对

B、错

10、对散列表进行查找时，如果该元素不存在表中，需要遍历所有表中元素后才能判断查找失败。

A、对

B、错

第2关：查找客观题测试（二）

1、采用链地址法构造的散列表不存在冲突现象。

A、对

B、错

解：好的，以下是一个例子来说明链地址法构造的散列表存在冲突现象：

假设我们使用链地址法构造一个散列表，其中散列函数是将元素的值映射到哈希表的索引。假设哈希表的长度为5，我们有以下元素：

1. 元素A的值为5，哈希值为1
2. 元素B的值为10，哈希值为2
3. 元素C的值为15，哈希值为3
4. 元素D的值为20，哈希值为4
5. 元素E的值为25，哈希值为1

由于哈希表长度为5，索引0-4都是有效的哈希地址。但是，当我们将这些元素插入哈希表时，我们会遇到冲突现象。

首先，我们将元素A插入到索引1的位置。然后，我们将元素E插入到索引1的位置。由于索引1已经被元素A占用，因此元素E将无法插入到索引1的位置。此时，我们将使用链地址法来解决冲突。我们将元素E添加到索引1位置的链表中。

类似地，当我们将元素B插入到索引2的位置时，也会遇到冲突现象。由于索引2已经被元素C占用，因此元素B将无法插入到索引2的位置。此时，我们将使用链地址法来解决冲突。我们将元素B添加到索引2位置的链表中。

因此，尽管我们使用了链地址法来构造散列表，但在某些情况下仍然存在冲突现象。

?2、散列表中需要删除一个元素，不管用哪种方法处理冲突，都只需简单的把该元素删除即可。

A、对

B、错

3、如果要求一个线性表既能快速查找，又能适应动态变化的要求，最好采用哈希查找。

A、对

B、错

解：这个说法是错误的。哈希查找适用于数据结构中的查找操作，它可以在平均情况下实现接近O(1)的查找时间复杂度。然而，哈希查找并不适用于所有情况，特别是当数据结构需要频繁进行插入和删除操作时。

在动态变化的数据结构中，通常采用平衡二叉搜索树（如AVL树、红黑树等）或B树等数据结构，它们可以保持数据的有序性，同时支持快速的插入和删除操作。这些数据结构在插入和删除操作时，可以保持树的平衡，从而保证查找、插入和删除的时间复杂度都是O(log n)。

因此，如果要求一个线性表既能快速查找，又能适应动态变化的要求，最好采用平衡二叉搜索树或B树等数据结构，而不是哈希查找。

4、散列表的查找效率主要取决于构造散列表时选择的散列函数和处理冲突的方法。

A、对

B、错

5、B-树的查找过程是先在一个结点内部的关键字中寻找，再顺着指向子树的指针向下寻找。在一个结点内查找时，只能采用顺序查找方法。

A、对

B、错

6、散列表的装填因子 α 越小，发生冲突的可能性越大，反之 α 越大，发生冲突的可能性越小。

A、对

B、错

解：一般情况下，设散列表空间大小为m，填入表中的元素个数是n,则称α=n/m为散列表的装填因子。?

7、随着装填因子的增大，采用链地址法解决冲突，其平均查找长度比用开地址法解决冲突时的平均查找长度增长得慢。

A、对

B、错

解：在链地址法中，当发生冲突时，新插入的元素会被添加到链表的末尾。因此，随着装填因子的增大，链表中的元素数量会逐渐增加，但是每个元素仍然被分配一个固定的位置。因此，在链地址法中，平均查找长度与装填因子的大小关系相对较小。

而在开地址法中，当发生冲突时，新插入的元素会被分配到下一个可用的位置。因此，随着装填因子的增大，可用的位置会逐渐减少，导致平均查找长度逐渐增加。

?8、二叉排序树的平均查找长度为 O(log2?n)

A、对

B、错

9、n个关键字的有序表，折半查找的平均查找长度近似为 log2?(n+1)?1

A、对

B、错

10、散列表中二次聚集指的是散列表中出现的非同义词冲突。

A、对

B、错

第3关：查找客观题测试（三）

1、在平衡二叉树中插图一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，A的右孩子的平衡因子为-1，则应该做（）型调整以使其平衡。

A、LL

B、LR?

C、RL

D、RR

2、若平衡二叉树的高度为5，且所有非叶子结点的平衡因子均为1，则该平衡二叉树的结点总数为（）

A、10

B、12

C、20

D、32

3、对于长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（? ? ）

A、n/2

B、(n+1)/2

C、(n-1)/2

D、n/4

4、下面有关查找性能方面的叙述种错误的是（? ?）

A、查找成功的平均查找长度是指找到指定元素所需比较关键字的比较次数的期望值。

B、查找不成功的平均查找长度是指没有找到指定元素，但找到该元素插入位置所需关键字比较次数的期望值。

C、平均查找长度与元素的查找概率无关

D、平均查找长度与元素在结构中的分布情况有关。

5、设一个元素集合有n（n＞1)个元素，分别存放在两个表中，表A按元素的关键子从小到大存放，表B则无序存放。若对表A按有序表的顺序查找算法，对表B按一般表的顺序查找算法从表的前端顺序查找。设查找表中每个元素的查找概率相同，则在两个表中平均查找长度为（ ）

A、表A大于表B

B、表A小于表B

C、表A与表B相同

D、谁大谁小不确定

6、对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素（计数从1开始）的查找次数为（ ）

A、3

B、4

C、5

D、6

7、下列选项中不能构成折半查找中关键字比较序列的是（? ）

A、500，200，450，180

B、500，450，200，180

C、180，500，200，450

D、180，200，500，450

8、折半查找与二叉排序树的时间性能（? ）

A、相同

B、有时不相同

C、完全不相同

D、不定

解：二叉排序树在形态均匀时查找性能最好?，此时与折半查找一样，为log2N

9、二叉树为二叉排序树的（? ?）条件是其任一结点的值均大于其左子女的值，小于其右子女的值

A、充分不必要

B、必要不充分

C、充分必要

D、既不充分也不必要

10、利用逐个数据插入的方法建立序列{35，45，25，55，50，10，15，30，40，20}对应的二叉排序树后，查找元素20需要进行（ ）次元素之间的比较。

A、4

B、5

C、7

D、10

第4关：查找客观题测试（四）

1、设任意一棵非空的二叉排序树T1中，删除某结点v之后形成的二叉排序树T2，再将v 插入T2形成二叉排序树T3.下列关于T1与T3的叙述中正确的是：

A、仅1，3

B、仅1，4

C、仅2，3

D、仅2，4

1. 若v是T1的叶节点，则T1与T3不同。

2. 若v是T1的叶节点，则T1与T3相同。

3. 若v不是T1的叶节点，则T1与T3不同。

4. 若v不是T1的叶节点，则T1与T3相同。

?

2、在顺序存储的线性表R[n]上进行顺序查找，设查找成功和查找不成功的概率相等，各占1/2，则总平均查找长度为（? ）

A、(n+1)/2

B、3(n+1)/4

C、n

D、n(n+1)/2

3、当在一个有序的顺序表上进行查找时，既可以使用顺序查找，也可以使用折半查找，前者的查找速度（? ）

A、一定没有后者快

B、取决于表是递增的还是递减的

C、在平均情况下比后者快

D、在平均情况下比后者慢

4、已知一个长度为16的顺序表L，其元素按照关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字比较次数最多为（? ）次。

A、6

B、7

C、4

D、5

5、当采用分块查找时，数据的组织方式为（ ）

A、数据分成若干块，每块内数据有序。

B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C、数据分成若干块，每块内数据有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

D、数据分成若干块，每块（除最后一块外）数据个数相等。

6、在二叉排序树中，关键字最小的结点的（? ）

A、左指针一定为空。

B、右指针一定为空

C、左右指针均为空

D、左右指针均不为空

7、构造一棵具有n个结点的二叉排序树，在理想情况下树的深度为（ ）

A、n/2

B、n

C、?log2(n+1)?

D、?log2(n+1)?

8、高度为7的AVL树最多有（ ）结点。

A、63

B、64

C、65

D、127

9、已知一个长度为15的顺序表L，其元素按关键字大小有序排列。若采用折半查找法查找一个不存在的元素，则比较次数最多的是（? ? ?）

A、4

B、5

C、6

D、7

10、向一棵平衡二叉树上插入一元素时，可能要对最小不平衡子树进行调整，此调整分为（ ）种旋转类型。

A、2

B、3

C、4

D、5

第5关：查找客观题测试（五）

1、含有n个非终端结点的m阶B 树的关键字的个数最少是（ ）

A、n

B、(m-1）xn

C、nx(?m/2?-1)

D、(n-1)X(?m/2?-1)+1

2、在一棵高度为h的B树中插入一个新的关键字时，为查找插入位置，需读取的结点数为（? ）

A、h-1

B、h

C、h+1

D、h+2

3、如果在一棵m阶B 树中删除关键字导致结点需要与其右兄弟或左兄弟结点合并，那么被删关键字所在结点（根节点除外）的关键字数在删除之前应为（? ）

A、?m/2?

B、?m/2?-1

C、?m/2?

D、?m/2?-1

4、下面关于B树B+树的叙述错误的是（? ）

A、B树和B+树都是平衡的多叉查找树。

B、B树和B+树都可用于文件的索引结构。

C、B树和B+树都能有效地支持顺序查找。

D、B树和B+树都能有效地支持随机查找。

5、以下说法中，不符合m阶B树定义要求的是（ ）

A、根节点最多m棵子树。

B、所有叶子节点都在同一层上。

C、各节点内关键字均升序或降序排列。

D、叶节点之间通过指针链接。

6、从19个元素中查找其中任意一个元素，如果最多进行4次元素之间的比较，则采用的查找方法只可能是（ ）

A、分块查找

B、折半查找

C、散列查找

D、二叉排序树

7、以下二叉树中，（ ）是完全二叉树。

A、AVL树

B、满二叉树

C、单支二叉树

D、二叉排序树

8、以下二叉排序树中查找效率最高的是（? ）

A、AVL树

B、所有结点都没有右子女的二叉排序树

C、右子树为空的二叉排序树

D、所有结点都没有左子女的二叉排序树

9、若散列表采用开地址法解决冲突，发生堆积的原因主要是（? ）

A、表中装入过多的记录

B、选择解决冲突的方法不适当

C、散列函数计算出的地址分布不均匀

D、装填因子过大

10、以下关于散列表的说法正确的是（? ）

A、所有记录都按关键码有序排列

B、所有记录可以顺序存取

C、存取速度快但占用存储空间较多

D、若装填因子小，查找速度可达线性级

第6关：查找客观题测试（六）

1、设散列表长m=14,散列函数Hash(key)=key % 11。表中已有4个结点，地址分别为addr(15)=4, addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如用二次探测法解决冲突，关键字值为49的散列地址为（? ）

A、8

B、3

C、5

D、9

2、若将10个元素散列到容量为100000个元素的散列表中，则（? ）产生冲突。

A、一定会

B、一定不会

C、仍可能会

D、以上都不对

3、已知一个线性序列{38，25，74，63，52，48}，假定采用散列函数Hash(key)=key % 7 计算散列地址，并散列存储在散列表A[10]中，若采用线性探测法解决冲突，且个元素的查找概率相等，则在该散列表中查找成功的平均查找长度为（? ）

A、1.50

B、1.67

C、1.83

D、2.24

4、已知一棵3阶B树，如图所示，删除关键字78得到一个新的B树，其最右叶结点中关键字是（? ）

A、60

B、60,62

C、62,65

D、65

5、有一棵具有15个关键字的4阶B树，则含有关键字的结点数最多是（? ）

A、5

B、6

C、10

D、15

6、在一棵高度为2的5阶B树中，所含关键字的个数最少是（? ）

A、5

B、7

C、8

D、14

7、已知一棵5阶B树有53个关键字，并且每个结点的关键字都达到最少，则该树的高度是（? ）

A、3

B、4

C、5

D、6

8、随着散列表的装填因子a 的增大，查找表中指定元素的平均查找长度也要增大，可以平稳控制平均查找长度的增大幅度达到最小的解决冲突的方法是（ ）

A、线性探测法

B、二次探测法

C、双散列法

D、链地址法

9、散列表采用链地址法解决冲突，查找成功的平均查找长度（ ）

A、直接与关键字个数有关

B、直接与表的长度有关

C、直接与装填因子有关

D、直接与散列函数有关

10、在如图所示的AVL树中，插入关键字22后，关键字24所在结点的左右子结点中保存的关键字是

A、20,53

B、22,53

C、13,53

D、20,22