2017年数据结构课程设计题目及报告范例

18. 重言式判别

【问题描述】

一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。

【基本要求】

(1) 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括 \，\和 \，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。逻辑变元 为大写字母。表达式中任何地方都可以含有多个空格符。

(2) 若是重言式或矛盾式，可以只显示\，或\，否则显示 \以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。

【测试数据】 (1) (A|~A)&(B|~B) (2) (A&~A)&C (3) A|B|C|D|E|~A (4) A&B&C&~B (5) (A|B)&(A|~B)

(6) A&~B|~A&B;O ,0;0,1;1,0;1,1 。

19. 哈夫曼编/译码器

【问题描述】

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成 本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编 /译码系统。试为这样的信息收发站写一个哈夫

21

曼码的编/译码系统。

【基本要求】

一个完整的系统应具有以下功能：

(1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

(3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。

(4)P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。

(5)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

【测试数据】

(1)利用教科书例 6-2 中的数据调试程序。

(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树 , 并实现以下报文的编码和译码：\VORITE\。 字符 A B C D E F G H I J K 5 Y L M 频度 186 64 13 22 32 103 21 15 47 57 1 字符 N 频度 57

【选作内容】

O P Q R S T U V W X 32 20 Z 63 15 1 48 51 80 23 8 18 1 16 1 (1)上述文件CodeFile中的每个\或\实际上占用了一个字节的空间，只起到示意或模拟的作用。为最大限度地利用编码存储能力，试改写你的系统，将编码结果以二进制形式存放在文件CodeFile中。

(2)修改你的系统，实现对你的系统的原程序的编码和译码(主要是将行尾符

22

编/译码问题)。

(3)实现各个转换操作的源/目文件，均由用户在选择此操作时指定。

20. 图遍历的演示

【问题描述】

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。

【基本要求】

以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

【测试数据】

任选国内城市，起点为合肥，暂时忽略里程。 【实现提示】

设图的结点20-30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，?，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

【选作内容】

(1)借助于栈类型(自己定义和实现)，用非递归算法实现深度优先遍历。 (2)以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。

21. 教学计划编制问题

【问题描述】

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这

23

样的前提下设计一个教学计划编制程序。

【基本要求】

(1)输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

(2)允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

(3)若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。

【测试数据】

学期总数：65；学分上限：103；该专业共开设12门课，课程号从CO1到C12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见教科书图7.26。

22. 校园导游咨询

【问题描述】

设计一个校园导游程序，为来访的客人提供各种信息查询服务。 【基本要求】

(1) 设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。

(2)为来访客人提供图中任意景点相关信息的查询。

(3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。 【测试数据】

以合肥学院南艳湖校区为例。 【实现提示】

一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向网。顶点和边均 含有相关信息。 【选作内容】

24