基本习题部分

目的：字符串是一种基础且广泛使用的数据结构，与字符串相关的题目既可 以考察基本程序设计能力和技巧，也可以考查算法设计能力。 题目：求字符串之间距离 要求：设有字符串 X，称在 X 的头尾及中间插入任意多个空格后构成的新 字符串为 X 的扩展串，如字符串 X 为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□” 和“abcb□cd□”都是 X 的扩展串，这里“□”代表空格字符。如果 A1 是字符串 A 的 扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度，那么定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定 义为它们的 ASCII 码的差的绝对值，而空格字符与其它任意字符之间的距离为 已知的定值 K，空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串 中，必定存在两个等长的扩展串 A1、B1，使得 A1 与 B1 之间的距离达到最小， 将这一距离定义为字符串 A、B 的距离。请编写程序，求出字符串 A、B 的距离。

求解 2 个字符串的最长公共子串。输入的 2 个字符串可以从键盘读入，也可 以从两个文本文件中读入。 实现提示：对于采用动态规划法和后缀树算法的，要对算法设计思想能够进 行详细阐述，并分析算法的时间复杂和空间复杂度。能够详细阐述多种算法并设 计完成的，总分可达到 80 分。

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

问题描述： 设有两个用单链表表示的集合 A、B，其元素类型是 int 且以递增方式存储， 其头结点分别为 a、b。要求下面各问题中的结果集合同样以递增方式存储，结 果集合不影响原集合。 实现要求： （1）编写集合元素测试函数 IN_SET，如果元素已经在集合中返回 0，否则 返回 1； （2）编写集合元素输入并插入到单链表中的函数 INSERT_SET，保证所输 入的集合中的元素是唯一且以递增方式存储在单链表中； （3）编写集合元素输出函数，对建立的集合链表按递减方式输出； （4）编写求集合 A、B 的交 C=A∩B 的函数，并输出集合 C 的元素； （5）编写求集合 A、B 的并 D=A∪B 的函数，并输出集合 D 的元素； （6）求集合 A 与 B 的对称差 E=（A-B）∪（B-A） 的函数，并输出集合 D 的元素； （7）设计一个菜单，具有输入集合元素、求集合 A、B 的交 C、求集合 A、 B 的并 D、求集合 A 与 B 的对称差 E、退出等基本的功能。 测试数据：由读者自定，但集合 A、B 的元素个数不得少于 16 个。

目的：二叉树是常用的重要非线性数据结构，在客观世界中有着广泛的应用。 通过本题可以加深对于二叉树这一数据结构的理解。掌握二叉树的存储结构及各 种操作。 要求：一棵二叉树可以按照如下规则表示成一个由 0、1、2 组成的字符序列， 我们称之为“二叉树序列 S”： 例如，下图所表示的二叉树可以用二叉树序列 S=21200110 来表示。 任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或 蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点， 那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出 这棵树中最多和最少有多少个点能够被染成绿色。

任务：设计散列表实现电话号码查找系统。 要求： ①设每个记录有下列数据项：用户名、电话号码、地址； ②从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表； ③采用一定的方法解决冲突； ④查找并显示给定电话号码的记录； 可以选作内容： ①系统功能的完善； ②设计不同的散列函数，比较冲突率； ③在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均 查找长度的变化。

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均 不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或 环）。 要求： ①求出有向图中从起点到终点的所有简单路径。其中起点和终点可以由用户 自行设定。 ②求出有向图中从起点到终点的指定长度（如 K）的所有简单路径。其中起 点和终点可以由用户自行设定。

问题描述：设计一个程序求出完成整项工程至少需要多少时间以及整项工程 中的关键活动。 基本要求：（1）对一个描述工程的 AOE 网，应判断其是否能够顺利进行。 （2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每 一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。

目的：本课程设计是求中缀算术表达式真值问题。求中缀算术表达式值的问 题是数据结构中栈的一个典型应用。通过本题，学生应掌握中缀表达式和后缀表 达式的转换方法和后缀表达式求值问题。 要求：已知某种类型的布尔表达式由“T”、“F”、“！”、“&”和“|”组成，其中， “T”代表真值 True，“F”代表真值 False，“！”代表逻辑非运算，“&”代表逻辑与运 算，“|”代表逻辑或运算。并且，运算符“！”、“&”和“|”的优先级为：“！”最高， “|”最低，“&”介于“！”和“|”之间。你的任务是，计算给定布尔表达式的真值。 例如，布尔表达式“（T|T）&F&（F|T）”的真值为“F”.

用三种以上方法实现字符串模式匹配，比如 BF、KMP 和 BM 方法等，并利 用科学合理的方法针对这几种方法进行性能比较。

编程实现快速排序、堆排序、希尔排序、冒泡排序、归并排序算法，学生可 增加其它排序算法，并完成不同排序算法的性能对比分析。 要求： ①时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间 性能等。 ②实验数据应具有说服力，包括： 规模范围要大（如从 100 到 10000） 数据的初始特性类型要多，因而需要具有随机性； 实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。 ③算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 ④实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 ⑤要给出实验的方案及其分析。

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

