评分及理由

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

学生答案中给出的排列顺序是 {"for", "repeat", "do", "while"}，对应的概率分别是 0.15、0.15、0.35、0.35。按照查找概率降序排列应该是 {"do", "while", "for", "repeat"} 或 {"while", "do", "for", "repeat"} 等，但学生给出的排列顺序并不是按概率降序排列，而是将概率较小的元素放在前面。然而，学生明确指出了使用顺序查找方法，这是正确的。计算平均查找长度时，学生没有给出具体计算过程和结果，但根据排列顺序，实际平均查找长度应为 0.15×1 + 0.15×2 + 0.35×3 + 0.35×4 = 3.1，这比题目给出的折半查找的 2.2 还要差，因此排列顺序错误。但考虑到学生正确指出了顺序查找方法，且标准答案中允许按实际元素表示降序排列，但学生排列明显不符合降序，因此扣分。得分为 1 分（仅给方法分）。

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

学生答案中提出使用二叉排序树，并给出了具体的节点关系：根节点为 "for"（概率 0.15），左子节点为 "do"（概率 0.35），右子节点为 "repeat"（概率 0.15），"repeat" 的右子节点为 "while"（概率 0.35）。这种构建方式不是最优的二叉排序树，因为最优二叉搜索树应该将高概率节点放在靠近根的位置。学生计算的平均查找长度为 0.15×1 + 2×(0.35+0.15) + 3×0.35 = 0.15 + 1 + 1.05 = 2.2，但根据其节点关系，实际查找长度应为："for" 查找长度 1（概率 0.15），"do" 查找长度 2（概率 0.35），"repeat" 查找长度 2（概率 0.15），"while" 查找长度 3（概率 0.35），所以平均查找长度 = 0.15×1 + 0.35×2 + 0.15×2 + 0.35×3 = 2.2。虽然计算过程有误（2×(0.35+0.15) 不正确），但最终结果 2.2 正确。根据标准答案，二叉排序树方法可以接受，且计算正确给分。得分为 4 分（构建树结构不最优扣 1 分，但计算正确）。

题目总分：1+4=5分