《数据结构练习题.doc》由会员分享，可在线阅读，更多相关《数据结构练习题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、第7章实验（4学时）1.验证性实验（满分90）以下验证性实验都做（1）邻接矩阵l 邻接矩阵的C语言描述l 基本运算的算法建立无向网的邻接矩阵、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u，则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历（2）邻接表l 邻接表的C语言描述l 基本运算的算法建立无向网的邻接表、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u，则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历2.2.综合性实验（满分100）（1）教学计划编制问题描述学历进修需要学生在一定的
2、时间内完成一定的课程学习，每一门课有一定的学分，修满学分，可获取相应的学历。因为有些课程内容是另一些课程的学习基础，所以课程学习之间存有一定的先后次序。如：某学历的计算机专业需要学习的课程及课程之间的关系如表1所示。表1 计算机专业进修课程课程进修关系图课程编号课程名称学分C1程序设计基础2C2离散数学3C3数据结构4C4汇编语言3C5程序设计与分析2C6计算机原理3C7编译原理4C8操作系统4C9高等数学7C10线性代数5C11普通物理2C12数值分析3C13软件工程3C14数据库原理3本设计的主要任务是根据需要完成的课程的先修关系、每学期开设的课程总数及总的学习时间，制定出教学计划。需事先
3、的基本功能如下。l 课程进修目录的读入。l 课程进修目录的编辑，如课程增加、删除、信息修改等。l 满足一定条件的教学计划的输出。设计要求l 设学期总数不超过8，课程总数不超过5，设计一份课程进修单，包括：学期总数、一学期的学分上限、每门课的课程编号、学分和直接先修课程的课程号。l 实现上述基本功能。l 按各学期中的学习负担尽量均匀地制定教学计划。l 按尽可能短的时间完成学习，制定教学计划。l 如果无解，报告适当信息。实现提示l 要制定教学计划，首先要得到所有课程的进修先后次序，它必是一个有向无环图。l 由课程信息中部分课程之间的先修关系，求全部课程的进修次序，即为拓扑排序问题。l 如果是各学期
4、均分学时，首先计算出每学期应该承担的学分，依次从拓扑序列取得课程。注意，一门课程不能跨越两学期。l 如果是尽可能快地完成学业，要求先给出每学期最多能承担的学分，依次从拓扑序列取得课程。同样注意，一门课程不能跨越两个学期。（2）修道士野人问题问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：l 修道士和野人都会划船，但船一次只能载C人。l 在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否则修道士将会被野人吃掉。假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。设计要求l 设计表
5、示野人、修道士、船的位置信息等数据的逻辑结构和存储结构。l 从键盘输入修道士与野人的人数N和船可容纳的人数C。l 设计检测某一时刻两岸修道士是否安全的算法。l 输出安全过河的详细路径。l 界面友好，操作简单。l 设计做够多的测试用例。实现提示l 一侧的野人数目和修道士数目以及船在哪一岸共同构成一种状态，分析一下会发现合法的状态只有17种。此时这个问题的求解便类似于寻路问题，已知两个结点和所有节点间的连接关系，求两结点之间的一条路径（最短路径），简单地进行广度优先搜索即可。l 用一个三元组（x1，x2，x3）表示渡河过程中的各个状态。x1表示左岸上修道士的个数，x2表示左岸上野人的个数，x3表示
6、小船位置（0-在右岸上，1-在左岸上）。合法的状态举例：State allStates=State(3,3,1)，/左岸3修道士，3野人，船在左岸State(2,2,1)，State(1,1,1)，State(3,0,1)，State(0,3,1)，State(3,1,1)，l 根据给出的小船上的位置数量，生成小船上的安全状态，即在船上的时候修道士的人数也要比野人的数量要多（除非修道士人数为0）。渡船优先规则：左岸一次运走的人越多越好（即左岸运多人优先），同时野人优先运走；右岸一次运走的人越少越好（即右岸运少人优先），同时修道士优先运走。l 类似于操作系统中的银行家算法的安全性检测，即让修道士
7、跟野人上船后，检测当船到达对岸后，两岸修道士的安全状态，若修道士安全，则将此结点加入到邻接表中。l 采用广度优先搜索，得到首先搜索到的边数最少的一条通路。（3）食物送递服务问题描述有一个小村，被水围困，村中有n（n30）个住户，现在要给他们送去食物。因每户的储备不一样，能够自救的时间也不同，若超过自救时间段，该住户的人就会被饿死。根据住户地理上的分布和各家能够自救的时间，设计算法求用最短时间把食物送到的方案。设计要求l 设计住户的抽象模型和存储结构。l 程序中包含测试数据。另外提供交互方式输入数据。l 设计用最短时间把食物送到的算法。l 设计结果输出格式，尽量做到易懂实现提示l 采用有向图结构
8、，建立问题的抽象模型。l 可采用邻接矩阵作为图的存储结构。l 这是一个典型的哈密顿路问题，是一个NP问题，不可能在多项式时间内精确解决，因为顶点不多，可考虑搜索算法。图的搜索有两种：深度优先和广度优先。广度优先搜索的存储空间要求太高，建议采用深度优先搜索。l 本题找时间最短的方案，所以不能任意搜索。搜索前，应先进行预处理，求出任意两点之间的最短路径。这个问题可用Floyd算法实现。l 搜索前可行性判断：如果每个顶点都是走最短路时，假设需要总时间为s，那么所有的自救实现都比s小；否则，不可能有答案。l 搜索中可能性判断：因为每个家庭的自救时间是有限的，所以需要进行所搜中的可行性判断：如果在当前家
9、庭i的时刻t加上从当前点i到下一个家庭j的时间costij，超过了j家庭的自救时间，则不需要继续搜索，表示不存在可行方案。（4）校园导游问题描述校园占地几千亩，生活设施分布较散；校园内景色优美，景点甚多。在校园内移动，因时间、交通工具和用户兴趣等原因，需要选择线路。本设计的主要任务是为在哈尔滨工程大学校区内生活、购物、参观的人们提供行走线路查询、选择、景点介绍的帮助。需实现的基本功能如下：l 景点信息的查询。l 邻接景点信息的查询。l 给出到某个景点的最佳路线。l 给出到所有景点的最佳路线。l 修改景点信息。设计要求l 设计校园游览图，景点不少于6个。l 设计图的存储结构。l 文件读入或键盘输
10、入图的顶点信息和边信息，在内存中创建图。l 实现上述基本功能。l 设计足够多的测试用例。实现提示由于景点与道路信息可能在多个地方使用，特别是景点浏览时不通过遍历获取景点信息，可以考虑将景点与景点信息分开存储，道路标志与道路的其他信息分开存储。如：图中仅给出景点标识，具体的景点信息存储与一张线性表中，如表2所示。表2 景点信息表景点标志景点名称景点地点V1学子超市V2北门V3正门同样，道路与道路信息分开存储，如表3所示。表3 道路信息表道路标志距离沿路景点a1150V1，V3a2150a3（5）中国邮路问题问题描述一个邮递员从邮局选好邮件去投递，然后回到邮局。当然他必须经过他所管辖的每条街至少一
11、次。请为他设计一条投递路线，使其所行的路程尽可能短。设计要求l 设计邮递员的辖区，并将其抽象成图结构进行表示，建立其存储结构（注：数据输入可以键盘输入和文件输入两种方式）。l 按照输入邮局所在位置，为邮递员设计一条最佳投递路线，要能考虑到辖区一般情况。实现提示l 在无向图中，从某一结点出发，经过每边一次并且经过图中所有的结点（不一定一次）到达终点。如果终点与起点重合，称为存在欧拉回路，如果终点与起点不重合，称为存在欧拉通路。存在欧拉回路的图称为欧拉图。直观地说，一个无向图如果可以从一点出发，笔不离纸地一笔画出，就存在欧拉回路或欧拉通路，如果还能回到起点，就是欧拉图。l 中国邮路问题可以转化成图的问题来解。以街道为边，街道的长度为边的权，以邮局和街道的交叉点为结点，得到带权图G。如G中不含有奇数度结点，则G是欧拉图。以邮局为起点的欧拉回路就是问题的解。如G中含有奇数度结点，则可在这些奇数度结点间添加新的边，使原有的某些边成为双边，并且使添加的边的权数之和最小。这样一来G的结点就都是偶数度的结点，G就成了欧拉图，从而求出问题的解。因此，求中国邮路问题的解就是在G中添加一些边，使图中所有结点的度数都变成偶数，求添加边的权数之和最小的添法。