选择合适的存储结构表示广义表，并能实现下列运算要求： ①用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的 功能。 ②取广义表 L 的表头和表尾的函数 head（L）和 tail（L）。 ③能用这两个函数的复合形式求出广义表中的指定元素。 ④由广义表的字符串形式到广义表的转换函数 Lists Str_ToLists_（S）； 例如 Str_ToLists_（“ （a,（a,b）,c）”）的值为一个广义表。 ⑤由广义表到广义表的字符串形式的转换函数 char * Lists_To_Str（L）。 ⑥最好能设置多个广义表。 算法编写

目的：后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计 算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如： 2 1 + 3 ,即（2 + 1） * 3 通过本课程设计，应使学生掌握后缀表达式的特点、栈的基本方法和基本原 理，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的 能力，为后续计算机专业课程的学习打下坚实的基础。 要求：实现一个简单的后缀表达式计算器。假定表达式里的基本数值为实数， 可用的运算符包括+,-,,/,^，其中的 ^ 表示求幂运算。 ①假定输入表达式里的数和运算符之间都有空格，这样可以简化输入的处理； ②输入的算术表达式以分号为结束符。计算器应该能输入并计算一系列表达 式，遇到一行的第一个字符就是分号时程序结束。 ③上题的计算器增加一元函数功能，允许表达式里写 sin, cos, tan, log（自然 对数）等函数，还可以考虑加入自定义的其他数学函数。（选做）

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

设有 3 个传教士和 3 个野人来到一条河的左岸，打算乘一只船从左岸渡到右 岸去。该船的负载能力为 2 人。在任何时候，如果野人人数超过传教士人数，那 么野人就会把传教士吃掉。野人绝对服从传教士的指挥和调度。 提示： 基于河的一岸求解问题，比如左岸，不需考虑船在河中央的状态。用三个变 量人数、野人数、船是否在左岸三个变量描述问题的状态，比如（M,W,B）。用 函数来使问题的状态发生变化，最后到达目标状态。 初始状态：（3,3,1），目标状态：（0,0,0） 要求： 编程求解问题；给出中间状态；给出解序列（函数调用序列）

邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返 回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的 每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为 中国邮路问题。 Left Bank 13 10 9 11 8 13 12 8 7 7 6 7 5 3 15 5 17 4 11 R13 R14 R15 R12 R8 R7 R2 R1 R3 R4 R5 R9 R10 R11 R6 12 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 房屋 编程要求： （1）求解用户输入的图形的中国邮路问题 要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和最 终结果。 （2）加入图形编辑器 系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图形 和最终结果。 （3）附加要求 能够图形显示求解过程。 提示：此题请查阅相关资料后再做题。

计算机网络要求网络中的计算机被连接起来，本问题考虑一个“线性”的网 络，在这一网络中计算机被连接到一起，并且除了首尾的两台计算机只分别连接 着一台计算机外，其它任意一台计算机恰连接着两台计算机。图 1 中用圆点表示 计算机，它们的位置用直角坐标表示。网络连接的计算机之间的距离单位为英尺。 由于很多原因，我们希望使用的电缆长度应可能地短。你的问题是去决定计 算机应如何被连接以使你所使用的电缆长度最短。在设计方案施工时，电缆将埋 在地下，因此连接两台计算机所要用的电缆总长度等于计算机之间的距离加上额 外的 16 英尺电缆，以从地下连接到计算机，并为施工留一些余量。 下图是计算机的最优连接方案，这样一个方案用电缆的总长度是： （4 + 16） + （5 + 16） + （5.38 + 16） + （11.18 + 16） = 90.01 英尺 基本要求： 输入网络中的计算机总数和每台计算机的坐标。 输出使电缆长度最短的连接方案。给出最优连接方案中每两台相邻计算机之 间的距离，以及总的电缆长度。 提高要求： 参考图 2，用图形化的方式显示结果，包括点的坐标、最优路径、相邻计算 机之间的距离。

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

