A.若插入过程中根节点发生分裂,则B树的高度加1
B.每当进行插入运算,就在B树的最下面一层增加一个新节点
C.若要删除的关键码出现在根节点中,则不能真正删除,只能做标记
D.删除可能引起B树节点个数减少,但不会造成B树高度减少
若关系中的某一属性组的值能唯一地标识一个元组,则称该属性组为(54);若关系中的某一超码,当去掉其中任一属性后,均不再为超码,则称其为(55)。
A.主码
B.超码
C.候选码
D.全码
A.为了防止桶溢出,在散列文件设计时,需要预留一些空间大小不固定的桶
B.用散列文件组织数据时,需要使用文件记录中的一个或多个域作为查找码
C.如果散列文件中散列函数的“均匀分布性”不好,可能会造成桶溢出
D.好的散列函数产生的存储地址分布应尽可能是随机的
【问题 1】(8 分)
用回溯法求解此 0-1 背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W )函数,其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出 0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
位(bit)?
(2)若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码?