2021年软件设计师模拟题5

本题考查应试者对关系模式中主键、外键和模式分解及相关知识的掌握程度。

从商品关系的函数依赖集F1可以导出商品号决定商品关系的全属性，所以商品号是商品关系的主键。

从仓库关系的函数依赖集F2可以导出（仓库号，商品号）决定仓库关系的全属性，所以仓库关系的主键是（仓库号，商品号）。又由于商品号是商品关系的主键，故商品号是仓库关系的外键。

仓库关系存在冗余、插入异常和删除异常，以及修改操作的不一致。例如，仓库号为"12"的商品有3种，其地址就要重复3次，如下表所示，故仓库关系存在冗余

公司总部与分部之间通过Internet传输数据，需要采用加密方式保障数据安全。加密算法中，对称加密比非对称加密效率要高。RSA和ECC属于非对称加密算法，MD5为摘要算法，故选择RC-5。

数据库通常采用三级模式结构，其中，视图对应外模式、基本表对应模式、存储文件对应内模式。数据的独立性是由DBMS的二级映像功能来保证的。数据的独立性包括数据的物理独立性和数据的逻辑独立性。数据的物理独立性是指当数据库的内模式发生改变时，数据的逻辑结构不变。为了保证应用程序能够正确执行，需要通过修改概念模式与内模式之间的映像。数据的逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的。数据的逻辑结构发生变化后，用户程序也可以不修改。但是，为了保证应用程序能够正确执行，需要修改外模式与概念模式之间的映像。

完整性约束包括：实体完整性约束、参照完整性约束和用户自定义完整性约束三类。实体完整性要求主键中的任一属性不能为空，同时主键不能有重复值。参照完整性要求外键的值，要么为空，要么为对应关系的主键值。同时仅当参照关系中没有任何元组的外键值与被参照关系中要删除元组的主键值相同时，系统才可以执行删除操作，否则拒绝执行删除操作。用户定义的完整性是针对某一具体数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求。一般用于限制某字段值的取值范围，此范围不涉及其他数据表的值。从以上描述来看，根据题目的要求，以上3种完整性约束都无法达到目的。所以需要考虑触发器，触发器的功能一般比完整性约束要强得多。触发器的原理是通过编写相应的触发器脚本代码，来对某个字段值的变化进行监控，一旦值发生变化，则触发器脚本执行。在本题中，需要达到的效果是EMP中的工资产生变化，则需要判断变化值是否在P关系规定的范围之内，所以应在EMP上建立触发器。

根据题干描述，应用系统需要使用某公司开发的类库，该应用系统由一组窗格组成，应用需要协调窗格之间的行为，并且不能引用窗格自身，在这种要求下，对比4个候选项，其中中介者模式用一个中介对象封装一系列的对象交互。中介者使用的各对象不需要显式的相互调用，从而使其耦合松散。可以看出该模式最符合需求。

根据题干描述，在线文档系统需要根据用户的查询需求逐步将查询请求依次传递，对比4个候选项，其中在责任链模式中，很多对象由每一个对象对其下家的引用而连接起来形成一条链。请求在这个链上传递，直到链上的某一个对象决定处理此请求。因此责任链模式是能够满足该要求的最好模式。

根据函数依赖定义，可推出“（城市，街道）→U”和“（邮政编码，街道）→U”，因此，（城市，街道）和（街道，邮政编码）都是候选关键字。包含在任何一个候选关键字中的属性称为主属性，不包含在任何候选关键字中的属性称为非主属性。因为关系R只有3个属性，而且都包含在关键字中，因此，R中的3个属性都是主属性，而无非主属性。

根据函数依赖定义，可推出“（城市，街道）→U”和“（邮政编码，街道）→U”，因此，（城市，街道）和（街道，邮政编码）都是候选关键字。包含在任何一个候选关键字中的属性称为主属性，不包含在任何候选关键字中的属性称为非主属性。因为关系R只有3个属性，而且都包含在关键字中，因此，R中的3个属性都是主属性，而无非主属性。

因为每个员工允许有多个家庭成员，如果将这么多家庭成员都记录下来，势必造成表中数据的冗余，所以应该将家庭成员、关系及联系电话加上员工号设计成一个独立的模式。

