假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）。

题目

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为()

A.(n+1)/2

B.n

C.3n/4

D.n/4

正确答案：A

第2题：

对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为()。

A.(n-1)/2

B、n/2

C、(n+1)/2

D、n

参考答案：C
解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

第3题：

长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为（）。

正确答案：

n/2
【解析】在线性表的任何位置插入一个元素的概率相等，即概率为p=1/(n+1)，则插入一n+1个元素时所需移动元素的平均次数为E=i/(n+i)=n/2。

第4题：

对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率3/8，第四个元素的概率为1/4，则查找任一元素的平均查找长度为______。

A．11/8

B．7/4

C．9/4

D．11/4

正确答案：C
对顺序表查找，ASL＝，代入题目得：ASL=4*(1/8)+3*(1/4)+2*(3/8)+1*(1/4)=9/4

第5题：

设顺序存储的线性表共有287个元素，按分块查找的要求等分成7块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为(28)。

A．41

B．25

C．45

D．62

正确答案：B
解析：287个元素，按分块查找的要求等分成7块，则每块有41个元素。于是查找概率相等的情况下，查找确定块需要4次比较，块中进行顺序查找需要21次比较，所以查找成功时的平均查找长度为25。

第6题：

设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为______。

A．21

B．23

C．41

D．62

正确答案：B
解析：分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由分块有序的线性表和索引表组成。表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＝log₂(b+1)-1+(s+1)/2≈log₂(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题：

在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为().

Bn/2

C(n+1)/2

D(n-1)/2

参考答案：C

第8题：

对长度为10的顺序表进行查找,若查找前面5个元素的概率相同,均为1／8,查找后面5个元素的概率相同,均为3／40,则查找任一元素的平均查找长度为()。

A.5.5

B.5

C.39/8

D.19/4

参考答案：C

第9题：

对长度为10顺序表进行顺序查找，若查找前5个元素的概率相同，均为1/8，查找后5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为______。

A．55

B．5

C．39/8

D．19/4

正确答案：C
解析：查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的节点。
平均查找长度：为确定记录在查找表中的位置，须与给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。对含有n个记录的表，查找成功时的平均查找长度定义为：

，其中，Pi为对表中第i个记录进行查找的概率，且

。
在此，

第10题：

线性表L=(a1，a2，…，an)用数组表示，假定删除表中任何一元素的概率相同，则删除一个元素平均需要移动元素的个数为【】。

正确答案：(n-1)/2
(n-1)/2 解析：删除每一个元素需要移动的个数分别是：0，1，2，…n-1。用高斯公式即可求出：平均移动每个元素的个数=(0+n-1)*n/2/n=(n-1)/2。

假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在

题目

相似问题和答案

更多相关问题

相关内容