（1）问题描述： 写出求一个二分图的最大匹配的算法，并用于解决下面的问题。 第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇 家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 2 名飞 行员，其中 1 名是英国飞行员，另 1 名是外籍飞行员。在众多的飞行员中，每 一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行 的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配 合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多 的飞机。 （2）编程任务： 对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员 配对方案，使皇家空军一次能派出最多的飞机。 数据输入： 由文件 input.txt 提供输入数据。文件第 1 行有 2 个正整数 m 和 n。n 是皇 家空军的飞行员总数（n2->3->5；P2：1->3->2->5；P3：1->3->5； P4：1->4->5；P5：1->4->3->5。此时的 T5 就是如图所示的一棵树。 定义 devi 为 Pi 的偏离点（deviation node），定义为在 Ti 上，Pi 对应的那一 分枝中，第 1 个（按从 s 到 t 的顺序）不在 Ti - 1 上的点（i > 1）。为描述的方 便，设 dev1 为 P1 的第 2 个点。因此，在图 1 中，dev1~dev5 的编号分别为 2、 3、5、4 和 3。显而易见，devi 至少是 Pi 的第 2 个点。接下来是 Yen 算法的核 心部分，即每当求出一个 Pi 时，都可以从 Pi 上发展出若干条候选路径。发展的 方法是这样的，对于 Pi 上从 devi 的前一个点到 t 的前一个点这一段上的每个点 v，都可以发展出一条候选路径。用 Pi sv表示 Pi 上从 s 到 v 的子路径，用 Pi vt 表示从 v 到 t 的满足下列条件的最短路径：condition 1：设点 v 在 Ti 上对应的 点为 v'，则 Pi vt 上从点 v 出发的那条边不能与 Ti 上从点 v'出发的任何一条边相 同。condition2：Pi vt 上，除了点 v，其它点都不能出现在 Pi sv上。如果找得出 Pi vt， 则把 Pi sv和 Pi vt 连起来就组成了一条候选路径。其中 condition 1 保证了候选路径 不与 P1~Pi 重复；condition 2 保证了候选路径无环。 以图中的例子为基础，可以举一个发展候选路径的例子。在求出了 P5 之后， 要在 P5 上发展候选路径。P5 的偏离点是 3 号点。因此 v 的范围是{4, 3}。 当 v = 4 时，Pi sv = 1 -> 4，因此，根据 condition 2，在 Pi vt 上不能出现 1 号 点。找到 P5 上的 4 号点在 T5 上对应的那一点，也就是图 6-中位于阴影 3 号点 上面的 4 号点，在 T5 上从它出发的有（4, 5）和（4, 3）这两条边，因此，根 据 condition 1，在 Pi vt 上不能出现这两条边。假设在这样的情况下，求出了从 4 号点到 t 的最短路径为 4 -> 2 -> 5，它就是 Pi vt。此时发展出的候选路径就是 1 -> 4 -> 2 -> 5。 当 v = 3 时，Pi sv = 1 -> 4 -> 3，因此，根据 condition 2，在 Pi vt 上不能出 现 1 号点和 4 号点。找到 P5 上的 3 号点在 T5 上对应的那一点，也就是图 6-66 中阴影的 3 号点，在 T5 上从它出发的只有（3, 5）这一条边，因此，根据 condition 1，在 Pi vt 上不能出现边（3, 5）。假设在这样的情况下，我们求出了从 3 号点 到 t 的最短路径为 3 -> 2 -> 5，它就是 Pi vt。此时发展出的候选路径就是 1 -> 4 -> 3 -> 2 -> 5。 显而易见，在从 Pi 发展出的所有候选路径中，只有当 v 是 devi 的前一个 点时，条件 1 才有可能阻挡掉 2 条或 2 条以上边。当 v 不是 devi 的前一个点 时，条件 1 只会阻挡掉 1 条边，那就是本身位于 Pi 上，从 v 出发的那条边。 不仅从 Pi，从之前的 P1~Pi - 1，我们都发展过若干条候选路径。从候选路径的集 合中取出最短的一条，就是 Pi + 1。把 Pi + 1 从候选路径的集合里删掉；然后再 从它发展新的候选路径，添加到候选路径的集合里，如此循环，直到求出 Pk 为 止。如果在求到 Pk 之前，候选路径的集合就空了，那么说明 Pk 不存在。 （2）课程设计目的 学习、掌握、编程实现 Yen 算法，知道如何求解第 K 短最短路径。 （3）基本要求 ①给定一个加权图，编程实现 Yen 算法，依次输出所有的无环最短路径。 ②候选路径集合用堆存储实现，方便快速选取最短的一条。 ③分析 Yen 算法的时间复杂性。 （4）实现提示 在 Yen 算法中会调用 Dijkstra 算法，图可用邻接矩阵表示。

（1）问题描述 设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、 乘、除等基本代数运算。 （2）课程设计目的 能够应用线性数据结构解决实际问题。 （3）基本要求 ①长整数长度在一百位以上。 ②实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解 a+b modn, a-b mod n, ab mod n, a÷b mod n。 ③输入输出均在文件中。 ④分析算法的时空复杂性。 （4）实现提示 需将长整数的加法转化为多个一般整数加法的组合。