E-R图时结构化分析过程的工具，用于数据建模，将现实世界中的事物抽象信息世界里的数据。

本题考查关系代数运算方面的基础知识。

自然联接 是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果集中将重复属性列去掉。本试题中

的含义是R×S后，选取R和S关系中R.C=S.C∧R.D=S.D的元组，再进行R.A、R.B、R.C、R.D和S.E 的投影关系运算。可见该关系运算表达式与是等价的。

根据函数依赖定义，可知ACD→U，ABD→U，所以ACD和ABD均为候选关键字。根据主属性的定义“包含在任何一个候选码中的属性叫做主属性（Prime attribute），否则叫做非主属性（Nonprime attribute）”，所以，关系R中的4个属性都是主属性。

根据函数依赖定义，可知ACD→U，ABD→U，所以ACD和ABD均为候选关键字。根据主属性的定义“包含在任何一个候选码中的属性叫做主属性（Prime attribute），否则叫做非主属性（Nonprime attribute）”，所以，关系R中的4个属性都是主属性。

为了保证数据库的完整性（正确性），数据库系统必须维护事务的以下特性（简称ACID）：①原子性（Atomicity）：事务中的所有操作要么全部执行，要么都不执行。②一致性（Consistency）：主要强调的是，如果在执行事务之前数据库是一致的，那么在执行事务之后数据库也是一致的。③隔离性（Isolation）：即使多个事务并发（同时）执行，每个事务都感觉不到系统中有其他的事务在执行，因而也就能保证数据库的一致性。④持久性（Durability）：事务成功执行后它对数据库的修改是永久的，即使系统出现故障也不受影响。

概念数据模型是按照用户的观点来对数据和信息建模，主要用于数据库设计。概念模型主要用实体—联系方法（Entity-Relationship Approach）表示，所以也称E-R模型。

本题考查编译原理基础知识。

计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式"46+5*（120-37）"的后缀表达式形式为"46 5 120 37-*+"。计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中，重复以上过程，直到后缀表达式扫描结束。

表达式"a-b*（b+d）"的后缀表达式形式为"abcd+*-。

参考课程有关内容。1、先在图中标注信号量 2、遵循P前面的信号量，V后面的信号量的原则。

本题考查编译原理基础知识。

计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式"46+5*（120-37）"的后缀表达式形式为"46 5 120 37-*+"。计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中，重复以上过程，直到后缀表达式扫描结束。

表达式"a-b*（b+d）"的后缀表达式形式为"abcd+*-。

本题考查数据结构基础知识。

用验证的方法求解，以高度为3的满二叉树（如下图所示）为例进行说明。

若m=2n+1，则结点m是n的右孩子结点。

二叉排序树的查找路径是自顶向下的，平均查找长度取决于树的高度。

分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。

动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。

贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。

题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。

分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。

动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。

贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。

回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。

题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。0/1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430,采用部分背包问题可以将物品拆分，故放1、2、3号物品后还可以放入部分4号物品，故总容量为630。

哈夫曼树是一种特殊的二叉树，但它不是完全二叉树，也不是平衡二叉树，给出n个权值{w1，w2，…，wn}构造一棵具有n个叶子结点的哈夫曼树的方法如下：

第一步，构造n个只有根结点的二叉树集合F={T1，T2，…，Tn}，其中每棵二叉树Ti的根结点带权为Wi（1≤k≤n）

第二步，在集合F中选取两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，令新二叉树根结点的权值为其左、右子树上根结点的权值之和

第三步，在F中删除这两棵二叉树，同时将新得到的二叉树加入到F中

第四步，重复第二步和第三步，直到F只含有一棵二叉树为止，这棵二叉树便是哈夫曼树

综上所述，我们可以知道哈夫曼树中权值最小的两个结点互为兄弟结点

由于叶子节点没有子树，因此它的度为0。而除根节点外，其它的节点都应该可以做为子节点，即可以用于计算度。在本题中告我有5个度为1的结点，4个度为2的结点，2个度为3的结点，那么树中总的度数为5+8+6=19，因此树中除根节点外，就应该有19个节点，所以树中总的节点数应该为20，那么叶子节点数=20-5-4-2=9。

二分法查找（折半查找）的基本思想是：（设R[low,…,high]是当前的查找区）

