最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wl最小的树，其中对于最优二叉树，n表示(31)；对于最优查找树，n表示(32)；构造这两种树均(33)。

admin2009-02-15 25

问题最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wl最小的树，其中对于最优二叉树，n表示(31)；对于最优查找树，n表示(32)；构造这两种树均(33)。

选项 A、节点数
B、叶节点数
C、非叶节点数
D、度为2的节点数

答案B

解析 (31)～(33)(31)假设有n个权值{w1,w2,…，wn)，是构造一棵有n个叶子节点的二又树，每个叶子节点带权wi，则其中带权路径长度WPL=∑wili最小的二又树称做最优二又树或哈夫曼树。所以最优二叉树中n表示叶节点。(32)如果只考虑查找成功的情况，则使查找性能达到最佳的判定树是其带权内路径长度之和值PH=∑wili，取最小值的二叉树为最优查找树。其中n为二叉树上节点的个数(即有序表的长度)；li为第i个节点在二叉树上的层次数；节点的权wi=cpi(i=1～n)，其中pi为节点的查找概率，c为某个常量。因此最优查找树中n表示所有节点数。(33)构造哈夫曼树和最优查找树均需对n个关键字进行动态插入。

转载请注明原文地址:https://kaotiyun.com/show/gkxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wl最小的树，其中对于最优二叉树，n表示(31)；对于最优查找树，n表示(32)；构造这两种树均(33)。

软件设计师上午基础知识考试

软考中级

在图4-1所示的系统中，R1、R2、R3为3个加工部件，每个加工部件的失效率均为λ，可靠性均为尺。则该系统的可靠性为(4)。若每个加工部件的平均无故障时间为5000小时，则该系统的平均无故障时间为(5)小时。

在无线通信中不能采用CSMA/CD方式，这是因为无线通信存在(59)，采用CSMA/CA技术是指(60)，MAC层的分布式协调功能提供(61)，站点发出的确认帧ACK，要在(62)间隔发送。为解决隐蔽站带来的问题，802.11允许(63)。

DQDB同时支持(49)两种服务。DQDB子网的双总线结构由(50)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(51)访问控制方式，其中能够提供非等时服务是(52)，它用于(53)业务。

ATM协议将网络分为多个功能层，信元生成由(44)层完成，汇聚子层属于(45)层。对OC-12接口标准，ATM网络的有效数据率(去掉信元中的开销位)约为(46)Mbit/s。A类服务是指(47)。在ATM网络内部(NNI中)，允许的虚电路数为(48)。

学习马克思主义的目的是

关于小肠的描述，错误的是（）

健康促进中社会动员的手段有

阿托品对下列平滑肌的松弛作用最强的是()

个人贷款是指贷款人向符合条件的()发放的用于个人消费、生产经营等用途的本外币贷款。

从四个选项选择最合适的一个填入问号处，使之呈现一定的规律性。()

国民政府整顿财政的措施中，成效最为显著的是()。

下列选项中属于应用法学的是

=_______.