华中师范大学网络教育学院《算法设计与分析》练习题库及答案

《算法设计与分析》练习题库及答案(加粗红色字体为2013下新增题目)概念题：请解释下列术语。1．数据类型2．队列3．多项式复杂度4．满二叉树5．NP-难度6．算法7．SIMD(并行算法)8．连通图9．抽象数据类型10．指数复杂度11．递归12．完全二叉树13．状态空间树14．NP-完全的15．算法与过程16．有向图与无向图17．树18．P类问题19.确定的算法20.NP问题21.最小生成树22.动态规划23.数据结构24.排序二、填空题1.简单递选分类过程中所需进行移动存储的操作次数较少，其最大值为___________。2.一组有序的n个数，采用逐个查找算法查找一给定的数是否出现在序列中，其算法复杂性为_____________。3.动态规划实际上是研究一类__________________的算法，其应用非常广泛。4.BFS算法的中文名称是______________________算法。5.一棵树中定义为该树的高度或深度。6.二分检索树要求树中所有结点中的元素满足。7.比较树的结点由称为和的两种结点组成。8.外结点用一个结点表示，在二分检索算法中它表示不成功检索的一种情况。9.由根到所有内部结点的距离之和称为;由根到所有外部结点的距离之和称为.10．max和min被看成是两个内部函数，它们分别求取两个元素的大者和小者，并认为每次调用其中的一个函数都只需作次元素比较。11．如果用分治策略来设计分类算法，则可使最坏情况时间变为o(nlogn)。这样的算法称为。12.贪心算法可行的第一个基本要素是。13.当一个问题的最优解包含着它的子问题的最优解时，称此问题具有性质。14.二路归并模式可以用树来表示。15.kruskal算法对于每一个无向连通图g产生一棵。16．因为如果有环，则可去掉这个环且不增加这条路径的长度(不含有负长度的环)。如果k是这条最短路径上的一个中间结点，那么—由i到k和由k到j的这两条子路径应分为别是由i到k和．由k到j的最短路径。否则，这条由i到j的路径就不是具有最小长度的路径。于是，原理成立。17.为了把动态规划应用于得到一棵最优二分检索树的问题，需要把构造这样的一棵树看成是一系列决策的结果，而且要能列出求取序列的递推式.18.所谓可靠性设计最优化问题是在的约束下，如何使系统的可靠性达到最优的问题。19.货郎担问题是求取具有的周游路线问题。20.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：__________，__________，__________，__________，__________。21.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是___________。22.某一问题可用动态规划算法求解的显著特征是_____________________。23.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。三、程序填空题。1．对二叉树的先根次序周游算法递归表示为：procedurePREORDER(T)//T是一棵二元树。T中每个结点有三个信息段：ICHILD，，DATA，RCHILD//ifT≠0thencallVISIT(T)__________(1)_____________________(2)___________endifendPREORDER2．递归求取最大和最小元素procedureMAXMIN(i．j.fmax，fmin)//A(1：n)是含有n个元素的数组，参数i，j是整数，1≤i，j≤n////该过程把A(i，j)中的最大和最小元素分别赋给fmax和fmin//integeri，j；globaln，A(1：n)case ：i=j：fmaxßfminßA(i) ：i=j-1：ifA(i)<A(j)thenfmaxßA(j)；fminßA(i)elsefmaxßA(i)；fminßA(j)endif:else:midß___________(1)_________________________(2)______________ fmaxßmax(gmax，hmax)fminßmin(gmin，hmin)endcaseendMAXMIN3．用回溯法求子集和数问题的递归回溯算法procedureSUMOFSUB<s，k，r)//找W(1：n)中和数为M的所有子集，进入此过程时X(1)，…，X(k-1)的值已确定。。这些对Ｗ(j)按非降次序排列。假定W(1)≤M.//globalintegerM，n;globalrealW(1：n)；globalBooleanX(1：n)realr,s；integerk，j//生成左儿子。注意，由于，因此s+W(k)≤M// X(k)ß1 ifs+W(k)=Mthen//子集找到／／ print(X(j),jß1tok)elseifs+W(k)+W(k+1)<=Mthen//B=yrue//______________(1)__________________endif//生成右儿子和计算B的值//endif ifs+r-W(k)≥Mands+W(k+1)≤M／／B＝true／／thenX(k)ß0_______________(2)_________________ endifendSUMOFSUB4．用回溯法求n-皇后问题的所有解procedureNQUEENS(n)//此过程使用回溯法求出在一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置//integerk，n，X(1:n)X(1)ß0；kß1//k是当前行；X(k)是当前列//whilek>0do//对所有的行执行以下语句//X(k)ßX(k)+1//移到下一列//whileX(k)≤nandnotPLACE(k)do//此处能放这个皇后吗//____________(1)___________repeatifX(k)≤n//找到一个位置//thenifk＝n//是一个完整的解吗//thenprint(X)//是，打印这个数组//else_______(2)_______；_______(3)_______；//转向下一行//endifelse_______(4)_______//回溯//endifrepeatendNQUEENS5.二分查找算法procedurebinsrch1(a，n，x，j)//除n>0外，其余说明与binsrch同//integerlow，high，mid，j，n;lowß1;highß(1)//high总比可能的取值大1//whilelow<(2)domidßifx<a(mid)//在循环中只比较一次//then(3)else(4)//x≥a(mid)//endifrepeatifx=a(low)thenjßlow//x出现//elsejßo//x不出现//endif；endbinsrch16.求图中每对顶点之间的最短路径。procedureall—Paths(cost，a,n)／／cost(n，n)是n结点图的成本邻接矩阵；a(i，j)是结点vi到vj的最短路径的成本；cost(i，j)＝0，1≤i≤n／／integeri，j，k，n；realcost(n，n)，a(n，n)foriß1tondoforj<--1tondoa(i，j)<--cost(i，j)repeatrepeat／／将cost(i，j)复制到a（i,j）／／fork<--1toondo／／对最高下标为k的结点的路径//foriß-1tondo／／对于所有可能的结点对／／fori<--1tondoa(i，j)<--min{(1)，(2)}repeatrepeatrepeatendall—Paths7.简单的合并与查找运算procedureu(i，j)//根为i和j的两个不相交集合用它们的并来取代//integeri，jParent(i)<--j;enduproceduref(i)//找包含元素i的树的根//integeri，jj<--i;while⑴do//若此结点是根，则Parent(j)<--0//⑵;repeatreturn(j)endf8.插入分类procedureinsertionsort(a，n)／／将a(1：n)中的元素按非降次序分类，n≥1//a(0)ß-∞／／开始时生成一个虚拟值//forjß⑴tondo／／a(1:j-1)已分类//itemßa(j)；iß⑵whileitem<a(i)do／／0≤i<j／／a(i+1)ßa(i)；ißi-1repeata(i+1)ß-itemrepeatendinsertionsort9.归并分类proceduremergesort(low,high)／／a(low:high)是一个全程数组，它含有high-low+1≥0个待分类的元素//integerlow,high；iflow<high；thenmidß//求这个集合的分割点//call⑴／/将一个子集合分类／／call⑵／／将另一个子集合分类／／call⑶／／归并两个已分类的子集合//endifendmergesort10.使用链接表归并已分类的集合proceduremerge1(q，r，p)／／q和r是全程数组link(1:n)中两个表的指针。这两个表可用来获得全程数组a(1：n)中已分类元素的子集合。此算法执行后构造出一个由p所指示的新表，利用此表可以得到按非降次序把a中元素分好类的元素表，同时q和r所指示的表随之消失。假定link(0)被定义,且假定表由0所结束／／globaln,a(1:n),link(0:n)localintegeri，j，kißq；jßr；kß0／／新表在link(0)处开始//while⑴and⑵do//当两表皆非空时作//ifa(i)≤a(j)／／找较小的关键字／／thenlink(k)ßi;kßi；ißlink(i)／／加一个新关键字到此表//else⑶endifrepeatifi=0then⑷elselink(k)ßiendifpßlink(0)endmergel11.作业排序算法的概略描述proceduregreedy-job(d，j，n)／／作业按p1≥p：≥…≥Pn的次序输入，它们的期限值d(i)≥1,1≤i≤n,n≥1.j是在它们的截止期限前完成的作业的集合／／

