1、中国石油大学（北京）远程教育学院 期 末 考 试 数据结构课程设计数据结构课程设计 学习中心：学习中心：_ 姓名：姓名：_ 学号：学号：_ 关于课程考试违规作弊的说明关于课程考试违规作弊的说明 1、提交文件中涉嫌抄袭内容（包括抄袭网上、书籍、报刊杂志及其他已有论文） ，带有明显外校标记，不符合学院要求或学生本人情况，或存在查明出处的内 容或其他可疑字样者，判为抄袭，成绩为“0”。 2、两人或两人以上答题内容或用语有 50%以上相同者判为雷同，成绩为“0”。 3、所提交试卷或材料没有对老师题目进行作答或提交内容与该课程要求完全不 相干者，认定为“白卷”或“错卷”，成绩为“0”。 数据结构课程设计
2、数据结构课程设计 一一.课程设计题目课程设计题目 选题说明：选题说明： 学号尾号为学号尾号为 0、1、2 的学生完成第的学生完成第 1 题题 学号尾号为学号尾号为 3、4、5 的学生完成第的学生完成第 2 题题 学号尾号为学号尾号为 6、7 的学生完成第的学生完成第 3 题题 学号尾号为学号尾号为 8、9 的学生完成第的学生完成第 4 题题 1. 任意长的整数加减法运算任意长的整数加减法运算 设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。例如： 1234，5123，4512，3451，2345 与-1111，1111，1111，1111，1111 的加法结果为： 0123，401
3、2，3401，2340，1234。基本要求如下： （1）利用链表实现长整数的存储，每个节点含一个整型变量； （2）整型变量的范围：-（215 -1）（215 -1）； （3）输入与输出形式每四位一组，组间用逗号分隔开。如： 1986,8213,1935,2736,3299； （4）界面友好，每步给出适当的操作提示，并且系统具有一定的容错能力。 至少给出下面的测试数据： （1）0； 0 （2）-2345,6789； -7654,3211 （3）-9999,9999； 1,0000,0000,0000 （4）1,0001,0001； -1,0001,0001 （5）1,0001,0001； -1,
4、0001,0000 （6）-9999,9999,9999； -9999,9999,9999 （7）1,0000,9999,9999； 1 2. 建立通信网络建立通信网络 在 n 个城市建设通信网络，只需架设 n-1 条线路即可。设计算法，求出如果以最低的 经济代价建设这个通信网络。要求如下： （1）至少包含 10 个城市； （2）城市数 n 由键盘录入； （3）城市坐标由随机函数产生小于 100 的整数； （4）输出生成树中各条边以及它们的权值； 3. 实现两个链表的合并实现两个链表的合并 基本功能要求： （1）建立两个链表 A 和 B，链表元素个数分别为 m 和 n 个。 （2）假设元素分别
5、为(x1,x2,xm)，和(y1,y2, yn)。把它们合并成一个线性表 C，使得： 当 m=n 时，C=x1,y1,x2,y2,xn,yn,xm 当 nm 时，C=y1,x1,y2,x2,ym,xm,yn 输出线性表 C （3）用直接插入排序法对 C 进行升序排序，生成链表 D，并输出链表 D。 测试数据： （1） A 表（30，41，15，12，56，80） B 表（23，56，78，23，12，33，79，90，55） （2） A 表（30，41，15，12，56，80，23，12，34） B 表（23，56，78，23，12） 4. 二叉树的建立与遍历二叉树的建立与遍历 问题描述 建立
6、一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 基本要求 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并 采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 测试数据 ABCDEGF（其中 表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 二二. .课程设计要求课程设计要求 （1）要求利用结构和程序设计语言 C 语言或 C+完成上述题目。 （2）课程设计要独立思考，独立完成。课程设计报告雷同超过 60%，不论什么原因， 一律 0 分处理。 （3）算法设计及实现中，只能采用线性表、树
7、和图结构完成，不得用数据库。 （4）最后提交的内容：源程序与课程设计报告）最后提交的内容：源程序与课程设计报告 word 文档。提交文档。提交 word 文文 档，将源程序粘贴在课程设计报告最后面，不能提交压缩包文档。档，将源程序粘贴在课程设计报告最后面，不能提交压缩包文档。 （5）请以远程教育学院课程设计报告模板为样本，完成设计报告。 三三. .课程设计报告书写规范课程设计报告书写规范 课程设计报告必须包含下面内容： （1）需求分析 此部分叙述算法的功能、输入、输出及运行环境。 （2）概要设计 在此部分给出算法用到的主要数据结构、主要函数及其功能的介绍，各函数之间的调 用关系示意图。 （3）详细设计 此部分给出主要算法的设计思想及实现。 （4）程序测试 在这部分给出程序运行结果的屏幕截图，以及测试分析。 （5）感想与体会 在这部分给出算法设计过程中的问题、程序调试过程的问题，算法存在的不足及改进 思路。
