下列的叙述不正确的个数是()。(1)9阶B-树，除根以外的任一结点的关键字个数不少于4(2)理想情况下，在散列表中查找一个元素的时间复杂度为0(1)(3)在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻(4)在索引顺序表的查找中，对索引表既可以采用顺序查找方法，也可采用=分查找方法A.1 B.2 C.3 D.4

第1题：

第2题：

正确答案：C
解析：本题考查数据结构中哈希表的基础知识。线性探测法解决冲突的方法是：若在地址r处发生冲突，则探测地址 r+1，若已到达表尾，则再从表头出发进行探测。若是插入元素，则找到一个空闲单元为止。若表已满则采用其他策略解决冲突；若是访问元素，则找到元素或一个空闲单元为止。
  初始哈希表为空，根据序列(16，25，35，43，51，62，87，93)和哈希函数H(Key)=Key mod 7构造哈希表的过程如下。
  ①16 mod 7=2  25 mod 7=4  35 mod 7=0  43 mod 7=1，地址2、4、0、1空闲，所以插入对应元素。
  ②51 mod 7=2，地址2处冲突，因此探测地址3，该单元空闲，因此51存入地址3。由于62 mod 7=6，地址6处空闲，所以将62插入地址6。
  ③87 mod 7=3，地址3处冲突，因此依次探查地址4、5，地址5空闲，因此87存入地址5；93 mod 7=2，地址2处冲突，因此依次探查地址3、4、5、6、7，地址7空闲，因此93存入地址7。
  为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。对于含有n个记录的表，查找成功时的平均查找长度定义为：，其中，Pi为对表中第i个记录进行查找的概率，且，一般情况下，均认为查找每个记录的概率是相等的，即 Pi=1/n。Ci为找到表中其关键字与给定值相等的记录时(为第i个记录)，和给定值已进行过比较的关键字个数。对于本试题所构造的哈希表，平均查找长度ASL=(1+1+1+1+2+1+3+6)/8=2。

第3题：

顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。

第4题：

下面关于折半查找法的叙述中，正确的是（）。

• A、只要线性表中元素按值有序排列，就可以采用折半查找
• B、只要线性表采用顺序存储结构，就可以采用折半查找
• C、线性表中元素按值有序排列，并且采用顺序存储结构时才能采用折半查找
• D、在链表中也可以采用折半查找

第5题：

采用拉链法解决冲突的散列表中，查找的平均查找长度（）

• A、直接与关键字个数有关
• B、直接与装填因子a有关
• C、直接与表的容量有关
• D、直接与散列函数有关

第6题：

下面关于散列查找的说法正确的是（）

• A、在采用线性探测法处理冲突的散列表中，同义词在表中一定相邻；
• B、除留余数法是所有散列函数中最好的；
• C、在散列表中进行查找，“比较”次数的多少与冲突有关；
• D、散列函数构造的越复杂越好，因为这样随机性好，冲突小。

第7题：

以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为（），时间复杂度为（）。

第8题：

既希望较快的查找又便于线性表动态变化的查找方法是（）。

• A、顺序查找
• B、折半查找
• C、散列查找
• D、索引顺序查找

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

在顺序表（2，4，6，8，10）中采用折半查找方法查找元素5，要经过（）次元素之间的比较。

第16题：

在散列查找中，平均查找长度主要与（）有关。

• A、散列表长度
• B、散列元素个数
• C、装填因子
• D、处理冲突方法

第17题：

在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

第18题：

设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为（）在链式存储结构上实现顺序查找的平均时间复杂度为（）

第19题：

在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。

第20题：

在索引顺序表的查找中，对索引表既可以采取顺序查找，也可以采用折半查找。

第21题：

第22题：

第23题：