当前位置:文档之家› 数据结构课程设计

数据结构课程设计

1.一元稀疏多项式计算器[问题描述]设计一个一元稀疏多项式简单计算器。

[基本要求]输入并建立多项式;输出多项式,输出形式为整数序列:n, c1, e1, c2, e2,……, cn, en ,其中n是多项式的项数,ci, ei分别是第i项的系数和指数,序列按指数降序排序;多项式a和b相加,建立多项式a+b;多项式a和b相减,建立多项式a-b;[测试数据](2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3)(1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1)(x+x3)+(-x-x3)=0(x+x2+x3)+0=(x3+x2+x)[实现提示]用带头结点的单链表存储多项式,多项式的项数存放在头结点中。

2.背包问题的求解[问题描述]假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wn=T,要求找出所有满足上述条件的解。

例如:当T=10,各件物品的体积为{1,8,4,3,5,2}时,可找到下列4组解:(1,4,3,2)、(1,4,5)、(8,2)、(3,5,2)[实现提示]可利用回溯法的设计思想来解决背包问题。

首先,将物品排成一列,然后顺序选取物品转入背包,假设已选取了前i件物品之后背包还没有装满,则继续选取第i+1件物品,若该件物品“太大”不能装入,则弃之而继续选取下一件,直至背包装满为止。

但如果在剩余的物品中找不到合适的物品以填满背包,则说明“刚刚”装入背包的那件物品“不合适”,应将它取出“弃之一边”,继续再从“它之后”的物品中选取,如此重复,直至求得满足条件的解,或者无解。

由于回溯求解的规则是“后进先出”因此自然要用到栈。

3.完全二叉树判断用一个二叉链表存储的二叉树,判断其是否是完全二叉树。

4.最小生成树求解(1人)任意创建一个图,利用克鲁斯卡尔算法,求出该图的最小生成树。

5.最小生成树求解(1人)任意创建一个图,利用普里姆算法,求出该图的最小生成树。

6.树状显示二叉树编写函数displaytree(二叉树的根指针,数据值宽度,屏幕的宽度)输出树的直观示意图。

输出的二叉树是垂直打印的,同层的节点在同一行上。

[问题描述]假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用(层号,须打印的空格数)来界定。

第0层:根在(0,32)处输出;第1层:因为根节点缩进了32个空格,所以下一层的偏移量(offset)为32/2=16=screenwidth/22。

即第一层的两个节点的位置为(1,32-offset),(1,32+offset)即(1,16),(1,48)。

第二层:第二层的偏移量offset为screenwidth/23。

第二层的四个节点的位置分别是(2,16-offset),(2,16+offset),(2,48-offset),(2,48+offset)即(2,8),(2,24),(2,40),(2,56)。

……第i层:第i层的偏移量offset为screenwidth/2i+1。

第i层的每个节点的位置是访问第i-1层其双亲节点时确定的。

假设其双亲的位置为(i-1,parentpos)。

若其第i层的节点是其左孩子,那末左孩子的位置是(i,parentpos-offset),右孩子的位置是(i,parentpos+offset)。

[实现提示]利用二叉树的层次遍历算法实现。

利用两个队列Q,QI。

队列Q中存放节点信息,队列QI中存相应于队列Q中的节点的位置信息,包括层号和需要打印节点值时需要打印的空格数。

当节点被加入到Q时,相应的打印信息被存到QI中。

二叉树本身采用二叉链表存储。

7.综合排序[问题描述]利用随机函数产生N个随机整数(2000以上),对这些数进行多种方法进行排序。

[基本要求]①分别采用插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。

②统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。

8.哈夫曼编码/译码器[问题描述]要传输一些数据(比如英文单词),设计一个利用哈夫曼算法的编码系统,为这些单词编码。

并在接收端进行译码。

[基本要求]①将需要传输的数据存放在数据文件data.txt 中。

②读入数据文件并为其编码,将编码后的内容存入文件code.txt中。

③读入code.txt,译码。

并将译码后的内容输出在屏幕上。

9.停车场管理[问题描述]设停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在南端,最先到达的第一辆车停放在停车场的最北端),若停车场内已停了n辆汽车,则后来的汽车只能在门外的通道上等候,一旦有车开走,收排在通道上的第一辆车即可开入;当停车场内每辆车要离开时,在它之后进入的车辆必须先退出停车场为其让路,待该辆车开出大门,其他车辆再按原次序进入停车场,每辆停放在停车场的车在它离开停车场时必须按它停留在停车场内的时间长短交纳停车费。

