《算法与数据结构》课程设计任务书 (1)
- 格式：doc
- 大小：135.00 KB
- 文档页数：5
《算法与数据结构》课程设计任务书
一、课程设计任务要求
1．每人需从课程设计题目中选取一题完成。
2．自选题目需提前向指导教师提出申请，并得到许可。
3．须独立完成，可讨论但不可抄袭。
4．凡雷同的课程设计全部以零分处理，无论是谁抄袭谁。
5．源程序必须可运行，并实现题目的要求。
6．课程设计需提交源程序和课程设计报告书，并进行答辩。
二、时间及考勤要求
1．从获得题目起即可开始。
2．课程设计完成后，即可立即申请答辩。
3．课程设计的实际安排时间是17周下半周到18周上半周，在该段时间内必须完成答辩，超过该时间段未完成答辩或答辩未合格者，以不及格处理。
4．在课程设计的实际安排时间段内（即17周下半周到18周上半周），每人只有一次答辩机会，未通过者即以不及格处理。
5．在17周下半周之前申请答辩者，如未通过，可以继续申请答辩。
6．在课程设计的实际安排时间段内，未完成设计或未完成答辩者，必须在安排的机房继续工作直至答辩完成。
7．选题必须在15周周三选定，并不可更改。
三、课程设计题目及要求
1．算术表达式求值
题目描述：
由用户输入一个只包含“+”、“ ”、“*”、“/”、“(”、“)”和整数的中缀表达式，经程序计算后，输出表达式的值。
题目要求：
（1）具有友好、美观的交互界面
（2）可以反复多次进行算法表达式的输入与计算。
2．文本查找与替换工具
题目描述：
设计一个文本查找与替换工具，能在指定文本中查找指定的关键字，并能够用将指定关键字替换为其他文本。
题目要求：
（1）用户可以指定待查找文本的名称与位置。
（2）可以选择查找与替换两种功能。
（3）查找功能返回关键字在文本中出现的次数及位置
（4）替换功能将关键字更换为用户给出的其它替换文本。
（5）具有友好、美观的交互界面
3．哈夫曼编译码器
题目描述：
使用哈夫曼编码对电文进行编码，能够获得最短的码文，从而缩短信息传输时间，降低传输成本。
请设计一个哈夫曼编译码器，能够使用哈夫曼编码对文本进行编码和译码。
题目要求：
（1）文本及其中所包含的字符集、每个字符的出现次数可以人工指定或手动输入，也可以通过程序进行统计。
（2）可以选择编码与译码两种功能。
（3）能够将文本编码为由0和1构成的待传输码文。
（4）能够将0和1构成的码文译回原文。
（5）具有友好、美观的交互界面
4．迷宫问题
题目描述：
一个迷宫可以视为一个二维平面，平面中的每个位置或者是通路、或者是障碍，由一个通路可以到达相邻的通路。
请编写程序，找出从迷宫入口（左上角）到达迷宫出口（右下角）的最短路径。
题目要求：
（1）迷宫可以随机生成，也可以指定，但规模应不小于10 10。
（2）要求的是最短路径，而不是任意路径。
（3）最短路径可以用坐标形式输出，也可以用图形形式输出。
（4）具有友好、美观的交互界面
5．内部排序算法的效率比较
题目描述：
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。
试通过随机的数据比较各算法进行排序所消耗的时间，以获得对排序算法效率的直观感受。
题目要求：
（1）从以下常用的内部排序算法至少选择5种进行比较：直接插入排序、折半折入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、归并排序。
并且，快速排序、堆排序和归并排序这三种排序至少要选择2种。
（2）待排序表的表长为20000；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较。
（3）输出每组数据使用每种排序算法进行排序所消耗的时间。
6．校园导游程序
题目描述：
设计一个校园导游程序为来访的客人提供各种信息查询服务。
题目要求：
（1）设计学校的旗山校区北区校园平面图，所含场所不少于10个。
以图中顶点表示校内各场所，存放场所名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意场所相关信息的查询。
（3）为来访客人提供图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径。
（4）具有友好、美观的交互界面
7．工程项目的关键活动
题目描述：
一项工程可以由若干项活动构成，每项活动都有一个持续时间。
这些活动的执行有先后次序之分，依赖于某些事件。
对于一项活动，当它可以开始执行时，它可能可以延迟，也可能不能延迟。
所有不能延迟执行的活动，就称为关键活动。
将工程中的活动用AOE网表示，即可求出关键活动。
题目要求：
（1）由用户输入AOE网，首先是输入事件(顶点)数量，然后输入活动(边)数量，最后输入每项活动(边)及其持续时间。
每项活动用三个整数<m, n, q>表示，m表示该活动的起点事件(顶点)编号，n表示该活动的终点事件(顶点)编号，q表示该活动的持续时间。
（2）计算出并输出所有活动的最早和最晚开始时间。
（3）输出所有的关键活动。
（4）可以反复多次进行AOE的输入与关键活动的计算。
8．岛屿群交通
题目描述：
大西洋上有一个岛屿群，由许多个小岛组成，在某些小岛之间有桥梁相接。
现在有一个外来的旅行团，乘船到达了其中的某个小岛，他们想要通过桥梁到达另一个小岛。
为了不浪费时间，他们找到了被誉为“智者”的你，给了你岛屿群的交通图，请你判断他们是否能够到达目的地。
题目要求：
（1）由用户输入岛屿交通图，即岛屿数量、以及桥梁的数量，然后输入每座桥梁连通的岛屿。
每座桥梁用一对整数(m, n)表示，即该桥梁连通编号为m和n的小岛。
（2）由用户输入初始所处的小岛，以及要到达的小岛，判断由初始小岛是否能够到达目的小岛并将结果输出。
如果可以到达，请同时输出路径。
（3）可以反复多次输入不同的岛屿交通图；对于每张岛屿交通图，可以反复多次判定任意两个小岛之间是否可达。
9．岛屿群桥梁网络建设
大西洋上的另一个岛屿群的居民也想修建一些桥梁来连接小岛，但是他们吸取了前一个岛屿群居民的教训，希望修建的这些桥梁能够把所有的小岛都连接起来，不能够有任何两个小岛不能互通。
为了能够花最少的钱办这件事办成，他们找到了被誉为“智者”的你，给了你在不同小岛之间修建桥梁的造价列表，请你告诉他们修建其中的那几座桥梁可以达到目的，而且造价最少。
题目要求：
（1）由用户输入桥梁造价列表，即岛屿的数量、以及可能建造的桥梁的数量，然后输入每座可能建造的桥梁，用三个整数(m, n, q)表示，即该如果建造该桥梁，则可以连通编号为m和n的小岛，且该桥梁的造价为q。
（2）输出选择建造的桥梁，以及总的造价。
（3）可以反复多次输入不同的桥梁造价列表进行计算。
