《个题目“数据结构”课程设计方案指导书 .docx》由会员分享，可在线阅读，更多相关《个题目“数据结构”课程设计方案指导书 .docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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) 完成全
16、部功能评定为“良”以上。选题十：一元多项式运算【问题描述】1. 能够依据指数降序排列建立并输出多项式。2. 能够完成两个多项式的相加、相减，并将结果输入。【任务要求】1. 储备结构。2. 多项式相加的基本过程的算法（可以使用程序流程图）3. 可以提出算法的改进方法。【测试数据】可编辑资料 - - - 欢迎下载精品名师归纳总结自行设定，留意测试将活区删空等特别情形。【成果评定】3) 完成“相加”与“相减”功能评定为“及格”或“中等”。4) 对算法有所改进和优化评定为“良好”。选题十一：集合的交、并、差运算【问题描述】编制一个能演示执行集合的交、并和差运算的程序。【任务要求】1) 集合元素用小写英
17、文字母，执行各种操作应以对话方式执行。2) 算法要点：利用单链表表示集合。懂得好三种运算的含【测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成交、并和差功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题十二：动态查找表【问题描述】利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。【任务要求】算法输入：指定一组数据。算法输出：显示二叉排序树的中序遍历结果、查找胜利与否的信息、插入和删除后的中序遍历结果 排序结果 。算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。【测试数据】自行设定，留意测试将活区删
18、空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题十三：同学成果治理【问题描述】本例对同学的成果治理做一个简洁的模拟，用菜单挑选方式完成以下功能：登记同学成果。查询同学成果。插入同学成果。删除同学成果。【任务要求】算法输入：操作要求，同学信息算法输出：操作结果算法要点：把问题看成是对线性表的操作。将同学成果组织成次序表，就登记同学成果即是建立次序表操作。查询同学成果、插入同学成果、删除同学成果即是在次序表中进行查可编辑资料 - - - 欢迎下载精品名师归纳总结找、插入和删除操作。【测试数据】自行设定，留意测试将活区删空等特别
19、情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题十四：马踏棋盘【问题描述】将马随机放在国际象棋的8*8 棋盘 Bord8 8的某个方格中，马按走棋规章进行移动。要求每个方格上只进入一次，走遍棋盘上全部64 个方格。【任务要求】编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1， 2， ， 64 依次填入一个 8* 8 的方阵，输出之。测试数据：由读者指定, 可自行指定一个马的初始位置。实现提示：每次在多个可走位置中挑选一个进行摸索，其余未曾摸索过的可走位置必需用适当结构妥当治理，以备摸索失败时的“回溯” 悔棋 使用。【
20、测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题十五： joseph环【问题描述】编号是 1 ， 2， ,n的 n个人依据顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开头任选一个正整数作为报数上限值m,从第一个仍开头顺时针方向自1 开头次序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向的下一个人开头重新从1 报数，如此下去，直到全部人全部出列为止。设计一个程序来求出出列次序。【任务要求】利用单向循环链表储备结构模拟此过程，依据出列的次序输出各
21、个人的编号。测试数据：m 的初值为 20， n=7 ,7 个人的密码依次为3， 1， 7， 2， 4，7， 4，第一m=6,就正确的输出是什么？要求： 输入数据：建立输入处理输入数据，输入m 的初值， n，输入每个人的密码，建立单循环 链表。输出形式：建立一个输出函数，将正确的输出序列可编辑资料 - - - 欢迎下载精品名师归纳总结【测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题十六： 最小生成树【问题描述】在 n 个城市之间建设网络，只需保证连通即可，求最经济的架设方法。对于图，其生
22、成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（Minimun Spanning Tree ），简称为 MST。有两种特别典型的算法： Prim 算法和 kruskal 算法。【任务要求】设计程序完成如下功能：对给定的网和起点，用出全部的最小生成树。储备结构可自行挑选。PRIM 算法和 kruskal 算法的基本思想求解【测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成其中一个算法相应功能评定为“及格”或“中等”。2) 完成两个算法并对算法有所改进和优化评定为“良好”。选题十七：通讯录治理【问题描述】该设计采纳菜单作为应用
23、程序的主要界面，用掌握语句来转变程序执行的次序，掌握语句是实现结构化程序设计的基础。该设计的任务是利用一个简洁有用的菜单，通过菜单单项进行挑选，实现和完成通讯录治理中常用的几个不同的功能。【任务要求】（ 1） 菜单内容1、 通讯录链表的建立2、 通讯者结点的插入3、 通讯者结点的查询4、 通讯者结点的删除5、 通讯录链表的输出0、 退出治理系统请挑选 05：（ 2） 设计要求使用 05 来挑选菜单项，其他输入就不起作用。（ 3） 功能函数设计可编辑资料 - - - 欢迎下载精品名师归纳总结5 个不同功能的算法实现编程题，目的是练习利用链表结构来解决实际应用问题的才能，进一步懂得和熟识线形表的链
24、式储备结构。【测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题十八：运动会分数统计【问题描述】参与运动会有 n 个学校，学校编号为1n。竞赛分成m 个男子工程，和w 个女子工程。工程编号为男子1m，女子 m+1 m+w。不同的工程取前五名或前三名积分。取前五名 的积分分别为： 7、5 、3 、2、1，前三名的积分分别为：5、 3、2 。哪些取前五名或前三名由同学自己设定。（ m=20,n=20）【任务要求】功 能 要 求 ： 1. 可 以 输 入 各 个 工 程 的 前 三 名 或 前
25、五 名 的 成 绩 。2) 能统计各学校总分，3) 可 以 按 学 校 编 号 、 学 校 总 分 、 男 女 团 体 总 分 排 序 输 出 。4.可以按学校编号查询学校某个工程的情形。可以按工程编号查询取得前三或前五名的学校。动规定：输入数据形式和范畴：工程20 以内的整数（假如做得更好可以输入学校的名称，运的名称）输 出 形 式： 有 中 文 提 示 ， 各 学 校 分 数 为 整 形界面要求：有合理的提示，每个功能可以设立菜单，依据提示，可以完成相关的功能要求。储备结构：同学自己依据系统功能要求自己设计，但是要求运动会的相关数据要储备在数据文件中。（数据文件的数据读写方法等相关内容在c
26、 语言程序设计的书上，请自学解 决 ） 请 在 最 后 的 上 交 资 料 中 指 明 你 用 到 的 存 储 结 构 。 测试数据：要求使用1、全部合法数据。 2、整体非法数据。 3、局部非法数据。进行程序测试，以保证程序的稳固。测试数据及测试结果请在上交的资料中写明。【测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题十九：航班信息的查询与检索【问题描述】该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞可编辑资料 - - - 欢迎下载精品名师归纳总结时间以
27、及到达时间等信息进行查询。【任务要求】对于本设计，可采纳基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采纳最简洁的次序查找方法进行，因此他们用得较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表（8 条记录）航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京
28、2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航班号一项的格式为：K0K1K2K3K4K5CZ3869其中 K0 和 K1 的输入值是航空公司的别称，用两个大写字母标示，后4 位为航班号， 这种航班号关键字可分成两段，即字母和数字。其余七项输入内容由于不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。【测试数据】自行设定，留意测试将
29、活区删空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题二十：哈希表应用【问题描述】利用哈希表进行储备。【任务要求】任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。设计目的：实现哈希表的综合操作简体中文掌握台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。显示元素：显示已经创建的哈希表。查找元素：查找哈希表中的元素，分为查找胜利和查找不胜利。插入元素：在哈希表中，插入一个元素，分为插入
30、胜利和失败。删除元素：在已有的数据中，删除一个元素。退出系统：退出程序。可编辑资料 - - - 欢迎下载精品名师归纳总结【测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化评定为“良好”。选题二十一：拓扑排序【问题描述】拓扑排序可判定AOV 网络中是否存在回路，使的全部活动可排成一个线性序列，使用每个活动的全部前驱活动都排在该活动的前面。关键路径的工期打算了整个工程的工期。任何关键路径上的终端元素的推迟将直接影响工程的预期完成时间（例如在关键路径上没有浮动时间）。【任务要求】构建 AOV 网络，并输出其拓扑序列结果，输出该图的关键路径和关键活动，储备结构自行挑选。【测试数据】自行设定，留意测试将活区删空等特别情形。【成果评定】1) 基本完成相应功能评定为“及格”或“中等”。2) 对算法有所改进和优化，输出全部拓扑排序和全部关键路径评定为“良好”。可编辑资料 - - - 欢迎下载