长度为10的表,采用顺序查找法,平均查找长度ASL是?紧急,

长度为10的表,采用顺序查找法,平均查找长度ASL是?紧急,
长度为10的表,采用顺序查找法,平均查找长度ASL是?紧急,

长度为10的表,采用顺序查找法,平均查找长度ASL是?紧急,
如果一定可以找到的：
则10个数,每个被找到的概率是1/10;
每个元素被找到的长度分别是：1,2,3,.,10；
ASL=（1+2+3+.+10）/10=11/2.
如果有找不到的可能性,则设找的可能性是a；(a=10/总的元素数)
则11/2*a+(1-a)*10=10-9/2*a

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

全部展开

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为随机函数。
通常，当关键字长度不等时采用此法构造散列地址较适当。
我自己家的电脑有点问题，不能算出来啦，你自己参考一下吧

收起