B

[解析] 对单链表和顺序表进行顺序查找，都需要逐个扫描表中元素，因此其平均查找长度相同，都是(n+1)/2。

C

[解析] 折半查找要求表的存储结构有随机存储特性，且表中元素要有序，因此本题选C。

B

[解析] 对长度为n的有序顺序表进行折半查找，其平均查找长度与有n个结点的完全二叉树同数量级，即O(log₂n)，因此本题选B。

D

[解析] 折半查找的平均查找长度可用二叉判定树分析，其高度与完全二叉树相同，根据完全二叉树的性质，有。

D

[解析] 对有序顺序表中的元素进行查找所需要的总比较次数与对应元素在表中的位置有关，最多不会超出该表对应二叉判定树的高度，因此本题选D。

D

[解析] 采用折半查找的查找序列为50，24，13，18。注意，每次在一个查找区间找中点时，如果区间中元素个数为偶数，如n=4，则取中间偏前的元素，即。

B

[解析] 折半查找的平均查找长度和最大查找长度都是O(log₂n)；二叉排序树的查找性能与数据的输入顺序有关，最好情况下的平均查找长度与折半查找相同，但最坏情况下，即形成单支树的场合，其查找长度为O(n)。

B

[解析] 根据m阶B树的定义，树中的每个结点最多有m棵子树，且严格限制所有失败结点在同一层次上，所以是m叉高度平衡树。此外，B树根结点中的各关键字值都大于它左边子树上所有结点的关键字值，同时小于它右边子树上所有结点的关键字值，且结点内所有关键字是从小到大有序排列的，所以它又是查找树。

C

[解析] 根据B树的定义，10阶B树的根结点最多可以有9个关键字(m=10-1)，最少有1个关键字。

B

[解析] 根据m阶B树的定义，树中每个结点最多有m棵子树，有m-1个关键字，若插入新关键字后该结点的关键字数超过了m-1，则需要进行分裂。

B

[解析] 根据B树的性质，新关键字插入在叶结点上。为查找插入位置需读取的结点数等于树的高度。

C

[解析] B树和B+树都是平衡的m叉查找树，都用于文件的索引结构，都能有效地支持随机查找，因为结点中的元素有序，且是顺序存储。理想情况下，每深入一层，就把查找范围缩小到原来的1/m，很快逼近到查找的目标。但对于B树整体而言不支持顺序查找，即不能方便地顺序扫描整棵树中的所有结点，而B+树所有叶结点有一条链把它们顺序链接起来，所以B+树能支持顺序查找。

C

[解析] 散列法存储的基本原理是：将元素的关键字作为自变量，通过一定的函数(称为散列函数)，计算出对应的函数值，把这个函数值作为元素的存储地址。

C

[解析] 发生冲突的原因是由于在使用散列函数时经常把不同的关键字值映射到同一个散列地址上，即不同的自变量得到了相同的函数值。

D

[解析] 装填因子不是选择散列函数的原则。当然，不同的散列函数在装填因子不断增大的情况下，平均查找长度的增长速度是不同的。

A

[解析] 散列法通过函数值可以直接找出其存储地址，而无须进行多次关键字的比较(冲突发生时除外)，因此查找速度非常快，时间复杂度为常量级。

C

[解析] 同义词子表所链接的各个表项的关键字互为同义词，意味着虽然这些关键字的值不同，但用同一个散列函数计算出的散列地址相同。

A

[解析] 散列表的平均查找长度与处理冲突的方法有关，与装填因子a有关，与表的长度无关。

C

[解析] 在长度为9的有序顺序表中进行折半查找，在相等查找概率下的查找性能可以用如下图所示的二叉判定树来分析。
   
   每个圆形结点代表表中的一个数据元素，结点旁边附加的数字是该数据元素在表中的序号。在相等查找概率的情况下，查找成功的平均查找长度和查找不成功的平均查找长度分别为
   ASL_succ=(1×1+2×2+3×4+4×2)/9=25/9
   ASL_unsucc=(3×6+4×4)/10=34/10

B

[解析] 根据m阶B树的定义，每个结点至多有m棵子树，所以至多有m-1个关键字；所有失败结点都在同一层上，所以②③正确。①④不正确，因为除根结点之外所有非失败结点至少有棵子树；当插入一个索引项引起B树结点分裂后，只有当根结点需要分裂时，树才长高一层。综合以上分析，本题选B。

C

[解析] 根据m阶B树的定义，每个结点(包括根结点)至多有m棵子树，选项A正确。B树是高度平衡的，它限制所有失败结点都在同一层次上，B树的叶结点是最底层非叶结点，不是失败结点，它也应在同一层次上，选项A、B、D正确。B树除根结点以外的所有非失败结点至少有m/2(m为偶数)或m/2+1(m为奇数)棵子树，根结点至少有两棵子树，选项C不正确。

