首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列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
102
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(33)在关键路径上。活动GH的松弛时间是(34)。(34)
CPU中的数据总线宽度会影响(4)。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(27)
假设系统中有三类互斥资源R1、R2和R3,可用资源数分别为10、5和3。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,此时系统剩余的可用资源数分别为(22)。如果进程按(23)序列执行,那么系统
假设某公司营销系统有营销点关系S(营销点,负责人姓名,联系方式)、商品关系P(商品名,条形码,型号,产地,数量,价格),其中,营销点唯一标识S中的每一个元组。每个营销点可以销售多种商品,每一种商品可以由不同的营销点销售。关系S和P的主键分别为(15),S
国标16260中,在描述外部(内部)效率度量时,给出了若干针对计算机系统时间消耗的定义,以下描述项中正确的有(31)。①响应时间是指从按下传送键到得到结果为止所需要的时间。②处理时间是指从接受一个消息到送出它的结果之间计算机的历时时间。③周转时间是指
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=l;high=n;while(high>low)ifA[low]+A[hig
虚拟存储体系由___________两级存储器构成。
随机试题
简述慢性血源性骨髓炎手术指征和禁忌证。
第二类危险源的内容不包括( )。
我国经营性金融机构包括()。
下列各项中关于会计账簿的基本内容中,说法正确的有()。
【2015年河北石家庄.单选】马卡连柯提出的“要尽量多地要求一个人,也要尽可能地尊重一个人”,反映了德育的()。
软件能力成熟度模型CMM(Capability Maturity Model)描述和分析了软件过程能力的发展和改进程度,确立了一个软件过程成熟程度的分级标准。该模型的第2级为可重复级,它包含了(62)关键过程域。
"Themorethatyouread,themorethingsyouwillknow.Themorethatyoulearn,themoreplacesyou’llgo."Thesesimple-but-t
Alargepartofeffectiveleadershipisdependentonsomethingcalled"style".Butstyleisdifficulttoteach,andwhatmakes
Everyoneknowsthathumanlanguagecanbeasuperbmeansofcommunication.Therefore,itcanbedamnably【M1】______
Whatisthebesttitleforthispassage?
最新回复
(
0
)