文章

103

粉丝

0

获赞

0

访问

3.7k

头像
2013年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年6月26日 18:23
阅读数 33

(1)概率最高的是 "do" 和 "while" (0.35),其次是 "for" 和 "repeat" (0.15)。
因此,一种可能的排列方式是:
{ "do", "while", "for", "repeat" }

{ "while", "do", "for", "repeat" }
或将 "for" 和 "repeat" 互换位置。
只要保证高概率元素在前,低概率元素在后即可。

应该使用顺序查找(或称线性查找)。

ASL=(0.35×1)+(0.35×2)+(0.15×3)+(0.15×4)
ASL=0.35+0.70+0.45+0.60
ASL=2.10

(2)

  • 元素应如何排列?
    与顺序存储结构类似,为了实现更短的平均查找长度,链式结构中的元素也应该按照它们的查找概率降序排列。将查找概率高的元素放在链表的前面,这样在顺序遍历链表时,能更快地找到高概率的元素。
    所以,排列方式依然是:
    { "do", "while", "for", "repeat" } (或其他等效的降序排列)

  • 应使用何种查找方法?
    链式存储结构通常不支持高效的随机访问(如折半查找),因此最常用的查找方法是顺序查找。

  • 查找成功时的平均查找长度是多少?
    对于链式存储结构,顺序查找的平均查找长度计算方式与顺序存储的顺序查找完全相同,因为它也是从链表头开始逐个比较。

  • ASL=(0.35×1)+(0.35×2)+(0.15×3)+(0.15×4)
    ASL=0.35+0.70+0.45+0.60
    ASL=2.10


评分及理由

(1)得分及理由(满分5分)

得分:5分

理由:学生正确理解了...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发