下载文档原格式
并行计算期末试题及答案1. 基础概念部分并行计算是一种计算模式，它使用多个处理单元同时执行计算操作，以加快计算速度。
在现代计算机系统中，我们常常使用多核处理器、图形处理器（GPU）或者分布式系统来实现并行计算。
1.1 并行计算的优势并行计算具有以下几个优势：加速计算速度：通过同时执行多个计算任务，可以极大地提高计算效率。
解决大规模问题：并行计算可以处理大规模和复杂的问题，提供更精确的结果。
降低能耗：通过合理利用处理器资源，可以降低计算任务的能耗。
应用广泛：并行计算可以应用于各个领域，如科学计算、大数据分析、机器学习等。
1.2 并行计算的分类并行计算按照任务之间的关系可以分为两类：数据并行：将数据划分为多个子集，同时在不同的处理器上进行计算，然后将计算结果汇总。
常见的应用包括矩阵运算、图像处理等。
任务并行：将任务划分为多个子任务，每个子任务由一个独立的处理器执行，最后将各个子任务的结果合并。
常见的应用包括并行搜索算法、并行排序等。
2. 并行计算的算法设计2.1 并行算法设计要点在设计并行算法时，需要考虑以下几个要点：任务划分：将计算任务划分为多个子任务，确保各个子任务之间的计算工作均衡，并保持任务之间的独立性。
任务调度：合理安排各个处理器上的任务执行顺序和时间，最大程度地减少通信开销和等待时间。
数据通信：处理器之间需要进行数据交换和通信，应选择合适的通信方式，并考虑通信延迟和带宽等因素。
数据同步：在多个处理器之间，可能需要进行数据同步操作，确保各个处理器之间的数据一致性。
2.2 并行算法实例：并行矩阵乘法并行矩阵乘法是一个常见的数据并行算法，可以有效地利用多核处理器加速大规模矩阵运算。
具体算法如下：步骤1：将输入矩阵划分为若干个小矩阵，每个小矩阵分配给一个处理器。
步骤2：每个处理器计算相应小矩阵的部分结果。
步骤3：将各个处理器计算得到的部分结果进行求和，得到最终的矩阵乘积结果。
3. 并行计算的应用举例3.1 科学计算在科学计算领域，有大量的计算任务需要处理大规模的数据和复杂的数学模型。
第十二章 并行程序设计基础习题例题：1、假定有n 个进程P(0)，P(1)，…，P(n -1)，数组元素][i a 开始时被分配给进程P(i )。
试写出求归约和]1[]1[]0[-+++n a a a 的代码段，并以8=n 示例之。
2、假定某公司在银行中有三个账户X 、Y 和Z ，它们可以由公司的任何雇员随意访问。
雇员们对银行的存、取和转帐等事务处理的代码段可描述如下：/*从账户X 支取￥100元*/atomic {if (balance[X] > 100) balance[X] = balance[X]-100； }/*从账户Y 存入￥100元*/atomic {balance[Y] = balance[Y]-100；}/*从账户X 中转￥100元到帐号Z*/atomic {if (balance[X] > 100){balance[X] = balance[X]-100；balance[Z] = balance[Z]+100；} }其中，atomic {}为子原子操作。
试解释为什么雇员们在任何时候（同时）支、取、转帐时，这些事务操作总是安全有效的。
3、考虑如下使用lock 和unlock 的并行代码：parfor (i = 0；i < n ；i++){noncritical sectionlock(S)；critical sectionunlock(S)；}假定非临界区操作取T ncs时间，临界区操作取T cs时间，加锁取t lock时间，而去锁时间可忽略。
则相应的串行程序需n( T ncs + T cs )时间。
试问：①总的并行执行时间是多少？②使用n个处理器时加速多大？③你能忽略开销吗？4、计算两整数数组之内积的串行代码如下：Sum = 0；for(i = 0；i < N；i++)Sum = Sum + A[i]*B[i]；试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。
1、名词解释：（1）等分宽度：把网络划分为两个相等的部分（节点数之多差1），所需要去掉的网络边的条数。
（2）网络直径：网络中两个节点之间的最远的距离（3）并行运行时间：从第一台处理机开始执行任务开始，到最后一台处理机执行完任务所经历的时间。
（4）并行步：能够同时执行的操作数。
（5）加速比：同一任务在串行计算下的运行时间/并行计算下的运行时间。
2、介绍超立方体网络互连方式的性能指标解答：q维超立方体，等分宽度为2q-1，网络直径：q，网络接口数：q3、按照指令流和数据流，并行计算机可以分为哪些类型？各自适合什么样的并行计算？排名在前20的计算机都是什么类型的计算机？它们的区别是什么？解答：（1）SIMD：适合指令/操作级并行（2）MIMD：适合块、回路或子程序级的并行4、并行算法有哪些设计方法？（1）流水线技术（2）分而治之策略（3）平衡二叉树方法（4）倍增技术（5）加速级联策略5、举例说明平衡树方法的原理？参考：使用n/2台计算机，可以在⎡⎤nlog步完成运算。
26、Logp模型有哪些参数？BSP模型有哪些参数？这两个模型之间的关系是什么？（1） L ：源处理机与目标处理机之间进行消息通信所需要等待的延迟时间上限（2） o ：处理机用于发送或接收每个消息的时间开销（3） g ：连续发送/接收消息的时间间隙（4） P ：处理机个数BSP 模型：（1） P ：处理机数（2） g ：选路器吞吐率（3） L ：全局同步之间的时间间隔关系：（1） 本质上等效，可以相互模拟（2） 用BSP 模拟LOGP 所进行的计算时，通常会慢常数倍。
（3） 反之，慢对数倍7、 题目记不清了，只要知道两个公式就可以了，对于logp ：L+2o 对于logGp ：t α+t β8、 计算加速比和效率的题，具体记不清了，只要会使用公式就可以了。
9、 关于群集系统中QR 分解的题目。
将矩阵的行列都分成5等分，得到它的25个任务，按照贪婪算法的调度思想，画出子任务执行的并行步。
！第１题（1）什么是并行计算（2）它的优点有哪些（3）可以通过哪些结构完成并行计算1．并行计算就是在并行计算或分布式计算机等高性能计算系统上所做的超级计算。
（P3）2．计算极大地增强了人们从事科学研究的能力，大大地加速了把科技转化为生产力的过程，深刻地改变着人类认识世界和改造世界的方法和途径。
计算科学的理论和方法，作为新的研究手段和新的设计与创造技术的理论基础，正推动着当代科学与技术向纵深发展。
（P4）3．单指令多数据流SIMD、对称多处理机SMP、大规模并行处理机MPP、工作站机群COW、分布共享存储DSM多处理机。
（P22）第2题什么是网络计算它的特点它与分布式计算、集群计算的关系（P104）网络计算：在工作站机群COW环境下进行的计算称为网络计算。
特点：网络计算结合了客户机/服务器结构的健壮性、Internet面向全球的简易通用的数据访问方式和分布式对象的灵活性，提供了统一的跨平台开发环境，基于开放的和事实上的标准，把应用和数据的复杂性从桌面转移到智能化的网络和基于网络的服务器，给用户提供了对应用和信息的通用、快速的访问方式。
与分布式计算、集群计算的关系：，分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。
集群计算是使用多个计算机，如典型的个人计算机或UNIX工作站；多个存储设备；冗余互联，来组成一个对用户来说单一的高可用性的系统。
因此，网络计算与分布式计算和集群计算都是属于计算密集型，数据密集型和网络密集型应用。
第3题表征并行系统的性能指标有哪些并行系统的加速比如何定义它能否完全确定系统的性能为什么a.表征并行系统的性能指标主要有：CPU和存储器的基本性能指标，通信开销以及系统机器的成本、价格与性价比，还有系统加速比和系统可扩放性（p88页）；其中CPU和存储器的基本性能指标包括：工作负载，并行执行时间，存储器的层次结构和存储器的带宽。
并行计算的参考题目1、讨论某一种算法的可扩放性时，一般指什么？88答：讨论某一种算法的可扩放性时，实际上是指该算法针对某一特定机器结构的可扩放性2、使用“Do in Parallel”语句时，表示的是什么含义105答：表示算法的若干步要并行执行3、并行计算机的存储访问类型有哪几种？26答：存储访问类型有：UMA（均匀存储访问）、NUMA（非均匀存储访问）、COMA（全高速缓存存储访问）、CC-NUMA（高速缓存一致性非均匀存储访问）、NORMAl（非远程存储访问）4、什么是同步？它有什么作用？如何实现？107答：同步是在时间上强使各执行进程在某一点必须相互等待。
作用：确保个处理器的正确工作顺序以及对共享可写数据的正确访问（互斥访问）。
实现方法：用软件、硬件和固件的方法实现。
5 在并行加速比的计算中，常用的三种加速比定律分别是哪三种？（P83）答：常用的三种加速比定律分别是：适用于固定计算负载的Amdahl定律，适用于可扩放问题的Gustafson定律和受限于存储器的Sun和Ni定律。
6、试比较Amdahl定律、Gustafson定律、Sun和Ni定律三种加速定律的应用场合。
83 答：Amdahl定律适用于固定计算负载的问题Gustafson定律适用于可扩放性问题Sun和Ni定律适用于受限于存储器的问题。
7.并行算法的基本设计技术有哪些？它们的基本思想是什么？139答：(1)基本技术有：划分设计技术(又分为均匀划分技术、方根划分技术、对数划分技术和功能划分技术)、分治设计技术、平衡树设计技术、倍增设计技术、流水线设计技术等。
(2)基本思想分别如下：a.划分设计技术：(P139) 将一原始问题分成若干部分，然后各部分由相应的处理器同时执行。
b.分治设计技术：(P144)将一个大二复杂的问题分解成若干特性相同的子问题分而治之。
若所得的子问题规模仍嫌过大，可反复使用分治策略，直至很容易求解诸子问题为止。
并行计算 - 练习题2021年《并行计算系统》复习题1. （15分）给出五种并行计算机体系结构的名称，并分别画出其典型结构。
①并行向量处理机（PVP）②对称多机系统（SMP）③大规模并行处理机（MPP）④分布式共享存储器多机系统（DSM）⑤工作站机群（COW）2. （10分）给出五种典型的访存模型，并分别简要描述其特点。
①均匀访存模型（UMA）：物理存储器被所有处理机均匀共享所有处理机访存时间相同适于通用的或分时的应用程序类型②非均匀访存模型（NUMA）：是所有处理机的本地存储器的集合访问本地LM的访存时间较短访问远程LM的访存时间较长③Cache一致性非均匀访存模型（CC-NUMA）： DSM结构④全局Cache访存模型（COMA）：是NUMA的一种特例，是采用各处理机的Cache组成的全局地址空间远程Cache的访问是由Cache目录支持的⑤非远程访存模型（NORMA）：在分布式存储器多机系统中，如果所有存储器都是专用的，而且只能被本地存储机访问，则这种访问模型称为NORAM 绝大多数的NUMA支持NORAM 在DSM中，NORAM的特性被隐匿的3. （15分）对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明该网络是否是一个对称网络。
网络直径：8 节点的度数：2对剖宽度：2该网络是一个对称网络4. （15分）设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时，不可并行化的部分为1个小时。
问：（1）该程序的串行比例因子是多少，并行比例因子是多少？串行比例因子：1/10 并行比例因子:9/10（2）如果有10个处理机并行执行该程序，可达到的加速比是多少？ 10/(9/10 + 1) = 5.263（3）如果有20个处理机并行执行该程序，可达到的加速比是多少？ 10/(9/20 + 1)= 6.8975. （15分）什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？一个计算机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处理机数目的增加而按比例提高。
并⾏计算考试复习1在并⾏机系统中，主流操作系统有UNIX/Linux，AIX(IBM)，HPUX(HP)，Solaris(SUN)，IRIX(SGI)等。
2 常⽤的并⾏算法设计的基本技术有划分，分治，倍增，流⽔域，破对称，平衡树等设计技术。
3 Matlab并⾏程序编写过程分为创建对象，创建⼯作，指定⼯作任务，提交⼯作，等待和返回计算任务结果六步。
1. 云计算是对（ D ）技术的发展与运⽤A. 并⾏计算 B⽹格计算 C分布式计算 D三个选项都是2. IBM在2007年11⽉退出了“改进游戏规则”的（ A ）计算平台，为客户带来即买即⽤的云计算平台。
A. 蓝云B. 蓝天C. ARUZED. EC23. 微软于2008年10⽉推出云计算操作系统是（ C ）A. Google App EngineB. 蓝云C. AzureD. EC24. 2008年，（ A ）先后在⽆锡和北京建⽴了两个云计算中⼼A. IBMB. GoogleC. AmazonD. 微软5. 将平台作为服务的云计算服务类型是（ B ）A. IaaSB.PaaSC.SaaSD.三个选项都不是6. 将基础设施作为服务的云计算服务类型是（ A ）A. IaaSB.PaaSC.SaaSD.三个选项都不是7. IaaS计算实现机制中，系统管理模块的核⼼功能是（ A ）A. 负载均衡 B 监视节点的运⾏状态 C应⽤API D. 节点环境配置8. 云计算体系结构的（ C ）负责资源管理、任务管理⽤户管理和安全管理等⼯作B. 资源池层C. 管理中间件层D. SOA构建层9. 下列不属于Google云计算平台技术架构的是（ D ）A. 并⾏数据处理MapReduceB.分布式锁ChubbyC. 结构化数据表BigTableD.弹性云计算EC210. 在⽬前GFS集群中，每个集群包含（ B ）个存储节点A.⼏百个B. ⼏千个C.⼏⼗个D.⼏⼗万个11. 下列选项中，哪条不是GFS选择在⽤户态下实现的原因（ D ）A.调试简单B.不影响数据块服务器的稳定性C. 降低实现难度，提⾼通⽤性D. 容易扩展12. GFS中主服务器节点存储的元数据包含这些信息（ BCD ）A.⽂件副本的位置信息B.命名空间C. Chunk与⽂件名的映射D. Chunk副本的位置信息13. 单⼀主服务器（Master）解决性能瓶颈的⽅法是（ ABCD ）A.减少其在数据存储中的参与程度B. 不适⽤Master读取数据C.客户端缓存元数据D. 采⽤⼤尺⼨的数据块14. （ B ）是Google提出的⽤于处理海量数据的并⾏编程模式和⼤规模数据集的并⾏运算的软件架构。
计算机学院研究生《并行计算》课程考试试题（2010级研究生，2011.1）1．（12分）定义图中节点u 和v 之间的距离为从u 到v 最短路径的长度。
已知一个d 维的超立方体，1）指定其中的一个源节点s ，问有多少个节点与s 的距离为i ，其中0≤i ≤d 。
证明你的结论。
2）证明如果在一个超立方体中节点u 与节点v 的距离为i ，则存在i ！条从u 到v 的长度为i 的路径。
1)有id C 个节点与s 的距离为i 。
证明：由超立方体的性质知：一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有id C 种选择方式，即与s 的距离为i 得节点就有id C 个。
2)证明：由1）所述可知：节点u 与节点v 的距离为i 则分别表示u 、v 节点的二进制位数中有i 位是不同的。
设节点u 表示为：121D .........j j i j i d D D D D D +-+，节点v 表示为：''121D .........j j i j i dD D D D D +-+，则现在就是要求得从121D .........j j i j i d D D D D D +-+变换到''121D .........j j i j i d D D D D D +-+ 的途径有多少种。
那么利用组合理论知识可知共有*(1)*(2)*...*2*1i i i --即!i 中途径。
所以存在i ！条从u 到v 的长度为i 的路径。
2．（18分）6个并行程序的执行时间，用I-VI 表示，在1-8个处理器上执行了测试。
下表表示了各程序达到的加速比。
对其中的每个程序，选出最适合描述其在16个处理器上性能的陈述。
a ） 在16个处理器上的加速比至少比8个处理器上的加速比高出40%。
b ） 由于程序中的串行程序比例很大，在16个处理器上的加速比不会比8个处理器上的加速比高出40%。
c ） 由于处理器增加时开销也会很大，在16个处理器上的加速比不会比8个处理器上的加速比高出40%。
给出分析过程和结论。
3. （10分）经测试发现，1）一个串行程序，94%的执行时间花费在一个可以并行化的函数中。
现使其并行化，问该并行程序在10个处理机上执行所能达到的加速比是多少？能达到的最大加速比是多少？2）一个并行程序，在单个处理机上执行，6%的时间花费在一个I/O 函数中，问要达到加速比10，至少需要多少个处理机？ 1）由Amdahl 定律知：加速比1(1)/Speedup f f p=+-依题意知：6%,10f p ==代入计算得：16.4994%6%10Speedup =≈+最大加速比为：111lim lim16.7(1)/6%p pSpeedupf f p f→∞→∞===≈+-2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%f f pp≤=+-+得：23.5p≥故至少需要24台处理机。
4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？2）若超立方体中的结点10110011和进行通讯，如果按照环网拓扑结构，从出发，在超立方体中依次经过哪些节点才能把一条消息传递到？如果按照超立方体拓扑结构，又是如何实现从传递一条消息到的？5．（16分）已知12个具有单位执行时间的任务，任务图如下。
现在3个处理机上处理该任务集，请用Coffman-Graham算法求该任务集的调度优先表L，并用Graham表调度算法调度L，给出任务调度的Gantt图表示。
6．（10分）采用与前序遍历二元树的PRAM算法相同的数据结构，设计一个后序遍历二元树的PRAM算法。
7．（10分）下面是一个串行程序段，用OpenMP最大限度地开发其并行性。
这里假设a、b均为正实值数组，有合法的定义。
float rowterm[m]float colterm[q];int i, j;#pragma omp parallel {#pragma omp sections{#pragma omp parallel for private(j)for ( i=0; i<m; i++) {rowterm[i] = 0.0;#pragma omp parallel for reduction(+:rowterm[i])for (j=0; j<p; j++)rowterm[i] += a[i][2*j] * a[i][2*j+1];#pragma omp parallel forfor (j=0; j<p; j++) {a[i][2*j] /= rowterm[i];a[i][2*j+1] /= rowterm[i];}}}#pragma omp sections{#pragma omp parallel for private(j)for ( i=0; i<q; i++) {colterm[i] = 0.0;#pragma omp parallel for reduce(+:colterm [i])for ( j=0; j<p; j++)colterm[i] += b [2*j][i] * b [2*j+1] [i];#pragma omp parallel forfor ( j=0; j<p; j++) {b [2*j][i] /= colterm[i]; b [2*j+1] [i] /= colterm[i];}} } }8．（12分）查阅文献并结合自己的体会，列举1-2个你的研究领域里存在的典型并行计算应用，讨论一下它们适合的并行计算模式（不少于500字）。
答案1. 证明：（1）由超立方体的性质知： 一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有id C 种选择方式，即与s 的距离为i 得节点就有id C 个。
（2)由(1)所述可知：节点u 与节点v 的距离为i 则分别表示u 、v 节点的二进制位数中有i 位是不同的。
设节点u 表示为：121D .........j j i j i d D D D D D +-+，节点v 表示为：''121D .........j j i j i dD D D D D +-+，则现在就是要求得从121D .........j j i j i d D D D D D +-+变换到''121D .........j j i j i d D D D D D +-+ 的途径有多少种。
那么利用组合理论知识可知共有*(1)*(2)*...*2*1i i i --即!i 中途径。
所以存在i ！条从u 到v 的长度为i 的路径。
2. 解： 由题可知计算规模是固定的，所以在并行环境下，根据Amdahl 定律可知： 加速比S=1/(1/p+f(1-1/p))，其中p 为处理器数，f 为串行分量的比例，则，f=(p/s-1)/(p-1)，同时对于固定规模的问题，并行系统所能达到的加速上限为1/f ，即受到串行分量的比例的限制。
在2个处理器的环境下，根据上图数据计算各并行程序的串行分量的比：并行程序I ：f 1=0.20; 并行程序II ：f 2=0.06; 并行程序III ：f 3=0.06; 并行程序IV ：f 4=0.02; 并行程序V ：f 5=0.15; 并行程序VI ：f 6=0.03;在16个处理器的环境下，根据上图数据计算各并行程序的加速比如下： 并行程序I ：S 1=4.00并行程序II ：S 2=5.72; 并行程序III ：S 3=8.41; 并行程序IV ：S 4=10.00; 并行程序V ：S 5=4.77; 并行程序VI ：S 6=10.67;则个并行程序在16个处理器的环境下与8个处理器的环境下的加速比提高了：并行程序I ：d 1=20%; 并行程序II ：d 2=31%; 并行程序III ：d 3=49%; 并行程序IV ：d 4=60%; 并行程序V ：d 5=25%; 并行程序VI ：d 6=64%;根据并行程序I 、V 的串行分量的比和16个处理器的环境下的加速比可知，对并行程序I 、V 在16个处理器上性能的陈述都选(b);根据并行程序II 和III 的串行分量的比和16个处理器的环境下的加速比可知，对并行程序II 在16个处理器上性能的陈述选(c);根据并行程序III 、IV 、VI 在16个处理器的环境下的加速比可知，对并行程序III 、IV 、VI 在16个处理器上性能的陈述都选(a);3. 1）由Amdahl 定律知：加速比1(1)/Speedup f f p=+-依题意知：6%,10f p ==代入计算得：16.4994%6%10Speedup =≈+最大加速比为：111lim lim16.7(1)/6%p pSpeedupf f p f→∞→∞===≈+-2)由题意知：此时的串行时间比例为6%则：由式子111094%(1)/6%f f pp≤=+-+得：23.5p≥故至少需要24台处理机。
4．（12分）将一个由256个节点组成的环以dilation-1的方式嵌入到一个8维超立方体里，环中的节点编号为0~255，1）问环节点31，127，255分别映射到超立方体的哪个节点上？31:00010000;127:01000000;255:10000000若超立方体中的结点和进行通讯，如果按照环网拓扑结构，从出发，在超立方体中依次经过哪些节点才能把一条消息传递到？如果按照超立方体拓扑结构，又是如何实现从传递一条消息到0101 1001的？1011 0011: 2210101 1001：1101011 0011(221)->1011 0001(222)->1011 0000(223)->1001 0000(224)->1001 0001->……->1000 0000(255)->0000 0000(0)->0000 0001->…..->0101 1100（104）->0101 1101（105）->0101 1111（106）->0101 1110（107）->0101 1010（108）->0101 1011（109）->0101 1001（110）1011 0011->1011 0001->1011 1001->1001 1001->1101 1001->0101 1001(第一种方法)1011 0011->0011 0011->0111 0011->0101 0011->0101 1011->0101 1001(第二种方法)1101 0011->1001 0011->1101 0011->0101 0011->0101 0001->0101 1001(第三种方法)5.Step1：R=｛T11,T12｝是无直接后继的任务，任取，选T12,有a(T12)<-1；Step2：i从2到12循环，完成对a(Tj)(j=1,2…12)赋值i=2；R=｛T11，T10｝，N(T10)=｛1｝，N(T10)={0}，选T11，则a(T11)<-2；i=3; R=｛T9，T6，T10｝，N(T9)=2,N(T6)={2,1},N(T10)=1,选T10则a(T10)<-3;i=4;R={T9,T6,T7,T8},N(T9)=2,N(T6)={2,1},N(T7)=3,N(T8)=3,T9，T6任选，选T6，a(T6)<-4;i=5;R={T9,T7,T8},N(T9)=2,N(T7)=3,N(T8)=3,选T9，则a(T9)<-5;i=6;R={T4,T5,T7,T8},N(T4)=5,N(T5)=5,N(T7)=3,N(T8)=3,任选T7，T8，选T7，则a(T7)<-6;i=7;R={T4,T5,T8},N(T4)=5,N(T5)=5,N(T8)=3,选T8，则a(T8)<-7;i=8;R={T4,T5,T3},N(T4)=5,N(T5)=5,N(T3)={7,6}，T4，T5任选,选T4，则a(T4)<-8 i=9,R={T5,T3},N(T5)=5,N(T3)={7,6},选T5，则a(T5)<-9;i=10,R={T2,T3},N(T2)={9,8,4},N{T3}={7,6}，选T3，a(T3)<-10;i=11,R={T2},N(T2)={9,8,4}，选T2，a(T2)<-11;i=12,a(T1)<-12;Step3：构造L表：L=｛T1,T2,T3,T5,T4,T8,T7,T9,T6,T10,T11,T12｝；Step4:6. 策略如下：在执行后序遍历时，我们系统地访问树中所有的边，而且每条边要通过两次：一次从父节点到子节点，而另一次从子节点到父节点。