试为停车场编写按上述要求进行管理的模拟程序。

[基本要求]①要求以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理;②要求处理的数据元素包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻;③该系统完成以下功能:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费);④要求栈以顺序结构实现,队列以链表实现。

[测试数据]设n=2,输入数据为:(‘A’,1,5),(‘A’,2,10),(‘D’,1,15),(‘A’,3,20),(‘A’,4,25),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。

其中‘A’表示到达,‘D’表示离开,‘E’表示输入结束。

10.约瑟夫环[问题描述]约瑟夫问题的一种描述是:编号为1,2,…,n 的n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。

一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数,报到m 时停止报数。

报m 的人出列,将他的密码作为新的m 值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。

试设计一个程序,求出出列顺序。

[基本要求]利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。

[测试数据]m 的初值为20;n =7,7个人的密码依次是:3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5。

11.纸牌游戏[问题描述]编号为1-52张牌,正面向上,从第2张开始,以2为基数,是2的倍数的牌翻一次,直到最后一张牌;然后,从第3张开始,以3为基数,是3的倍数的牌翻一次,直到最后一张牌;然后…从第4张开始,以4为基数,是4的倍数的牌翻一次,直到最后一张牌;...再依次5的倍数的牌翻一次,6的,7的直到以52为基数的翻过,输出:这时正面向上的牌有哪些?12.猴子吃桃子问题(1人)[问题描述]有一群猴子摘了一堆桃子,他们每天都吃当前桃子的一半且再多吃一个,到了第10天就只余下一个桃子。

用多种方法实现求出原来这群猴子共摘了多少个桃子。

[基本要求]1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解13.字符串的操作(1人)[基本要求](1)字符串采用数组存储,建立两个字符串String1和String2。

输出两个字符串。

(2)将字符串String2的头n个字符添加到String1的尾部。

输出结果。

(3)查找串String3在串String1中的位置,若String3在String1中不存在,则插入String3在String1中的m位置上。

输出结果。

测试数据:(1)String1: “typedefstructArcBox”String2: “VertexTypedata”String3: “data”n:6,m:7(2)String1: “structArcBox”String2: “VertexType”String3: “Box”n:3,m:314.宿舍管理查询软件[基本要求]为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求:A.采用交互工作方式B.建立数据文件,数据文件按关键字(姓名、学号、房号)进行排序(冒泡、选择、插入排序等任选一种)查询菜单: (用二分查找实现以下操作)按姓名查询、按学号查询、按房号查询15.敢死队问题[问题描述]有M个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。

如果前一个战士没完成任务,则要再派一个战士上去。

现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5时,对应的战士就去执行任务,且此战士不再参加下一轮计数。

如果此战士没完成任务,再从下一个战士开始数数,被数到第5时,此战士接着去执行任务。

以此类推,直到任务完成为止。

排长是不愿意去的,假设排长为1号,请你设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

[基本要求]至少采用两种不同的数据结构的方法实现.16.数制转换问题[基本要求]任意给定一个M进制的数x ,请实现如下要求1)求出此数x的10进制值(用MD表示)2)实现对x向任意的一个非M进制的数的转换。

至少用两种或两种以上的方法实现上述要求(用栈解决,用数组解决,其它方法解决)。

17.教学计划安排检验程序(拓扑排序)[问题描述]针对学院的计算机系本科课程,根据课程之间的依赖关系,制定课程安排计划,并满足各学期课程数大致相同。

按照用户输入的课程数,学期数,课程间的先后关系数目以及课程间两两间的先后关系,程序执行后会给出每学期应学的课程。

[基本要求](1) 输入的形式和输入值的范围:输入间用空格隔开。

要求用户输入的课程数小于20,学期数小于或是等于8,课程名的长度小于等于10个字符。

(2) 程序所能达到的功能:按照用户的输入,给出每学期应学的课程。

(4) 测试数据:输入:学期数:5,课程数:12,课程间的先后关系数:16,课程的代表值:v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。

课程间两两间的先后关系:v1 v2,v1 v3, v1 v4,v1v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11 v6输出:第1学期应学的课程:v1 v9第2学期应学的课程:v2 v4 v10 v11第3学期应学的课程:v3 v6 v12第4学期应学的课程:v5 v8第5学期应学的课程:v718. 迷宫问题[问题描述]以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。

相关主题