A.二叉树的度为2
B.只有一个结点的二叉树的度为1
C.二叉树的左右子树可任意交换
D.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树的结点个数
A、n/2
B、
C、log2n
D、n
E、n3+n1+n2
F、1+n2
G、n2+1
H、1
L、n+1
J、n1
K、n2
L、n1+1
可将算法的时间复杂度降低到O(nlog2n),算法的思想是对于关键码序列(keylow,keylow+1,…,keyhigh),轮流以keyk为根,k=low,low+1,…,h,求使得|W[low-1][k-1]-W[k][high]|达到最小的k,用keyk作为由该序列构成的拟最优二叉搜索树的根。然后对以keyu为界的左子序列和右子序列,分别施行同样的操作,建立根keyk的左子树和右子树,试编写一个函数,实现上述试探算法。要求该函数的时间复杂度应为O(nlog2n)。
v).有向树T的每个顶点u可以看作客户,其服务需求量为w(u).每条边(u,v)的边长d(u,v)可以看作运输费用.如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构需付出的服务转移费用为w(u)×d(u,v).树根处已设置了服务机构,现在要在树T中增设k处独立服务机构,使得整棵树T的服务转移费用最小.服务机构的独立性是指任例两个服务机构之间都不存在有向路径.
算法设计:对于给定的有向树T:计算在树T中增设k处独立服务机构的最小服务转移费用.
数据输入:由文件input.txt.给出输入数据.第1行有2个正整数n和k.n表示有向树T的边数:k是要增设的服务机构数.有向树T的顶点编号为0,1,...,n.根结点编号为0.接下来的n行中,每行存表示有向树T的一条有向边的3个整数.第i+1行的3个整数wi、vi、di分别表示编号为i的顶点的权为wi,相应的有向边为(i,vi),其边长为di.
结果输出:将计算的最小服务转移费用输出到文件output.txt.
当元素类型为字符串时,为避免复杂的散列码转换,可以改用键树(trie)结构来实现词典ADT。
a)remove()接口复杂度中的因子r可否消除?
b)put()接口复杂度中的因子r可否消除?
c)试举例说明,以上实现方式在最坏情况下可能需要多达Ω(nr)的空间,其中n=|S|为字符串集的规模。
d)试改用列表来实现各节点,使所需空间的总量线性正比于S中所有字符串的长度总和——当然,get()接口的效率因此会降至O(hr),其中h为树高,同时也是Ss中字符串的最大长度。
e)键树中往往包含大量的单分支节点。试如图x9.5所示,通过折叠合并相邻的单分支节点,进一步提高键树的时、空效率。改进之后,键树的时、空复杂度各是多少?
f)习题[8-19](173页)曾介绍过四叉树(quadtree)结构,并指出其深度不受限制的缺陷。若将四个象限的二进制编码视作字符,即将字符表取作∑={00,01,10,11},则四叉树可以看作键树的特例,试基于这一理解,仿照以上技巧对四叉树进行压缩,使其深度不致超过O(n)。
在内管为φ180×10mm的套管换热器中,将流量为3500kg/h的某液态烃从100℃冷却到60℃,其平均比热为2&38kJ/(kg。K),环隙走冷却水,其进出口温度分别为40℃和50℃,平均比热为4.174kJ/(kg。K),基于传热外面积的总传热系数K=2000W/(m2K),且保持不变。设热损失可以忽略。试求:(1)冷却水用量;(2)计算两流体为逆流和并流情况下的平均温差及管长。
A.ρ=(P+K)÷(gH)
B.ρ=PK÷(gH)
C.ρ=(P+K)÷(1.02gH)
D.ρ=9.8(P+K)÷H
为使二叉搜索树结构支持多个相等数据项的并存,需要增加一个BST::searchAll(e)接口,以查找出与指定目标e相等的所有节点(如果的确存在)。
a)试在BST模板类(教材185页代码7.2)的基础上,扩充接口BST::searchAll(e)。要求该接口的时间复杂度不超过o(k+h),其中h为二叉搜索树的高度,k为命中节点的总数;
b)同时,改进原有的BST::search(e)接口,使之总是返回最早插入的节点e—即先进先出。
A.I 和 M
B.I 和 L
C.J 和 L
D.J 和 K