阅读下列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[i][j]之中, Tij的根结点的序号rij存在于r[i][j]之中, 它的权值存在于w[i][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[i][i]=0.0, 用一维数组表示w[i*(n+1)+i]=q[i]; // 即:w[i][i]=q[i], 用一维数组表示}int i, j, k, m, length; // m表示根结点的下标或序号, 范围为0~nfloat minimum;for(length=1; length<=n; length++) //处理的序列长度由1到nfor(i=0; i<=n-length; i++){ //i为二叉查找树Tij的起始序号j=i + length; //j为二叉查找树Tij的终止序号。如:处理序列a1a2a3时,//相应的二叉查找树为T03, i=0, 而j=3w[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[i][j]=m}} //构造好的最优二叉查找树的根结点的序号在r[0][n]中

阅读下列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[i][j]之中, Tij的根结点的序号rij存在于r[i][j]之中, 它的权值存在于w[i][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[i][i]=0.0, 用一维数组表示

w[i*(n+1)+i]=q[i]; // 即:w[i][i]=q[i], 用一维数组表示

}

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[i][j]=m

}

} //构造好的最优二叉查找树的根结点的序号在r[0][n]中


相关考题:

阅读下列程序说明和C++程序,把应填入其中(n)处的字句,写在对应栏内。【说明】阅读下面几段C++程序回答相应问题。比较下面两段程序的优缺点。①for (i=0; i<N; i++ ){if (condition)//DoSomething…else//DoOtherthing…}②if (condition) {for (i =0; i<N; i++ )//DoSomething}else {for (i=0; i <N; i++ )//DoOtherthing…}

●试题二阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】该程序运行后,输出下面的数字金字塔【程序】includestdio.hmain (){char max,next;int i;for(max=′1′;max=′9′;max++){for(i=1;i=20- (1) ;++i)printf(" ");for(next= (2) ;next= (3) ;next++)printf("%c",next);for(next= (4) ;next= (5) ;next--)printf("%c",next);printf("\n");}}

试题三(共 15 分)阅读以下说明和 C 程序,将应填入 (n) 处的字句写在答题纸的对应栏内。

图2-1是基于软交换的网络分层模型。请将选项应填入(n)处的字句写在答题纸对应的解答栏内。

(a)智能网概念模型中分布功能平面模型如下图所示,请根据此图将应填入(n)处的 字句写在答题纸的对应栏内。

()阅读下列说明和C语言程序,将应填入 (n)处的语句写在答题纸的对应栏内。[说明]下面程序是一个带参数的主函数,其功能是显示在命令行中输入的文本文件内容。[C语言函数]#include"stdio.h"main(argc,argv) int argc; char *argv[]; { (1) ; if((fp=fopen(argv[1],”r’’))== (2) ) { printf(”file not open!\n”);exit(0);} while( (3) ) putchar( (4) ); (5); }

阅读下列说明和C++-代码,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 某发票(lnvoice)由抬头(Head)部分、正文部分和脚注(Foot)部分构成。现采用装饰(Decorator)模式实现打印发票的功能,得到如图5-1所示的类图。【C++代码】 #include using namespace std; class invoice{ public: (1){ cout

阅读下列说明,补充(1)-(9),将解答填入答题纸的对应栏内。

阅读下列说明和C++代码,回答问题,将解答填入答题纸的对应栏内。【说明】某航空公司的会员积分系统将其会员划分为:普卡 (Basic)、银卡(Silver)和金卡 (Gold) 三个等级。非会员 (NonMember) 可以申请成为普卡会员。会员的等级根据其一年内累积 的里程数进行调整。描述会员等级调整的状态图如图 5-1 所示。现采用状态 (State) 模式实现上述场景,得到如图 5-2 所示的类图。【问题1】(15分)阅读上述说明和C++代码,将应填入 (n) 处的字句写在答题纸的对应栏内。

阅读下列说明和?C++代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】阅读下列说明和?Java代码,将应填入?(n)?处的字句写在答题纸的对应栏内。【说明】某快餐厅主要制作并出售儿童套餐,一般包括主餐(各类比萨)、饮料和玩具,其餐品种类可能不同,但其制作过程相同。前台服务员?(Waiter)?调度厨师制作套餐。现采用生成器?(Builder)?模式实现制作过程,得到如图?6-1?所示的类图。