模拟与分析 （1）问题描述 细胞自动机是一个时间和空间都离散的动态系统，每个细胞自动机都是由细 胞单元（cell）组成的规则网格，每个细胞元都有 k 个可能的状态，其当前状态 由其本身及周围细胞元的前一状态共同决定。其具体细节在上题中已有所描述， 此处略去。 （2）课程设计目的 了解细胞自动机的基本原理，并能实现对细胞自动机的模拟以及在此基础上 做有价值的分析。 （3）基本要求 ①编写 tribute 模型的模拟（最好有图形界面，可用 C 的图形库）。 ②该模型是一个一维模型，包含 N 个参与者（细胞元，N 可配置，缺省为 10，此处就用 10 说明问题），将其命名为 actors。这 10 个 actors 组织成一个环 形，每个 actor 都有一定的初始化财富量（可随机确定，在 300~500 之间均匀分 布，也可设定），标记为 W。 ③该模型的基本规则为： 1.Actors 只可以和它的邻居（左邻居和右邻居）进行交互，只有两种可能的 交互动作：一是向其邻居索取供品（demand tribute），二是和其邻居结为联盟 （alliance）。 2.一个离散的时间片（表示 1 年）内，3 个随机选择的 Actors 一个接一个 的被激活，每个 Actor（A）会向他的其中一个邻居（T）索取 Tribute，T 可以 pay，也可以拒绝并 fight，如果 pay，T pay A min（250,WT）；如果 fight，交战 双方都会造成财富损失，每方损失的是对方财富量的 25%，如果其中一方的财富 不足以承担这一数量时，双方的损失将成比例缩减，此时财富不足的那一方（ B ） 将失去全部财富， 引起另一方（ A ） 的财富损失为 0.25（B/（0.25A））B。 3.A 选取 T 的原则是使得 WT * （WA–WT）/WA 最大，但如果没有 T 使 得该值大于 0，A 选择不动作。 4. T 选取 pay 或 fight 的哪一动作依据的是哪一种动作花费更少。 5.另外，每一年，每个 Actors 都有少量额外的财富（20）补充进来。 6.作为A 和B 交互的副产品，会产生一个A 对B 的承诺值（Commitments）， 简称 C，C 会在如下三种情况下增加：A pays tribute to B；A receives tributefrom B；和 A fights on the same side as B。而当 A fight on opposite sides withB 时 C 会 降低。 7.C 值的范围为 0~1，每次增加及减少幅度都是 0.1。 8.初始化时，各 Actors 对其它 Actor 的 C 值为 0。又由于规则 6 的对称性， 所以任何时刻 A 对 B 的 C 值和 B 对 A 的 C 是相同的。 9.引入 Commitments 后，A 选取 T 的范围扩大，不仅仅是其邻居 Actor， 可以是任何一个 Actor。当 A 收取 T 的贡品时，位于 A 和 T 之间的 Actor 会根 据其与 A 和 T 的 C 值大小决定加入 C 值较大的一方，如果两 C 值相同，则保 持中立。只有当 A 和 T 之间的所有 Actor（环形的两个方向均可）都加入 A 方， A 才能向 T 收取贡品。对于存在若干个满足上述条件的 T，选取原则将按照规 则 3 进行扩展。 10.规则 9 中，如果 K 要加入 A（T），仅当 K 和 A（T）相邻，或 K 和 A （T）之间的所有 Actor 都加入 A（T）。 11. A 形成的联盟的财产计算为：W= WA+C（A1,A）WA1+…，其中 C（A1,A） 为 A1 对 A 的承诺值，A1 为联盟中的一名成员，WA1 为 A1 的财产。收取的 贡品仅归 A 所有，而战斗的负担由联盟共同承担，其费用比例就是各 Actor 的 C 值。 12. 所有 Actor 的 C 值、W 值对任何一个 Actor 都是可见的，在任何计算 中都可使用。 ④ 上述规则描述了 Tribute 模型，规则 1 到 5 是未引入 Commitments 时的 基本模型，基本模型的模拟是本设计的要求内容；加上规则 6 到 12 是引入 Commitments 后的扩展模型，扩展模型的模拟是本设计的选做内容。 ⑤ 模拟时间应超过 1000 年。 ⑥ 根据上述模拟得出 Tribute model 较为全面的实验结果：财富的变化规律； 各参数对结果的影响等。 （4）实现提示 可用循环队列实现自动机的存储

的模拟与分析 （1）问题描述 细胞自动机是一个时间和空间都离散的动态系统，每个细胞自动机都是由细 胞单元（cell）组成的规则网格，每个细胞元都有 k 个可能的状态，其当前状态 由其本身及周围细胞元的前一状态共同决定。 例如：The Game of Life 1．细胞元形成二维数组。 2．每个细胞元有两个状态：living 和 dead。 3．t+1 时刻的状态由 t 时刻的状态决定。 4．状态变迁规则 1：一个 living 的细胞元依旧保持存活，如果其周围存在 2 或 3 个 living 细胞元，否则死亡。 5．状态变迁规则 2：一个 dead 的细胞元依旧保持死亡，除非其周围恰好 3 个 living 细胞元。 一个演化图例如下： 细胞自动机从某种程度上反映了生物群落的演化，也可应用到许多计算机问 题中。 （2）课程设计目的 了解细胞自动机的基本原理，并能实现对细胞自动机的模拟以及在此基础上 做有价值的分析。 （3）基本要求 ①编写 Gossip 模型的模拟（最好有图形界面，可用 C 的图形库）。 ②该模型是一个二维模型，并按如下条件处理边界问题：右边界的右邻居是 左边界，同理，左边界、上边界、下边界也一样， ③该模型的基本规则为：如果你的邻居中有人得知某消息，那么你将有 5% 的概率从其中获知消息的一个邻居那里获得该消息（即如果只有一个邻居有消息， 得知概率为 5%，有两个邻居就是 10%，依此类推）；如果你已经得知该消息， 那么你将保存。 ④依据上述模拟得出 Gossip 模型较为全面的实验结果：消息覆盖率随时间 的变化；不同概率值的影响等。 （4）实现提示 可用数组实现自动机的存储。

（1）问题描述 本题目做一个 N x M 的扫雷游戏，每个方格包含两种状态：关闭（closed） 和打开（opened），初始化时每个方格都是关闭的，一个打开的方格也会包含两 种状态：一个数字（clue）和一个雷（bomb）。你可以打开（open）一个方格， 如果你打开的是一个 bomb，那么就失败；否则就会打开一个数字，该数字是位 于[0，8]的一个整数，该数字表示其所有邻居方格（neighboring squares）所包含 的雷数，应用该信息可以帮助你扫雷。 具体实现要求的细节： ①能够打开一个方格，一个已打开的方格不能再关闭。 ②能够标记一个方格，标记方格的含义是对该方格有雷的预测（并不表示真 的一定有雷），当一个方格标记后该方格不能被打开，只能执行取消标记的操作， 只能在取消后才能打开一个方格。 ③合理分配各个操作的按键，以及各方格各种状态如何合理显示。 （2）课程设计目的 掌握线性结构的应用，并体会如何用计算机程序完成一个有趣的游戏。 （3）基本要求 ①能够给出游戏结果（输、赢、剩余的雷数、用掉的时间按妙计）。 ②游戏界面最好图形化，否则一定要清楚的字符界面。 （4）实现提示 用二维数组表示 N x M 区间，要仔细考虑如何初始的布置各个雷以及各个 方格的状态及变化。

