2022年个题目“数据结构”课程设计方案指导书 .docx
《2022年个题目“数据结构”课程设计方案指导书 .docx》由会员分享,可在线阅读,更多相关《2022年个题目“数据结构”课程设计方案指导书 .docx(11页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精品_精品资料_选题一:迷宫与栈问题【问题描述】以一个 mXn 的长方阵表示迷宫, 0 和 1 分别表示迷宫中的通路和障碍.设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.【任务要求】1) 第一实现一个以链表作储备结构的栈类型,然后编写一个求解迷宫的非递归程序.求得的通路以三元组(i, j,d)的形式输出.其中:(i, j)指示迷宫中的一个坐标, d 表示走到下一坐标的方向.如,对于以下数据的迷宫,输出一条通路为:(1, 1, 1),( 1, 2, 2),( 2, 2, 2),( 3 ,2, 3),( 3, 1, 2),.2) 编写递归形式的算法,求得迷宫中全
2、部可能的通路.3) 以方阵形式输出迷宫及其通路.【测试数据】迷宫的测试数据如下:左上角(0, 1)为入口,右下角( 8, 9)为出口.0123456789010111111111100100010121001000101310000110014101110000151000100001610100010017101110110181100000000出口91111111111出口入口入口01234567890123456789【成果评定】1. 完成“任务要求”第1 项成果评定为“及格”-“中”.2. 完成“任务要求”第2 项和第 3 项成果评定为“良”或以上.选题二:算术表达式与二叉树【问题描
3、述】一个表达式和一棵二叉树之间,存在着自然的对应关系.写一个程序,实现基于二叉树表示的算术表达式的操作.【任务要求】假设算术表达式Expression 内可以含有变量(a z)、常量( 0 9)和二元运算符(+, -,* , / , 乘幂).实现以下操作:1) ReadExpreE以字符序列的形式输入语法正确的前缀表达式并构造表达式E.2) WriteExpreE用带括弧的中缀表达式输出表达式E.3) AssignV,c实现对变量 V 的赋值( V=c),变量的初值为0.4) ValueE对算术表达式 E 求值.可编辑资料 - - - 欢迎下载精品_精品资料_5) CompoundExpr (
4、 P,E1, E2) -构造一个新的复合表达式(E1) P( E2)【测试数据】1分别输入 0 .a. -91. +a*bc . +*5x2*8x . +*3x3*2x2x6并输出.2每当输入一个表达式后,对其中的变量赋值,然后对表达式求值.【成果评定】1. 完成“任务要求”第1 项和第 2 项成果评定为“及格”-“中”.2. 完成“任务要求”第3 项至第 5 项成果评定为“良”及以上.选题三:银行业务模拟与离散大事模拟【问题描述】假设某银行有4 个窗口对外接待客户,从早晨银行开门(开门9: 00am ,关门5:00pm )起不断有客户进入银行.由于每个窗口在某个时刻只能接待一个客户,因此在客
5、户人数众多时需要在每个窗口前顺次排队,对于刚进入银行的客户(建议:客户进入时间使用随机函数产生),假如某个窗口的业务员正闲暇,就可上前办理业务.反之,如4 个窗口均有窗户所占,他便会排在人数最少的队伍后面.【任务要求】1) 编制一个程序以模拟银行的这种业务活动并运算一天中客户在银行逗留的平均时间.2) 建议有如下设置:a) 客户到达时间随机产生,一天客户的人数设定为100 人.b) 银行业务员处理时间随机产生,平均处理时间10 分钟.3) 将一天的数据(包括业务员和客户)以文件方式输出.【测试数据】由随机数产生器生成【成果评定】1) 能按教材要求完成“任务要求”第1 项成果评定为“及格”-“中
6、”.2) 完成“任务要求”第2 项至第 3 项成果评定为“良”及以上.选题四:文学讨论助手与模式匹配算法KMP【问题描述】文学讨论人员需要统计某篇英文小说中某些形容词的显现次数和位置.试写一个实现这一目标的文字统计系统【任务要求】1) 英文小说存于一个文本文件中.待统计的词聚集合要一次输入完毕,即统计工作必需在程序的一次运行之后就全部完成.程序的输出结果是每个词的显现次数和显现位置所在的行的行号,格式自行设计.待统计的“单词”在文本串中不跨行显现,它或者从行首开头,或者前置以一个空格符.2) 模式匹配要基于 KMP 算法.3) 推广到更一般的模式集匹配问题,并设待查模式串可以跨行(提示:定义操
7、作GetAChar).【测试数据】可编辑资料 - - - 欢迎下载精品_精品资料_1) 文本文件为 testword.c2) 待统计的词集: if 、else、for 、while 、return 、void、int 、char、typedef 、struct【成果评定】1) 完成“任务要求”第1 项成果评定为“及格”-“中”.2) 完成“任务要求”第2 项至第 3 项成果评定为“良”及以上.选题五:北理珠校内导游询问与最短路径【问题描述】1) 从北京理工高校珠海学院的平面图中选取有代表性景点(10-15 个),抽象成一个无向带权图.以图中顶点表示景点,边上的权值表示两的之间距离.2) 本程序
8、的目的是为用户供应路径询问.依据用户指定的始点和终点输出相应路径, 或者依据用户指定的景点输出景点的信息.【任务要求】1) 从北京理工高校珠海学院的平面图中选取有代表性景点(10-15 个),抽象成一个无向带权图.以图中顶点表示校内各景点,存放景点名称、代号、简介等信息.以边表示路径,存放路径长度等信息.2) 为来访客人供应图中任意景点相关信息的查询.3) 为来访客人供应图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简洁路径.4) 区分汽车线路与步行线路.【测试数据】北理珠校内导游图(距离可估量).【成果评定】1) 完成“任务要求”第3 项成果评定为“及格”.2) 完成“任务要求”
9、第1-3 项成果评定为“中”以上.3) 完成“任务要求”第1-4 项成果评定为“良”以上.选题六: B- 树与 B+ 树及其操作【问题描述】学习并讨论 B-树与 B+树,并编写演示它们操作的程序.【任务要求】1) B-树构建、查找、插入和删除操作程序.2) B+树构建、查找、插入和删除操作程序.【测试数据】【成果评定】1) 完成“任务要求”第1 项成果评定为“及格”-“中”.2) 完成“任务要求”第1-2 项成果评定为“良”以上.选题七:哈夫曼 Huffman编/ 译码器【问题描述】可编辑资料 - - - 欢迎下载精品_精品资料_利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,
10、降低传输成本.但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原).对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编 / 译码系统.试为这样的信息收发站写一个哈夫曼码的编 / 译码系统.【任务要求】一个完整的系统应具有以下功能:1) I:初始化( Initialization ).从终端读入字符集大小n,以及 n 个字符和 n 个权值, 建立哈夫曼树,并将它存于文件hfmTree 中.2) E:编码( Encoding).利用以建好的哈夫曼树(如不在内存,就从文件hfmTree 中读入),对文件 ToBeTran中的正文进行编码,然后将结
11、果存入文件CodeFile 中.3) D:译码( Decoding ).利用已建好的哈夫曼树将文件CodeFile 中的代码进行译码,结果存入文件TextFile 中.4) P:印代码文件( Print ).将文件 CodeFile 以紧凑格式显示在终端上,每行50 个代码.同时将此字符形式的编码文件写入文件CodePrin 中.5) T:印哈夫曼树( Tree Printing ).将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中.【测试数据】1) 利用教科书例6-2(严蔚敏数据结构 P148)中的数据调试程序.2)
12、用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“ THIS PROGRAM IS MY FAVORITE”.字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161【成果评定】1) 完成“任务要求”第1 项成果评定为“及格”-“中”.2) 完成“任务要求”第1-2 项成果评定为“良”以上.选题八:内部排序算法比较【问题描述】在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶, 或大致执行时间.试通过随机数据比较各种算法的关键
13、字比较次数和关键字移动次数,以取得直观感受.【任务要求】1) 对以下 7 种常用的内部排序算法进行比较:冒泡排序、直接插入排序、简洁挑选排序、希尔排序、堆排序、归并排序、快速排序.2) 待排序表的表长不小于100.其中的数据要用伪随机数程序产生.至少要用5 组不同的输入数据作比较.比较的指标为有关键字参与的比较次数和关键字的移动次数(关键字交换计为3 次移动).3) 最终要对结果作出简洁分析,包括对各组数据得出结果波动大小的说明.【测试数据】由随机数产生器生成可编辑资料 - - - 欢迎下载精品_精品资料_【成果评定】1) 完成“任务要求”4 个排序算法及比较评定为“及格”-“中”.2) 完成
14、“任务要求”全部排序算法及比较成果评定为“良”以上.选题九:简洁行编辑程序【问题描述】文本编辑器程序是利用运算机进行文字加工的基本软件工具,实现对文本文件的插入、删除等修改操作.限制这些操作以行为单位进行的编辑程序称为行编辑程序.被编辑的文本文件可能很大,全部读入编辑程序的数据空间(内存)的作法既不经济,也不总能实现.一种解决方法是逐段的编辑.任何时刻只把待编辑文件的一段放在内存,利为活区.试依据这种方法实现一个简洁的行编辑程序.设文件每行不超过320 个字符,很少超过80 个字符.【任务要求】实现以下 4 条基本编辑命令:1) 行插入:格式: i将插入活区中第 行之后.2) 行删除.格式:
15、d删除活区中第 到第 行.例如“ d10”和“ d10 14”3) 活区切换.格式:n将活区写入输出文件,并从输入文件中读入下一段,作为新的活区.4) 活区显示.模式:p逐页的(每页 20 行)显示活区内容,每显示一页之后请用户打算是连续显示以后各页(假如存在).印出的每一行要前置行号和一个空格符,行号固定 占 4 位,增量为 1.各条命令中的行号均须在活区中各行行号范畴之内,只有插入命令的行号可以等于活区第一行行号减 1,表示插入当前屏幕中第一行之前,否就命令参数非法.【测试数据】自行设定,留意测试将活区删空等特别情形.【成果评定】1) 完成“插入”与“删除”功能评定为“及格”.2) 完成全
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年个题目“数据结构”课程设计方案指导书 2022 题目 数据结构 课程设计 方案 指导书
限制150内