（1）确定该区间的中点位置：mid=[（low+high）/2]

（2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下

若R[mid].key＞k，则由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…,mid-1]中。因此，新的查找区间是左子表R[low,…,high]，其中high=mid-1

若R[mid].key＜k，则要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找区间是右子表R[low,…,high]，其中low=mid+1

若R[mid].key=k，则查找成功，算法结束

（3）下一次查找是针对新的查找区间进行，重复步骤（1）和（2）

（4）在查找过程中，low逐步增加，而high逐步减少。如果high＜low，则查找失败，算法结束。

本题考查数据结构基础知识。

从题中的邻接表中可知，该图的边为＜v1，v3>、＜v1，v2>、＜v2，v5>、＜v2，v6>、＜v3，v6>、＜v3，v2>、＜v5，v4>、＜v6，v4>、＜v6，v5>，如下图所示，显然，这是个有向图。

在无向图中，若存在边（vi，vj），则它同时为vj和vi之间的边。在上面的邻接表中，存在边＜v1，v3>，而不存在＜v3，v1>，因此该图不是无向图。

对于无向图，其边数e和顶点数n的关系为e=n×（n-1）/2。对于有向图，其边数e和顶点数n的关系为e = n×（n-1），因此该图不是完全图。

若有向图为强连通图，则任意两个顶点间要存在路径。在该有向图中，由于顶点v4没有出边，因此，不存在v4到其他顶点的路径，因此该图不是强连通图。

本题考查队列概念。

先要理解下栈和队列的概念。栈是先进后出，后进先出。队列是先进先出，后进后出。

栈的概念是弹压，就像子弹壳装弹，一粒一粒压进去，但是打出来的时候是从上面打出来的，最先压进去的最后弹出来，如果进去顺序是123，打出来顺序是321，这就是后进先出；队列是的概念就是我们平时排队，按次序来，你排在第1个，那你就第一个轮到，就是先进先出，先到先来。

而本题考察的是输出受限的双端队列，其是指只有一端可以进行出队操作而从两端都可以进行入队操作的队列。那么，其可能的输出队列是有很多种的。

在本题中，d已经进入了队列，说明a、b、c都已经进入了队列，因为d最先出队列，说明d肯定从左侧端入列。

当d从左侧入队列，且最先出队列时，那会有以下八种情况：

1. a、b、c都于左侧进入队列，则出栈序列为：d、c、b、a

2. a、b于左侧入队列，c位于右侧入队列，则出栈序列为：d、b、a、c

3. b、c于左侧入队列，a位于右侧入队列，则出栈序列为：d、c、b、a

4. a、c于左侧入队列，b位于右侧入队列，则出栈序列为：d、c、a、b

5. a于左侧入队列，b、c位于右侧入队列，则出栈序列为：d、a、b、c

6. b于左侧入队列，a、c位于右侧入队列，则出栈序列为：d、b、a、c

7. c于左侧入队列，a、b位于右侧入队列，则出栈序列为：d、c、a、b

8. a、b、c于右侧入队列，则出栈序列为：d、a、b、c ? 所以答案选择D。

在完全二义树中对结点可如下编号：根结点为1号，其左孩子结点为2号，右孩子结点为3号,对于编号为i的结点，其左孩子结点若存在，则编号为2i,其右孩子结点若存在，则编号为2i+1。可将序列中的元素放入一棵完全二叉树上进行判断，如下图所示。

根据堆的定义，可知选项D不是堆。

单向链表仅设头指针时，在表尾插入结点时需要遍历整个链表，时间复杂度为o（n）,仅设尾指针时，在表尾插入结点的时间复杂度为O（1）,但是不能访问除了尾结点之外的所有其他结点。而单向循环链表仅设头指针时，在表尾插入结点时需要遍历整个链表，时间复杂度为0（n）,仅设尾指针时，在表尾插入结点的时间复杂度为0（1）,同时达到表头结点的时间复杂度为0（1）,因此对于题中给出的操作要求，适合采用仅设尾指针的单向循环链表。

图的深度优先遍历即纵向优先遍历，类似于二叉树的前序遍历。

采用插入排序算法对6个整数{5，2，4，6，1，3}进行从小到大排序的过程如表所示。

