《数据结构实习题目》由会员分享，可在线阅读，更多相关《数据结构实习题目（6页珍藏版）》请在金锄头文库上搜索。
1、一元多项式计算能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。矩阵的运算采用十字链表表示稀疏矩阵，并实现矩阵的加法运算, 要求：要检查有关运算的条件，并对错误的条件产生报警。迷宫求解输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出；宾馆订房和退房系统假设一个宾馆有n个标准的客房，每个标准客房有m个标准间，利用链表、栈或者队列等数据结构设计出具有订房和退房等功能的管理系统。建立二叉树和线索二叉树分别用以下方法建立二叉树并用图型显示出来：用先序遍历的输入序列用层次遍历的输入序列用先序和中序遍历的结果最后对所建立的二叉树
2、进行中序线索化，并对此线索树进行中序遍历(不使用栈)。学生成绩查询系统试编写程序完成学生成绩记录的查询。学生基本情况学号姓名成绩99070101李军98.599070102王颜霞8699070103孙涛5699070104单晓宏9699070105张华8399070106李小明7299070107陈小婷98若按学号进行顺序查找，例如：输入99070103，则输出 56。 按学号排序后对学号进行折半查找。 随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。马的遍历问题设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按
3、象棋的规则不重复地走过棋盘上的每一位置。要求：1)依次输出所走过的各位置的坐标。2)最好能画出棋盘的图形形式，并在其上动态地标注行走过程。教学计划编制问题大学的每个专业都要编制教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。每个课程的先修关系都是确定的，可以有任意多门，也可以没有。每一门课程恰好一个学期。试在这样的情况下设置一个教学计划编制程序。设计要求：针对计算机系本科课程，根据课程之间的依赖关系(如高级语言、离散数学应在数据结构之前开设)制定课程安排计划，并满足各学期课程数目
4、大致相同。设计一个模拟计算器的程序要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。八皇后问题设计程序完成如下要求：在88的国际象样棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。要求：1)依次输出各种成功的放置方法。2)最好能画出棋盘的图形形式，并在其上动态地演示试探过程。33的九宫问题在一个33的九宫中有18这8个数及一个空格随机地摆放在其中的格子里。如下图10.1(a)所示。现在要求实现这样的问题：将该九宫格调整为如下图10.1(b)所示的形式。调整的规则是：每次只能将与空格(上、下或左、右)相邻的一个数字平移到空格中。试编程实现这一问题的求解。23712318684
5、54765 (a)(b)图10.1图的遍历过程演示设计程序完成如下功能：对给定的图结构和起点，产生深度优先遍历和广度优先遍历序列，并给出求解过程的动态演示。运动会分数统计参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。(m=20,n=20)功能要求：1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各学校总分， 3) 可以按学校编号、学校总分、男女团体总分排序输出；4) 可以按学
6、校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数(如果做得更好可以输入学校的名称，运动项目的名称)输出形式：有中文提示，各学校分数为整型界面要求：有合理提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。构造n个城市连接的最小生成树一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小
7、生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)输入带排序序列生成二叉排序树，并调整使其变为平衡二叉树。要求能将平衡化过程动态地演示出来。递增有序设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。Josephus问题设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。二叉树叶子结点的数目编写
8、递归算法，计算二叉树中叶子结点的数目。求二叉树结点位置编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。求无向图的连通分量个数采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。求有向图路径基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(ij)。改写折半查找将折半查找的算法改写成递归算法。停车场管理系统设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门
9、外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。通讯录管理 该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现结构化程序设计的基础。该设计的任务是利用一个简单实用的菜单，通过菜单单项进行选择，实现和完成通讯录管理中常用的几个不同的功能。（1）菜单内容1、 通讯录链表的建立2、 通讯者结点的插入3、 通讯者结点的查询4、 通讯
10、者结点的删除5、 通讯录链表的输出0、 退出管理系统请选择05：（2）设计要求使用05来选择菜单项，其他输入则不起作用。（3）功能函数设计文本文件单词的检索与计数 该设计的主要目的是熟悉串类型的实现方法和文本模式匹配方法，熟悉如何利用模式匹配算法实现一般的文本处理技术。（1）设计要求与分析 要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，
11、统计输出该单词在文本的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。1、 建立文本文件建立文本文件的实现思路（1）定义一个串变量（2）定义文本文件（3）输入文件名，打开该文件（4）循环读入文本行，写入文本文件，其过程如下：While（不是文件输入结束）读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；（5）关闭文件2、给定单词的计数 该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器加1，直到整个文件扫描结束；然后输出单词的次数。3、检索单词出现在文本文件中的行号、次数及其位置4、主控菜单程序
12、的结构（1）头文件包含（2）菜单选择包括：1、 建立文件2、 单词计数3、 单词定位4、 退出程序 （3）选择14执行相应的操作，其他字符为非法。哈夫曼编码的应用 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。本设计要求是对输入的一串电文字实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。其中用到哈夫曼树和哈夫曼编码的概念，还包括字符串以及文件的读写等概念。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分
13、支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为喝个叶子对应的自负的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程为解码。电报通信是传送文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi,编码长度为Li，电文中有n种字符，则电文编码总长为WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，WiLi恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一颗哈夫曼树，
14、此构造过程称为哈夫曼编码。根据设计要求和分析，要实现本设计，必须实现以下几个方面的功能：（1）哈夫曼树的建立（2）哈夫曼编码的生成（3）编码文件的译码订票系统设计航班信息，订票信息的存储结构，设计程序完成如下功能：录入：可以录入航班情况(数据可以存储在一个数据文件中，数据结构、具体数据自定)查询：可以查询某个航线的情况(如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓)；可以输入起飞抵达城市，查询飞机航班情况；订票：(订票情况可以存在一个数据文件中，结构自己设定)可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件航班信息的查询与检索 该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。 对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。每个航班记录包括八项，分别是：航班号、起点
