数据结构练习题

数据结构练习题练习题21.在双向链表中，前趋指针和后继指针分别为prior和next。若要指针p往后移动两个结点，即指向当前结点后继的后继，则需执行语句o若要指针p向前移动一个结点，即指向当前结点的前趋，则需执行语句O.在有n个叶子结点的哈夫曼树中，其结点总数为。.数据的逻辑结构被分为集合结构、线性结构、和。.第一个顶点和最后一个顶点相同的路径称为。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为..堆排序属于（稳定、不稳定）排序。快速排序属于（稳定、不稳定）排序。.从一个栈顶指针为top的非空链式栈中删除结点，并不需要返回栈顶的值和回收结点时应执行的操作。27.在有n个顶点的无向图中，每个顶点的度最大可达。28.对于下面的二叉树，按后根遍历所得到的结点序列为。.带头结点的双链表H中两个指针域为prior和next,则双链表H为空的条件可以表示为。.在二叉链表中判断某指针p所指结点为叶子结点的条件是。--得分评卷人31.写出下图所示的A0V网的所有拓扑有序序列。如G中含有奇数度结点，则可在这些奇数度结点间添加新的边，使原有的某些边成为双边，并且使添加的边的权数之和最小。这样一来G的结点就都是偶数度的结点，G就成了欧拉图，从而求出问题的解。因此，求中国邮路问题的解就是在G中添加一些边，使图中所有结点的度数都变成偶数，求添加边的权数之和最小的添法。32.试将右图所示的一棵二叉树还原成森林。33.以数据集｛2,5,7,9,13｝为权值构造一棵哈夫曼(Huffman)树，并计算其带权路径长度。34.试写出一组键值(83,40,63,13,84,35,96,57,39,79,61,15)应用二路归并排序算法从小到大排序后各趟的结果。35.已知图中二叉排序树的各结点的值依次为32-40，请标出各结点的值。图二叉排序树36.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。Voidlevel(BSTreeroot,p)｛intlevel=0;if(!root)(1)；else{level++;while(root->key!=p->key)(if(root->key>p->key)(2);else(3);level++;)(4);))37试将折半查找的算法改写成递归算法。38.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列入队列和出队列的算法。第7章实验(4学时).验证性实验(满分90)以下验证性实验都做(1)邻接矩阵邻接矩阵的C语言描述基本运算的算法一一建立无向网的邻接矩阵、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u,则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历(2)邻接表邻接表的C语言描述基本运算的算法——建立无向网的邻接表、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u,则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历2..综合性实验(满分100)(1)教学计划编制U问题描述学历进修需要学生在一定的时间内完成一定的课程学习，每一门课有一定的学分，修满学分，可获取相应的学历。因为有些课程内容是另一些课程的学习基础，所以课程学习之间存有一定的先后次序。如：某学历的计算机专业需要学习的课程及课程之间的关系如表1所示。表1计算机专业进修课程课程进修关系图课程编号课程名称学分C1程序设计基础2C2离散数学3C3数据结构4C4汇编语言3▼C4C1 »c2♦C♦C9»CIOACl1C5程序设计与分析2C6计算机原埋3C7编译原理4C8操作系统4C9高等数学7CIO线性代数5Cll普通物理2C12数值分析3C13软件，程3C14数据库原理3本设计的主要任务是根据需要完成的课程的先修关系、每学期开设的课程总数及总的学习时间，制定出教学计划。需事先的基本功能如下。课程进修目录的读入。课程进修目录的编辑，如课程增加、删除、信息修改等。满足一定条件的教学计划的输出。&设计要求设学期总数不超过8,课程总数不超过5,设计一份课程进修单，包括：学期总数、一学期的学分上限、每门课的课程编号、学分和直接先修课程的课程号。实现上述基本功能。按各学期中的学习负担尽量均匀地制定教学计划。按尽可能短的时间完成学习，制定教学计划。如果无解，报告适当信息。③实现提ZF要制定教学计划，首先要得到所有课程的进修先后次序，它必是一个有向无环图。由课程信息中部分课程之间的先修关系，求全部课程的进修次序，即为拓扑排序问题。如果是各学期均分学时，首先计算出每学期应该承担的学分，依次从拓扑序列取得课程。注意，一门课程不能跨越两学期。如果是尽可能快地完成学业，要求先给出每学期最多能承担的学分，依次从拓扑序列取得课程。同样注意，一门课程不能跨越两个学期。(2)修道士野人问题问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：修道士和野人都会划船，但船一次只能载C人。在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否则修道士将会被野人吃掉。假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。(2设计要求设计表示野人、修道士、船的位置信息等数据的逻辑结构和存储结构。从键盘输入修道士与野人的人数N和船可容纳的人数Co设计检测某一时刻两岸修道士是否安全的算法。输出安全过河的详细路径。界面友好，操作简单。设计做够多的测试用例。③实现提小一侧的野人数目和修道士数目以及船在哪一岸共同构成一种状态，分析一下会发现合法的状态只有17种。此时这个问题的求解便类似于寻路问题，已知两个结点和所有节点间的连接关系，求两结点之间的一条路径(最短路径)，简单地进行广度优先搜索即可。用一个三元组(xl,x2,x3)表示渡河过程中的各个状态。xl表示左岸上修道士的个数，x2表示左岸上野人的个数，x3表示小船位置(0-在右岸上，1-在左岸上)。合法的状态举例：StateallStates[]={State(3,3,D,〃左岸3修道士，3野人，船在左岸State(2,2,l),State(l,l,l),State(3,0,l),State(0,3,l),State(3,l,l),...}根据给出的小船上的位置数量，生成小船上的安全状态，即在船上的时候修道士的人数也要比野人的数量要多(除非修道土人数为0)。渡船优先规则：左岸一次运走的人越多越好(即左岸运多人优先)，同时野人优先运走；右岸一次运走的人越少越好(即右岸运少人优先)，同时修道土优先运走。类似于操作系统中的银行家算法的安全性检测，即让修道士跟野人上船后，检测当船到达对岸后，两岸修道土的安全状态，若修道土安全，则将此结点加入到邻接表中。采用广度优先搜索，得到首先搜索到的边数最少的一条通路。(3)食物送递服务问题描述有一个小村，被水围困，村中有n(n<30)个住户，现在要给他们送去食物。因每户的储备不一样，能够自救的时间也不同，若超过自救时间段，该住户的人就会被饿死。根据住户地理上的分布和各家能够自救的时间，设计算法求用最短时间把食物送到的方案。(2设计要求设计住户的抽象模型和存储结构。程序中包含测试数据。另外提供交互方式输入数据。设计用最短时间把食物送到的算法。设计结果输出格式，尽量做到易懂③实现提示采用有向图结构，建立问题的抽象模型。可采用邻接矩阵作为图的存储结构。这是一个典型的哈密顿路问题，是一个NP问题，不可能在多项式时间内精确解决，因为顶点不多，可考虑搜索算法。图的搜索有两种：深度优先和广度优先。广度优先搜索的存储空间要求太高,建议采用深度优先搜索。本题找时间最短的方案，所以不能任意搜索。搜索前，应先进行预处理，求出任意两点之间的最短路径。这个问题可用Floyd算法实现。搜索前可行性判断：如果每个顶点都是走最短路时，假设需要总时间为S,那么所有的自救实现都比S小；否则，不可能有答案。搜索中可能性判断：因为每个家庭的自救时间是有限的，所以需要进行所搜中的可行性判断：如果在当前家庭i的时刻t加上从当前点i到下一个家庭j的时间cost[i]g],超过了j家庭的自救时间，则不需要继续搜索，表示不存在可行方案。(4)校园导游.问题描述校园占地几千亩，生活设施分布较散；校园内景色优美，景点甚多。在校园内移动，因时间、交通工具和用户兴趣等原因，需要选择线路。本设计的主要任务是为在哈尔滨工程大学校区内生活、购物、参观的人们提供行走线路查询、选择、景点介绍的帮助。需实现的基本功能如下：景点信息的查询。邻接景点信息的查询。给出到某个景点的最佳路线。给出到所有景点的最佳路线。修改景点信息。色设计要求设计校园游览图，景点不少于6个。设计图的存储结构。文件读入或键盘输入图的顶点信息和边信息，在内存中创建图。实现上述基本功能。设计足够多的测试用例。③实现提示由于景点与道路信息可能在多个地方使用，特别是景点浏览时不通过遍历获取景点信息，可以考虑将景点与景点信息分开存储，道路标志与道路的其他信息分开存储。如：图中仅给出景点标识，具体的景点信息存储与一张线性表中，如表2所示。表2景点信息表景点标志景点名称景点地点VI学子超市•••V2北门•••V3正门••••••••♦•••同样，道路与道路信息分开存储，如表3所示。表3道路信息表道路标志距离沿路景点al150VI,V3a2150•••a3•••••••♦•••♦•••（5）中国邮路问题问题描述一个邮递员从邮局选好邮件去投递，然后回到邮局。当然他必须经过他所管辖的每条街至少一次。请为他设计一条投递路线，使其所行的路程尽可能短。仁设计要求设计邮递员的辖区，并将其抽象成图结构进行表示，建立其存储结构（注：数据输入可以键盘输入和文件输入两种方式）。按照输入邮局所在位置，为邮递员设计一条最佳投递路线，要能考虑到辖区一般情况。③实现提示在无向图中，从某一结点出发，经过每边一次并且经过图中所有的结点（不一定次）到达终点。如果终点与