首页学历类考试大学计算机科学
(填空题)

假定一个顺序表的长度为50,并假定查找每个元素的概率都相同,则在查找成功情况下的平均查找长度(),在查找不成功情况下的平均查找长度()

正确答案

来源:www.examk.com

答案解析

对于含有n个记录的表,查找成功时的平均查找长度为ASL = ∑P i C i 。其中n为查找表中第i个记录的概率,C i 为找到表中其关键字与给定值相等的第i个记录时,和给定值已进行过比较的关键字个数。这里n的值为1/50,所以ASL等于51/2。 对于顺序查找,不论给定值为何值,查找不成功时和给定值进行比较的关键字个数均为n+l;所以不成功时为50+1=51。

相似试题

  • (填空题)

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

    答案解析

  • (填空题)

    假定在索引查找中,查找表长度为n,每个子表的长度相等,设为s,则进行成功查找的平均查找长度为()。

    答案解析

  • (单选题)

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

    答案解析

  • (简答题)

    假定查找有序表A[25]中每一元素的概率相等,试分别求出进行顺序、二分查找每一元素时的平均查找长度。

    答案解析

  • (简答题)

    对于长度为n的线性表,若采用分块查找(假定总块数和每块长度均接近,用顺序查找确定所在块),则时间复杂性为多少?

    答案解析

  • (填空题)

    假定对长度n=50的有序表进行折半查找,则对应的判定树高度为(),最后一层的结点数为()。

    答案解析

  • (填空题)

    假定对长度n=50的有序表进行二分查找,则对应的判定树高度为(),判定树中前5层的结点数为(),最后一层的结点数为()。

    答案解析

  • (简答题)

    假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[11],若采用除留余数法构造散列函数和链接法处理冲突,试求出每一元素的散列地址,画出最后得到的散列表,求出平均查找长度。

    答案解析

  • (简答题)

    假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探查法处理冲突,试求出每一元素的散列地址,画出最后得到的散列表,求出平均查找长度。

    答案解析

快考试在线搜题