资源描述：
《并行计算习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2.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个处理器
2、上运行的并行程序加速比是p-1，根据Amdahl定律，串行分量为多少?答：p/(1+f(p-1))=p-1,f=1/(p-1)25.5假定开始时Pi(1《i《n)存有数据di，所谓累加求和是指用，来代替中的原始值di，算法5.3给出了在PRAM模型上累加求和算法。Input:diarekeptinPi,whereOutput:replacesdiinprocessorPiBeginforj=0tologn-1dofori=2j+1tonpar-do(i)di=di+di-2j(ii)Pi=diend
3、forendforEnd(1）试用n=8为例子，按照上述算法逐步计算出累加和。(2）分析算法的时间复杂度。6.333542113338240727.2（1）例:A={1,3,6,8,11,13}p=6;B={2,4,5,7,10,12,14},q=7=3,=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},B
4、13={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*}B111’={1*,2}B121’={7,8*,10}A1111={},A1112={}A121
5、1={},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]=a¹pat[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]=b¹pat[s]=aWIT[4]=4w=1,j=4,s=4-1+1=4pat[w]=pat[s]=aw=2,j=4,s=4-1+
6、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]=a¹pat[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
7、,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(
8、q+w-1)=t(9+4-1)=b<>P(4)=awit[q]=wit[9]=w=4duel=p=67.5(2)请画出一个16输入的双调归并网络7.6(2)给定序列（1，2，3，4，5，6，7，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)=1
