课程设计题目

《课程设计题目》由会员分享，可在线阅读，更多相关《课程设计题目（5页珍藏版）》请在装配图网上搜索。

1、一、哈夫曼编/译码器1. 问题描述利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间， 降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码；在接收端 将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道）， 每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/ 译码系统。2. 基本要求系统应具有以下功能：（1）C:编码（Coding）。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码（Decoding）。利用已建好的哈夫曼树将文件code

2、file中的代 码进行译码，结果存入 textfile 中。（3）P：打印代码文件（Print）。将文件codefile以紧凑格式显示在终端上， 每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。（4）T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的 方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 treeprint 中。二、农夫过河问题1. 问题描述一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西 全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫 才能撑船。如果农夫在场，则狼不

3、能吃羊，羊不能吃白菜；否则狼会吃羊，羊会 吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而 狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。三、电话号码查询系统1. 问题描述设计哈希表实现电话号码查找系统。2. 基本要求（1）每个记录有下列数据项：电话号码、用户名、地址。（2）从键盘输入各记录，分别以电话号码和用户名为关键字设计哈希表； 采用不同的哈希函数，比较冲突率。（3）采用适当的方法解决冲突；在哈希函数确定的前提下，尝试不同类型 处理冲突的方法，考察平均查找长度的变化。（4）查找并显示给定电话号码的记录。（5）查找并显示给定用户名的记录。四、单机文件系统搜索引擎

4、1. 问题描述用户在使用计算机的过程中，经常会出现找不到自己所需要的文件的现象， 而 Internet 上广泛应用的搜索引擎采用基于全文关键字的检索方式，其命中率远 高于操作系统提供的对文件名中关键字进行检索的方法。本实验的目的在于设计 并实现一个针对本地文件系统，基于关键字的文件搜索引擎。2. 基本要求（1）输入：用户想要检索的文件中出现的关键字。（2）输出：包含用户输入的关键字的文件名称以及所在位置。（3）需要准备如干格式统一的文本文件，内容随意，作为搜索的目标文件 库。要求文件数量大于 1000 个。目标文件库中可随机划分若干子目录，将目标 文件分布其中。（4）筛除停用词，建立汉语词库。

5、（5）采用深度优先或者广度优先的方式对整个目标文件库所在目录进行遍 历，建立所有目标文件的关键词索引表。（6）为每一个词语建立文档级索引表。五、兑奖算法1. 问题描述设兑奖方式为：从1到22选出5个不重复的数字a0,a1,a2,a3,a4,而主办方开 出5个号码P。、P2、P3、P4，外加一个特别号P5，得奖方式如下： 头等奖：5 个号码完全相同，即a0,a1,a2,a3,a4= P0，P1，P2，P3，P4。二等奖：a0,a1,a2,a3,a4中有4个号码出现在 P0，P1，P2，P3，P4，另一个号 码等于P5。三得奖：a0,a1,a2,a3,a4中有4个号码出现在 P。，P1，P2，P3

6、，P4，另一个号 码不等于 P5。四等奖：a0,a1,a2,a3,a4中有 3 个号码出现在 P。，P1，P2，P3，P4。五等奖：a0,a1,a2,a3,a4中有 2 个号码出现在 P。，P1，P2，P3，P4。 问题是：根据投注情况，求出中奖的注。2. 基本要求（1）设计投注的数据结构。（2）设计投注方式：键盘输入或从文件输入等（3）设计求解中奖注的算法。（4）输出中奖注。（5）分析算法的时间复杂度。3. 实现提示投的注具有相同数据结构、相同数据个数，可采用数组存放投注号码。判断 该注是否中奖，中几等奖，就是判定该号码符合哪个中奖条件。最直接的算法就 是把投注号与奖号逐个进行比较。其他算法

7、可据此改进，如有序比较等。六、任务调度1. 问题描述多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个 任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按 一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时 间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的 执行顺序。（1）忽略任务提交的时间差，即认为各任务同时提交。（2）各任务不同时提交。2. 设计要求（1）基本要求：a）为任务列表设计数据结构和存储结构。b）任务输入，至少包括任务编号及所需 CPU 的服务时间，任务数不 得少于 5 个。c）如果按提交顺序执行，求出每个任务

8、的开始执行时间、终止时间、 等待时间和所有任务的平均等待时间。d）按平均等待时间最短，设计任务调度算法，输出任务的执行序列； 求出每个任务的开始执行时间、终止时间、等待时间和所有任务 的平均等待时间。并把结果与c）对比。（2）较高要求： 最短作业优先，存在“长任务饥饿”的问题，即如果动态地不断加入 作业，只要提交作业所需的 CPU 服务时间比较短，则先提交的长任务 将一直得不到服务，如何解决该问题？七、设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。设计要求：要检查有关运算的条件，并对错误的条件产生报警。八、常用内部排序算法的分析和

9、比较1. 问题描述 分析直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排 序、归并排序、基数排序等内部排序算法的思想，通过交换次数和比较次数 来对这些算法进行比较。2. 设计要求（1）通过给定的记录数目及排序思想，设计相应的存储结构。（2）程序中包含测试数据分为部分有序、部分逆序、完全随机三种情况，通过三种测试数据对每一个排序算法进行验证（3）分别设计一个统计交换次数和比较次数的函数来进行计数。（4）分析每种排序算法在三种测试数据下的数据规模、排序时间、交换次数、 比较次数、辅助空间。（5）根据上述分析，从待排序的记录数目 n 、记录的大小（规模） 、关键字的 结构及其初始状态、对稳定性的要求、存储结构、时间和辅助空间复杂度 等角度出发来讨论每种排序算法适用的环境。九、排序算法演示系统的设计与实现1. 问题描述设计一个图形化界面的演示系统，能实现常用内部排序算法的动态演示。2. 设计要求（1） 有图形化界面。（2） 测试数据的生成包括部分有序、部分逆序、完全随机三种情况。（3）能实现演示过程（排序过程）的显示和存储。（4）能实现对比结果的显示和存储。