数据结构 答案在后面
要求：
一、独立完成，下面已将五组题目列出，请按照学院平台指定的做题组数作答，．．
每人只答一组题目，多答无效，满分100分； ．．．．．．．．．．．．
平台查看做题组数操作：学生登录学院平台→系统登录→学生登录→课程考试→离线考核→离线考核课程查看→做题组数，显示的数字为此次离线考核所应做哪一组题的标识；
例如：“做题组数”标为1，代表学生应作答“第一组”试题； 二、答题步骤：
1. 使用A4纸打印学院指定答题纸（答题纸请详见附件）；
2. 在答题纸上使用黑色水笔按题目要求手写作答；答题纸上全部信息要求手．．．．．．写，包括学号、姓名等基本信息和答题内容，请写明题型、题号； 三、提交方式：请将作答完成后的整页答题纸以图片形式依次粘贴在一个 ．．．．．．．Word．．．． 文档中上传（只粘贴部分内容的图片不给分），图片请保持正向、清晰； ．．．
1. 完成的作业应另存为保存类型是“Word97-2003”提交; ．．．．．．．．．．．．．．．．．．．．．2. 上传文件命名为“中心-学号-姓名-科目.doc”; 3. 文件容量大小：不得超过20MB。
提示：未按要求作答题目的作业及雷同作业，成绩以分记！ ．．．．．．．．．．．．．．．．．．．．0．．．
题目如下： 第一组：
一、编程题（每小题30分，共60分）
(一)
1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表 中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 (二)
1. 设计在单链表中删除值相同的多余结点的算法。 2. 设计一个求结点x在二叉树中的双亲结点算法。
二、解答题（20分）
(一)
对下面的带权无向图采用prim算法从顶点①开始构造最小生成树。（写出加入生成树顶点集合S和选择Edge的顺序）
① 9 10 ② 7 ③ 5 6 7 ④ ⑤ ⑥
11 8
S： 顶点号 ① ① ① ① ① ①
Edge： （顶点，顶点，权值） （，，） （，，） （，，） （，，） （，，） 三、画图题（20分）
(一)
已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树对应的二叉树。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 data parent
A 0 B 1 C 1 D 1 E 2 F 2 G 3 H 3 I 4 J 4 K 5 L 6 M 6 N 7 O 8
第一组答案：
一、编程题（每小题30分，共60分）
(三)
1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表 中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
答：
数据结构 第一组 答案 天津大学离线