（1）问题描述 在本设计题目中，需要使用不相交集合数据结构（disjoint set data structure） 来构造一个 NN 的从左上角到右下角只有一条路径的随机迷宫，然后在这一迷 宫上执行深度优先搜索。 该设计共包含如下四个部分： ①不相交集合数据结构的设计和实现 不相交集合即对于任意两个集合 A 和 B，A∩B=ø。不相交集合常可以表示 为树，此时两个不相交集合的并的实现很容易，如图所示。不相交集合常可用来 根据等价关系对集合进行等价划分。 ②构建随机迷宫 应用不相交集合构建迷宫的算法简要描述如下：给定一个 NN 的方格 （cells），初始时每个方格的四面都是墙（walls），如图 6-58（a）所示，其中的 S 是迷宫的开始处，F 是迷宫的结束处。NN 迷宫的 N 2 个方格 0，1，…，N 2 -1 初始时每个方格自己成为一个等价类，即{0}，{1}，…，{N2 -1}。生成随机迷宫 的方法是随机选择一个内部墙（连接两个相邻方格的墙），如果该内部墙关联的 两个相邻的方格属于不同的等价类就将该墙除去，在除去该墙的同时将这两个等 价类合并。直到所有的方格都在一个等价类中，就完成了随机迷宫的生成。 ③寻找迷宫路径 迷宫一旦建立后，将迷宫表示为一个无向图：方格作为图中的顶点，如果两 个相邻的方格之间没有墙则两个顶点之间有边。为找到从 S 到 F 的一条唯一的 路径，在该图上从 S 处开始出发先深搜索，如果搜索到达了 F，则搜索停止。 ④将迷宫和路径用图形方式画出 用图形方式将上述算法获得的随机迷宫及其上的最短路径画出。用线段来表 示迷宫中的墙，用在每个方格中心的点来表示路径。 （2）课程设计目的 掌握不相交集合结构的实现和使用，掌握图的基本算法，建立集合、等价划 分、图、搜索等事物之间如何关联的认识。 （3）基本要求 ①不相交集合应用数组进行物理存储。 ②在生成随机迷宫时，考虑如何使选取墙的次数尽量少。 ③在先深搜索找到路径时，要求找到最短的路径，即记录最短路径上的方格， 所以先深搜索过程应该是采用栈的非递归实现。此时，在先深搜索结束时，栈中 就存放了最短路径上的方格，而不是先深搜索过程访问的所有方格。 ④迷宫和路径的图形显示的实现方式不限制，如可以选择 VC，TC 或 Java 等。 （4）实现提示 不相交集合可父链数组进行物理存储，先深搜索采用栈的非递归实现可参阅 一些资料，这样的资料很多。

要求： （1）正确显示系统时钟； （2）能准确定位时钟刻度和时分秒针的位置； （3）能随窗口大小的变化而变化。 算法设计及程序设计中技术重点： 在应用程序中，经常有一些任务在后台处理，实现方式有两种：计时器和 OnIdle 循环处理。计时器是程序中最常用的后台任务机制之一，其时间间隔最低 约 55 毫秒，被广泛用于时钟、磁盘备份程序或需要在某一时刻运行的程序等。 多媒体计时器能编程设定 1 毫秒或者更小，它是诸如 MIDI 序列发生器之类 的专用型应用程序的理想选择，在 Windows API 中有很多查询时钟的函数，利 用它们就可以编写出高精度的计时器。 使用计时器只需要了解两个函数：CWnd：：SetTimer（）函数用来设置一个 计时器以指定的时间间隔触发，CWnd：：SetTimer（）函数用来使一个正在运行 的计时器停止。计时器以两种方式通知应用程序计时器间隔时间已到：发送 WM-TIMER 消息和调用应用程序定义的回调函数。其中前者相对比较简单，但 对于多个计时器则应使用回调函数。计时器消息发送给应用程序时都是低优先级， 因此只有当消息对列中没有其他消息时才回处理它们。 计时器消息不能在消息队列中积存，这避免了出现永远无法清空消息队列的 状态。尽管如此，Windows 应用程序决不应该花费过量的时间来处理消息，除非 该处理过程已经委派给辅助线程。如果主线程运行时间过长而没有检查消息队列， 则程序的响应能力会受到影响。 程序运行结果图

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

编程实现平衡二叉树，功能要求： 能实现插入结点、删除结点、查找元素，并需显示调整平衡的过程。

编程实现 B 树，功能要求： ①插入关键字 ②删除关键字 ③查找关键字

编程实现 B+树，功能要求： ①插入关键字 ②删除关键字 ③查找关键字