jß{1}

for⑴tondo

ifj∪{i}所有作业都能在它们的截止期限前完成then⑵endifrepeatendgreedy—job12.生成二元归并树算法lineproceduretree(l，n)／／l是n个单结点二元树的表//foriß1ton-1docallgetnode(t)／／用于归并两棵树／／lchild(t)<--least(l)／／最小的长度／rchild(t)<--least(l)weight(t)<--⑴callinsert(l，t)repeat⑵／／留在l中的树是归并树"endtreekruskal算法lineprocedurekruskal(e,cost，n，t,mincost)／／g有n个结点，e是g的边集。cost(u，v)是边(u，v)的成本。t是最小成本生成树的边集。mincost是它的成本"realmincost，cost(1:n，1:n)；integerParent(1:n)，t(1：n-1，2)，n；以边成本为元素构造一个min—堆Parentß1／／每个结点都在不同的集合中矿ißmincostß0whilei<n一1and堆非空do从堆中删去最小成本边(u，v)并重新构造堆jßfind(u)；kßfind(v)ifj≠kthen⑴t(i，1)<—ut(i，2)ßvmincost<—⑵callunion(i，k)endif

repeat

ifi≠n-1thenprint(‘nospanningtree’)endif

return

endkruskal多段图的向前处理算法lineprocedurefgraPh(e，k，n，P)／／输入是按段的顺序给结点编号的，有n个结点的k段图。e是边集，c(i，j)是边<i，j>的成本。P(1:k)是最小成本路径//realcost(n)，integerd(n一1)，P(k)，r，j，k，n⑴forj<--n一1to1by一1do／／计算cost(j)／／设r是一个这样的结点，<j，r>∈e且使c(j,r)+cost(r)取最小值cost(j)+c(j，r)+cost(r)d(j)ßrrepeat／／找一条最小成本路径／／P(1)<一1；P(k)ßnforj<--2to⑵do//找路径上的第斗个结点／／P(j)<--d(P(j一1))repeatendfgraPh15．求最小元的并行算法proceduremimdmin(a(1)，a(2),...，a(n)，min)输入；i＝{a(1)，a(2),…，a<n}}输出：i中最小元min处理器个数；pifn>pthenforeachpi：1≤i≤ppardoforj＝i+ptonsteppdoif⑴thena(i)ßa(j)endifrepeatendforkßpelsekßn；endifwhilek>ldoforeachpi：1≤i≤[k／2]pardoifa(k-i+1)<a(i)then⑵endifendforkß[k／2]repeatminßa(1)endmimdmin16．0／1背包问题的回溯法求解。procedurebknaPl(m，n，w，P，fw，fp，x)／／m是背包容量。有n种物品，其重量与效益分别存在数组w(1：n)和P(1：n)中sp(i)/w(o≥P(i+1)／w(i+1)。fw是背包的最后重量，fp是背包取得的最大效益。x(1：n)中每个元素取0或1值。若物品k没放人背包，则x(k)；0；否则x(k)＝1//