D

[解析] 根据m阶B树的定义，除根结点之外所有非失败结点至少有棵子树，所以除根结点之外的所有非失败结点至少有-1个关键字，根结点至少有1个关键字，所以共有(n-1)×(-1)+1个关键字。

A

[解析] m阶B树的失败结点即为查找失败走到的结点，对n个关键字查找不成功的情况是待查找的关键字值介于n个关键字中某两个关键字值之间，这样的可能性有n+1种，因此失败结点有n+1个。

B

[解析] 当每个结点的关键字都达到最少的时候，求此时树的高度即为求树的最大高度，可以用以下公式计算：。

C

[解析] 在具有n个关键字的m阶B树中进行查找时，从根结点到关键字所在结点的路径上所涉及的结点数最多等于树的高度，而每访问一个结点，最多读1次盘，因此读盘次数最多为h。

C

[解析] 在插入过程中为查找插入位置读入的结点数为h，假设它们一直保存在内存中，最坏情况下从叶结点到根结点都要分裂，共分裂h次，每次写出2个结点，再加上1次写出分裂出的新根结点，共读/写了3h+1次磁盘。

B

[解析] 根据m阶B树的定义，除根结点之外每个非失败结点至少有个关键字。因为在B树中不论被删关键字在哪一层的结点上，最后都能归结到叶结点上的删除。如果在删除关键字之前叶结点中关键字数已经是，那么在删除关键字之后该结点的关键字数不足就必须进行结点的调整，当然不一定是结点合并，还要看兄弟结点内的关键字数。但如果要做结点合并，其兄弟结点关键字数一定也是。

C

[解析] 如果被删关键字不在叶结点，则需要用它右边子树最小关键字(在叶结点内)或它左边子树最大关键字(在叶结点内)填补上来，再到叶结点中删除填补上去的关键字，这个过程需要读盘h次。假设它们一直保存在内存中，最坏情况下从叶结点到根结点的下一层结点共h-1层要做结点合并，每次合并需读入1个兄弟结点，写出合并后的结点，共3h-2次读/写盘，另外共删除了h个结点。

B

[解析] 从空树开始，最初建立的是根结点，又是叶结点。以后分裂成p个结点，经过了p-1次分裂。

A

[解析] 根据m阶B树最大高度的推导，到了失败结点这一层，因此有n≥。

A

[解析] 让每一层关键字个数达到最多，高度就会降到最低。设该树的最小高度为h，则10^h≥960，。

B

[解析] 用除留余数法转换后的散列表在表的装填因子不断趋向1的过程中，查找性能退化速度最慢，说明它产生的冲突最少，散列地址均匀分布在地址空间各处。

D

[解析] 散列函数都有一个假定，即函数值应以同等概率取到值域的每个值，否则函数值不能均匀地分布到散列表的地址空间中。

C

[解析] 散列表中的“堆积”现象是由于同义词之间冲突而产生的探测序列占用了其他非同义词应该存放的存储空间，导致与非同义词之间冲突而产生探测序列之间的互相交织，从而延长了查找到“下一个空位”的时间，使得查找性能下降。

D

[解析] 探查次数最少的情况是第1个关键字通过1次比较后插入，第2个关键字通过2次比较后插入……第k个关键字通过k次比较后插入。总的探查次数=1+2+…+k=k(k+1)/2。

D

[解析] 线性探测、二次探测和双散列都属于解决冲突的开地址法，寻找下一个空位的操作仅限于散列表本身的基本存储空间，随着表的装满程度的增加，冲突越来越多，查找某一表项的平均查找次数也越来越多，以线性探测最甚。而链地址法设置溢出存储空间，装填因子a的增大，仅表明基本存储空间装得越来越满，但大多数发生冲突的表项都存放到溢出空间去了，在基本存储空间的冲突没有大幅增加，平均查找次数也不会大幅增长。

D

[解析] 常用的解决冲突的方法有两大类：开地址法和链地址法。开地址法中寻找下一个可存放元素的空位不超出表的范围，它又有线性探测、二次探测或双散列之分。链地址法采用链表方式，在表的范围之外分配空间存放发生冲突的元素。

B

[解析] 根据散列函数可计算的散列地址有7个，为0～6。如果有新的元素需要插入到这些地址，需要的探测次数如下：0号地址冲突，需要探查2次找到空位；1号地址、2号地址本身为空，1次探查就可找到空位；3号地址需要6次探查找到空位；4号地址需要5次，5号地址需要4次，6号地址需要3次探查找到空位。查找不成功的平均查找长度为ASL_unsucc=(2+1+1+6+5+4+3)/7=3.14。

