Thursday, July 08, 2004

 

Some problems for 2003 Chinese High Level Programmer Test

作者:chzg99
出处:http://www.csdn.net/Develop/article/26/26439.shtm
http://www.csdn.net/develop/article/26/26440.shtm
http://www.csdn.net/Develop/article/26/26182.shtm
http://www.csdn.net/Develop/article/26/26181.shtm

数据库基础知识包括数据库模型,关系数据库的基础知识,数据库系统的结构,SQL的使用,常用数据库管理系统的知识。考生在复习时除了看教材相关部分外,还应该多做历届相关真题,同时可参考《数据库系统概论》萨师煊(第三版),因为该书中有更详细的一些概念说明,而教材中有些地方没有讲到。
1.在数据库逻辑结构的设计中,将E-R模型转换为关系模型应遵循相关原则。对于三个不同实体集和它们之间的多对多联系m:n:p,最少可转换为____个关系模式。

A. 2 B.3 C. 4 D. 5

答案:C

解析:书本上讲过两个不同实体集和它们之间的多对多联系时,可把两个不同实体集转换成两个关系模式,多对多的联系可以转换成一个关系模式。对于三个不同实体集和它们之间的多对多联系m:n:p,也是把三个不同实体集转换成三个关系模式,其中的两个多对多的联系最少可以转换成一个关系模式,所以共4个关系模式。

2.给定关系模式R(U,F),U={A,B,C,D,E},F={B→A,D→A,A→E,AC→B},其属性AD的闭包为__(1)__,其候选关键字为__(2)__。

(1) A. ADE B. ABD C. ABCD D. ACD

(2) A. ABD B.ADE C.ACD D.CD

答案:(1) A (2) D

解析:(1)闭包的定义在教材中没有给出,具体的闭包定义考生可参考《数据库系统概论》萨师煊(第三版),第184页。求属性集的闭包可由固定的算法推出:设X(0)=AD;计算X(1);逐一扫描F集合中各个函数依赖,找左部是A、D或AD的函数依赖,得到:A→E,D→A。于是X(1)= X(0) ∪EA=ADE。由于X(0) ≠X(1),所以再逐一扫描F集合中各个函数依赖,找左部是ADE的子集的那些函数依赖,得到 A→E,D→A。于是X(2)= X(1) ∪EA=ADE。由于X(2)= X(1),所以算法到此为止,其属性AD的闭包为X(2),即ADE。 (2)对于键和函数依赖的关系,有两个条件:设关系模式R(A1,A2...An),F是R上的函数依赖集,X是R的一个子集,①X→A1A2...An∈F+ (它的意思是X能够决定唯一的一个元组) ②不存在X的真子集Y,使得Y也能决定唯一的一个元组,则X就是R的一个候选键(它的意思是X能决定唯一的一个元组但又没有多余的属性集)。可以利用Armstrong 的推理规则,求出X使得X→ABCDE。由D→A和AC→B,可得:DC→B,由B→A得:DC→A,又由A→E得:DC→E。而DC→C,DC→D。所以由上可知:DC→ABCDE。故候选关键字为CD。

3.若有关系模式R(A,B,C)和S(C,D,E),对于如下的关系代数表达式:

E=∏A,D(σB<'2003'∧R.C=S.C∧E='80'(R×S))

E=∏A,D(σR.C=S.C(σB<'2003'(R)×σE='80'(S)))

E=∏A,D(σB<'2003'(R) σE='80'(S))

E=∏A,D(σB<'2003'∧E='80'(R S))
正确的结论是__(20)__ ,表达式 __(21)__ 的查询效率最高。

(1) A. E1≡E2≡E3≡E4 B. E3≡E4但E1≠E2

C. E1≡E2但E3≠E4 D. E3≠E4但E2≡E4

(2) A. E1 C. E3 B. E2 D. E4

答案:(1)A (2) C

解析:(1)这道题的查询含义是:找出R.C=S.C时,其中B<'2003'且E='80',只含A、D属性的这些记录。从E1、E2、E3、E4式子中看出它们是等价的。(2)查询优化的目的就是为了系统在执行时既省时间又能提高效率。优化的策略主要有以下几点:①在关系代数表达式中尽可能早地执行选择操作(早选择)(这是最总要最基本的一条) ②把笛卡尔积和随后的选择操作合并成F联接运算(F联接) ③同时计算一连串的选择和投影操作(同时算) ④保留同一子表达式的结果 ⑤适当对关系文件进行预处理 ⑥计算表达式之前先估计一下怎么计算合算。根据第一条可知E3是查询效率最高的。

4.集合A={d.b.c}上的二元关系R为:R={,,)},则二元关系R是____。

A.自反的 B.反自反的 C.对称的 D.传递的

答案:D