integern，k，y(1：n)，i，x(1：n)；real，m，w(1：n)，P(1：n)，fw，fp，cw，cp；cwßcpßo；kß1；fpßl／／cw是背包当前重量；cp是背包当前取得的效益值//loopwhilek≤nand⑴≤mdo／／将物品、k放人背包／／cwßcw+w(k)；cpßcp+P(k)；y(k)ß1；kßk+1repeatifk>nthenfpßcp；fwßcw；kßn；xßy／／修改解//else⑵／／超出m，物品k不适合／／endifwhilebound(cp、cw，k，m)≤fpdo//上面置了fp后，bound=fp//whilek0andy(k)1dokßk-1，//找最后放人背包的物品//repeatifk＝0thenreturnendif//找最后放人背包的物品//y(k)ß0；cwßcw-w(k)；cpßcp—P(k)／／移掉第k项／／repeatkßk+1repeat

endbknaPl17.设计只求一个哈密顿环的回溯算法。ProcedureHamiltonian(n){k←1;x[k]←0;Whilek>0dox[k]←x[k]+1;whileB(k)=falseandx[k]≤ndo______eq\o\ac(○,1)________repeatIfx[k]≤nthenifk=nthen{printx;return}else{k←k+1;x[k]←0;}endifelse______eq\o\ac(○,2)________endifrepeatend}procedureB(k){G[x[k-1],x[k]]≠1thenreturnfalse;fori←1tok-1doifx[i]=x[k]thenreturnfalse;endifrepeatreturntrue;}18.设计一个算法在一个数组A中找出最大数和最小数的元素。Voidmaxmin(A,n)intA[];intn;{intmax,min,i;max=A[1];min=A[1];for(i=2;i<=n;i++)if(____eq\o\ac(○,1)___)max=A[i];elseif(A[i]<min)____eq\o\ac(○,2)____;printf(“max=%d,min=%d\n”,max,min);}19.选择排序：设数组中有N个数，取I=1，2，3，„„N-1，每次找出后N-I+1个数字中最小的与第I个数字交换位置。程序如下：uses

