数据结构实训题目()_数据结构实习题目

数据结构实训题目()由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实习题目”。

注意：第5题和第7题有改动，第6题加了一句提示

一、停车场管理

仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

[问题描述]

设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

[测试数据]

设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。

[基本要求]

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。

[实现提示]

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

[选作内容]

（1）两个栈共享空间，思考应开辟数组的空间是多少？

（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。

（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。

（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

二、员工管理系统

综合运用线性表、查找、排序的相关知识，解决一个实际应用问题。通过本次实习，要求熟练掌握线性表的存储结构，能在对应的存储结构上进行各种操作，并能分析不同的查找和排序方法的时空性能。[问题描述]

每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。

[基本要求]

（1）排序：按不同关键字，对所有员工的信息进行排序。（2）查询：按特定条件查找员工。

（3）更新：按编号对某个员工的某项信息进行修改。（4）插入：加入新员工的信息。

（5）删除：按编号删除已离职的员工的信息。

[选作内容]

实现图形用户界面。

三、校园导游程序

[问题描述]

用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介

等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。

[基本要求]

（1）查询各景点的相关信息；

（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。（4）增加、删除、更新有关景点和道路的信息。

[选作内容]

（1）求多个景点的最佳（最短）游览路径。（2）区分机动车道和人行道。（3）实现导游图的仿真界面。

四、编写一个杂货店排队模拟程序。

该模拟程序中包含多个队列，可以使用队列数组来模拟这些队列。假设杂货店共5条收银线，顾客可随机进入支付。顾客会进入最短的队伍，如果队伍一样长，那么选择最靠近的一个队伍。每次交易完成所消耗的时间也是随机的。

完成一些额外工作，扩展杂货店排队程序，使得客户可以：

 如果所有队伍都一样长，可以选择不排队。

 如果等待超过了某个时间，可以离开队伍。 在给定的时间间隔内，检查另一个队伍是否更短。 如果另一个队伍更短，则切换队伍。

五、猜动物

猜动物：假设你是一个动物，程序问问题试图猜出你是哪种动物。如果程序的猜测正确，就开始另一轮游戏。如果程序不能断定你是哪种动物，你就提供一些信息给程序以使下次再玩游戏时，程序会聪明一点儿。

举例：假设你现在是一只浣熊（raccoon）。游戏开始 ***** 猜动物游戏 *****

程序： 请在心里想好一种动物,让我来猜一猜

你是哺乳动物吗？'

用户：y

程序：你比猫大吗？ 用户：y

程序：我猜是袋鼠，我猜的对吗 用户：Y

程序：我猜对了！程序：继续玩吗？ 用户：Y

（再完一次）

程序：你是哺乳动物吗？'用户：Y

程序：你比猫大吗？ 用户：Y

程序：我猜是袋鼠，我猜的对吗 用户：N

程序：我认输了,你是什么？ 用户：浣熊

程序：请键入一个问题,便得通过此问题可以将袋鼠和浣熊区分开.用户：你有大口袋吗？

程序：对于浣熊你有大口袋吗？(Y/N)用户：N

程序：噢,我明白了 程序：退出游戏吗?„„

这样你就给程序提供了一个以后可以区分袋鼠和浣熊的问题。

程序使用的数据存储在一棵二叉树中，每个非叶子结点包含一个问题。当程序开始后，它只知道4种动物。

根结点的问题是“是哺乳动物吗？”。如果是，左子树的问题是“比猫大吗？”，如果是，答案是袋鼠，否则，答案是老鼠 否则，不是哺乳动物，问“生活在水中吗？”如果是，答案是鳟鱼，否则，答案是知更鸟

如果叶子结点包含正确的动物，一切都好。如果猜的不对，程序将从用户那里引出信息，并用这些信息改进二叉树。

主要功能函数：

（1）建立初始状态的二叉树（2）猜策过程

（3）学习过程，若猜测失败，扩展叶结点

六、硬币游戏

在游戏开始之前，在桌上将三个硬币放置成一条直线。游戏开始的时候，中间一个硬币是背面朝上，其他两个硬币是正面朝上。游戏目标是改变硬币的摆放形式，让中间一个硬币正面朝上，其他两个硬币背面朝上。具体规则如下：

（1）任何时候都能翻转中间的硬币（从正面翻成背面或相反）

（2）当另外两个硬币都是正面或都是背面的时候能够翻转一端的硬币（从

正面翻成背面或相反）；

不能通过任何其他方式翻转硬币，如平移它们。但是，只要满足这些规则，你就能够翻转硬币。

（提示：使用无向图，图中每个顶点代表三个硬币的一种状态（8种状态对应8个顶点，一个状态可用一个字符串表示，如”+-+”表示了一个中间一个硬币是背面朝上，其他两个硬币是正面朝上的状态）；当使用其中一条规则能在两个状态之间来回移动时，就通过一个边连接无向图的两个顶点。

该游戏使三个硬币从一种状态改变成另外一种状态，其实就是查找相应两个顶点之间路径的问题，该路径只能沿着边进行。）

七、编写程序帮助旅游者找出从一个城市到另一个城市的最短旅行

路径。

该程序应该读取一个包含了一个城市列表和一个连接城市的路径列表的数据文件。每个城市信息包含城市名称、城市级别（首都、直辖市、省会、地极市、县级市），每条路径包含两城市之间的距离、最低费用、最少花费时间。

程序功能要求：

（1）能进行城市信息的修改（2）能进行城市之间路径的修改

（3）能按满足不同用户的查询，如自费旅游的人希望费用最省，因公出差的人希望花费时间最少等。

某两地之间的最低费用路线（自费旅游的人）某两地之间的花费时间最少路线（因公出差的人）某两地之间的距离最短的路线（自己开车出行的人）

八 问题描述： 设计哈希表实现电话号码查询系统。基本要求：

1、设每个记录有下列数据项：电话号码、用户名、地址；

2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；

3、采用再哈希法解决冲突；

4、查找并显示给定电话号码的记录；

5、查找并显示给定用户名的记录。

6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。九 哈夫曼编码/译码器

设字符集为26个英文字母，其出现频度如下表所示。先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。

字符 频度 字符 频度 字符 频度

空格 186 j 1 t 80

a 64 k 5 u 23

b 13 l 32 v 8

c 22 m 20 w 18

d 32 n 57 x 1

e 103 o 63 y 16

f 21 p 15 z 1

g 15 q 1

h 47 r 48

i 57 s 51