答案制作人： 翟宏宇 答案审核人：.pdf

1 一、单项选择题（每小题一、单项选择题（每小题 2 2 分，共分，共 1010 分）分） 1．C 2．B 3. C 4. D 5．B 二、填空题（每空二、填空题（每空 2 2 分，共分，共 1010 分）分） 1． O(1) 2． head(head(tail(head(tail(Ls))))) 3． 14 4． 6 5． 12 三三、、简答题简答题（（第第 1 1 题题 1515 分，其余分，其余每题每题 10 分，共分，共 45 分分）） 1. （15 分） （1） 对应的二叉树为： ………………………………………..（4 分） （2） 对应的后序线索树为： ……………………（9 分，画错或漏画一处扣 1 分） 二二〇〇〇〇七七 ————二二〇〇〇〇 八八 学年学年 第第 2 2 学期学期 参考答案及评分标准参考答案及评分标准 课程名称：课程名称： 数据结构数据结构 参考班级：参考班级： 0609251 命题教师：命题教师： 翟宏宇翟宏宇 答案答案[A[A 或或 B]B]：： B B 答案制作人：答案制作人： 翟宏宇翟宏宇 答案审核人：答案审核人： 2 （3） 这棵二叉树转换成对应的森林为： ……………………………………（每个 1 分，共 2 分） 2． （10 分） 第一步： 第二步： 第三步： 二二〇〇〇〇 七七 ————二二〇〇〇〇 八八 学年学年 第第 2 2 学期学期 参考答案及评分标准参考答案及评分标准 3 第四步： 第五步： 第六步： ……..………… （每错一步扣 2 分， 错五步不得分） 3． （10 分） 计算字符集 A，B，C，D 出现的次数分别为 9，1，5，3。

………..…………（2 分） 令它们为权值构造哈夫曼树为： （注： 0/1 分支可以颠倒，对应编码 0/1 也可颠倒） 其哈夫曼编码如下： A：1 B：000 C：01 D：001 ………………………... （编码每个 1 分，树结构 4 分） 二二〇〇〇〇 七七 ————二二〇〇〇〇 八八 学年学年 第第 2 2 学期学期 参考答案及评分标准参考答案及评分标准 4 4． （10 分）利用 Floyd 算法求出任意两顶点的最短路径： ……………………………………………..（除第一个外，每个矩阵 2 分，注：矩阵名可不为 A） 二二〇〇〇〇 七七 ————二二〇〇〇〇 八八 学年学年 第第 2 2 学期学期 参考答案及评分标准参考答案及评分标准 5 四四、、算法题： （共算法题： （共 15 分分） 参考算法： invert(Linklist q=p->next; while(q) { r=q->next; q->next=p; p=q; q=r; }//while L->next=NULL; L=p; } 二二〇〇〇〇 七七 ————二二〇〇〇〇 八八 学年学年 第第 2 2 学期学期 参考答案及评分标准参考答案及评分标准 6 一、单项选择题（每小题一、单项选择题（每小题 分，共分，共 分）分） （五号黑体字） 1． 2． 3. 4. 5． （内容为五号宋体字，单倍行距） 二、多项选择题二、多项选择题 （错选、多选不得分。

每小题（错选、多选不得分每小题 分，共分，共 分）分） 1． 2． 3． 4． 5． （内容为五号宋体字，单倍行距） 三、判断题（每小题三、判断题（每小题 分，共分，共 分）分） 1．×× 2．√√ （内容为五号宋体字，单倍行距） 四、填空题（每空四、填空题（每空 分，共分，共 分）分） 1． 2． （内容为五号宋体字，单倍行距） 五、简答题（每小题五、简答题（每小题 分，共分，共 分）分） 1. （内容为五号宋体字，单倍行距） 六、六、计算题计算题（每小题（每小题 分，共分，共 分）分） 1． （内容为五号宋体字，单倍行距） 七、论述题（每小题七、论述题（每小题 分，共分，共 分）分） 1． （内容为五号宋体字，单倍行距） 二二〇〇〇〇 ————二二〇〇〇〇 学年学年 第第 学期学期 参考答案及评分标准参考答案及评分标准 7 一、单项选择题（每小题一、单项选择题（每小题 分，共分，共 分）分） （五号黑体字） 1． 2． 3. 4. 5． （内容为五号宋体字，单倍行距） 二、多项选择题二、多项选择题 （错选、多选不得分。

每小题（错选、多选不得分每小题 分，共分，共 分）分） 1． 2． 3． 4． 5． （内容为五号宋体字，单倍行距） 三、判断题（每小题三、判断题（每小题 分，共分，共 分）分） 1．×× 2．√√ （内容为五号宋体字，单倍行距） 四、填空题（每空四、填空题（每空 分，共分，共 分）分） 1． 2． （内容为五号宋体字，单倍行距） 五、简答题（每小题五、简答题（每小题 分，共分，共 分）分） 1. （内容为五号宋体字，单倍行距） 六、六、计算题计算题（每小题（每小题 分，共分，共 分）分） 1． （内容为五号宋体字，单倍行距） 七、论述题（每小题七、论述题（每小题 分，共分，共 分）分） 1． （内容为五号宋体字，单倍行距） 二二〇〇〇〇 ————二二〇〇〇〇 学年学年 第第 学期学期 参考答案及评分标准参考答案及评分标准 。