现有如下关系模式：R（A#，B#，C，D，E)其中：A#B#组合为码R上存在的函数依赖有A#B#→E，B#→C，C→D1.该关

实体集R(A#,A1,A2,A3),其中A#为码

实体集S(B#,B1,B2)，其中B#为码

从实体集R到S存在多对一的联系，联系属性是D1。

(1)设计相应的关系数据模型;

(2)如果将上述应用的数据库设计为一个关系模式，如下：

RS(A#,A1,A2,A3,B#,B1,B2,D1),指出该关系模式的码。

(3)假设上述关系模式RS上的全部函数依赖为：A1→A3,指出上述模式RS最高满足第几范式?(在1NF～BCNF之内)为什么?

?A、<class 'char'>

B、<class 'int'>

C、<class 'float'>

D、<class 'str'>

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)。

B.X端实体的码

C.XY端码组合

D.X端或Y端的码