（1） 问题描述 一棵具有红黑特征的树是一棵特殊的二元查找树，它在每个结点上增加一种 额外属性——颜色（只能是红或黑）。 红黑树（Red-Black Tree）是一棵具有如下特征的二元查找树： 1．每一个结点或者是红色或者是黑色。 2．每个叶结点都是黑色。 3．如果一个结点是红色，那么它的两个孩子结点都是黑色。 4．从任何一个结点到所有以该结点为子树的叶结点的简单路径上拥有相同 的黑色结点。如下图就是一个红黑树的实例： 一般叶结点是不存放数据的，它作为哨兵用来表示已经到达叶结点。 从一个结点 x 到 x 子树中叶结点的路径（不包括 x）上黑色结点的个数称 为 x 的黑色高度（black-height），标记为 bh（x）。 对于红黑树我们可以证明如下定理：任何一个具有 n 个内部结点的红黑树 其高度至多为 2log（n+1）。该定理决定了红黑树可以保证查找时间复杂性一定时 O（logn）（具有和平衡树类似的性质）。 （2）课程设计目的 认识 Red-Black Tree 结构，并能依据其优点解决实际问题。 （3）基本要求 ①设计并实现 Red-Black Tree 的 ADT，该 ADT 包括 Tree 的组织存储以及 其上的基本操作：包括初始化，查找，插入和删除等。并分析基本操作的时间复 杂性。 ②实现 Red-Black Tree ADT 的基本操作演示（要求应用图形界面）。 ③演示实例为依次插入 A L G O R I T H M 并依同样的次序删除。 （4）实现提示 考虑树的旋转。

设计程序以实现构造哈夫曼树，要求如下： ①构造哈夫曼树。 ②能演示构造过程。 ③求解出所构造的哈夫曼树的带权路径长度。 ④给出哈夫曼编码。

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

采用哈夫曼编码思想实现文件的压缩和恢复（解压缩）功能。 要求： ① 实现文本文件的压缩和解压缩功能。 ② 运行时的压缩原文件的规模应不小于 5KB。 ③ 给出文件的压缩比。 ④ 提供恢复文件与原文件的相同性对比功能。

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111

（1）问题描述 如果将 n 个元素插入到一个一棵二元查找树中，所得到的树可能会非常不平 衡，从而导致上面的查找时间很长。一种通常的处理办法是首先将这些元素进行 随机置换，即先随机排列这些元素，然后再依次插入到二元查找树中，此时的二 元查找树往往是平衡的，这种二元查找树称为随机二元查找树。但是这样的处理 存在一个问题，即这样的处理方法只适用于固定的元素集合（已经预先知道了所 有的元素）。如果没有办法同时得到所有的元素的话，即一次收到一个元素，则 没有办法进行处理，此时可以用 treap 来处理这种情况，图 6-61 给出了一个 treap 结构。 Treap 结构中每个节点 x 有两个域，一个是其关键字值 key[x]，一个是优先 级数 priority[x]（它是一个独立选取的随机数），上图节点中左边的字符就是 key[x]， 右边的整数就是 priority[x]。对于 treap 结构，其关键字遵循二元查找树性质， 其优先级遵循最小堆性质，即：如果 v 是 u 的左儿子，则 key[v]key[u]，如果 v 是 u 的儿子，则 priority[v]>priority[u]。 所以这种结构被命名为 treap（tree+heap）。 有了 treap，假设依次插入关键字到一棵 treap 中，在插入一个新节点时：首 先给该节点随机选取一个优先数；然后将该节点按关键字插入到 treap 中的二元 查找树中，此时 priority 可能会不满足堆的性质；最后按照 priority 调整 treap， 在保证二元查找树性质的同时调整 treap（需要一系列旋转）使之按 priority 满足 堆性质。图 6-62 给出了在 treap 结构上进行插入操作的处理过程。 （2）课程设计目的 认识 treap 结构，对二元查找树和随机二元查找树建立深入的认识，能编程 实现二元查找树、堆、treap 等结构以及其上的基本操作。 （3）基本要求 ① 用数据结构知识设计和实现 treap 结构以及上的基本操作：插入和删除。 ② 编程实现随机二元查找树。 ③ 产生若干个依次插入二元查找树的元素序列（元素个数自己设定），针对 该序列分别实现三种情况：插入到一般二元查找树、插入到 treap、用随机二元 查找树处理。分别得出三种情况处理后的结果二元树的高度，进行实际的数据对 比，从对比结果中发现一些规律。 ④ 应模拟出各个操作的结果，模拟过程应该是可视的，即可以看到依次插 入元素后各结构的变化情况。 ⑤ 对随机二元树的高度、对 treap 的高度、对 treap 中的插入操作、对 treap 插入操作中旋转次数等指标进行理论分析。 （4）实现提示 需要设计一个合适的随机排列算法来完成随机二元查找树的实现。

（1） 问题描述 二项堆是二项树的集合，而二项树是基于递归定义的，即二项树 Bk 是一棵 在 Bk-1 的基础上递归定义的有序树，它由两个 Bk-1 形成链接形成：一棵 Bk-1 树 的根是另一棵 Bk-1 根的最左儿子。下图给出了图示： 图（a）说明二项树的递归定义，图（b）给出 B0~B4 的图例，图（c）表明 了 Bk 的另一种表现形式。 二项堆 H 是满足如下二项堆特征的二项树集合： 1．H 中的每棵二项树都满足堆特征，即每个结点的值都大于等于其父结点 的值。 2．H 中的每棵二项树根结点的度互不相同。 其中性质 2 意味着对于任何 k，H 中只可能是存在或不存在 Bk。如果 H 中 存在 Bk，就会对 H 贡献 2 k 个结点，用二进制表示就是在第 k 为 1，所以对于 n 个结点的 H，n 的二进制表示[blog n , blog n-1 ….. b0]中第 i 为 bi 就表示了 H 中是 否存在 Bi，相反的事实也成立。根据这一事实也可以看出 n 个结点的二项堆至 多⌊log n⌋+1 个二项树。 下图为一二项堆的实例： （2）课程设计目的 认识二项树、二项堆数据结构，并能应用该结构解决实际问题。 （3） 基本要求 ① 设计二项堆 ADT，其上的基本操作包括：Make Heap （x）, Find-Min, Union，Insert，Extract-Min，Decrease Key （x），Delete。 ②实现二项堆 ADT，包括实现二项堆的存储结构以及其上的基本操作，并 分析基本操作的时间复杂性。 ③实现二项堆 ADT 的基本操作演示（要求应用图形界面）。 （4）实现提示 其中的 UNION 是关键操作，部分其它操作可在此基础上构造。UNION 操 作可类似二进制加法进行。

