种操作。
要求：一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：
例如，图1所表示的二叉树可以用二叉树序列S=21200110来表示。
图1 二叉树序列示意图
任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。 题5：打印机任务队列
目的：通过本课程设计，应使学生掌握队列的基本方法和基本原理，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
要求：打印机的打印队列中，每一个打印任务都有一个优先级，为1~9的一个整数（9的优先级最高，1的优先级最低），打印按如下方法进行。
（1）取出打印队列中队首的打印任务J；
（2）如果打印队列中存在优先级高于J的打印任务，则将J移动到打印队列的队尾；否则，打印J.
现在的问题是，要确定你要打印的文件何时打印完毕。给定当前打印队列（一个优先级队列）和你的打印任务在当前打印队列中的位置，确定你的打印任务完成时需要多长时间。为了简化问题，假定没有新的打印任务加入到打印队列中；并且，假定完成任何一个打印任务均需要1min时间，向打印队列中加入一个打印任务或从打印队列中移除一个打印任务不需要时间。
例如，当前打印队列为“1 1 9 1 1 1”且你的打印任务在队首时，需要5min。 题7：求解布尔表达式
目的：本课程设计是求中缀算术表达式真值问题。求中缀算术表达式值的问题是数据结构中栈的一个典型应用。通过本题，学生应掌握中缀表达式和后缀表
达式的转换方法和后缀表达式求值问题。
要求：已知某种类型的布尔表达式由“V”、“F”、“！”、“&”和“|”组成，其中，“V”代表真值True，“F”代表真值False，“！”代表逻辑非运算，“&”代表逻辑或运算。并且，运算符“！”、“&”和“|”的优先级为：“！”最高，“|”最低，“&”介于“！”和“|”之间。你的任务是，计算给定布尔表达式的真值。
例如，布尔表达式“(V|V)&F&(F|V)”的真值为“F”. 题8：谣言传播问题
目的：通过本课程设计，应使学生掌握如何用图结构解决实际问题的能力，加深对于图结构的理解和认识。掌握图的存储方法和关于图的经典算法。提高学生的程序设计能力。
要求：股票经纪人往往对谣言很敏感，你老板希望你能找到一个好方法向他们散布谣言，从而使他在股市占有战术优势。为了达到最有效果，需要谣言传播的尽量快。不幸的是，股票经纪人只相信从他们信任的信源传播来的消息，因此，在你散布谣言之前，需要对他们的联系网进行详细考察。对于一个股票经纪人，他需要一定时间才能将信息传送给他联系人，给你这些信息，你的任务是，决定选谁作为第一个传送谣言的人，以使谣言传遍所有人的时间最短，当然，如果谣言不能传遍所有人的话，你也要给出说明。
例如，假设共有3个联系人，联系人1传递信息给联系人2和3所有的时间分别为4和5；联系人2传送信息给联系人1和3所有的时间分别为2和6；联系人3传送信息给联系人1和2所有的时间均为2，则选择联系人3作为第一个传送谣言的人，可以使谣言传遍所有的人时间最短，为2.
（选择有向图中的一个源点，使它到其余各顶点的最短路径中最长的一条路径最短） 题9：分形问题
目的：递归是基本的算法思想和设计方法之一，也是数据结构重点讲授的部分，是许多算法的基础，对它们的理解和运用直接关系着其他算法的理解和应用。因此，熟练掌握递归是十分重要的。通过本题，应使学生加深对于递归方法的理解，提高运用递归解决问题的能力。
要求：分形是一种具有自相似性的现象，在分形中，每一组成部分都在特征上和整体相似，只不过仅仅是缩小了一些而已，一种盒子分形定义如下：
（1）规模为1的盒子分形为
X
（2）规模为2的盒子分形为
X X
X X X
（3）若用B(n - 1)表示规模为n-1的盒子分形，则规模为n的盒子分形为
B(n - 1) B(n - 1)
B(n - 1)
B(n - 1) B(n - 1)
你的任务是，输出规模为n的盒子分形。例如，规模为3的盒子分形输出如下：
X X X X X X X X X X
X X X X X
X X X X X X X X X X
题10：网络布线
计算机网络要求网络中的计算机被连接起来，本问题考虑一个“线性”的网络，在这一网络中计算机被连接到一起，并且除了首尾的两台计算机只分别连接着一台计算机外，其它任意一台计算机恰连接着两台计算机。图2中用圆点表示计算机，它们的位置用直角坐标表示。网络连接的计算机之间的距离单位为英尺。
图2 网络布线示意图
由于很多原因，我们希望使用的电缆长度应可能地短。你的问题是去决定计算机应如何被连接以使你所使用的电缆长度最短。在设计方案施工时，电缆将埋在地下，因此连接两台计算机所要用的电缆总长度等于计算机之间的距离加上额外的16英尺电缆，以从地下连接到计算机，并为施工留一些余量。
图3是计算机的最优连接方案，这样一个方案用电缆的总长度是 (4 + 16) + (5 + 16) + (5.38 + 16) + (11.18 + 16) = 90.01英尺
图3 最优连接方案示意图
要求：
（1）基本要求：
输入网络中的计算机总数和每台计算机的坐标。
输出使电缆长度最短的连接方案。给出最优连接方案中每两台相邻计算机之间的距离，以及总的电缆长度。
（2）提高要求：
参考图2、图3，用图形化的方式显示结果，包括点的坐标、最优路径、相邻计算机之间的距离。 题11：数独游戏
在一个9×9的大正方形中，包含9个3×3的小正方形。如图4所示。可以看到，其每行、每列、每个小正方形，都有9个空格。
图4 数独游戏棋盘示意图
要求只用1到9这些数字，填满大正方形中所有的81个空格，同时满足： （1）在每列的9个空格中分别填入1到9，且每个数字在此列中只能出现一次； （2）在每行的9个空格中分别填入1到9，且每个数字在此行中只能出现一次；
（3）在每个小正方形的9个空格中分别填入1到9，且每个数字在此正方形中只能出现一次；
游戏一开始会给定了某些空格的值。参加游戏的人根据这些已知的值以及上面的约束条件，推理出剩余的空格的值。
图5 数独题目示例
图6 解题结果