综上，元素间共比较12次。从上表中的第4步可看出，当待插入的元素比已排序部分的所有元素都要小时，需要比较和移动的元素最多，因此当输入数据序列正好从大到小排列，而需要将其从小到大排序时，元素间的比较次数最多。

当序列基本有序时，使用插入排序效率是最高的，能达到这种算法的最优效果，O（n）。

当序列基本有序时，使用插入排序效率是最高的，能达到这种算法的最优效果，O（n）。

排序算法的稳定性如下表所示：

深度为k的二叉树最多有2^k-1个结点（k≧1）

31是27的父亲节点，31必须在27前面

本题考查数据结构基础知识。对55个元素构成的有序表进行折半查找时，可用判定树描述查找过程，由于A[19]小于中间元素A[28]，所以判定树的左分支如下所示。从中可知，查找过程中参与比较的元素分别为A[28]、A[14]、A[21]、A[17]、A[19]。

在系统开发中，原型是系统的一个早期可运行的版本，它反映最终系统的部分重要特性。 从原型是否实现功能来分，可分为水平原型和垂直原型两种。水平原型也称为行为原型，用来探索预期系统的一些特定行为，并达到细化需求的目的。水平原型通常只是功能的导航，但未真实实现功能。水平原型主要用在界面上。垂直原型也称为结构化原型，实现了一部分功能。垂直原型主要用在复杂的算法实现上。 从原型的最终结果来分，可分为抛弃式原型和演化式原型。抛弃式原型也称为探索式原型，是指达到预期目的后，原型本身被抛弃。抛弃式原型主要用在解决需求不确定性、二义性、不完整性、含糊性等。演化式原型为开发增量式产品提供基础，逐步将原型演化成最终系统，主要用在必须易于升级和优化的场合，适合于 Web项目。

本题考查面向对象中的基本概念。

在收到消息时，对象要予以响应。不同的对象收到同一消息可以产生完全不同的结果，这一现象叫做多态（polymorphism）。在使用多态的时候，用户可以发送一个通用的消息，而实现的细节则由接收对象自行决定。这样，同一消息就可以调用不同的方法。绑定是一个把过程调用和响应调用所需要执行的代码加以结合的过程。在一般的程序设计语言中，绑定是在编译时进行的，叫做静态绑定。动态绑定则是在运行时进行的，因此，一个给定的过程调用和代码的结合直到调用发生时才进行。

动态绑定是和类的继承以及多态相联系的。在继承关系中，子类是父类的一个特例，所以，父类对象可以出现的地方，子类对象也可以出现。因此在运行过程中，当一个对象发送消息请求服务时，要根据接收对象的具体情况将请求的操作与实现的方法进行连接，即动态绑定。

本题主要考查拓扑序列。

在给出拓扑图求拓扑序列时，我们应该掌握一个关键因素，那就是箭头的画出节点在箭头指向节点前，如果一个节点被很多箭头所指，那么应该要在所有这些箭头的画出节点之后才是本节点。拓扑序列的开始节点应该是没有箭头所指的节点，在本题中应该是5或6，这里需要注意它们谁在最前面都可以。那么按照这个原则我们就可以知道本题的拓扑序列应该为6 5 4 3 2 1或者5 6 4 3 2 1。

本题考查面向对象技术的基础知识。 考生应该了解UML的典型模型，包括用例图、类图、序列图、活动图等。本题考查类图，类图主要是对系统的词汇建模，或者对简单的协作建模，或者对逻辑数据库模式建模，而用例图对系统的需求建模。 类图中，类和类之间的关系有依赖关系、关联关系、聚集关系、组合关系和泛化关系，其中聚集关系和组合关系是表示更强的关联关系，表示整体和部分的关系，而组合关系的类之间具有相同的生命周期。图中类University和类School之间是聚集关系，类Person和类PersonRecord之间是依赖关系，表示Person与PersonRecord之间的语义关系，其中PersonRecord发生变化会影响Person的语义。

本题考查统一建模语言（UML）的基本知识。

用例图（use case diagram）展现了一组用例、参与者（Actor）以及它们之间的关系。用例图通常包括用例、参与者，以及用例之间的扩展关系（＜＜extend>>）和包含关系（＜＜include>>），参与者和用例之间的关联关系，用例与用例以及参与者与参与者之间的泛化关系。如下图所示。

