首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
admin
2009-02-15
71
问题
阅读下列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的最优二叉查找树T
ij
的代价C
ij
存在于数组元素c
[j]之中, T
ij
的根结点的序号r
ij
存在于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,存放最优二叉查找树T
ij
的代价C
ij
。
(3) new float[(n+1)*(n+1)]
按数组a长度n+1申请动态二维数组w,存放最优二叉查找树T
ij
的权值W
ij
。
(4) w[i*(n+1)+j-1]+p[j]+q[j]
由W
ij-1
递推计算W
ij
。
(5) c[i*(n+1)+k-1]+c[k*(n+1)+j]
找C
ik
+C
kj
(k=i+1,…,j)的最小值的m=k,求C
ij
。按照一般二维数组的写法是: c
[j]=w
[j]+c
[m-1]+c[m][j]。
转载请注明原文地址:https://kaotiyun.com/show/gMDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下不正确的软件测试原则是(39)。
以下关于模块耦合关系的叙述中,耦合程度最低的是__________(39),其耦合类型为___________(40)耦合。(39)
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(25)
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(50)
以下关于数据流图的叙述中,不正确的是()。
若某文件系统的目录结构如下图所示,假设用户要访问文件f1.java,且当前工作目录为Program,则该文件的全文件名为(24),其相对路径为(25)。 (24)
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
V模型是具有代表意义的测试模型,以下理解正确的是______。A.V模型认为测试阶段是与开发阶段并行的B.V模型是软件开发螺旋模型的变种,它反映了测试活动与分析和设计的关系C.V模型造成需求分析阶段隐藏的问题一直到后期的验收测试才被发现D.V模型是
随机试题
领导者对权力的来源、性质、内容及行使等方面的系统认识或根本看法、态度被称为
精气神明衰惫之象为筋将衰惫之象为
患者,女,34岁。宫外孕破裂出血,拟急诊手术。血压70/40mmHg,脉搏125次/分,面色苍白。此时应立即进行的处理是
屋面防水等级为I级的防水层耐用年限是()。
工期在12个月以内的施工合同在其履行期间通常()市场价格变化调整合同价款。
银行个人信贷产品定位的第一步是()。
增值税一般纳税人发生存货的盘亏及毁损,其进项税额需要作转出处理。()
关于法律关系的主体,下列表述不符合规定的是()。
甲公司2011年和2012年有关业务资料如下:(1)2011年5月20日,甲公司与乙公司的原股东A公司签订股权转让合同。合同约定:甲公司向A公司购买其所持有的乙公司80%股权;以乙公司2011年5月31日经评估确认的净资产价值为基础确定股权转让价格;甲公
设随机变量X服从参数为1的指数分布,则随机变量y=min(X,2)的分布函数().
最新回复
(
0
)