数据结构课程设计2011-2012-2题目一：池塘夜降彩色雨【问题描述】：设计一个程序，演示美丽的“池塘夜雨”景色；色彩缤纷的雨点飘飘洒洒地从天而降，滴滴入水有声，溅起圈圈微澜。【基本要求】：（1）雨点的空中出现位置、降落过程的可见程度、入水位置、颜色、最大水圈等，都是随机确定的；（2）多个雨点按照各自的随机参数和存在状态，同时演示在屏幕上。（3）增加“电闪雷鸣”景象。（4）增加风的效果，展现“风雨飘摇”的情景题目二：哈夫曼编码器【问题描述】：利用哈夫曼树实现编码并译码的系统。【基本要求】：从终端读入一段字符集，系统自动统计出字符的个数n以及各个字符出现的次数w作为权值，建立哈夫曼树，并将哈夫曼树以凹入表示法的形式显示在屏幕上。利用已建好的哈夫曼树对字符进行编码，并将该段文字的编码存人一个文件code中，然后输出这段编码。 题目三：算术表达式求值演示【问题描述】：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示中缀表达式变为后缀表达式并对后缀表达式求值的过程。【基本要求】：以字符序列的方式从终端输入语法正确的、不含变量的整数表达式。利用中缀表达式变为后缀表达式算法和后缀表达式的求值算法实现对算术四则混合运算表达式的求值，并演示出在求值中运算符栈、操作数栈、输入字符和主要操作的变化过程。 题目四：农夫过河问题【问题描述】：从前，一个农夫带着一只狼，一只羊和一棵白菜过河（注意该狼已经被农夫驯服了，但还是会吃羊）。他要将所有东西安全的带到河的对岸。不幸的是河边只有一条小船，只能装下农夫和他的一样东西，并且农夫必须每次都随船过河，因为只有他能撑船。在无人看管的情况下，狼要吃羊，羊要吃白菜，因此农夫不能在河的某边岸上单独留下狼和羊，也不能单独留下羊和白菜。那么农夫如何才能使三样东西平安过河呢？【基本要求】：1、输出农夫过河问题求解的详细步骤。2、分别采用深度优先搜索算法和广度优先搜索算法实现。题目五：运动会分数统计【问题描述】：参加运动会的n个学校编号为1n。比赛分成m个男子项目和w个女子项目，项目编号内分别为1m和m+1m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。【基本要求】：产生各学校的成绩单，内容包括各校所取得的各项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。题目六：校园导游咨询【问题描述】：设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】：（1）设计你的学校的校园平面图，所含景点不少于十个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访的客人提供图中任意景点相关信息的查询。（3）求出校园平面图的最小生成树。题目七：最小生成树问题【问题描述】：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。【基本要求】：（1）利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。（2）利用堆排序实现选择权值最小的边。（3）输出生成树中各条边以及他们的权值。题目八：迷宫问题【问题描述】：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】：1、编写一个求解迷宫的非递归程序，求得迷宫中所有可能的通路。2、以方阵形式输出迷宫及其通路。题目九：图遍历的演示【问题描述】：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。【基本要求】：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。题目十：内部排序算法比较【问题描述】：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。【基本要求】：(1)对以下六种常用的内部排序算法进行比较：希尔排序、直接选择排序、快速排序、直接插入排序、堆排序、冒泡排序、。（2）待排序表的表长和数据可以由用户自己确定，也可以由随机数产生程序自动产生；至少要用五组不同的输入数据作比较；比较的指标为关键字的比较次数和关键字的移动次数（关键字的交换计为三次移动）。（3）最后要对结果作出简单分析。题目十一：表达式二叉树类型的实现【问题描述】：一个表达式和一棵二叉树之间，存在着自然的对应关系。一个算术表达式可以用一棵表达式二叉树来表现，对表达式二叉树分别进行前序、中序和后序遍历就得到相应的前缀、中缀和后缀表达式。编写一个程序，实现基于二叉树表示的算术表达式Expression的操作。【基本要求】：假设算术表达式 Expression内可以含有变量（az）、常量（09）和二元运算符（+、-、*、/、(乘幂)）。实现以下操作：（1） 以字符序列的形式输入语法正确的前缀表达式并构造表达式二叉树。（2） 用带括号的中缀表达式和不带括号的后缀表达式输出表达式Expression。（3） 实现对变量V的赋值并且对算术表达式Expression求值。题目十二：航空客运订票系统【问题描述】：航空客运订票的业务活动包括：查询航线、客票预定和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。【基本要求】：（1）每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期几）、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等侯替补的客户名单（包括姓名、所需票量）；（2）全部数据可以只放在内存中。（3）系统能实现的操作和功能如下： 查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额。 承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补； 承办退票业务：根据客户提供的情况（日期、航班），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。题目十三：集合的并、交和差运算【问题描述】：编制一个能演示集合的并、交和差运算的程序。【基本要求】：（1）集合的元素限定为小写字母字符a,z。（2）演示程序以用户和计算机的对话方式执行。【测试数据】：（1）Set1=“magazine”,set2=”paper”,Set1set2=”aegimnprz”,Set1set2=”ae”Set1-set2=”gimnz”题目十四：哈希表设计【问题描述】：已知一个含有100个纪录的表，关键字为中国人姓氏的拼音，给出此表的哈希表设计方案。【基本要求】：1、哈希函数H（Key）为关键字的第一个字母在字母表中的序号，解决哈希冲突的方法采用链表法。 2、实现哈希表的插入、查找、建立和删除等算法。 3、编写一个测试主函数，按第一个字母的顺序输出哈希表中所有的关键字。【选作内容】：1、哈希函数H（Key）为关键字的第一个字母在字母表中的序号，解决哈希冲突的方法采用线性探测开放定址法。2、编写一个测试主函数。题目十五：图书管理系统【问题描述】：设计一个计算机管理系统，完成图书管理的基本业务。【基本要求】：1、每种书的登记内容包括书号、书名、著作者和库存量。 2、对书号建立索引表（线性表）以提高查找效率。 3、要求系统具有如下功能： 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加。借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变库存量。归还：注销对借阅者的登记，改变该书的库存量。 题目十六：地铁计费系统【问题描述】：已知某市地铁一号线经过的站点序列为迈皋桥，红山动物园，南京站，新模范马路，玄武门，鼓楼，珠江路，新街口，张府园，三山街，中华门，安德门，小行，中胜，元通，奥体中心，计费规则为17站2元；811站3元，1215站4元。设计一个地铁计费程序，计算某人从A站到B站的车费，并输出经过的站点及站点数以及车费情况。【基本要求】：（1）要求分别采用顺序存储结构和链式存储结构实现上述算法，如何存储数据效率会更高。（2）将上述站点绘制成图（可以只选择其中10个点），实现该图的深度优先搜索和广度优先搜索遍历，并输出站点序列。题目十七：电话簿查询系统【问题描述】：设计一个完成电话簿的查询功能的管理系统。要求实现一种具有较高查找效率的电话簿，支持增加联系人和删除联系人，各数据元素按指定树型关系分类排列显示，并将该树型关系保存在指定文件中。【基本要求】：1、每个联系人的登记内容包括姓名、手机号，家庭电话、办公室电话和Email地址。 2、分别采用线性表和基于索引的块链存储结构来存储电话簿，对姓名建立索引表以提高查找效率。3、例如，一种树型关系如下：全部： 同学 中学同学 大学同学 研究生同学 同事 计算机系 电力系题目十八： 马踏棋盘【问题描述】：设计一个国际象棋的马踏遍棋盘的演示程序。【基本要求】：将马随机放在国际象棋的8*8棋盘Board88的某个方格中，马按照走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，3，64依次填入一个8*8的方阵，输出之。测试数据可以自行指定一个马的初始位置（i,j）,0i,j7。【选作内容】：1、求出从某一起点出发的多条以致全部行走路线。2、演示寻找行走路线的回溯过程。题目十九：八皇后问题【问题描述】：设计一个求解八皇后问题的演示程序。八皇后问题如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上。八皇后问题布局图之一如下图所示： QQQQQQQQ【基本要求】：编写实现八皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。