（1）问题描述 优先队列 priority queue 是一种可以用于很多场合的数据结构，该结构支持 如下基本操作： •Insert（S, x）——将元素 x 插入集合 S •Minimum （S）——返回 S 中最小的关键字 •Extract–Min （S）——删除 S 中的最小关键字 •DecreaseKey（S,n,key）——将 S 中的结点 n 的关键字减小为 key 要求以堆作为辅助结构设计并实现一个优先队列。要将堆结构嵌入到队列结 构中，以作为其数据组织的一部分。 应用该优先队列实现作业的优先调度： 一个作业 ti =（si，ei），si 为作业的开始时间（进入时间），ei 为作业的结束 时间（离开时间）。作业调度的基本任务是从当前在系统中的作业中选取一个来 执行，如果没有作业则执行 nop 操作。本题目要求的作业调度是基于优先级的 调度，每次选取优先级最高的作业来调度，优先级用优先数（每个作业一个优先 数 pi）表征，优先数越小，优先级越高。作业 ti 进入系统时，即 si 时刻，系统给 该作业指定其初始优先数 pi = ei -si，从而使越短的作业优先级越高。该优先数在 作业等待调度执行的过程中会不断减小，调整公式为：pi = pi - wi，其中的 wi 为 作业 ti 的等待时间：wi= 当前时间-si。一旦作业被调度，该作业就一直执行，不 能被抢占，只有当前执行作业指向完成时，才产生下一轮调度。所以可以在每次 调度前动态调整各作业的优先数。 编程实现这样一个作业调度系统。 （2）课程设计目的 熟悉堆结构的应用，优先队列的构造，解决实际问题。 （3）基本要求 ①给出优先队列的 ADT 描述，包括队列的逻辑结构及其上基本操作。 ②以堆结构为辅助结构实现优先队列的存储表示并实现其上的基本操作。 ③作业集合中的各作业随机生成，根据作业的 s 属性和 e 属性动态调整作业 队列，不断加入作业，作业结束删除作业。 ④要对作业调度的结果给出清晰的输出信息，包括：何和作业进入，何时调 度哪个作业，何时离开，每个作业等待多长时间，优先数的动态变化情况等。

