精选优质文档-倾情为你奉上计算机学院研究生并行计算课程考试试题（2010级研究生，2011.1）1（12分）定义图中节点u和v之间的距离为从u到v最短路径的长度。已知一个d维的超立方体，1）指定其中的一个源节点s，问有多少个节点与s 的距离为i，其中0id。证明你的结论。2）证明如果在一个超立方体中节点u与节点v的距离为i，则存在i！条从u到v的长度为i的路径。1)有个节点与s的距离为i。证明：由超立方体的性质知：一个d维的超立方体的每个节点都可由d位二进制来表示，则与某个节点的距离为i的节点必定在这d位二进制中有i位与之不同，那么随机从d位中选择i位就有种选择方式，即与s的距离为i得节点就有个。2)证明：由1）所述可知：节点u与节点v的距离为i则分别表示u、v节点的二进制位数中有i位是不同的。设节点u表示为：，节点v表示为：，则现在就是要求得从变换到 的途径有多少种。那么利用组合理论知识可知共有即中途径。所以存在i！条从u到v的长度为i的路径。2（18分）6个并行程序的执行时间，用I-VI表示，在1-8个处理
