评分及理由

（1）得分及理由（满分5分）

学生答案中，对于顺序存储结构，正确指出了按访问频率（即查找概率）排序，并给出了排列顺序["do", "while", "for", "repeat"]，这实际上是将概率最高的两个元素（p1=0.35, p4=0.35）放在最前面，符合降序排列的原则。查找方法选择了顺序查找，并正确计算了平均查找长度ASL=0.35×1+0.35×2+0.15×3+0.15×4=2.1。答案与标准答案完全一致。因此得5分。

（2）得分及理由（满分5分）

学生答案中，对于链式存储结构，提出了两种方案：哈希表或二叉排序树（平衡二叉树）。标准答案给出了两种可能：顺序查找单链表（ASL=2.1）或二叉排序树（ASL=2.0）。学生提到的哈希表在本题查找概率不均的情况下，若设计得当可能获得O(1)的查找性能，但题目未给出哈希函数设计等具体信息，此方案不够具体。学生主要计算了二叉排序树（平衡二叉树）的平均查找长度，并给出了两种计算过程：

• 0.35×2 + 0.15×1 + 0.15×2 + 0.35×3 = 2.2（此计算有误，结果应为2.2，但学生未明确此树结构）
• 0.35×2 + 0.15×1 + 0.35×2 + 0.15×3 = 2.0（此计算正确，对应一种可能的二叉排序树）

学生正确指出了链式存储可采用二叉排序树（平衡二叉树）的查找方法，并给出了一个正确的ASL=2.0的计算（尽管另一个计算有误）。根据标准答案的答案二，此部分可得3分（二叉排序树方法1分，ASL计算正确2分）。但学生未明确元素排列方式（二叉排序树本身隐含了元素按关键字有序排列），且哈希表方案不够具体，因此扣1分。本小题得4分。

题目总分：5+4=9分