（1）问题描述 双端优先队列是一个支持如下操作的数据结构： •Insert （S, x） – 将元素 x 插入集合 S •Extract –Min （S） –删除 S 中的最小关键字 •Extract –Max （S） –删除 S 中的最大关键字 可用小大根交替堆来实现对上述三个操作的支持。小大根交替堆是一个满足 如下小大根交替条件的完全二元树：如果该二元树不空，那么其上的每个元素都 有一个称为关键字的域，且针对该关键字，二元树按层次形成了小大根交替的形 式，即对于小大根交替堆中的任何一个结点 x，如果 x 位于小根层次，那么 x 就 是以 x 为根节点的二元树中键值最小的结点，并称该结点为一个小根结点。同 样的道理，如果 x 位于大根层次，那么 x 就是以 x 为根节点的二元树中键值最 大的结点，并称该结点为一个大根结点。在小大根交替堆中根结点位于小根层次。 下图给出了一个具有 12 个顶点的小大根交替堆实例。每个结点中的数值就 是该结点对应元素的键值。 假设要在该图的堆中插入键值为 5 的元素。和普通堆一样，小大根交替堆 上的插入算法也要针对从新插入结点到根结点的路径进行处理。对于上面的例子， 需要比较键值 5 和其父结点键值（此处是 10）的大小关系，此处由于 10 位于 小根层次且 5 heap[k].key 且 k 是根结点孙子。 对于此种情况也是先将 heap[k]的元素移到根结点，将 item 插入 k 结 点所在位置。然后考察 k 的父结点 parent，如果 item.key>heap[parent].key， 就将 heap[parent]和 item 元素互换，这一交换保证了 parent 结点处的键值是以 parent 为根结点的子堆中最大的，即 parent 满足了大根条件。此时需考虑如何 将 item 插入到以 k 为根的子堆中，现在该子小大根交替堆的根结点为空，显然 此时的情况和初始情况完全相似，因此可以重复上述处理过程。 对于本例有 item.key=12，且根结点的所有儿子和孙子中的最小键值为 9，设 9 所对应的结点用 k 标记，其父结点用 p 标记。由于有 9xm（图 6-79 就是这种情况） 对每个 xi,i+10，ys0，xsx， b>0，cy”并退出； 如果 ypy”并退出； 如果 ycy* 找到所有 aixright， 而且 a,b 都是离散点的坐标，insert（a,b,p）的处理流程是： 1．mid=p->left->xright； 2．若 a=p->xleft 且 b=p->xright，则执行有关的插入操作；返回； 3．若 ，则执行 insert（a,b,p->left）；返回；//左边插入，递归执行 4．若 ，则执行 insert（a,b,p->right）；返回；//右边插入，递归执行 5．执行 insert（a,mid,p->left）；执行 insert（mid,b,p->right）；返回；//两边都 递归插入 这是一个递归过程。其中第 1 步执行完后，第 2,3,4,5 步只有一步会被执行。 若执行了第 2 步，则称节点 p 为一个插入点，关键工作都是在插入点进行的。若 执行了第 3,4 或 5 步，则 p 都不会被称为插入点。在插入点进行的关键工作会在 不同的应用中体现为不同的操作，如可以给每个节点上定义一个 count 变量，该 变量 count 用来记录覆盖该结点的线段条数，此时每次插入操作使 count 变量增 1。 设 aM ： 如 果 p->C>0 ， p->M=p->xright-p->xright;p->C=0 且 v 是叶子结点，p->M=0；p->C=0 且 v 是内 部结点，p->M=p->left->M+p->right->M。只要每次插入或删除线段区间时，在访 问到的结点上更新 M 的值，不妨称之为 UPDATA，就可以在插入和删除的同时 维持好 M。求整个线段树的并集长度时，只要访问 root->M 的值。这在许多动态 维护的题目中是非常有用的，它使得每次操作的维护费用只有 logn。类似的，还 有求并区间的个数等等。 （2）课程设计目的 掌握线段树的基本原理，编程实现线段树及其上的基本操作，应用线段树解 决实际问题。 （3）基本要求 ①编程实现线段树的数据结构定义、线段树的初始化操作、线段树的插入和 删除操作。 ②应用线段树解决一维线段上的计算几何问题，如求解这些线段的并集的长 度，给定一个点，多少线段覆盖这个点等等。 ③用线段树解决二维图形上的计算几何问题，如坐标轴的上半平面上有 N 个矩形。每个矩形都有一条边在 x 轴上，记这条边为区间[Ai,Bi]，记该矩形的高 为 Hi，i=1,…,N。其中 ≤Bi≤109，1≤i≤N≤40000。 信息的输入格式：N A1B1H1 A2B2H2 … ANBNHN 要求输出平面上被这些矩形覆盖的部分的面积。 ④应用线段树解决二维图形上的计算几何问题，平面上有 N 个矩形，矩形 的边平行于坐标轴。每个矩形左下角和右上角的坐标是（xli,yli）和（xui,yui）， i=1,…,N。其中坐标值的范围是[-10000,10000]，1≤N≤5000。 输入格式： N xl1yl1xu1yu1 xl2yl2xu2yu2 … xlNylNxuNyuN 要求输出平面上被这些矩形覆盖的部分轮廓的周长。 （4）实现提示 对于要求③，在节点结构中增加 intheight 即节点对应线段被覆盖的高度，初 始为 0。 并在每个插入点 p 处执行 p->height=max{h,p->height}。所有矩形都处理完以 后，就可以求总面积了。下面的过程 area（h,p）将节点 p 对应的区间上高度 的部分的面积累加到变量 sumarea 中：area（h,p），1.diff=p->height-h；2.若 diff>0， 则执行 sumarea+=diff（p->xright-p->xleft）；h=p->height；3.若 p->left 非空，则 执行 area（h,p->left）；area（h,p->right）。 对于要求④，核心是设计一条竖直扫描线，从左到右扫描，每当扫描线固定 在某个位置时，计算该扫描线被这些矩形覆盖的部分的长度（不妨称为扫描到的 长度）和被这些矩形覆盖的区间的段数（不妨称为扫描到的段数）。例如，当扫 描线位于虚线所在位置时，扫描到的段数是 2 段；扫描到的长度自然是这两段长 度的和。注意到下面的事实：一是扫描到的长度和段数只有在扫过矩形的竖直边 时才会发生变化。二是当扫描线从位置 1 移到位置 2 时：[2位置 1 扫描到的段 数（位置 2 横坐标-位置 1 横坐标）]就是扫描线从位置 1 到位置 2 扫描到的水 平轮廓的长度,[abs（位置 2 扫描到的长度-位置 1 扫描到的长度）]就是扫描线在 位置 2 遇到的竖直轮廓的长度。需要说明的是：当扫描线恰好位于一条竖直边上 时，其扫描到的长度和段数是有歧义的，定义此时扫描到的长度和段数为扫描线 位于竖直边右边任意近位置时扫描到的长度和段数。后面的实际算法是一条竖直 边一条竖直边的扫描的，如果有两条竖直边横坐标相同，那么求出的长度和段数 与这里定义类似，只是分步得到。由上面的观察，计算轮廓周长 sum 的过程大 致如下：（1）初始设 sum=0，scanlength=0，scanseg=0，scanpos=-10000。 （2）找下一条竖直边（x,low,up）=（竖直边的横坐标，下端点的纵坐标， 上端点的纵坐标），计算当前扫描到的长度 newscanlength 和段数 newscanseg。 sum+=2scanseg*（x-scanpos）; sum+=abs（newscanlength-scanlength）; scanlength=newscanlength;scanseg=newscanseg; scanpos=x; （3）若还有竖直边未扫描，则转（2）。