顺序存储平均搜索长度

1. 如何比喻平均查找长度

以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为4。

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找的时间复杂度是O（2为底的log(n)），也就是说它的平均查找长度只和该有序表的长度有关，当长度为10时，平均查找长度为log10（2为底），其>3，<4，所以平均查找长度为4次。

(1)顺序存储平均搜索长度扩展阅读：

二分查找的查找过程：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

2. 采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为多少

(1+n)/2

(1+2+3+...+n)/n = (1+n)/2

对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。

顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存储单元的长度。

(2)顺序存储平均搜索长度扩展阅读：

删除L的第i个数据元素，并用e返回其值。

Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5

{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)

// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1

ElemType *p,*q;

if(i<1||i>L.length) // i值不合法

return ERROR;

p=L.elem+i-1; // p为被删除元素的位置

e=*p; // 被删除元素的值赋给e

q=L.elem+L.length-1; // 表尾元素的位置

for(++p;p<=q;++p) // 被删除元素之后的元素左移

*(p-1)=*p;

L.length--; // 表长减1

return OK;

}

3. 长度为10的表，采用顺序查找法，平均查找长度ASL是 紧急，在线等

1 查找的基本概念

查找 就是在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则，查找失败。
查找表 是一组待查数据元素的集合。
静态查找 是仅仅进行查询和检索操作，不改变查找表中数据元素间的逻辑关系的查找。
动态查找 是除了进行查询和检索操作外，还对查找表进行插入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑关系。

平均查找长度 （ASL-Average Search Length）：在查找过程中，对每个结点记录中的关键字要进行反复比较，以确定其位置。因此，与关键字进行比较的平均次数，就成为平均查找长度。它是用来评价一个算法好坏的一个依据。
对含有n个数据元素的查找表，查找成功时的平均查找长度为：

，其中，n是结点的个数；pi是查找第i个结点的概率；ci是找到第i个结点所需比较的次数。

2 线性表的查找

就介绍三种在线性表中进行查找的方法：顺序查找、折半查找和分块查找。

2.1 顺序查找

算法思想：又称线性查找，是一种最简单的查找方法。从第1个元素到最后1个元素，逐个进行比较，直至找到为止。
查找表的存储结构：既适用于顺序存储结构，也适用于链式存储结构。

例，对关键字序列{26，5，37，1，61，11，59，15，48，19}，希望查找关键字：37

顺序查找算法框图：

在等概率情况下，顺序查找成功的平均查找长度为：

顺序查找算法简单，但查找效率低。

2.2 折半查找(又称二分查找)

是查找一个已排好序的表的最好方法。算法思想：
将有序数列的中点设置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。即通过一次比较，将查找区间缩小一半。
二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，二分查找的先决条件是查找表中的数据元素必须有序。

算法步骤：
step1 首先确定整个查找区间的中间位置，mid = （ left + right ）/ 2；
step2 用待查关键字值与中间位置的关键字值进行比较：若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。
Step3 对确定的缩小区域再按二分公式，重复上述步骤；
最后 得到结果：要么，查找成功，要么，查找失败。
存储结构：用一维数组存放。

例，对有序表关键字序列{5，10，19，21，31，37，42，48，50，52}，查找k为19及66的记录。

算法描述：

折半查找中查到每一个记录的比较次数可通过二叉树来描述。

因此折半查找成功时进行的比较次数最多不超过树的深度。等概率时，折半查找的平均长度为：

当n很大时，ASLbin = log2(n+1)-1。

2.3 分块查找(又称索引顺序查找)

是顺序查找和折半查找的折中改进方法。

方法描述：将n个数据元素“按块有序”划分为m块（m £ n）。每一块中的结点不必有序，但块与块之间必须“按块有序”，即第1快中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。每个块中元素不一定是有序的。

算法描述：
step1 先选取各块中的最大关键字构成一个索引表；
step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找。

例

分块查找的平均查找长度为：

ASLbs = Lb + Lw

3 二叉排序树的查找

前三种查找方法各有千秋。二分法查找效率高，顺序法可以采用链表存储结构，操作灵活。但最好是既有二分法的高效率，又有链表灵活性的查找方法。二叉排序树实际上就是将数据元素组织成二叉树形式，以达到与二分法相同的查找效率，而又具有链表的插入、删除操作的灵活性。

二叉排序树查找步骤：
step1 首先建立起二叉排序树。
step2 将待查关键字值与树根结点进行比较，若相等，查找成功；
step3 否则根据比较结果确定查找路径：若小于根结点的关键字值，则与左子树的根结点的关键字值进行比较；若大于等于根结点的关键字值，则与右子树的根结点的关键字值进行比较。
step4 重复上述步骤，直到要么找到，查找成功；要么找不到，查找失败。

显然，类同折半查找，与关键字最大比较次数为树的深度。因此，二叉树的构造对二叉树的查找效率有很大的影响。

例，若按关键字序列{45，24，55，12，37，53，60，28，40，70}构造二叉树，则

若按关键字序列{12，24，28，37，40，45，53，55，60，70}构造二叉树，则

两棵二叉树的深度分别为4和10。

二叉排序树的平均查找长度为O(log2n)。

4 散列表的查找

前面讨论的查找方法中，结点在表中的位置是随机的，其位置与关键字之间不存在对应关系。因此在查找时，总是进行一系列的和关键字的比较，查找的效率与查找过程中进行比较的次数有关。散列表的查找则是一种不用比较而直接计算出记录所在地址，直接进行查找的方法。散列查找也称为哈希查找(Hashing)。

