数据结构练习题

数据结构练习题练习题21．在双向链表中，前趋指针和后继指针分别为prior和next。若要指针p往后移动两个结点，即指向当前结点后继的后继，则需执行语句

。若要指针p向前移动一个结点，即指向当前结点的前趋，则需执行语句

。22．在有n个叶子结点的哈夫曼树中，其结点总数为

。23．数据的逻辑结构被分为集合结构、线性结构、

和

。24．第一个顶点和最后一个顶点相同的路径称为

。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为

。25．堆排序属于

（稳定、不稳定）排序。快速排序属于

（稳定、不稳定）排序。26．从一个栈顶指针为top的非空链式栈中删除结点，并不需要返回栈顶的值和回收结点时应执行

的操作。27．在有n个顶点的无向图中，每个顶点的度最大可达

。28．对于下面的二叉树，按后根遍历所得到的结点序列为

。29．带头结点的双链表H中两个指针域为prior和next，则双链表H为空的条件可以表示为

。30．在二叉链表中判断某指针p所指结点为叶子结点的条件是

。得分评卷人31．写出下图所示的AOV网的所有拓扑有序序列。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）

；}}（1）

（2）

（3）

（4）

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