试对于任何指定的m和N，构造一棵存有N个关键码的m阶B树，使得在其中插入某个特定关键码之后，需要进行Ω（log_mN)次分裂。

答案

查看答案

发布时间：2022-08-05

更多“试对于任何指定的m和N，构造一棵存有N个关键码的m阶B树，使得在其中插入某个特定关键码之后，需要进行Ω（logmN)次分裂。”相关的问题

第1题

经过至多（n-1)+（n-2)=2n-3次比较，不难从任何存有n个整数的向量中找出最大者和次大者，试改进这一算法，使所需的比较次数（即便在最坏情况下)也不超过[3n/2]-2。

点击查看答案

第2题

设m≥3为奇数。试对任意的h＞0，构造一棵高度为h的m节B-树，使得若反复地对该树交替地执行插入、删除操作，则每次插入或删除操作都会引发h次分裂或合并。

点击查看答案

第3题

若构造一棵具有n个结点的二义排序树，最坏的情况下其深度不会超过n。()

若构造一棵具有n个结点的二义排序树，最坏的情况下其深度不会超过n。（)

此题为判断题(对，错)。

点击查看答案

第4题

考查任何一棵二叉树T。a)试证明，对于其中任一节点v∈T，总有depth（v)+height（v)≤height（T)；b)以上取等号的充要条件是什么？

点击查看答案

第5题

试证明，在二叉树中接入（attachAsLC（)或attachAsRC（))或摘除（remove（)或secede（))一棵非空子树之后a)该子树所有祖先的后代数目（size)必然变化;b)该子树所有祖先的高度（height)可能变化;c)对于非该子树祖先的任何节点，高度与后代数目均保持不变。

点击查看答案

第6题

试证明，对于任意大的正整数n，都存在一棵规模为n的AVL树，从中删除某一特定节点之后，的确需要做Ω（logn)次旋转，方能使全树恢复平衡。

点击查看答案

第7题

假定从空树开始建立一棵有n个关键码的m阶B树，最终得到有p(p>2)个非失败结点的B树。那么这p个结点最多经过()次分裂得来。

假定从空树开始建立一棵有n个关键码的m阶B树，最终得到有p（p>2)个非失败结点的B树。那么这p个结点最多经过（)次分裂得来。

A、p

B、p-1

C、p-2

D、p-3

点击查看答案

第8题

问题描述:T公司发现其研制的一个软件中有n个错误,随即为该软件发放了一批共m个补丁程序.每个

补丁程序都有其特定的适用环境,某补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用.一个补丁在排除某些错误的同时,往往会加入另一些错误.换句话说,对于每个补丁i,都有两个与之相应的错误集合B₁[j]和B₂[i],使得仅当软件包含B₁[i]中的所有错误,而不包含B2[i]中的任何错误时,才可以使用补丁i.补丁i将修复软件中的某些错误F₁[i],同时加入另一些错误F2[i].另外,每个补丁都耗费一定的时间.

试设计一个算法,利用T公司提供的m个补丁程序,将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少.

算法设计:对于给定的n个错误和m个补丁程序,找到总耗时最少的软件修复方案.

数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m,n表示错误总数,m表示补丁总数(1≤n≤20,1≤m≤100).接下来m行给出了m个补丁的信息.每行包括一个正整数,表示运行补丁程序i所需时间以及2个长度为n的字符串,中间用个空格符隔开.在第1个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于B1[i],若为“-”,则表示第k个错误属于B2[i],若为“0”,则第k个错误既不属于B1[i]也不属于B2[i],即软件中是否包含第k个错误并不影响补丁i的可用性.在第2个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于F₁[i],若为“-”,则表示第k个错误属于F₂[i],若为“0”,则第k个错误既不属于F₁[i]也不属于F₂[i],即软件中是否包含第k个错误不会因使用补丁i而改变.

结果输出:将总耗时数输出到文件output.txt.如果问题无解,则输出0.