用例图用于对系统的静态用例视图进行建模，主要支持系统的行为，即该系统在它的周边环境的语境中所提供的外部可见服务。

本题考查常见设计模式的功能，备选答案中除Delegation，其它均为经典设计模式。

适配器（adapter）模式。适配器模式将一个接口转换成客户希望的另一个接口，从而使接口不兼容的那些类可以一起工作。适配器模式既可以作为类结构型模式，也可以作为对象结构型模式。在类适配器模式中，通过使用一个具体类将适配者适配到目标接口中；在对象适配器模式中，一个适配器可以将多个不同的适配者适配到同一个目标。装饰（decorator）模式。装饰模式是一种对象结构型模式，可动态地给一个对象增加一些额外的职责，就增加对象功能来说，装饰模式比生成子类实现更为灵活。通过装饰模式，可以在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责；当需要动态地给一个对象增加功能，这些功能可以再动态地被撤销时可使用装饰模式；当不能采用生成子类的方法进行扩充时也可使用装饰模式。

代理（proxy）模式。代理模式是一种对象结构型模式，可为某个对象提供一个代理，并由代理对象控制对原对象的引用。代理模式能够协调调用者和被调用者，能够在一定程度上降低系统的耦合度，其缺点是请求的处理速度会变慢，并且实现代理模式需要额外的工作。

部署图展现了运行处理节点以及其中的构件的配置。部署图给出了体系结构的静态实施视图。它与构建视图相关，通产一个结点包含一个或多个构件。

本题考查对软件开发工具相关内容的了解。结构化方法（Structured Method）是强调开发方法的结构合理性以及所开发软件的结构合理性的软件开发方法。针对软件生存周期各个不同阶段，它包括结构化分析（SA）、结构化设计（SD）和结构化程序设计（SP）等方法。结构化分析方法给出一组帮助系统分析人员产生功能规约的原理与技术。它一般利用图形表达用户需求，使用的手段主要有数据流图、数据字典、结构化语言、判定表以及判定树等，其中不包括问题分析图。

静态结构：主要包括用例图、类图和包图

动态视图：主要包括活动图、状态图、序列图和协作图。动态视图中，交互视图描述了执行系统功能的各个角色之间相互传递消息的顺序关系，主要包括序列图、协作图

根据目的和用途不同，设计模式可分为创建型(Creadonal)模弍、结构型(Structural)模式和行为型(Behavioral)模式三种。创建型模式主要用于创建对象，结构型模式主要用于处理类或对象的组合，行为型模式主要用于描述类或对象的交互以及职责的分配。根据题干的描述，适用于该要求的设计模式应属于结构型模式。Flyweight(享元)和Proxy(代理)属于结构型模式。Flyweight模式通过运用共享技术，有效地支持大量细粒度的对象。系统只使用少量的对象，而这些对象都很相似，状态变化很小，对象使用次数增多。Proxy模式可为某个对象提供一个代理，并由代理对象控制对原对象的引用。代理模式能够协调调用者和被调用者，能够在一定程度上降低系统的耦合度。因此本题适合于采用Flyweight模式。

本题考查贪心算法和背包问题的知识点。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

0/1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430，采用部分背包问题可以将物品拆分，故放1、2、3号物品后还可以放入部分4号物品，故总容量为630。

① 有6个不同字母，需要采用3位二进制进行编码。② 本题对应的哈夫曼树如下所示：

若二叉树为单技树，那幺n个节点就分布在n层上。遍历序列则与遍历方法和二叉树的形态有关。例如，对于三个节点的单技二叉树，其形态可为：

CD能推出题中关系式的所有属性，因此R的候选关键字为CD。

判断是否为无损连接，首先进行R1∩R2=C，由于C不能推出R1或者R2中的任何属性值，因此该分解为有损分解。原关系式F中有D→A而分解的Rl（ABCE）中没有D，所以该分解不保持函数依赖。

根据题目对霍夫曼编码的描述，我们不难知道，每次都是选择当前最小的情况，这符合贪心算法总是找当前看来最优的情况，因此属于贪心策略。

