中国石油大学（北京）远程教育学院 期 末 考 试 《数据结构课程设计》

同学情

中国石油大学（北京）远程教育学院
期 末 考 试
《数据结构课程设计》
学习中心：_______   姓名：________  学号：_______   
关于课程考试违规作弊的说明
1、提交文件中涉嫌抄袭内容（包括抄袭网上、书籍、报刊杂志及其他已有论文），带有明显外校标记，不符合学院要求或学生本人情况，或存在查明出处的内容或其他可疑字样者，判为抄袭，成绩为“0”。
2、两人或两人以上答题内容或用语有50%以上相同者判为雷同，成绩为“0”。
3、所提交试卷或材料没有对老师题目进行作答或提交内容与该课程要求完全不相干者，认定为“白卷”或“错卷”，成绩为“0”。

《数据结构课程设计》
1.课程设计题目
学号为单数的学生完成1.1题，学号为双数的学生完成1.2题。
1.1 任意长的整数加减法运算
设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。例如：1234，5123，4512，3451，2345与-1111，1111，1111，1111，1111的加法结果为：0123，4012，3401，2340，1234。基本要求如下：
（1）        利用链表实现长整数的存储，每个节点含一个整型变量；
（2）        整型变量的范围：-（2^15 -1）~（2^15 -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,0001,0000
（6）-9999,9999,9999；  -9999,9999,9999
（7）1,0000,9999,9999；  1
  
1.2 建立通信网络
在n个城市建设通信网络，只需架设n-1条线路即可。设计算法，求出如果以最低的经济代价建设这个通信网络。要求如下：
（1）        至少包含10个城市；
（2）        城市数n由键盘录入；
（3）        城市坐标由随机函数产生小于100的整数；
（4）        输出生成树中各条边以及它们的权值；

2.课程设计要求
（1）要求利用结构和程序设计语言C语言或C++完成上述题目。
（2）课程设计要独立思考，独立完成。课程设计报告雷同超过60%，不论什么原因，一律0分处理。
（3）算法设计及实现中，只能采用线性表、树和图结构完成，不得用数据库。
（4）最后提交的内容：源程序与课程设计报告word文档。
（5）请以远程教育学院课程设计报告模板为样本，完成设计报告。

3.课程设计报告书写规范
       
课程设计报告必须包含下面内容：
（1）需求分析
此部分叙述算法的功能、输入、输出及运行环境。
（2）概要设计
在此部分给出算法用到的主要数据结构、主要函数及其功能的介绍，各函数之间的调用关系示意图。
（3）详细设计
此部分给出主要算法的设计思想及实现。
（4）程序测试
在这部分给出程序运行结果的屏幕截图，以及测试分析。
（5）感想与体会
在这部分给出算法设计过程中的问题、程序调试过程的问题，算法存在的不足及改进思路。