第八章测试1.
顺序查找算法适用于（ ）结构。
A:查找网 B:查找树 C:线性表 D:连通图
答案:C
2.
在顺序存储的线性表R[30]上进行顺序查找的平均查找长度为（ ）。
A:16
B:15.5
C:15 D:20 3.
对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为（ ）。
A:5 B:19/4
C:39/8
D:5.5 4.
如果有5个关键字{a,b,c,d,e}放在顺序表中，它们的查找概率分别为{0.35,0.25，0.20,0.15,0.05}，按照（ ）顺序存放可使平均查找长度达到最小。
A:d,a,b,c,e B:a,b,c,d,e C:a,c,e,d,b D:e,d,c,b,a 5.
对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（ ）。
A:n/4 B:(n-1)/2
C:n/2 D:(n+1)/2
6.
对线性表进行折半查找时，要求线性表必须（ ）。
A:以顺序方式存储 B:以链接方式存储 C:以顺序方式存储，且结点按关键字有序排序 D:以链接方式存储，且结点按关键字有序排序 7.
采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为（ ）。
A:O(n^2) B:O(log2n) C:O(nlog2n) D:O(n) 8.
采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数（ ）对应二叉判定树的高度（设高度≥2）。
A:小于等于
B:小于 C:大于 D:等于 9.
折半查找和二叉排序树的时间性能（ ）。
A:不定 B:有时不相同
C:相同 D:完全不同
10.
在常用的描述二叉排序树的存储结构中，关键字值最大的结点（ ）。
A:左右指针均不为空 B:右指针一定为空 C:左指针一定为空 D:左右指针均为空 11.
m阶B-树是一棵（ ）。
A:m+1叉高度平衡查找树 B:m-1叉高度平衡查找树 C:m叉高度平衡查找树 D:m叉查找树 12.
下列关于m阶B-树的说法中错误的是（ ）。
A:根结点中的数据是有序的 B:所有叶结点都在同一层次上 C:非失败结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树 D:根结点至多有m棵子树 13.
下面关于B-树和B+树的叙述中错误的是（ ）。
A:B-树和B+树都是平衡的多叉查找树 B:B-树和B+树都能有效地支持随机查找 C:B-树和B+树都可用于文件的索引结构 D:B-树和B+树都能有效地支持顺序查找 14.
散列法存储的基本思想是根据（ ）来决定元素的存储地址。
A:元素个数 B:元素的序号 C:非码属性 D:关键字值 15.
设一个散列表中有n个元素，用散列法进行查找，理想情况下的平均查找长度是（ ）。
A:O(1) B:O(n^2) C:O(log2n) D:O(n) 16.
使用散列函数将元素的关键字值映射为散列地址时，常会产生冲突。此时的冲突是指（ ）。
A:装填因子过大，数据元素过多 B:两个元素具有相同的序号 C:两个元素的关键字值不同，而非关键字值相同 D:不同关键字值对应到相同的存储地址 17.
以下关于散列函数选择原则的叙述中，不正确的是（ ）。
A:散列函数应是简单的，能在较短的时间内计算出结果 B:散列函数计算出来的地址应能均匀分布在整个地址空间中 C:散列函数的定义域应包括全部关键字值,值域必须在表范围之内 D:装填因子必须限制在0.8以下 18.
计算出的地址分布最均匀的散列函数是（ ）。
A:折叠法 B:平方取中法 C:数字分析法 D:除留余数法 19.
除留余数法的基本思路是：设散列表的地址空间为0～m-1，元素的关键字值为k，用p去除k，将余数作为元素的散列地址，即h(k)=k%p，为了减少发生冲突的可能性，一般取p为（ ）。
A:小于或等于m的最大素数 B:小于或等于m的最大合数 C:m D:大于m的最小素数 20.
解决散列法中出现的冲突问题常采用的方法是（ ）。
A:数字分析法、除留余数法、平方取中法 B:线性探测法、二次探测散列法、链地址法 C:数字分析法、除留余数法、线性探测法 D:数字分析法、线性探测法、双散列法 21.
在用开放定址法构造出的散列表中，散列到同一个地址而引起的“二次聚集”问题是由于（ ）引起的。
A:非同义词之间发生冲突 B:散列表“溢出” C:同义词之间发生冲突 D:同义词之间或非同义词之间发生冲突 22.
散列表的平均查找长度（ ）。
A:与处理冲突方法有关且与表的长度有关 B:与处理冲突方法有关而与表的长度无关 C:与处理冲突方法无关而与表的长度有关 D:与处理冲突方法无关且与表的长度无关 23.
在由n个元素组成的有序表上进行折半查找时，对任一个元素进行查找的长度都不会大于
。
A:错 B:对 24.
对于两棵具有相同关键码集合而形状不同的二叉查找树，按中序遍历它们得到的序列的各元素的顺序是一样的。
A:错 B:对 25.
在一棵AVL树中删除一个结点后，失去平衡的结点多于一个。
A:错 B:对
