一、填空题
1．顺序查找算法的平均查找长度为 n/2 。一个无序序列可以通过构造一棵二叉排序树而变成一个 有序 序列。
2．在查找操作中，查找的范围对象是 数据元素 。
3．假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为 。
4．长度为255的表，采用分块查找法，每块的最佳长度是 16 。
5．在分块查找方法中，首先查找 待查记录所在的块 ，然后再查找相应的 记录 。
二、选择题
1．树最适合用来表示 C 。
A．有序数据元素。 B．无序数据元素。
C．元素之间具有分支层次关系的数据。 D．元素之间无联系的数据。
2．按中序遍历二叉排序树，得到的序列是按关键字 A 序列。
A．升序 B．降序 C．无法确定 D．无序
3．折半查找要求查找表必需按关键字 A 。
A．有序 B．升序有序
C．降序有序 D．有序无序均可
4．顺序查找所对应的查找表是 B 。
A．动态查找表 B．静态查找表
C．无法确定。 D．均可以
5．按中序遍历二叉排序树，得到的序列是按关键字 B 序列。
A．降序 B．升序 C．无法确定 D．无法遍历
6．折半查找算法要求查找表中的记录按关键字 B 。
A．降序有序 B．有序 C．升序有序 D．有序与否均可以
8．由同一关键字集合构造的各棵二叉排序树（ D ）
A．其形态不一定相同，但平均查找长度相同
B．其形态不一定相同，平均查找长度也不一定相同
C．其形态均相同，但平均查找长度不一定相同
D．其形态均相同，平均查找长度也都相同
9．设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( B )
云南大学信息学院计算机科学与工程系《数据结构》课后作业
第2套 第9章 集合
一、 选择题
1. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )
A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2
2．适用于折半查找的表的存储方式及元素排列要求为( )
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
3．当采用分快查找时，数据的组织方式为 ( )
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
4. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A. LL B. LR C. RL D. RR
5. 下面关于m阶B树说法正确的是( )
①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字;
③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。
A． ①②③ B. ②③ C. ②③④ D. ③
6. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B．除留余数法是所有哈希函数中最好的
个人收集整理 仅供参考学习
1 / 3 第九章查找习题
一、判断题
1.折半查找法可以用于按值有序的线性链表的查找。
2.对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。
3.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
4.中序遍历二叉排序树的结点就可以得到排好序的结点序列。
5.哈希表存储的基本思想是由关键码的值决定数据的存储地址。
6.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。
7.装载因子是散列法的一个重要参数，它反映散列表的装满程度。
8.采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。个人收集整理 勿做商业用途
二、选择题
1.采用顺序查找方法查找长度为n的线性表，平均查找长度为
A.n B.n/2 C.(n+1)/2 D.(n-1)/2
2.对线性表采用折半查找法，该线性表必须
A.采用顺序存储结构 B.采用链式存储结构
C.采用顺序存储结构，且元素按值有序
D.采用链式存储结构，且元素按值有序
3.在按值有序的线性表(5,8,11,12,15,20,32,41,57)中采用折半查找法查找20需要进行多少次元素间的比较个人收集整理 勿做商业用途
A.3 B.4 C.5 D.6
4.按逐点插入法建立对应于序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后，查找62要进行多少次比较。个人收集整理 勿做商业用途
A.2次 B.3次 C.5次 D.6次
5.散列法存储的基本思想是根据哪个来决定存储地址。
A.散列表空间 B.元素的序号
C.装载因子 D.关键码值
6.散列法存储的冲突指的是
A.两个元素具有相同的序号
B.两个元素的关键码值不同，而非码属性相同
C.不同关键码值对应相同的存储地址
1 第9章 查找答案
一、填空题
1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 9 次。设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式
)1(log12nnnASL来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：
全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！
4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m的散列表，初始状态为空，现将n（n
二、单项选择题
（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为
Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;
Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。