解析:这道题属于离散数学范围。考生只需要清楚自反、反自反、对称、传递的含义,就能轻松解题。R不是自反的,因为R中不含。因为R中含有但不含< b,a >。也不是反自反的,因为含有。也不是对称的,因为R中含有但不含< b,a >。R是传递的,因为R中只有可以发生传递,而传递后的结果含在其中。

操作系统是软考上午必考的内容,虽然这部分的考题不多,但复习起来的内容还是比较多的。主要涉及到操作系统的类型的功能,操作系统的层次结构和进程概念,作业、处理机、存储、文件和设备等管理的原理和方法。细看起来每一部分都有可能出题。如果考生对操作系统知识不熟悉,光看王春森的高程教程是不够的,建议考生复习时参考汤子瀛的《计算机操作系统》。
1.在UNIX操作系统中,当用户执行如下命令:

1ink("/user/include/myfile.sh","/usr/userwang/youfile.sh")

则文件名"/usr/userwang/youfile.sh"存放在____。

A. user目录文件中 B. include目录文件中

C. userwang目录文件中 D. youfile.sh的文件内容中

答案:C

解析:1ink命令属于文件系统调用,主要是为了实现文件共享,它有两个参数:path1和path2,path1是源文件名称,path2是新建立的目录文件名称。1ink命令的实质是为文件建立一个新目录项,为文件增加一个新的路径名。上述1ink命令就使得用户userwang可以使用"/usr/userwang/youfile.sh"路径名对"/user/include”路径下的myfile.sh进行访问。如果用户不想共享文件了,还可以执行un1ink命令。

复习提示:考生应该对UNIX中的文件系统管理方式清楚。

2.假设在系统中—个文件有两个名字,它与—个文件保存有两个副本的区别是____。

A. 前者比后者所占用的存储空间更大

B. 前者需要两个目录项,后者只需要一个目录项

C. 前者存取文件的速度快,后者存取文件的速度慢

D. 前者改变与某个名字相联系的文件时,另一个名字相连的文件也改变;后者的另一个副本不改变

答案:D

解析:系统中—个文件有两个名字,则该文件有两个目录项与之关联,实际存储的文件只有一个。而对于—个文件保存有两个副本,则文件需要目录项,副本也需要目录项,而且实际存储的是三个文件:文件及两个副本。由此答案A显然不对,应该是后者比前者所占用的存储空间更大。答案B也不对,因为后者需要三个目录项。答案C不对,因为文件的存取速度与文件的存储方式有关,上题中前者与后者存储方式一样,只不过是目录项的个数有区别。一个文件有多个名字,可以看成是多个名字共享一个文件,所以改变与某个名字相联系的文件时,另一个名字相连的文件也改变,但后者文件与副本之间可以看成是独立的,所以另一个副本不改变。

3.在某超市里有一个收银员,且同时最多允许有n个顾客购物,我们可以将顾客和收银员看成是两类不同的进程,且工作流程如下图所示。为了利用PV操作正确地协调这两类进程之间的工作,设置了三个信号量S1、S2和Sn,且初值分别为0、0和n。这样图中的a应填写__(1)__,图中的b1、b2应分别填写__(2)__,图中的c1、c2应分别填写__(3)__。

(1) A. P(S1) B.P(S2) C.P(Sn) D.P(Sn)、P(S1)

(2) A.P(Sn)、V(S2) B.P(Sn)、V(S1) C.P(S2)、V(S1) D.V(S1)、P(S2)

(3) A.P(S1)、V(S2) B.P(Sn)、V(S1) C.P(S2)、V(S1) D. V(S1)、 P(S2)

答案:(1)C (2)D (3)A

解析:这是一道考查PV操作的题,所以首先得弄清楚那些地方需要互斥、那些地方需要同步。题目中给出了两类进程:顾客进程与收银元进程,由于超市是顾客进程之间的公有资源,而且超市里限制最多允许有n个顾客购物,所以要设置一个公有信号量Sn,初值是n,顾客进程在进入超市时要执行P(Sn),离开超市时要执行V(Sn)操作。顾客购物后要到收银员处付款,因此顾客进程与收银员进程之间是同步的关系,一次只允许一个顾客进程付款,整个超市只有一个收银员进程收费,所以需要为顾客进程设置一个私有信号量S2,为收银员进程设置一个私有信号量S1,由于开始时没有顾客去付款,收银员也没有收费,所以S1和S2的初值为0。当有顾客买完东西去付款时执行V(S1),通知收银员进程有顾客付款,此时收银员进程执行P(S1)操作后就可进入收费,收费完成后收银元进程执行V(S2),以通知顾客收费完毕,此时顾客执行P(S2)就可离开收银台,在离开超市时需执行V(Sn),释放资源。

复习提示:PV操作在操作系统中处于很重要得地位,要想合适的运用PV操作,必须很好的理解进程之间的互斥与同步,即那些进程之间是互斥的,那些进程之间是同步的。