每次在当前序列中取序列中点作为区域划分界限，然后对子区域分别递归地进行查找即可，代码如下：
   int binsearch(int A[],int l,int h,int x)
   {
   int m;
   if(l＞h)
   return -1;                        //未找到，返回-1
   else
   {
   m=(l+h)/2;
   if(x＜A[m])
   return(binsearch(A,l,m-1,x));    //在右段中查找
   else if(x==A[m])
   return m;                        //找到了，返回下标x
   else
   return(binsearch(A,m+1,h,x));    //在左段中查找
   }
   }

本题的哈希表构造过程如下：
   (1)H(22)=3*22 mod 11=0
   (2)H(41)=3*41 mod 11=2
   (3)H(53)=3*53 mod 11=5
   (4)H(46)=3*46 mod 11=6
   (5)H(30)=3*30 mod 11=2
   (6)H(13)=3*13 mod 11=6
   (7)H(1)=3*01 mod 11=3
   (8)H(67)=3*67 mod 11=3
   用链表法解决冲突的哈希表存储结构如下图所示。
   
   查找成功的平均查找长度为
   
   构造本哈希表的程序代码如下：
   typedef struct node
   {
   int key;
   struct node *next;
   } hashnode;
   hashnode ht[M];           //假设M是已经定义的常量
   void chash()
   {
   int x[]={22,41,53,46,30,13,1,67},i,j;
   hashnode *p;
   for(i=0;i＜M;++i)        //表头均置空
   ht[i].next=NULL;
   for(i=0;i＜N;++i)        //假设N是已经定义的常量
   {
   p=(hashnode *)malloc(sizeof(hashnode));
   p=＞key=x[i];
   j=(3*x[i]) % M;
   p-＞next=ht[j].next;     //将p结点插入到ht[j]之后
   ht[j].next=p;
   }
   }

实现本题功能的程序代码如下，可以验证其比较次数不超过m+n。
   void findx(int x)
   {
   i=0;j=N;
   while(B[i][j]!=x)
   if(B[i][j]＜x)
   ++i;
   else
   --j;
   cout＜＜i＜＜","＜＜j＜＜endl;
   }

先在有序表r中利用二分查找算法查找关键字值等于或小于x的结点，m指向正好等于x的结点或l指向关键字正好大于x的结点，然后采用移动法插入x结点即可。
   实现本题功能的程序代码如下：
   void bininsert(int A[],int x,int n)
   {
   int i=0,h=n-1,m,i;
   int inplace;                //在其位置之前插入x结点
   int find=0;                 //找到插入位置时为1
   while(l＜=h && find==0)
   //稍做改动，便成为二分查找法的非递归实现，读者可尝试
   {
   m=(l+h)/2;
   if(x＜A[m])
   h=m-1;
   else if(x＞A[m])
   l=m+1;
   else
   find=1;
   }
   if(find)
   inplace=m;
   else
   inplace=l;
   for(i=n-1;i＞=inplace;--i)  //采用移动法插入x结点
   A[i+1]=A[i];
   A[inplace]=x;
   }

先在索引表I中找出x在主表中的位置区间[1，h]，由于索引表按关键字key的顺序排序，所以这里的查找采用二分查找法。然后在主表A中的[1，h]区间中查找元素x，由于主表是无序的，所以这里的查找采用顺序查找法。
   实现本题功能的程序代码如下：
   typedef struct             //定义索引表结构
   {
   elemtype key;              //关键值
   int link;                  //指向主表的位置
   } index;
   typedef elemtype table[maxSize];
   //定义主表，maxSize是已经定义的常量
   index I[4]={{14,0},{34,5},{66,10},{85,15}};
   table A={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85};
   int search()
   {
   elemtype x;
   int place;                 //保存索引表中位置
   int i,l=0,h=3,m,find=0;
   cout＜＜"输入查找的值: ";
   cin＞＞x;
   while(l＜=h && find==0)    //采用二分查找法
   {
   m=(1+h)/2;
   if(x＜I[m].key)
   h=m-1;
   else if(x＞I[m].key)
   l=m+1;
   else
   find=1;
   }
   if(find)
   place=m-1;
   else
   place=1;
   if(place＜=2)              //找出x在A中的位置区间[l,h]
   {
   l=I[place].link;
   h=I[place+1].key-1;
   }
   else if(place==3)
   {
   l=I[place].link;
   h=19;
   }
   else                       //在索引表中未找到x的正确位置
   {
   cout＜＜"A中不存在"＜＜x＜＜endl;
   return 0;
   }
   i=1;                       //在A中的位置区间[1,h]中顺序查找x
   while(i＜=h && A[i]!=x)
   ++i;
   if(i＜=h)
   tout＜＜"位置="＜＜i＜＜endl;
   else                       //在主表中未找到x的正确位置
   {
   cout＜＜"A中不存在"＜＜x＜＜endl;
   return 0;
   }
   return 1;
   }
   }