4.1 散列表的概念

散列表 由散列函数的值组成的表。散列查找是建立在散列表的基础上，它是线性表的一种重要存储方式和检索方法。在散列表中可以实现对数据元素的快速检索。
散列函数 散列表中元素是由散列函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为散列函数），计算出的值，即为该元素的存储地址。表示为：
Addr = H（key）

例：以学生的学号作为学生记录的关键字，取学号的后两位作为散列后的地址，则可以得到下列这个关键字和地址的散列表：

显然，采用的散列函数为 H(k)=k-525000。

通常关键字集合比地址集合大得多，散列函数是个压缩函数，这样就会产生不同的关键字映射到同一散列地址的情况。如：

可见，三个不同的学号关键字，散列到同一地址79上。这种现象叫冲突。为了不产生冲突现象就要求使用均匀的散列函数，即散列地址是均匀分布的。但由于关键字集合比地址集合大得多，不可能完全避免冲突，因此在冲突出现时就要有解决办法。

4.2 散列函数的构造

散列函数是一个映射，它的设置很灵活，只要使得任何关键字由此所得的散列函数值都出现在表长允许的范围内即可。建立散列函数的原则:
(1) 均匀性: H（key）的值均匀分布在散列表中；
(2) 简单性: 以提高地址计算的速度。

散列函数常用的构造方法：

数字选择法

平方取中法

折叠法

除留余数法（求模取余法）

基数转换法

随机数法

4.2.1 数字选择法

若事先知道关键字集合，当关键字的位数比散列表地址位数多时，则可选取数字分布比较均匀的若干位组成散列地址。
选取的原则：尽量避免计算出的地址有冲突。
例： 有一组由8位数字组成的关键字，如表15.2左边一列所示。

分析这6个关键字可发现，前3位是相同的，第五位也只取2、7两个值，分布不均匀。第4、6、7、8位数字则分布较为均匀，因此，可根据散列表的长度取其中几位或它们的组合作为散列地址。例如，若表长为1000（地址为0～999），则可取4、6、7位的三位数字作为散列地址；若表长为100（地址为0～99），则可取4、6与7、8位之和并舍去进位作为散列地址。
这种方法的前提是：必须能预先估计到所有关键字的每一位上各中数字的分布情况。

4.2.2 平方取中法

通过关键字的平方值扩大差别，取关键字平方后的中间几位或其组合作为散列地址。因为乘积的中间几位数和乘数的每一位都相关，故由此产生的散列地址也较均匀，所取位数由散列表的表长决定。这是一种较常用的构造散列函数的方法。通常在选定散列函数时不知道关键字的全部情况，取其中的哪几位也不一定合适，在这种情况下，取一个数平方后的中间几位数作散列地址。
例： 关键字为 （0100，0110，1010，1001，0111）
关键字的平方结果（0010000，0012100，1020100，1002001，0012321）
若表长为1000，则可取其中间三位作为散列地址集，即
（100，121，201，020，123）

4.2.3 折叠法

若关键字位数很多，可将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址。折叠法又分移位叠加和边界叠加两种。移位叠加是将各段最低位对齐，然后相加；边界叠加则是两个相邻的段沿边界来回折叠，然后对齐相加。
例如：某资料室藏书近万册。采用国际标准图书编号（ISBN），每个编号10位十进制数字。可用折叠法构造一个4位数的哈希函数。
例： 关键字 key=58242324169，取散列表长度为1000，则

4.2.4 除留余数法

取关键字被某个不大于散列表表长m的数p除后所得余数为散列地址。
H（key） = key % p
这是一种最简单，也是最常用的构造散列函数的方法。
例：关键字 32834872 ，散列表长为4位十进制数。
p值可取小于9999的数，例如，取5000；
H（key）= 32834872 % 5000 = 4872
由经验得知：通常选p为小于散列表长的最大素数。

4.2.5 基数转换法

把关键字看成是另一个进制上的数后，再把它转换成原来进制上的数，取其中的若干位作为散列地址。一般取大于原来基数的数作为转换的基数，并且两个基数要互素。

4.2.6 随机数法

选取一个随机函数，取关键字的随机函数值作为它的散列地址，即
H(key)=random(key)
其中random为随机函数。

通常，当关键字长度不等时采用此法构造散列地址较适当。
我自己家的电脑有点问题，不能算出来啦，你自己参考一下吧

4. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素线性表，若分成25块，求其平均查找长度

长度为n(900)的表分成均等的b（25）个子表，则每个子表的长度为s，b=n/s（900/25=36）。

顺序查找时成功的平均查找长度为：

（b+s)/2+1=(25+36)/2+1=44

例如：

每块最佳长度为：根号625= 25，即每块25个结点，一共分为25块，此时平均查找长度=2((25+1)/2)= 26

(4)顺序存储平均搜索长度扩展阅读：

分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。

5. 对于长度为9的顺序存储的有序表，若采用二分查找，则平均查找长度为( )除以9。

选C
首先你知道原理吧
第五个查找1次
第二个和第七个查找两次
第一，第三和第六，第八要查找三次
第四和第九要查找四次
一共25次

6. 顺序查找法平均查找长度是多少

最好的情况：目标在第一个,一次找到
·····
最坏的情况：目标在最后一个,n次找到
那么：
平均长度：
（1+2+···+n）/n
=(n(n+1)/2)/n
=(n+1)/2