Relax1000 数据结构 · 第7章 查找 · 题目¶
第7章 查找¶
本章 65 题；题目册印刷页 42–50。
Q1¶
设包含 4 个数据元素的集合 S，各元素的查找概率依次为{0.35, 0.15, 0.15, 0.35}。将 S 保存在一个长度为 4 的顺序表中，保存的顺序可调整，采用顺序查找，查找成功的平均查找长度最小为（ ）。
- A．2.1
- B．2.2
- C．2.3
- D．2.9
Q2¶
下列关于折半查找，说法错误的有（ ）。
- A．折半查找的判定树一定是一颗平衡二叉树
- B．折半查找的判定树中，所有叶子结点（非失败结点）不一定在同一层
- C．折半查找的成功和失败平均查找长度都小于树高
- D．小数据量的情况下，可能线性查找性能更高
Q3¶
下列说法错误的是（ ）。
- A．进行折半查找的表必须是顺序存储的有序表
- B．折半查找所对应的判定树是一棵平衡二叉树
- C．对二叉排序树进行中序遍历得到的结点的值的序列是一个有序序列
- D．在由 n 个元素组成的有序表上进行折半查找时，对任一个元素进行查找的长度都不会大于log2(n)
原页版面片段（用于核对图表、公式、矩阵或代码）
Q4¶
下列选项中不能构成折半查找中关键字比较序列的是（ ）。
- A．500，200，450，180
- B．500，450，200，180
- C．180，500，200，450
- D．180，200，500，450
原页版面片段（用于核对图表、公式、矩阵或代码）
Q5¶
含有 10 个关键字的有序序列，关于其二分查找判定树（不含外部结点）的说法错误的是（ ）。
I．每个分支结点的左右子树的结点总数之差始终不变（1 或-1）
II．度为 1 的结点个数为 3
III．是一棵完全二叉树
IV．是一棵二叉排序树
- A．I、II、IV
- B．I、III
- C．II、IV
- D．I、II、III、IV
原页版面片段（用于核对图表、公式、矩阵或代码）
Q6¶
折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素 58，则它将依次与表中（ ）比较大小，查找结果是失败。
- A．20、70、30、50
- B．30、88、50，70
- C．20、50
- D．30、88、50
Q7¶
对 511个关键字的有序序列进行折半查找，查找失败的平均查找长度为（ ）。
- A．4097 511
- B．4097 512
- C．9
- D．10
原页版面片段（用于核对图表、公式、矩阵或代码）
Q8¶
设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 X，则最多需要比较（ ）次就可以断定数据元素 X 是否在查找表中。
- A．5
- B．6
- C．7
- D．8
Q9¶
假设在有序线性表 A[1..30]上进行二分查找，则比较五次查找成功的结点数为（ ）。
- A．8
- B．12
- C．15
- D．16
Q10¶
下列关于查找的说法中，正确的是（ ）。
- A．若数据元素保持有序，则查找时就可以采用折半查找法
- B．折半查找与二叉查找树的时间性能在最坏情况下是相同的
- C．折半查找法的平均查找长度一定小于顺序查找法
- D．折半查找法查找一个元素大约需要 O(log2n)次关键字比较
原页版面片段（用于核对图表、公式、矩阵或代码）
Q11¶
对于具有 152 个记录的文件，采用分块查找法，且每块长度为 8。若索引表和各块内均用顺序查找，则平均查找长度为（ ）。
- A．4.5
- B．9
- C．14.5
- D．13.5
Q12¶
当采用分块查找时，数据的组织方式为（ ）。
- A．数据分成若干块，每块内数据有序
- B．数据分成若干块，每块内数据无序但块间有序，每块内最大（或最小）的数据组成索引块
- C．数据分成若干块.，每块内数据有序，每块内最大（或最小）的数据组成索引块
- D．数据分成若干块，每块（除最后一块外）中数据个数需要相同
Q13¶
若对 961个记录的索引顺序表进行分块查找，块数为 31，索引查找采用二分查找，块内查找为顺序查找，那么查找成功的平均查找长度为（ ）（结果向上取整）。
- A．20
- B．21
- C．25
- D．26
Q14¶
对有 2500 个记录的索引顺序表（分块表）进行查找，若块内查找和块间查找都采用顺序查找最理想的块长为（ ）。
- A．50
- B．125
- C．500
- D．〔公式/符号见原页版面片段〕2 2500
原页版面片段（用于核对图表、公式、矩阵或代码）
Q15¶
下面是关于二叉排序树的说法，正确的是（ ）。
- A．已知二叉排序树的关键字的先序遍历序列，可以确定该二叉排序树
- B．同样一组记录，等概率成功查找时，二叉排序树平均查找时间一定小于顺序表平均查找时间
- C．n 个结点的二叉排序树有多种，等概率成功查找时，其中树高最小的二叉排序树不一定是平均查找长度最佳的
- D．在任意一棵二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与原二叉排序树相同
原页版面片段（用于核对图表、公式、矩阵或代码）
Q16¶
分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。
- A．(100，80，60，90，120，130，110)
- B．(100，120，110，130，80，60，90)
- C．(100，80，90，60，120，110，130)
- D．(100，60，80，90，120，110，130）
原页版面片段（用于核对图表、公式、矩阵或代码）
Q17¶
若想查找 63，哪个最有可能是在二叉排序树上进行的查找（ ）。
- A．2 25 101 39 80 70 59 63
- B．39 101 25 80 70 59 63
- C．101 70 2 39 25 59 80 63
- D．59 2 80 70 39 25 63
Q18¶
已知 10 个元素（54，28，16，34，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉排序树，查找值为 62 的结点所需比较次数为（ ）。
- A．2
- B．3
- C．4
- D．5
Q19¶
高度为 8 的平衡二叉树的结点数至少为（ ）。
- A．15
- B．54
- C．87
- D．255
Q20¶
含有 18 个结点的平衡二叉树的最大深度为（ ）。
- A．4
- B．5
- C．6
- D．7
Q21¶
在含有 15 个结点的平衡二叉树上，查找关键字为 28 的叶子结点（存在该结点），则依次比较的关键字有可能是（ ） 。
- A．30, 28
- B．38, 48, 28
- C．48, 18, 38, 28
- D．60, 20, 50, 40, 38, 28
Q22¶
在平衡二叉树中插入一个节点后造成了不平衡，设最低的不平衡节点为 A，并已知 A的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应作（ ）型调整以使其平衡。
- A．LL
- B．LR
- C．RL
- D．RR
Q23¶
一棵结点数为 12 的平衡二叉树，其最大高度为（ ）（根节点高度为 1）；叶子结点最多为（ ）个。
- A．4, 5
- B．5, 5
- C．5, 6
- D．4, 6
Q24¶
高度为 3 的平衡二叉排序树的形态共有（ ）种。
- A．13
- B．14
- C．16
- D．15
Q25¶
5 个结点的平衡二叉树有多少种不同的形态（ ）。
- A．5
- B．6
- C．7
- D．8
Q26¶
若将关键字 1,2,3,4,5,6,7依次插入初始为空的平衡二叉树 T，则 T中平衡因子为 0的分支结点的个数是（ ）。
- A．0
- B．1
- C．2
- D．3
Q27¶
下图有可能是一棵刚做过 BST 的（ ）操作，但尚未旋转调整的 AVL 树。
I．delete(2)
II．insert(3)
III．delete(4)
IV．insert(5) V．insert(8)
- A．II、III、V
- B．I、IV
- C．II、IV
- D．I、III、IV
原页版面片段（用于核对图表、公式、矩阵或代码）
Q28¶
下列关于二叉排序树和平衡二叉树说法，正确的是（ ）。
- A．对一棵二叉排序树，删除其中某个结点，再插入关键字与其相同的结点，二叉排序树不变
- B．对一棵二叉排序树，插入某个结点，再删除这个插入的结点，二叉排序树不变
- C．对一棵平衡二叉树，删除其中某个结点，再插入关键字与其相同的结点，平衡二叉树不变
- D．对一棵平衡二叉树，插入某个结点，再删除这个插入的结点，平衡二叉树不变
Q29¶
下列关于红黑树的说法正确的是（ ）。
I．红黑树的某棵子树（如果有的话），也一定是红黑树。
II．如果根结点黑高为 h，则内部结点数（含关键字的结点）最多有22ℎ − 1 个
III．红结点数量不会超过内部结点数量的一半
IV．任何一个结点的左右子树高度之差不超过 2 倍V．红黑树和平衡二叉树的查找、插入、删除操作，最坏时间复杂度数量级相同
- A．II、III、IV、V
- B．I、IV、V
- C．II、IV、V
- D．III、IV、V
原页版面片段（用于核对图表、公式、矩阵或代码）
Q30¶
下列关于红黑树和 AVL树的说法中，不正确的是（ ）。
I．一棵含有 n 个结点的红黑树的高度至多为 2〔公式/符号见原页版面片段〕2 〔公式/符号见原页版面片段〕 + 1
II．若一个结点是红色的，则它的父结点和孩子结点都是黑色的
III．红黑树的查询效率一般要优于含有相同结点数的 AVL 树
IV．若 AVL 树的某结点的左右孩子的平衡因子都是零，则该结点的平衡因子也是零
- A．I、III
- B．III
- C．II、IV
- D．III、IV
原页版面片段（用于核对图表、公式、矩阵或代码）
Q31¶
下列满足红黑树定义的是（ ）。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q32¶
在下图所示的红黑树中插入结点 2 且染成红色后，则下一步应进行的操作是（ ）。
- A．左旋
- B．右旋
- C．变色
- D．无需调整
原页版面片段（用于核对图表、公式、矩阵或代码）
Q33¶
将关键字 41， 38， 31， 12， 19， 8 依次插入空的红黑树后，下列对结果的树说法错误的是（ ）。
- A．有 2 个红色结点， 4 个黑色结点
- B．12 和 41 的黑高都为 0
- C．8 是 12 的孩子
- D．树中存在相邻的黑色内部结点
Q34¶
将关键字 5,4,3,2,1 依次插入初始为空的红黑树 T，则 T 的最终形态是（ ）。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q35¶
右图平衡二叉树，删除结点 32，经过（ ）调整。
- A．LL
- B．LR
- C．RL
- D．RR
原页版面片段（用于核对图表、公式、矩阵或代码）
Q36¶
下图平衡二叉树，删除结点 32，要经历（ ）次旋转。
- A．1
- B．2
- C．3
- D．4
原页版面片段（用于核对图表、公式、矩阵或代码）
Q37¶
下列关于 B 树的说法错误的是（ ）。
- A．高度为 h 的 m 阶 B 树最多存储〔公式/符号见原页版面片段〕ℎ − 1 个关键字
- B．所有叶结点都在同一层次上
- C．含 n 个结点（不含失败结点）的 m阶 B 树至少包含 〔公式/符号见原页版面片段〕 − 1 × ⌈〔公式/符号见原页版面片段〕/2⌉ − 1 + 1 个关键字
- D．和二叉搜索树相同，B 树高度的增加也是发生在底部
原页版面片段（用于核对图表、公式、矩阵或代码）
Q38¶
下列数据结构中，从根结点到任意叶结点的路径都是有序的是（ ）。
- A．AVL
- B．二叉查找树
- C．红黑树
- D．堆
Q39¶
在一棵含有 n 个关键字的 m 阶 B 树中进行查找，至多读盘（ ）次 。
- A．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- B．1 + 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕⌈〔公式/符号见原页版面片段〕/2⌉((〔公式/符号见原页版面片段〕 + 1)/2) + 1
- D．〔公式/符号见原页版面片段〕⌈〔公式/符号见原页版面片段〕/2⌉((〔公式/符号见原页版面片段〕 + 1)/2) + 1
原页版面片段（用于核对图表、公式、矩阵或代码）
Q40¶
下列关于 B 树的说法错误的是（ ）。
I．查找 B树的一个结点的前驱结点就是在找其左子树的最右结点
II．B 树支持顺序查找
III．B 树每次都需查询到叶结点，查询性能稳定
IV．使用 B 树进行范围查找时，需要依赖中序遍历
- A．II,III
- B．III
- C．III,IV
- D．II,IV
Q41¶
初始为空的 3 阶 B 树依次插入 10，26，16，12，3，28，18，插入并调整结束后，根节点的关键字为（ ）。
- A．10
- B．16
- C．10，16
- D．10，16，26
Q42¶
下图是一棵 3 阶 B 树，删除 27 后调整后 B树是（ ）。
- A．
- B．
- C．
- D．
原页版面片段（用于核对图表、公式、矩阵或代码）
Q43¶
下图所示 5 阶 B 树，删除关键字 24 后，再删除 59，所得 B 树的根节点是（ ）。
- A．45
- B．57
- C．38，45，57，88
- D．45，64
原页版面片段（用于核对图表、公式、矩阵或代码）
Q44¶
下面关于 m 阶 B+树的叙述，正确的是（ ）。
- A．每个结点内的关键字个数范围为 ⌈ 〔公式/符号见原页版面片段〕 2 ⌉ 〔公式/符号见原页版面片段〕
- B．所有叶子结点（含关键字）的关键字个数和是 n，那么非叶子结点关键字个数总和也为 n
- C．方便范围查找，也支持顺序查找
- D．B+树查找时，不一定要查到最后一层
原页版面片段（用于核对图表、公式、矩阵或代码）
Q45¶
下面关于 B 树和 B+树的叙述，不正确的结论是（ ）。
- A．B 树和 B+树都能有效支持顺序查找
- B．B 树和 B+树都能有效支持随机查找
- C．B 树和 B+树都是平衡的多叉树
- D．B 树和 B+树都可用于文件索引结构
Q46¶
已知一棵 5 阶 B 树中共有 53 个关键字，则树的最大高度为（ ），最小高度为（ ）。
- A．2
- B．3
- C．4
- D．5
Q47¶
在 7 阶 B 树中搜索第 2025 个关键字（按从上往下从左至右顺序），若根结点已读入内存，则最多需启动（ ）次 I/O。
- A．4
- B．5
- C．6
- D．7
Q48¶
具有 n 个关键码的 m 阶 B 树的失败节点个数最多为（ ） 。
- A．n+1
- B．n-1
- B．C．n * m
- D．⌈〔公式/符号见原页版面片段〕/2⌉ ∗ 〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
审计旁注（非原文）：改标号
选项区原文出现“B．C．”重叠标号；依后续解析，四项应按 A、B、C、D 理解，答案 A。
Q49¶
设哈希地址空间为 0～m-1，k 为记录的关键字，哈希函数采用除留余数法，即 Hash(k)=k%p，为了减少发生冲突的频率，一般取 p 为（ ）。
- A．m
- B．小于或等于 m 的最大质数
- C．大于 m 的最小质数
- D．小于等于 m的最大合数
原页版面片段（用于核对图表、公式、矩阵或代码）
Q50¶
哈希表采用线性探测法处理冲突，在查找某个关键词时，查找路径上的各个关键字（ ）。
- A．一定是同义词
- B．一定不是同义词
- C．可能是同义词
- D．都相同
Q51¶
下列关于哈希表的说法错误的是（ ）
- A．除留余数法是所有哈希函数中最好的
- B．采用链地址法解决冲突时，不存在聚集现象
- C．在哈希表查找中，比较操作一般也是不可避免的
- D．若散列表的装填因子 a<1，仍可能产生冲突
Q52¶
哈希函数为 H(key)=key MOD11，表中已存入关键字分别为 7、14，37、60 和 83 的五个记录，此时哈希表的装填因子 a=0.33。用二次探测再散列法解决冲突，则再放入关键字为 49 的记录时，它的位置下标是（ ）。
- A．5
- B．8
- C．9
- D．1
原页版面片段（用于核对图表、公式、矩阵或代码）
Q53¶
已知关键字序列{2, 52, 66, 30, 41, 21, 19, 6, 10, 16, 101, 1}，Hash 函数为 key%11，表长为 12，冲突解决方法为拉链法，请问该表的查找失败的 ASL 为（ ） 。
- A．22/11
- B．23/11
- C．23/12
- D．22/12
原页版面片段（用于核对图表、公式、矩阵或代码）
Q54¶
将关键字序列 (34，69，9，56，24，44) 散列存储到散列表中，散列表的是一个一维数组A[0....8 ]，散列函数 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 7，采用线性探测法解决冲突，现删除 24，插入关键字 51，则51 在散列表中的下标为（ ），查找失败的平均查找长度 ASL 为（ ）。
- A．3，16/7
- B．5，20/7
- C．3，19/9
- D．5，31/9
原页版面片段（用于核对图表、公式、矩阵或代码）
Q55¶
下列关于散列冲突的说法中，正确的是（ ）。
- A．再散列在处理冲突时不会产生“堆积”现象
- B．在哈希表中进行查找是不需要进行关键字比较的
- C．散列函数选的好可以减少冲突现象
- D．采用线性探测法处理冲突时，所有同义词在散列表中一定相邻
Q56¶
下述有关 hash 冲突时候的解决方法的说法，错误的是（ ）。
- A．通常有两类方法处理冲突：开放定址（OpenAddressing）法和拉链（Chaining）法
- B．开放定址更适合于造表前无法确定表长的情况
- C．在用拉链法构造的散列表中，删除结点的操作易于实现
- D．拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间
Q57¶
下面关于散列查找的说法，不正确的是（ ）。
- A．采用链地址法处理冲突时，查找任何一个元素的时间都相同
- B．采用链地址法处理冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的
- C．用链地址法处理冲突，不会引起二次聚集现象
- D．用链地址法处理冲突，适合表长不确定的情况
Q58¶
假定有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入足够长的散列表中，至少要进行（ ）次探测。
- A．k - 1
- B．k
- C．k(k - 1) / 2
- D．k(k + 1) / 2
Q59¶
如果要求一个线性表既能较快地查找，又能适应动态变化的要求，最好采用（ ）查找法。
- A．顺序查找
- B．折半查找
- C．分块查找
- D．哈希查找
Q60¶
散列表查找过程和给定值进行比较的关键字个数取决于（ ）。
- A．散列函数
- B．处理冲突的方法
- C．装填因子
- D．以上全部
Q61¶
高度为 5 的平衡二叉树（根节点高度为 1）的说法中，正确个数有（ ）个。
I.结点数最少为 12
II.根节点左右子树结点数之差最大为 11
III.若每个分支结点的平衡因子都为 1，那么根结点左子树有 7 个结点
IV.所有叶子结点的层高中，层高差最大为 2
- A．1
- B．2
- C．3
- D．4
Q62¶
高度为 4 的平衡二叉树最多有（ ）种不同的树形。
- A．15
- B．7
- C．315
- D．225
Q63¶
对于任意一棵有 10 个结点的平衡二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元(仅存放结点的数据信息)，则存放该平衡二叉树需要的存储单元数量至少是（ ）。
- A．31
- B．16
- C．15
- D．10
Q64¶
若 4 阶 B 树有 7 个不同的关键字，第二层上的关键字不小于 3 个，那么符合条件的不同 B 树有（ ）个。
- A．8
- B．9
- C．10
- D．11
Q65¶
若高度为 h 的 B 树（根节点高度为 1），初始时，根结点不在内存，每个结点占一个磁盘块。下列说法正确的是（ ）。
I.插入关键字导致结点发生分裂，树高一定会加 1
II.删除关键字导致结点合并，树高不一定减 1
III.删除一个关键字，可能会减少 h+1 个结点
IV.插入一个关键字，可能会发生 2h+1 次写磁盘
- A．I、II
- B．II、III
- C．III、IV
- D．II、IV