本题的哈希表构造过程如下：
   (1)H(22)=3*22 mod 11=0比较1次
   (2)H(41)=3*41 mod 11=2比较1次
   (3)H(53)=3*53 mod 11=5比较1次
   (4)H(46)=3*46 mod 11=6比较1次
   (5)H(30)=3*30 mod 11=2冲突
   d1=H(30)=2
   H(30)=(2+(7*30 mod 10)+1)mod 11=3比较2次
   (6)H(13)=3*13 mod 11=6冲突
   d1=H(13)=6
   H(13)=(6+(7*13 mod 10)+1)mod 11=8比较2次
   (7)H(1)=3*01 mod 11=3冲突
   d1=H(1)=3
   H(1)=(3+(1*7 mod 10)+1)mod 11=0冲突
   d2=H(1)=0
   H(1)=(0+(1*7 mod 10)+1)mod 11=8冲突
   d3=H(1)=8
   H(1)=(8+(1*7 mod 10)+1)mod 11=5冲突
   d4=H(1)=5
   H(1)=(5+(1*7 mod 10)+1)mod 11=2冲突
   d5=H(1)=2
   H(1)=(2+(1*7 mod 10)+1)mod 11=10比较6次
   (8)H(67)=3*67 mod 11=3冲突
   d1=H(67)=3
   H(67)=(3+(7*67 mod 10)+1)mod 11=2冲突
   d2=H(67)=2
   H(67)=(2+(7*67 mod 10)+1)mod 11=1比较3次
   
   构造本哈希表的程序代码如下：
   struct hterm
   {
   int key;                               //关键字值
   int si;                                //散列次数
   };
   struct hterm hlist[M];                 //假设M=11是已定义的常量
   int i,adr,sum,d;
   int x[N]={22,41,53,46,30,13,1,67};     //关键字赋值
   //假设N=8是已定义的常量
   float average;
   void chash()                           //创建哈希表
   {
   for(i=0;i＜M;++i)                      //置初值
   {
   hlist[i].key=0;
   hlist[i].si=0;
   }
   for(i=0;i＜N;++i)
   {
   sum=0;
   adr=(3*x[i]) % M;
   d=adr;
   if(hlist[adr].key==0)
   {
   hlist[adr].key=x[i];
   hlist[adr].si=1;
   }
   else
   {
   do                                     //处理冲突
   {
   d=(d+(x[i]*7) % 10+1) % M;
   sum=sum+1;
   } while(hlist[d].key!=0);
   hlist[d].key=x[i];
   hlist[d].si=sum+1;
   }
   }
   }

实现本题功能的函数代码如下：
   int find(int x)
   {
   int h,find=1;
   h=(3*s) % M;
   while(hlist[h].key!=s)
   {
   h=(h+(s*7) % 10+1) % M;
   if(hlist[h].key==0)
   {
   find=0;
   break;
   }
   }
   if(find==1)
   {
   return 1;     //成功返回1
   }
   else
   {
   return 0;    //失败返回0
   }
   }

实现本题功能的函数代码如下：
   int delnode(int s)
   {
   hashnode *p,*q;
   int i;
   i=(3*s) % M;
   p=ht[i].next;q=p;
   while(p!=NULL && p-＞key!=s)
   {
   cout＜＜p-＞key＜＜endl;
   q=p;
   p=p-＞next;
   }
   if(p!=NULL && p==q)    //p为第一个结点
   {
   ht[i].next=p-＞next;
   free(p);
   return 1;
   }
   else if(p!=NULL)      //p为其他结点
   {
   q-＞next=p-＞next;
   free(p);
   return 1;
   }
   else
   {
   return 0;
   }
   }

对B-树的线序遍历和查找算法与二叉排序树相应的算法相似。
   实现本题功能的程序代码如下。
   B-树结点的结构体定义如下：
   typedef struct node
   {
   int n;                                //当前结点中关键字的个数
   elemtype key[M];
   struct node *ptr[M];                  //M是已定义的常量
   } btree;
   查找：
   btree *search(btree *b,elemtype x)    //在b中查找值为x的结点
   {
   int i;
   if(b!=NULL)
   {
   i=0;
   while(i＜b-＞n && x＞b-＞key[i])
   ++i;
   if(i==b-＞n)
   return search(b-＞ptr[i],x);
   else if(x==b-＞key[i])    //在b中找到了，则返回b
   return b;
   else
   return search(b-＞ptr[i],x);
   }
   else
   return NULL;
   }
   void inorder(btree *b)
   {
   int i;
   if(b!=NULL)
   {
   for(i=0;i＜b-＞n-1;++i)
   cout＜＜b-＞key[i]＜＜",";
   for(i=0;i＜=b-＞n;++i)
   inorder(b-＞ptr[i]);
   }
   }