发布时间 : 星期三 文章软件设计师2010年下半年上午试题及详细答案更新完毕开始阅读
冲突主要分为结构冲突、属性冲突和命名冲突三类。 选项A显然是不正确的。
选项B不正确。因为结构冲突是指同一实体在不同的分E-R图中有不同的属性，同一对象在某一分E-R图中被抽象为实体而在另一分E-R图中又被抽象为属性，需要统一。
选项C不正确，因为属性冲突是指同一属性可能会存在于不同的分E-R图，由于设计人员不同或是出发点不同，对属性的类型、取值范围、数据单位等可能会不一致，这些属性对应的数据将来只能以一种形式在计算机中存储，这就需要在设计阶段进行统一。
选项D正确，因为命名冲突是指相同意义的属性在不同的分E-R图上有着不同的命名，或是名称相同的属性在不同的分E-R图中代表着不同的意义，这些也要进行统一。52、C 53、D
本题考查关系运算和E-R图的基本概念。
试题(52)的正确答案为C。简单属性是原子的、不可再分的。复合属性可以细分为更小的部分(即划分为别的属性)。有时用户希望访问整个属性，有时希望访问属性的某个成分，那么在模式设计时可采用复合属性。本题学生实体集Students的“家庭住址”可以进一步分为邮编、省、市、街道。
在大多数情况下，定义的属性对于一个特定的实体都只有单独的一个值。例如，对于一个特定的学生，只对应一个学生号、学生姓名，这样的属性叫做单值属性。但是，在某些特定情况下，一个属性可能对应一组值。例如，学生可能有0个、1个或多个亲属，那么学生的亲属的姓名可能有多个。这样的属性称为多值属性。为了将数据库模式设计得更合理，试题(53)应该将家庭成员、关系及联系电话加上学生号设计成为一个独立的实体。54、D 55、B 56、C
本题主要考查关系模式规范化方面的相关知识。
试题(54)的正确答案为D。因为根据函数依赖集F可知(时间，学生)可以决定关系R中的全部属性，故关系模式R的一个主键是(时间，学生)。
试题(55)的正确答案为B。因为根据函数依赖集F可知，R中的每个非主属性完全函数依赖于(时间，学生)，所以R是2NF。
试题(56)的正确答案为C。因为R2(学生，课程，成绩)的主键为(学生，课程)，而R2的每个属性都不传递依赖于R2的任何键，所以R2是BCNF。 57、D
本题考查数据结构的基础知识。
从题目中的图可以推导出，队头元素的指针为(Q.rear-Q.len+1+M)%M。 58、C
本题考查数据结构的基础知识。
树的带权路径长度为树中所有叶子节点的带权路径长度之和。哈夫曼树是指权值为w1，w2，?，wn的n个叶子节点的二叉树中带权路径长度最小的二叉树。 构造最优二叉树的哈夫曼算法如下：
(1)根据给定的n个权值{w1，w2，?，wn}，构成n棵二叉树的集合F={T1，T2，?，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均空。
(2)在F中选取两棵权值最小的二叉树作为左、右子树构造一棵新的二叉树，
置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。 (3)从F中删除这两棵树，同时将新得到的二叉树加入到F中。
重复(2)、(3)，直到F中只含一棵树时为止。这棵树便是最优二叉树(哈夫曼树)。
从以上叙述可知，哈夫曼树中权值最小的两个节点互为兄弟节点。 59、A
本题考查数据结构的基础知识。
拓扑排序是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。
对AOV网进行拓扑排序的方法如下：
(1)在AOV网中选择一个入度为零(没有前驱)的顶点且输出它； (2)从网中删除该顶点及与该顶点有关的所有边；
(3)重复上述两步，直至网中不存在入度为零的顶点为止。 本题中只有序列“6 5 4 3 2 1”可由上述过程导出。
对有向图进行拓扑排序的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路。 60、D
本题考查数据结构的基础知识。
对序列15，23，38，47，55，62，88，95，102，123进行二分查找的过程可用以下二叉树之一描述，其中，左图描述的是除2以后向下取整时的判定过程，右图则对应除2以后向上取整时的判定过程。
从上图可知，二分法查找95时，参与比较的元素依次为55、95，或者62、102、95。 61、B
本题考查数据结构的基础知识。
设树中的节点总数为n、分支数目为m，那么n=5+4+2+叶子节点数，m=5×1+4×2+2×3。
在树中，节点总数等于分支数目加上1，即n=m+1。 因此，叶子节点数=5×1+4×2+2×3+1-5-4-2=9 62、A
该题可以用主方法来求解，对该递归式，a=1，b=2，而f(n)=nlgn，属于
2
第二种情况，因此，其时间复杂度为Θ(nlgn)。该题还可以用递归树求解。 63、C
矩阵连乘问题指的是确定n个矩阵相乘的次序，即给这n个相乘的矩阵加括号，使得按照该顺序进行计算时所需要的标量乘法的次数最少。用m[1，n]来表示n个矩阵M1×M2×...×Mn相乘所需要的最小标量乘法的次数，则可以用递归式 其中pi-1pkpj分别表示第i个矩阵的行数、第k个矩阵的列数和第j个矩阵的列数来表示该问题的最优子结构。
根据上述递归式，自底向上求解得到m[1,4]=3100，对应的最优的加括号方式为(M1×(M2×M3))×M4。 64、A
该题考查算法分析的基础知识，以及对算法中循环结构的掌握。
分析算法时间复杂度并不是确定算法运行的具体时间的长短，而是执行某个(某些)操作的次数。该题要求计算count++语句执行的次数，根据上述C程序段可知，i=1时执行1次，i=2时执行2次，i=4时执行4次，i=8时执行8次，总共执行次数为1+2+4+8=15次。 65、B
0-1背包问题是一个经典的最优化问题，问题描述为：有n个物品，第i个物品价值为vi，重量为wi，其中vi和wi均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。该问题可以形式化地描述如下：
目标函数为，约束条件为，xi∈{0,1}
0-1背包问题具有最优子结构。考虑重量至多为W的背包中的物品的最大价值，若把第j个物品从背包中去掉，则剩下的背包中的物品的价值应该是n-1项物品(除了第j项)背包容量为W-wj的子问题的最大价值。该问题可以通过动态规划算法来求得最优解。同时可以通过回溯法和分支限界法进行系统的搜索得到最优解。但是由于问题不具有贪心选择性质，即通过局部最优选择不能得到全局最优解，因此用贪心算法求解不能保证得到最优解。66、A 67、D
本题考查公钥体系的概念和应用。
1976年斯坦福大学的Diffie和Hellman提出了使用不同的密钥进行加密和解密的公钥加密算法。设P为明文，C为密文，E为公钥控制的加密算法，D为私钥控制的解密算法，这些参数满足下列3个条件： (1)D(E(P))=P
(2)不能由E导出D
(3)选择明文攻击(选择任意明文-密文对以确定未知的密钥)不能破解E 加密时计算C=E(P)，解密时计算P=D(C)。加密和解密是互逆的。用公钥加密、私钥解密，可实现保密通信；用私钥加密、公钥解密，可实现数字签名。 68、B
本题考查考生对HTTP命令的掌握程度。
GET是HTTP协议提供的少数操作方法中的一种，其含义是读一个网页。HEAD命令用于读取网页头信息。POST命令用于把消息加到指定的网页上。没有READ这一命令。 69、C
本题考查数据交换网的基础知识。
帧中继(Frame Relay，FR)是为克服X.25交换网的缺陷、提高传输性能而发展起来的高速分组交换技术。帧中继网络不进行差错和流量控制，并且通过流水方式进行交换，所以比X.25网络的通信开销更少，传输速度更快。
帧中继提供面向连接的虚电路服务，因而比DDN专线更能提高通信线路利用率，用户负担的通信费用也更低廉。在帧中继网中，用户的信息速率可以在一定的范围内变化，从而既可以适应流式业务，又可以适应突发式业务，这使得帧中继成为远程传输的理想形式。
70、A
本题考查HTML文档中＜table＞标记常用的属性定义。Align用于定义文本的对齐方式。71、C 72、A 73、B 74、A 75、B