数据结构
在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。
题目
在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。
相似问题和答案
第1题：
下列关于搜索引擎的叙述中，正确的是( )。
A、 搜索引擎是在Internet上执行信息搜索的专用工具
B、 利用搜索引擎可方便用户有Internet上检索信息，但对信息检索效率的提高并不大
C、 利用搜索引擎搜索到的匹配条目一般以链接的形式显示在搜索结果网页中
D、 搜索引擎一般提供分类目录和关键字检索这两种搜索方式
第2题：
A、结构优化
B、页面优化
C、内容优化
D、网站外部链接优化
第3题：
●采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 (36) 。
(36) A．n
B．n／2
C．(n-1)／2
D．(n+1)／2
【解析】n个位置共需要搜索1+2+…+n次，即n*(n+1)/2.平均长度为(n+1)/2。
第4题：
设有序顺序表为{10，20，30，4，50，60，70)，采用折半搜索时，搜索成功的平均搜索长度是【 】。
2009-7-17 解析：ASLsucc=(1×1+2×2+3×4)/7= 17/7
第5题：
采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为(36)。
A．n
B．n/2
C．(n-1)/2
D．(n+1)/2
解析：n个位置共需要搜索1+2+…+n次，即n*(n+1)/2。平均长度为(n+1)/2。
第6题：
设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为______。
A．21
B．23
C．41
D．62
解析：分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由分块有序的线性表和索引表组成。表R[1,...,n]均分为b块，前 b-1块中结点个数为s=[n/b]，第b块的结点数允许小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。抽取各块中的最大关键字及其起始位置构成一个索引表ID[1,...,b)，即ID[i](1≤ i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。分块查找的基本思想是：索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。由于块内无序，只能用顺序查找。分块查找是2次查找过程。整个查找过程的平均查找长度是2次查找的平均查找长度之和。如果以二分查找来确定块，则分块查找成功时的平均查找长度为ASL1＝log2(b+1)-1+(s+1)/2≈log2(n/s+1)+s/2；如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)。在本题中，n=123,b=3,s=41,因此平均查找长度为(41×41+2×41+123)/(2×41)＝23。
第7题：
对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8；搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为(57)。
A．5.5
B．5
C．39/8
D．19/4
解析：搜索到表中任一元素的平均搜索长度为：(1/8)*1+(1/8)*2+(1/8)*3+(1/8)*4+(1/8)*5+[(1/8)*5+(3/40)*1]++[(1/8)*4+(3/40)*2)*[(1/8)*3+(3/40)*3]+[(1/8)*2+(3/40)*4]+[(1/8)*2+(3/40)*5]＝(1/8)*(1+2+3+4+5)*2+(3/40)*(1+2+3+4+5)=15/8*2+45/40＝30/8+9/8＝39/8。
第8题：
第9题：
对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为______。
A．n/2
B．(n+1)/2
C．(n-1)/2
D．n/4
解析：由于链表不能随机访问，要访问某个节点，必须从它的直接前驱的指针域出发才能找到。因此，链式存储的线性表，即使是有序表，也只能使用顺序查找。顺序查找时，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。
假设在每个位置查找概率相等，即P1=P2=…=Pn=1/n，若是从表头向表尾方向查找，则每个位置上查找比较次数为C1＝1，C2＝2，…，Cn＝n。于是，查找成功的平均查找长度为[*]
第10题：
（ ）的工作原理是接受用户查询请求后，同时在多个搜索引擎上搜索并将结果返回给用户。
A.目录索引 B.元搜索引擎 C.全文搜索引擎 D.门户搜索引擎