如果对包含100，000个字符，且这些字符都属于a到f。那么如果采用固定长度的编码，针对于每个字符需要3位来编码（因为有6个不同的字符，至少需要3位才能表示6种不同的变化）。那么对100000个字符编码，其编码长度为300000。

如果采用霍夫曼编码，那么首先我们就要根据字符出现的频率构造出其霍夫曼树。首先选择出现频率最低的4和8，生成子树，其父节点为12，然后放入出现频率队列中，后面的采用同样的道理，以此类推。构造出的霍夫曼树如下图所示：

对于循环队列，求队头元素的指针的计算公式为：(rear-len+1+M)%M。

求队列中元素个数公式为：(rear-fear+M)%M。其中fear表示队列的对头指针。

本题考查图结构基础知识。对于n个顶点的简单无向图，每个顶点最多与其余的n-1个结点邻接（若两个顶点之间有边，则称为邻接），因此，最多有n（n-1）条边，同时，由于边没有方向，因此一条边关联的两个顶点，邻接关系被计算了两次，所以边的个数为n（n-1）/2。

本题考查贪心算法和背包问题的知识点。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

0/1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430，采用部分背包问题可以将物品拆分，故放1、2、3号物品后还可以放入部分4号物品，故总容量为630。

根据题目对霍夫曼编码的描述，我们不难知道，每次都是选择当前最小的情况，这符合贪心算法总是找当前看来最优的情况，因此属于贪心策略。

如果对包含100，000个字符，且这些字符都属于a到f。那么如果采用固定长度的编码，针对于每个字符需要3位来编码（因为有6个不同的字符，至少需要3位才能表示6种不同的变化）。那么对100000个字符编码，其编码长度为300000。

如果采用霍夫曼编码，那么首先我们就要根据字符出现的频率构造出其霍夫曼树。首先选择出现频率最低的4和8，生成子树，其父节点为12，然后放入出现频率队列中，后面的采用同样的道理，以此类推。构造出的霍夫曼树如下图所示：

A1A3→A2，A2→A3，没有出现A4，所以候选关键字中肯定包A4，属性A1A3A4决定全属性，故为候选关键字。同理A1A2A4也为候选关键字。设U1={A1，A2}，U2={A1，A3}，那么可得出：U1∩U2→（U1-U2）=A1→A2，U1∩U2→（U2-U1）=A1→A3，而A1-A2，A1-A3?F+，所以分解ρ是有损连接的。又因为F1=F2=?，F+≠（F1∪F2）+，所以分解不保持函数依赖。

A1A3→A2，A2→A3，没有出现A4，所以候选关键字中肯定包A4，属性A1A3A4决定全属性，故为候选关键字。同理A1A2A4也为候选关键字。设U1={A1，A2}，U2={A1，A3}，那么可得出：U1∩U2→（U1-U2）=A1→A2，U1∩U2→（U2-U1）=A1→A3，而A1-A2，A1-A3?F+，所以分解ρ是有损连接的。又因为F1=F2=?，F+≠（F1∪F2）+，所以分解不保持函数依赖。

因为相关的条件判断要同时成立，因此需要用AND进行连接。

关系R（A,B,C,D,E）和S（B,C,F,G）做自然连接时，会以两个关系公共字段做等值连接，然后将操作结果集中重复列去除，所以运算后属性列有7个。

接下来分析关系表达式的SQL形式，题目中关系表达式先进行了R与S的自然连接。得到的结果集为：RS（R.A,R.B,R.C,R.D,R.E,S.F,S.G）。此后的选择操作“σ3＜6”可表达为“σR．C＜S．F”；最后进行投影操作“π1,3,6,7”即选出结果集的第1，3，6，7列，对应的列为：R.A，R.C，S.F，S.G（由于无重复字段，A，C，F，G及A,R．C,F,G或其它等价形式均可）。

自然连接

是指R与S关系中相同属性列名的等值连接运算后，再去掉右边重复的属性列名S.B、S.C，所以经

运算后的属性列名为：R.A、R.B、R.C、R.D、S.E和S.F，共有6个属性列。π1,3,5,6（σ3＜6（

））的含义是从

结果集中选取R.C＜S.F的元组，再进行R.A、R.C、S.E和S.F投影，故选项A是正确的。由于自然连接是指R与S关系中相同属性列名的等值连接，故需要用条件“WHERE R.B=S.B AND R.C=S.C”来限定；又由于经自然连接