软件工程是计算机软件的一个重要分支,主要应掌握软件工程的基本原理以及软件设计与测试方法。软考中每次考的题量虽然不多,但如果考生没有全面复习掌握软件工程的知识点,要想答对题不是件容易的事。如果考生只是一味的记住软件工程中的条条框框,而不去理解理论背后的含义,复习过程枯燥无味如同嚼蜡。只要考题陈述形式一变,许多考生就会无所适从。不过学软件工程的第一步,还是要先记住理论。2003年度的试题没有涉及到软件测试,2004年度的考生应该加强这方面的注意力与复习。建议考生参考Roger S.Pressman的《软件工程——实践者的研究方法》,考试中的许多知识点的叫法与解释都是来源于该书。

1.系统中模块的____不仅意味着作用于系统的小变动将导致行为上的小变化,也意味着规格说明的小变动将影响到一小部分模块。

A. 可分解性 B. 保护性 C. 可理解性 D. 连续性

答案:D

解析:在考虑模块化时,有一个重要问题:如何定义给定大小的一个合适模块?Meyer定义了五个标准:可分解性、保护性、可理解性、连续性、可组装性。模块可分解性是指如果一种设计方法提供了将问题分解成子问题的系统化机制,它就能降低整个系统的复杂性,从而实现一种有效的模块化解决方案。模块保护是指如果模块内出现异常情况,并且它的影响限制在模块内部,则错误引起的副作用就会被最小化。模块可理解性是指如果一个模块可以作为一个独立的单位(不用参考其他模块)被理解,那么它就易于构造和修改。模块连续性是指在程序中进行小的修改的能力以及使这些修改在仅仅一个或很少的几个模块中发生对应修改下的反应,则修改引起的副作用就会被最小化。模块可组装性是指如果一种设计方法使现存的(可复用的)设计构件能被组装成新系统,它就能提供一种不一切从头开始的模块化解决方案。由于本题设计到系统的小变动与规格说明的小变动将带来什么结果,根据题意应选D。

2.下面关于面向对象方法中消息的叙述,不正确的是______。

A. 键盘、鼠标、通信端口、网络等设备一有变化,就会产生消息

B.操作系统不断向应用程序发送消息,但应用程序不能向操作系统发送消息

C. 应用程序之间可以相互发送消息

D.发送与接收消息的通信机制与传统的子程序调用机制不同

答案:B

解析:消息是对象间互相联系的手段,消息刺激接收对象产生某种行为,通过操作的执行来完成相应行为。操作系统与应用程序之间可以互相发送消息,所以B是错误的。

3.面向对象技术中,对象是类的实例。对象有三种成份:________、属性和方法(或操作)。

A. 标识 B. 规则 C. 封装 D. 消息

答案:A

解析:对象有三种成份:标识、属性和方法(或操作)。每个对象都有自己的属性值,表示该对象的状态。对象中的属性只能够通过该对象所提供的操作来存取或修改。操作也称为方法或服务,它规定了对象的行为,表示对象所提供的服务。

4.软件开发的螺旋模型综合了瀑布模型和演化模型的优点,还增加了__(1)__。采用螺旋模型时,软件开发沿着螺线自内向外旋转,每转一圈都要对__(2)__ 进行识别和分析,并采取相应的对策。螺旋线第一圈的开始点可能是一个__(3)__ 。从第二圈开始,一个新产品开发项目开始了,新产品的演化沿着螺旋线进行若干次迭代,一直运转到软件生命期结束。

(1) A. 版本管理 B.可行性分析 C. 风险分析 D. 系统集成

(2) A.系统 B.计划 C. 风险 D.工程

(3)A.原型项目 B.概念项目 C. 改进项目 D. 风险项目

答案:(1) C (2) C (3) B

解析:软件开发的螺旋模型综合了瀑布模型和演化模型的优点,还增加了风险分析,每转一圈都要对风险进行识别和分析,螺旋线第一圈的开始点可能是一个概念项目。从第二圈开始,一个新产品开发项目开始了,新产品的演化沿着螺旋线进行若干次迭代,一直运转到软件生命期结束。

5.关于程序模块优化的启发式规则有若干条,以下规则中不符合优化原则的是__(1)__。如果一个模块调用下层模块时传递一个数据结构,则这种耦合属于__(2)__。

(1)A.通过模块的合并和分解,降低模块的耦合度,提高模块的内聚性

B.提高上层模块的扇出,减少模块调用的层次

C.将模块的作用范围限制在模块的控制范围之内

D.降低模块之间接口的复杂性,避免“病态连接”

(2)A.简单耦合 B.直接耦合 C.标记耦合 D.控制耦合

答案:(1)B (2) C

