2009级软件工程数据结构与算法课程综合训练题目

《2009级软件工程数据结构与算法课程综合训练题目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2009级软件工程专业数据结构与算法课程综合训练第一部分：实验题目实验一.大整数计算器问题描述：在很多高级程序设计语言中，整数值都是有取值范围的。然而在某些情况下，我们需要处理很大的整数，它无法在计算机硬件能直接表示的整数范围内进行处理，如果用浮点数來表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数就必须用软件的方法来实现大整数的算术运算。输入：稈序的输入是通过键盘完成的。输出：结果输出在屏幕上要求：1、必须用图形界面的方式来完成，界面类似于windows自带的计算器2、除了有支持windows自带计算器的输入模式外，还需要能够支持表达式输

2、入模式（支持的运算符有+、一、花/和括号）3、大整数应该没有位数限制实验二.文件压缩、解压缩问题描述：根据Huffman算法编写一个对文件进行压缩和解压缩的程序。该程序可以对所有的文件类型进行压缩，压缩Z后的文件后缀名为huffo同时，该程序可以对所有后缀名为huff的压缩文件进行解压缩。为了保存原来的文件名信息，使用该程序压缩之后的文件名应为'原来的文件名（包括后缀名）+.huff'o例如：对文件名为MyFile.exe进行压缩，则得到的压缩Z后的文件名为MyFile.exe.huff；相应的，对MyFile.exe.huff进行解压缩之后得到的文件名应该是MyFile.ex

3、e。该程序在压缩时，以字节为单位。由于一个字节最多可以表示256个不同的数据，所以可以根据字节所表示的数据值来表示Huffman算法的符号源，则最多有256个符号源。根据Huffman算法，对每个符号源根据其出现的频率进行可变长编码。该程序支持下面的操作：■压缩：Huffman-encodef订ename■解压缩：Huffman-decodefilename下面给出压缩文件的格式。♦符号源的个数（1个字节）♦符号源的值和其相应的huffman编码的长度（每个符号源2个字节）♦符号源的huffman编码串（按照上而的符号源的顺序，二进制格式）♦存储源文件的长度所需的字节个数（1个

4、字节）♦源文件的长度（以字节为单位）（字节的个数等于“存储源文件的长度所需字节个数”中的字节中的数据值）♦压缩后的数据（二进制格式）对上面提到的格式进行简单的说明。【采用16进制编辑器，如ultraedit,以二进制的格式打开源文件】源文件的内容为：4865606C6F09576F72606421在这个文件中，对各个符号进行统计、编码，可以得到下表中的数据：符号源的数据值（16进制）岀现频率Huffman编码根据上面的相应数据，可以得到对该文件进行Iluffnum压缩后，各个字段的数据值（字节间用I表示）符号源的个数：9符号源的值和其相应的huffman编码的长度：09

5、4

6、2

7、1

8、4

9、48

10、4

11、57

12、4

13、64

14、4

15、65

16、4

17、6C

18、2

19、6F

20、2

21、72

22、3符号源的huffman编码串：1110111111100110110110011111000010x表示源文件的长度（以字节为单位）的字节个数：1源文件的长度：12压缩后的数据：11000111

23、10100011

24、10110100

25、01010011

26、01111xxx【注意】当二进制串的个数不是8（字节的位数）的整数倍时，需要用0进行填充，上面的x表示的就是填充的数据位。按照压缩文件的格式，最终的压缩文件应该是：（用16进制表示）090904210448045704640465046C026F027203

27、EECD6784010007A3B45378【特别注意】压缩文件的格式是二进制，不要表示成二进制字符串，也不要表示成16进制的字符串。【另外】在实验报告中要给出文件的大小和压缩、解压缩的时间关系。同时以表格和曲线图的形式提供实验数据。尽可能的提高程序的性能，减少压缩/解压缩的时间，增加能够处理的文件的大小。第二部分实验报告—封面内容：标题：数据结构与算法课程综合训练组名：XXXX成员：（包括学号、姓名和班级）实验报告提交日期：年/月/日联系电话：XXXX二实验报告内容：（一）正文内容：1.实验名称：（即题目名称）2.实验内容：解决问题领域所用到的数据类型信息和数据结构；重点算法

28、描述以及算法的时间性能分析；程序运行结果（原始运行结果）；（二）实验总结：要求写出本实验开设的意义、重要性和必要性；通过这次实验，你有哪些收获?对这次实验题目有什么意见和建议？（三）致谢词；（四）参考文献；三实验报告提交形式：实验报告要求认真撰写并提交实验报告打印版和电子版；四试验报告提交时间：下学期开学后通知第三部分实验形式自由组合，每组人数控制在2--3人二要求完成每个实验题目，希望组内之间互相讨论三每组只需提交一份实验报告第四部分成绩评定-成绩=验收+报告验收：以小组形式，进行现场验收