2. 计算机
  3. 阅读下列C++程序和程序说明, 将应填入(n)处的字句写在答题纸的对应栏内。 【说明】构造最优二叉查找树。 具有n个结点的有序序列a1, a2, …, an存在于数组元素a[1]、a[2], …, a[n]之中, a[0]未被使用。结点a1, a2

阅读下列C++程序和程序说明, 将应填入(n)处的字句写在答题纸的对应栏内。 【说明】构造最优二叉查找树。 具有n个结点的有序序列a1, a2, …, an存在于数组元素a[1]、a[2], …, a[n]之中, a[0]未被使用。结点a1, a2

admin2009-02-15  94
问题 阅读下列C++程序和程序说明, 将应填入(n)处的字句写在答题纸的对应栏内。
【说明】构造最优二叉查找树。
   具有n个结点的有序序列a1, a2, …, an存在于数组元素a[1]、a[2], …, a[n]之中, a[0]未被使用。结点a1, a2, …, an-1, an的查找成功的概率p1, p2, …, pn-1, pn存在于数组元素 p[1]、p[2], …, p[n—1]、p[n]之中, p[0]未用。另外, 查找失败的概率q0, q1, …, qn-1, qn存在于数组元素q[0]、p[1], …, q[n-1]、q[n]之中。算法计算的序列ai+1, ai+2,…, aj-1, aj的最优二叉查找树Tij的代价Cij存在于数组元素c[j]之中, Tij的根结点的序号rij存在于r[j]之中, 它的权值存在于w[j]之中。为了便于内存的动态分配, 统统使用一维数组取代二维数组。
   const float MAXNUM=99999. 0; //尽可能大的浮点数
   template＜(1)＞
   void OPtimal_Binary_Search_Tree(float p[], float q[], Type a[], int n) {
       float  *C,   *W;
       c=(2);
       w=(3);
       int *r;
       r=new int[(n+1)*(n+1)];
       for(i=0; i＜=n; i++)
           {   c[i*(n+1)+i]=0. 0;     //  即：c=0.0, 用一维数组表示
               w[i*(n+1)+i]=q;      //  即：w=q, 用一维数组表示
           }
           int i, j, k, m, length;     //  m表示根结点的下标或序号, 范围为0～n
           float minimum;
           for(length=1; length＜=n; length++)   //处理的序列长度由1到n
               for(i=0; i＜=n-length; i++){  //i为二叉查找树Tij的起始序号
                   j=i + length;   //j为二叉查找树Tij的终止序号。如：处理序列a1a2a3时,
                                 //相应的二叉查找树为T03, i=0, 而j=3
                   w[i*(n+1)+j]=(4);
                   minimum =MAXMUM;
                   for(k=i+1; k＜=j; k++)   //考察以ai+1、ai+2,   …, ai为根的情况
                       if((5)＜minimum)
                       {   minimum=c[i*(n+1)+k-1]+c[k*(n+1)+j];m=k; }
                   c[i*(n+1)+j]=w[i*(n+1)+j]+c[i*(n+1)+m-1]+c[m*(n+1)+j];
                   r[i*(n+1)+j]=m;     //   r[j]=m
               }
   } //构造好的最优二叉查找树的根结点的序号在r[0][n]中
选项
答案(1) class Type (2) new float[(n+1)*(n+1)] (3) new float[(n+1)*(n+1)] (4) w[i*(n+1)+j-1]+p[j]+q[j] (5) c[i*(n+1)+k-1]+c[k*(n+1)+j]
解析 (1) class Type
   定义最优二叉查找树生成函数模板Optimal_Binary_Search_Tree。
(2) new float[(n+1)*(n+1)]
   按数组a长度n+1申请动态二维数组c，存放最优二叉查找树Tij的代价Cij。
(3) new float[(n+1)*(n+1)]
   按数组a长度n+1申请动态二维数组w，存放最优二叉查找树Tij的权值Wij。
(4) w[i*(n+1)+j-1]+p[j]+q[j]
   由Wij-1递推计算Wij。
(5) c[i*(n+1)+k-1]+c[k*(n+1)+j]
   找Cik+Ckj(k=i+1，…，j)的最小值的m=k，求Cij。按照一般二维数组的写法是： c[j]=w[j]+c[m-1]+c[m][j]。
转载请注明原文地址:https://www.kaotiyun.com/show/gMDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)