crt;

var

n:array[1..10]

of

integer;

i,j,k,t,min:integer;

begin

clrscr;

for

i:=1

to

10

do

read(n[i]);

for

i:=1

to

9

do

begin

min:=30000;

for

j:=i

to

10

do

begin

if

n[j]<min

then

begin

___eq\o\ac(○,1)____;

k:=j;

end;

end;

t:=n[i];

___eq\o\ac(○,2)____;

n[k]:=t;

end;

for

i:=1

to

10

do

write(n[i]:4);

end.四．问答题1.算法的重要的5个特征是什么？2.什么是动态规划？3．回溯程序的4种因素是什么？4．请解释贪心法的基本思想，并用贪心法解决如下背包问题。背包问题：n=3,M=30,(p1,p2,p3)=(20,14,25),(w1,w2,w3)=(20,15,15)5．请解释动态规划的基本思想，并写出用动态规划解决0/1背包问题所采用的递推方程式。6． 请解释动态规划的基本思想，并写出用动态规划解决多段图问题所采用的递推方程式。7．请解释回溯法的基本思想，并写出用回溯法解决子集和数问题的状态空间树。8．已知如下定义的数据结构，请画出它的逻辑示意图，并说明它是何种类型的数据结构。DS=<D,R,OP> D={1,2,3,4,5,6} R={<1,2>,<1,3>,<2,3>,<3,6>,<3,5>,<5,4>,<6,2>,<4,3>,<5,6>} 9．若将数据序列D={1,2,3}输入堆栈，请给出所有可能的堆栈输出。10.已知如下多段图，请用动态规划方法的向后处理法写出求解此问题的递推公式并完成对各结点的计算。11．请用Prim方法求下图所示的最小生成树。（请写出该方法的基本思想和主要中间过程）。11235641030452520551540355012.最佳原理的基本思想是什么？13.利用分枝定界法求解流动推销员问题。设给定5个城市的距离矩阵为D==(dij)5×514.将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？ 15.由0——1背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式? 16. 对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。《算法设计与分析》练习题库参考答案概念题：请解释下列术语。1．数据元素的集合。 2．队列是一个线性表，限制为只能在固定的一端进行插入，在固定的另一端进行删除。3．对于算法a，如果存在一多项式p()，使得对a的每个大小为n的输入，a的计算时间为o(p(n))，则称a具有多项式复杂度4．二叉树的层数i与该层上的结点数n的关系为：n(i)=。5．如果可满足性约化为一个问题L，则称该问题为NP-难度的。6．算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。。7．多数据单指令流8．若图的任意两个节点间均存在路径可达，则称该图为连通图。9.是指一个数学模型以及定义在该模型上的一组操作。10．算法的复杂度只能用指数函数对其限界。11．函数或过程直接或间接调用它自己。12．和高度相同的满二叉树的每个对应的顶点编号相同的树13．由所有可行状态所构成的树。14．如果L时NP难度的且L∈NP，则称问题L是NP-完全的。15．算法是一个步骤的序列，满足：有穷性、可行性、确定性、输入、输出；过程不需要满足由穷性。16．有向图的每条边有起点与终点之分，且用箭头指向边的终点。无向图的边无起点和终点之分，边无箭头。17．树(tree)是一个或多个结点的有限集合，，它使得：①有一个特别指定的称作根(root)的结点；②剩下的结点被分成m≥0个不相交的集合tl，…，tm，这些集合的每一个都是一棵树，并称t1，…，tm为这根的子树(subtree)。18．P是所有可在多项式时间内用确定算法求解的判定问题的集合。19．运算结果是唯一确定的算法20.nP是所有可在多项式时间内用不确定算法求解的判定问题的集合21．在一给定的无向图G=(V,E)中，(u,v)代表连接顶点u与顶点v的边（即），而w(u,v)代表此边的权重，若存在T为E的子集（即）且为无循环图，使得T中所有边的权重之和w(T)最小，则此T为G的最小生成树。22．动态规划是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。23．数据结构是相互之间存在一种或多种特定关系的数据元素的集合。24．排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来的操作。二、填空题nO(n)最优化问题宽度优先搜索结点的最大级数互异内结点和外结点方形内部路径长度、外部路径长度一次归并分类算法贪心选择性质最优子结构二元归并最小成本生成树最优性最优决策可容许最大成本c最小成本确定性有穷性可行性0个或多个输入一个或多个输出是的时间复杂性空间复杂性时间复杂度高低地方该问题具有最优子结构性质{BABCD}或{CABCD}或{CADCD｝三、程序填空题。1．callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))2．callMAXMIN(i，mid，gmax，gmin)callMAXMIN(mid+1,j,hmax,hmin)3．callSUMOFSUB(S+w(K),K+1,r-W(k))callSUMOFSUB(s，k+1，r—W(k))4．X(k)+X(k)+1k<-k+1；X(k)<-0kßk-15．（1）n+1(2)high-1(3)highßmid(4)lowßmid6．(1)a(i，j)(2)a(i，k)+a(k，j)7.(1)Parent(i)>0(2)j<--Parent(j)8.(1)2(2)j-19.(1)mergesort(low，mid)(2)mergesort(mid+1，high)(3)merge(low，mid，high)10.(1)i≠0(2)j≠0(3)link(k)ßj;kßj;jßlink(j)(4)llnk(k)ßj11.(1)iß2(2)jßj∪{i}12.(1)weight(lchild(t))+weight(rchild(t))(2)return(least(l))13.(1)ißi+1(2)mincost+cost(u，v)14.(1)cost(n)<--0(2)k一115．（1）a(j)<a(i)（2）a(i)ßa(k-i+1)16．（1）cw+w(k)（2）y(k)ß017. (1)x[k]←x[k]+1; (2)k←k-118. (1)A[i]>max (2)min=A[i]19.(1)min:=n[j] (2)n[i]:=n[k]四．问答题1.答:1)．确定性算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。在算法中不允许有诸如“计算5／0”或“将6或7与x相加”2)．能行性一个算法是能行的指的是算法中有待实现的运算都是基本的运算，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。整数算术运算是能行运算的一个例子，而实数算术运算则不是能行的，因为某些实数值只能由无限长的十进制数展开式来表示，像这样的两个数相加就违背能行性这一特性。3)．输入一个算法有0个或多个输入，这些输入是在算法开始之前给出的量，这些输入取自特定的对象集合。4)．输出一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。5)．有穷性一个算法总是在执行了有穷步的运算之后终止。2.答:在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关，这样的过程就构成一个多阶段决策过程。在50年代，贝尔曼(richardbellman)等人根据这类问题的多阶段决策的特性，提出了解决这类问题的“最优性原理”，从而创建了最优化问题的一种新的算法设计方法——动态规划。在多阶段决策过程的每一阶段，都可能有多种可供选择的决策，但必须从中选取一种决策。一旦各个阶段的决策选定之后，就构成了解决这一问题的一个决策序列。决策序列不同，所导致的问题的结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。显然，用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨拙的方法。贝尔曼认为，利用最优性原理(Principleofoptimality)以及所获得的递推关系式去求取最优决策序列可以使枚举量急剧下降。这个原理指出，过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对手初始决策所产生的状态构成一个最优决策序列。如果所求解问题的最优性原理成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段间的递推关系式3．答:分治法的基本思想为：（1）分解问题为若干子问题；对子问题求解；组合各自问题的解。快速排序过程为：procedurePARTITION(m，p)//在A(m)，A(m+1)，…，A(p-1)中的元素按如下方式重新排列：如果最初t=A(m)，则在重排完成之后，对于m和p-1之间的某个q，有A(q)=t，并使得对于m≤k<q，有A(k)≤t，而对于q<k<p，有A(k)≥t退出过程时，p带着划分元素所在的下标位置，即q的值返回。//integerm，p，i；globalA(m:p-1)v=A(m);i=m//A(m)是划分元素//1ooploopi=i+1untilA(i)≥vrepeat//i由左向右移//loopp=p-1untilA(p)≤vrepeat//p由右向左移//ifi<pthencallINTERCHANGE(A(i),A(p))//A(i)和A(p)换位//elseexitendifrepeatA(m)=A(p)；A(p)=v／／划分元素在位置p／／endPARTITIONprocedureQUICKSORT(p,q)//将全程数组A(1：n)中的元素A(p)，…，A（q）按递增的方式分类。认为A(n+1)已被定义，且大于或等于A(p：q)的所有元素；即A(n+1)＝+∞//integerp，q；globaln，A(1:n)ifp<qthenj=q+1callPARTITION(p,j)callQUICKSORT(p,j-1)／／j是划分元素的位置／／callQUICKSORT(j+1,q)endifendQUICKSORT 4．答:贪心法的基本思想为： （1）分析问题，求出最优化评价标准； （2）按评价标准排序； （3）从序列中顺序取元素； （4）若该元素符合要求，则放入结果表中；否则，删除它。 背包算法为：procedureGREEDY-KNAPSACK(P，W，M，X，n)//P(1:n)和W(1:n)分别含有按P(i)／W(i)≥P(i+1)／W(i+1)排序的n件 物品的效益值和重量。M是背包的容量大小，而x(1:n)是解向量//realP(1:n)，W(1:n)，X(1:n)，M，cu；integeri，n；X=0//将解向量初始化为零//cu=M//cu是背包剩余容量//fori=1tondo ifW(i)>cuthenexitendif Xi=1 cu=cu-W(i)repeatifi≤nthenX（i）=cu／W(i)endifendGREEDY-KNAPSACK 5．答:动态规划的基本思想为： （1）确定初始条件；（2）计算第一次结果；（3）用上一次的结果计算本次的结果；（4）若递推到了最终结果，则算法结束；否则，转（3）。 0/1背包问题的递推公式为：6．答:动态规划的基本思想为： （1）确定初始条件；（2）计算第一次结果；（3）用上一次的结果计算本次的结果；（4）若递推到了最终结果，则算法结束；否则，转（3）。 多段图的递推公式为： 7．答:回溯法的基本思想为： （1）分析问题，确定该问题的解空间及显示条件与隐式条件； （2）确定求解问题的状态空间树； （3）对该状态空间树按深度优先方法进行搜索； （4）对搜索的每一步，检查该状态是否为目标状态； （5）若为目标状态，则算法结束； （6）若不满足隐式条件，则回到上一层； （7）选择下一个孩子结点继续搜索；若无下一个孩子可搜索，则回到上一层继续； （8）若回到了最高层的上一层，则无解，算法结束。 子集和数问题的