解析:(1)关于程序模块优化的启发式规则有若干条:评估程序结构的“第一次迭代”以降低耦合并提高内聚;试图用高扇出使结构最小化;当深度增加时争取提高扇入;将模块的影响限制在模块的控制范围内;评估模块接口以降低复杂度和冗余并提高一致性;定义功能可以预测的模块,但要避免过分限制的模块;力争“受控入口”模块,避免“病态连接”;根据设计约束和可移植性需求,对软件进行打包。答案A 、C、D都符合上述准则,若要减少模块调用的层次即当深度增加时,应该争取提高扇入,所以答案B不符合原则。(2)一个数据结构的一部分借助于模块接口被传递是标记耦合。两个模块之间的耦合方式有七种:非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合、内容耦合。

6.软件设计包括四个既独立又相互联系的活动,分别为__(1)__、__(2)__、数据设计和过程设计。

(1)A.用户手册设计 B.语言设计 C.体系结构设计 D.文档设计

(2)A.文档设计 B.程序设计 C.实用性设计 D.接口设计

答案:(1) C (2) D

解析:设计模型可以表示成金字塔,这种形状的象征意义是重要的,金字塔是极为稳固的物体,它具有宽大的基础和低的重心。象金字塔一样,我们希望构造坚固的软件设计,我们通过用数据设计建立宽广的基础,用体系结构和接口设计建立坚固的中部,以及应用过程设计构造尖锐的顶部,从而创建出不会被修改之风轻易“吹倒”的设计模型。

7.美国卡内基—梅隆大学SEI提出的CMM模型将软件过程的成熟度分为5个等级,以下选项中,属于可管理级的特征是____。

A.工作无序,项目进行过程中经常放弃当初的计划

B.建立了项目级的管理制度

C.建立了企业级的管理制度

D.软件过程中活动的生产率和质量是可度量的

答案: D

解析:SEI的模型提供了衡量一个公司软件工程实践的整体有效性的方法,且建立了五级的过程成熟度级别,第一级:初始级,第二级:可重复级,第三级:定义级, 第四级:管理级,第五级:优化级。第四级管理级是指软件过程和产品质量的详细度量数据被收集,通过这些度量数据,软件过程和产品能够被定量地理解和控制,此级包含了第三级的所有特征。根据各选项应选择答案D。

5. 将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表,最少需要进行关键字比较____次。

A. 1 B. n-1 C. n D. 2n

答案:C

解析:考生首先要明白两个前提:一是要归并的两个表都是递增有序的且长度都为n,二是题目问的是最少的关键字比较次数,即最好的情况下的比较次数。而最好的情况应该是:一个表的所有关键字都大于(或小于)另一个表的所有关键字,如:(1 2 3 4)与(5 6 7 8)。比较的时候有两个指针分别指向两个表的第一个元素,由于一个表的关键字要都大于另一个表的关键字,所以关键字小的表中的元素挨个与关键字大的表的第一个元素比较后,先被并入到新表中,这时关键字大的表的指针还是指向第一个元素没变,此时只需将关键字大的表复制到新表中即可。所以花费的比较次数就是关键字小的表长,也就是n。

6.已知AOE网中顶点v1~v7分别表示7个事件,弧al~a10分别表示10个活动,弧上的数值表示每个活动花费的时间,如下图所示。那么,该网的关键路径的长度为__(1)__,活动a6的松驰时间(活动的最迟开始时间-活动的最早开始时间)为__(2)__。

(1) A. 7 B. 9 C. 10 D. 11

(2) A. 3 B. 2 C. 1 D. 0

答案:(1)C (2)A

解析:(1)关键路径就是从起点到终点最长的路径。直接从图中找即可,v1 v4 v5 v7就是一条,长度为10。(2)从关键路径中可以看出,v1到v4需要花费的时间为6,活动a6至少要在经过时间2后才能开始,最晚开始时间为:6-2=4 ,则活动a6的松驰时间是4-2=2。

7.对n个元素进行快速排序时,最坏情况下的时间复杂度为____。

A.O(1og2n) B.O(n) C.O(nlog2n) D. O (n2)

答案:D

解析:若进行快速排序的n个元素按关键字有序或基本有序时,快速排序将退化为起泡排序,时间复杂度为O (n2)。

复习提示:这是一道概念题,也是考生的拿分题,考生对概念一定要清楚。

8.任何一个基于“比较”的内部排序的算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为____。

A.10 B.11 C.21 D.36

答案:A

解析:内部排序中除了基数排序之外,都是基于“关键字间的比较”进行排序的。任何一个借助“比较”进行排序的算法,在最坏情况下所需的比较次数至少为é1og2(n!)ù,由此可解。具体解释考生可参考严蔚敏、吴伟民的《数据结构》291页。



<< Home

This page is powered by Blogger. Isn't yours?