数据结构习题及答案.doc

习题八 查找

一、单项选择题
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的链中有（ ）个记录。
A．1 B. 2 C. 3 D. 4
13. 关于杂凑查找说法不正确的有几个( )
（1）采用链地址法解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
（3）用链地址法解决冲突易引起聚集现象
（4）再哈希法不易产生聚集
A. 1 B. 2 C. 3 D. 4
14. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
15. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。
A. 一定会 B. 一定不会 C. 仍可能会

二、填空题
1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。

2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.

3．一个无序序列可以通过构造一棵_ _ _ _树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

4. 哈希表是通过将查找码按选定的__ __和 __ __，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_ __和 __ __。一个好的哈希函数其转换地址应尽可能__ __，而且函数运算应尽可能__ __。

5. 平衡二叉树又称__________，其定义是_____ _____。

6. 在哈希函数H（key）=key%p中，p值最好取__________。

7．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。

8. __________法构造的哈希函数肯定不会发生冲突。

9. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。

10．在散列存储中，装填因子α的值越大，则__ __；α的值越小，则__ __。

11. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。
#define N /*学生人数*/
int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/
{ int head=1,mid,rear=N;
do {mid=(head+rear)/2;
if(x<=a[mid]) __(1) __ else __(2)_ _;
}while(__(3)_ _);
if (a[head]<x) return head-1;
return head; }第九章 查找
一、单项选择题
1．B
2．C
3．D
4．C
5．B
6．B
7. C C
8．A
9．C
10．B
11．A
12. D
13. B
14. D
15. C

二、填空题
1. n n+1
2. 4
3． 二叉排序
4. (1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单
5. AVL树（高度平衡树，高度平衡的二叉排序树）
或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。
6. 小于等于表长的最大素数或不包含小于20的质因子的合数
7．k(k+1)/2
8. 直接定址法
9. 插入 删除
10． 存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小
11．(1)rear=mid-1 (2)head=mid+1 (3)head>rear