并行计算习题答案

12.1对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。答：推广至M元树时，k级M元树总结点数N的表达式为：N=1+m1+m2+...+m（k-1）=(1-mk)*1/(1-m);2.4试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么？答：N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=44.11一个在p个处理器上运行的并行程序加速比是p-1，根据Amdahl定律，串行分量为多少?答：p/(1+f(p-1))=p-1,f=1/(p-1)25.5假定开始时Pi(1《i《n)存有数据di，所谓累加求和是指用ijid1，来代替中的原始值di，算法5.3给出了在PRAM模型上累加求和算法。Input:diarekeptinPi,whereOutput:replacesdiinprocessorPiBeginforj=0tologn-1dofori=2j+1tonpar-do(i)di=di+di-2j(ii)Pi=diendforendforEnd(1）试用n=8为例子，按照上述算法逐步计算出累加和。(2）分析算法的时间复杂度。26.37.2（1）例:A={1,3,6,8,11,13}p=6;B={2,4,5,7,10,12,14},q=7p=3,q=3A={1,3,6*,8,11,13*}B={2,4,5*,7,10,12*,14},B’={2,4,5,6*,7,1012,13*,14}A11={1,3},A12={8,11},A13={}B11={2,4,5},B12={7,1012},B13={14}A11={1,3*},A12={8,11*},B11={2,4*,5},B12={7,10*,12},B11’={2,3*,4,5},B12’={7,10,11*,12},A111={1},A112={}A121={8},A122={}B111={2},B112={4,5}B121={7,10},B122={12}A111={1*}A121={8*}B111={2*}B121={7,10*}33542113338240723B111’={1*,2}B121’={7,8*,10}A1111={},A1112={}A1211={},A1212={}B1111={},B1111={}B1211={7},A1212={}6.7（1）pat=abaababa(m=8)WIT[1]=0，WIT[2]=1，w=1,j=2,s=2-1+1=2pat[w]=apat[s]=bWIT[3]=2，w=1,j=3,s=3-1+1=3pat[w]=pat[s]=aw=2,j=3,s=3-1+2=4pat[w]=bpat[s]=aWIT[4]=4w=1,j=4,s=4-1+1=4pat[w]=pat[s]=aw=2,j=4,s=4-1+2=5pat[w]=pat[s]=bw=3,j=4,s=4-1+3=6pat[w]=pat[s]=aw=4,j=4,s=4-1+4=7pat[w]=apat[s]=b为非周期串（2）pat=abaabaaab(m=9)WIT[1]=0，WIT[2]=1，w=1,j=2,s=2-1+1=2pat[w]=apat[s]=bWIT[3]=2，w=1,j=3,s=3-1+1=3pat[w]=a=pat[s]=aw=2,j=3,s=3-1+2=4pat[w]=bpat[s]=aWIT[4]=5w=1,j=4,s=4-1+1=4pat[w]=pat[s]=aw=2,j=4,s=4-1+2=5pat[w]=b=pat[s]=bw=3,j=4,s=4-1+3=6pat[w]=a=pat[s]=aw=4,j=4,s=4-1+4=7pat[w]=a=pat[s]=aw=5,j=4,s=4-1+5=8pat[w]=bpat[s]=aWIT[5]=1w=1,j=5,s=5-1+1=5pat[w]=apat[s]=b非周期串6.8(2)p=6,q=9j=q-p+1=9-6+1=4w=wit[j]=wit[4]=4T(q+w-1)=t(9+4-1)=bP(4)=awit[q]=wit[9]=w=4duel=p=67.5(2)请画出一个16输入的双调归并网络47.6(2)给定序列（1，2，3，4，5，6，7，8），请求其前缀和B(3,1)B(2,1)B(2,2)B(1,1)B(1,2)B(1,3)B(1,4)B(0,1)B(0,2)B(0,3)B(0,4)B(0,5)B(0,6)B(0,7)B(0,8)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)（（1）正向遍历B(0,1)=1,B(0,2)=2B(0,3)=3B(0,4)=4B(0,5)=5B(0,6)=6B(0,7)=7B(0,8)=8B(1,1)=2,B(1,2)=12,B(1,3)=30,B(1,4)=56,B(2,1)=24,B(2,1)=1680,B(3,1)=40320,C(3,1)C(2,1)C(2,2)C(1,1)C(1,2)C(1,3)C(1,4)C(0,1)C(0,2)C(0,3)C(0,4)C(0,5)C(0,6)C(0,7)C(0,8)（2）反向遍历C(0,1)=1,C(0,2)=2C(0,3)=6C(0,4)=24C(0,5)=120C(0,6)=720C(0,7)=5040C(0,8)=40320说明：求和或乘积均可,这里是求乘积。