首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
72
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在操作系统中,虚拟设备通常采用(11)设备来模拟低速设备(如打印机)。
GB/T18905-2002《软件工程产品评价》中确定的通用评价过程包括四个方面,即:确立评价需求,规定评价,设计评价和执行评价,其中有关“规定评价”部分包含的内容有(52)。
在进行软件编码规范评测过程中需要围绕几个方面的内容展开,以下描述中不属于编码规范评测内容的有(37)。
在面向对象分析和设计中,用类图给出系统的静态设计视图,其应用场合不包括___________(45)。下图是一个UMI,类图,其中类University和类School之间是___________(46)关系,类Person和类PersonRecord之间
以下关于模块耦合关系的叙述中,耦合程度最低的是__________(39),其耦合类型为___________(40)耦合。(40)
POP3协议采用___________(23)模式,客户端代理与POP3服务器通过建立___________(24)连接来传送数据。(24)
在计算机系统中总线宽度分为地址总线宽度和数据总线宽度。若计算机中地址总线的宽度为32位,则最多允许直接访问主存储器_____的物理空间。
假设磁盘块与缓冲区大小相同,每个盘块读入缓冲区的时间为10μs,由缓冲区送至用户区的时间是5μs,系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区,并送至用户区进行处理,那么采用单缓冲区需要花费的时间
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段,其中,___________并不是每个编译器都必需的。
编译和解释是实现高级程序设计语言的两种方式,其区别主要在于______。
随机试题
KPX-121配产器的偏孔直径为()。
引进500#乙二醇脱水装置中D—504保持适当的操作压力是必要的,其设计值为()MPa。
在已经有的报表中创建子报表,需要确保主报表和子报表所依赖的()已经正确地确立了关系。
下列关于温抗体型自身免疫性溶血性贫血的叙述不正确的是
基站机房共享时,必须根据所有设备的()及楼面结构布置等对机房楼面结构进行安全评估。
某资产评估事务所承包了W企业的一个评估业务,评估对象为W企业2014年购进的一条生产线M,账面原值为300万元,2017年进行评估。在评估过程中评估专业人员收集、整理、分析评估资料,经测算,从2012年到2017年M生产线的价格每年比上一年上长了10%。专
余涌:素食不会导致营养不良。研究表明,人体所需要的各种营养素,从蛋白质到各种微量元素,素食都可以足量含有。方宁:你说素食不会导致营养不良,我不同意。如果所有的人都素食,则目前所有与肉食有关的产业将全部倒闭,由此产生的失业大军将使难以计数的人陷入贫困而
线程在生命周期中要经历5种状态。如果线程当前是新建状态,则它可到达的下一个状态是()。
Ifyouareafanofsciencefiction,you’venodoubtencounteredthetermnanotechnol-ogy.Yetoverthepastyearalso,aseries
Theangryoldladydidn’tknowwho______forthebrokenglass.
最新回复
(
0
)