运算后，去掉了右边重复的属性列名S.B、S.C，使得第三列属性列名和第六列属性列名分别为R.C、S.F，所以选取运算σ3＜6需要用条件“WHERE R.C＜S.F”来限定。

本题考查对分布式数据库基本概念的理解。分片透明是指用户或应用程序不需要知道逻辑上访问的表具体是怎么分块存储的。复制透明是指采用复制技术的分布方法，用户不需要知道数据是复制到哪些节点，如何复制的。位置透明是指用户无须知道数据存放的物理位置。逻辑透明，即局部数据模型透明，是指用户或应用程序无须知道局部场地使用的是哪种数据模型

本题考查数据库基本概念和SQL语言。由于学生号Sno能唯一区别学生关系中的每一个元组（记录），所以Sno是学生关系的主键。虽然SD不是学生关系的码，但SD是关系Dept的主键，所以SD是外键。由于子查询中WHERE SD='MS'意味着找出数学系所有学生的年龄，所以当外查询的学生年龄都小于子查询中的学生年龄即满足条件。根据题意需查询其他系比数学系MS所有学生年龄都要小的学生姓名及年龄，所以外查询中的条件语句需加上SD＜>'MS'进行限定。

根据以上分析，完整的SQL语句如下：

SELECT Sname，Sage

关系R（A,B,C,D,E）和S（B,C,F,G）做自然连接时，会以两个关系公共字段做等值连接，然后将操作结果集中重复列去除，所以运算后属性列有7个。接下来分析关系表达式的SQL形式，题目中关系表达式先进行了R与S的自然连接。得到的结果集为：RS（R.A,R.B,R.C,R.D,R.E,S.F,S.G）。此后的选择操作“σ3＜6”可表达为“σR．C＜S．F”；最后进行投影操作“π1,3,6,7”即选出结果集的第1，3，6，7列，对应的列为：R.A，R.C，S.F，S.G（由于无重复字段，A，C，F，G及A,R．C,F,G或其它等价形式均可）。

数据库系统的三级模式为外模式、概念模式、内模式。（1）概念模式。概念模式（模式、逻辑模式）用以描述整个数据库中数据库的逻辑结构，描述现实世界中的实体及其性质与联系，定义记录、数据项、数据的完整性约束条件及记录之间的联系，是数据项值的框架。（2）外模式。外模式（子模式、用户模式）用以描述用户看到或使用的那部分数据的逻辑结构，用户根据外模式用数据操作语句或应用程序去操作数据库中的数据。外模式主要描述组成用户视图的各个记录的组成、相互关系、数据项的特征、数据的安全性和完整性约束条件。（3）内模式。内模式是整个数据库的最低层表示，不同于物理层，它假设外存是一个无限的线性地址空间。内模式定义的是存储记录的类型、存储域的表示以及存储记录的物理顺序，指引元、索引和存储路径等数据的存储组织。

本题考查数据库基本概念和SQL语言。由于学生号Sno能唯一区别学生关系中的每一个元组（记录），所以Sno是学生关系的主键。虽然SD不是学生关系的码，但SD是关系Dept的主键，所以SD是外键。由于子查询中WHERE SD='MS'意味着找出数学系所有学生的年龄，所以当外查询的学生年龄都小于子查询中的学生年龄即满足条件。根据题意需查询其他系比数学系MS所有学生年龄都要小的学生姓名及年龄，所以外查询中的条件语句需加上SD＜>'MS'进行限定。

根据以上分析，完整的SQL语句如下：

SELECT Sname，Sage

本题考查数据库基本概念和SQL语言。由于学生号Sno能唯一区别学生关系中的每一个元组（记录），所以Sno是学生关系的主键。虽然SD不是学生关系的码，但SD是关系Dept的主键，所以SD是外键。由于子查询中WHERE SD='MS'意味着找出数学系所有学生的年龄，所以当外查询的学生年龄都小于子查询中的学生年龄即满足条件。根据题意需查询其他系比数学系MS所有学生年龄都要小的学生姓名及年龄，所以外查询中的条件语句需加上SD＜>'MS'进行限定。

根据以上分析，完整的SQL语句如下：

SELECT Sname，Sage