【计算机类职业资格】软件水平考试（中级）软件设计师上午（基础知识）试题-试卷35及答案解析.doc

1、软件水平考试（中级）软件设计师上午（基础知识）试题-试卷 35及答案解析(总分：84.00，做题时间：90 分钟)一、选择题(总题数：21，分数：84.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_2.在计算机系统中，表征系统运行状态的部件是(18)。（分数：2.00）A.程序计数器B.累加计数器C.中断计数器D.程序状态字3.若项目集 IK含有 A.，则在状态 k时，仅当面临的输入符号 aFOLLOW(A)时，才采取“A.”动作的一定是(19)。（分数：2.00）A.LALR 文法B.LR(0)文法C.C

2、LR(1)文法D.SLR(1)文法4.在下列存储器中，访问速度最快的是(24)。（分数：2.00）A.硬盘存储器B.软盘存储器C.磁带存储器D.半导体 RAM(内存储器)5.基本块内的优化为(25)。（分数：2.00）A.代码外提，删除归纳变量B.删除多余变量，删除无用赋值C.强度削弱，代码外提D.循环展开，循环合并6.线性表采用链式存储时，其地址(31)。（分数：2.00）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以7.要使下表中描述的状态安全，可用资源的最小数目应为(32)。 （分数：2.00）A.2B.3C.4D.58.下列程序段执行后 s值为：(38)i

3、nt i=1, s=0; do if(!(i%2)continue; s+ =i; while(+ +i10);（分数：2.00）A.1B.45C.25D.以上均不是9.以文档作为驱动，适合于软件需求很明确的软件项目的生存周期模型是(49)。（分数：2.00）A.喷泉模型B.增量模型C.瀑布模型D.螺旋模型10.设有以下程序段 int x=0，s=0； while(!x!=0)s+=+x； printf(“%d”，s)；则(50)。（分数：2.00）A.运行程序段后输出 0B.运行程序段后输出 1C.程序段中的控制表达式是非法的D.程序段执行无限次11.面向对象分析阶段建立的三个模型中，核心的

4、模型是(62)。（分数：2.00）A.对象模型B.动态模型C.功能模型D.分析模型12.优化可生成(62)的目标代码。（分数：2.00）A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小软件是一种逻辑产品，它的开发主要是(1)。软件工程和计算机科学性质不同，软件工程着重于(2)。（分数：4.00）A.研制B.拷贝C.再生产D.复制A.原理的理论B.理论研究C.原理讨论D.建造软件系统某趾 M芯片，其存储容量为 16K8位，则该芯片引出线的最小数目应为(3)。存储器芯片的地址范围是(4)。（分数：4.00）A.8B.14C.16D.26A.0000H

5、00FFHB.0000HOFFFHC.000FH00FFHD.0000H3FFFH某机主存的读写周期为 1s，今采用增设 Cache 方案和多体交叉存取方案来使其有效访问周期减少到0.2s，设 Cache的命中率为 90%，则 Cache的读写周期应为(42)才能满足要求。设在多体交叉存取访问时，产生存储体访问冲突的概率为 10%，则应由(43)存储体并行工作才能满足要求。（分数：4.00）A.0.05B.0.1C.0.2D.0.4A.6B.8C.9D.10考虑一个具有等距间隔的站点的基带总线 LAN，数据输率为 10Mbps；总线长度为 1000m，传播速度为200m/s，发送一个 1000

6、bit的帧给另一个站，从发送开始到接收结束的平均时间是(49)；如果两个站严格地在同一时刻开始发送，它们的帧将会彼此干扰，如果每个发送站在发送期间监听总线，(50)可发现干扰。（分数：4.00）A.100B.105C.102.5D.110A.2B.2.5C.5D.5.5在微型计算机中，下列设备属于输出设备的是(52)。下列设备属于输入设备的是(53)。（分数：4.00）A.硬盘B.键盘C.鼠标D.打印机A.硬盘B.键盘C.鼠标D.打印机一棵深度为 1的满 k叉树有如下性质：第 1层上的结点都是叶子结点，其余各层上每个结点都有 k 棵非空子树，如果按层次顺序从 1开始对全部结点编号，则各层的结点

7、数目是(42)；编号为 n 的双亲结点(若存在)的编号是(43)；编号为 n的结点的第 i个孩子结点(若存在)的编号是(44)；编号为 n的结点有右兄弟的条件是(45)，其右兄弟的编号是(46)。（分数：10.00）A.K i-1B.k i -1C.k iD.K i+1A.B.C.D.A.n*k+iB.n*k+i+1C.(n-1)*k+iD.(n-1)*k+i+1A.(n-1)MOD k=OB.(n-1)MOD k0C.n MOD k=0D.n MOD k0A.n-1B.nC.n+1D.n+2按照规范的设计方法，一个完整的数据库设计一般分为以下 6个阶段：(51)：分析用户的需求，包括数据、功

8、能和性能需求。(52)：主要采用 ER模型进行设计，包括画 ER图。(53)：通过将 ER图转换成表，实现从 ER模型到关系模型的转换。(54)：主要是为所设计的数据库选择合适的存储结构和存取路径。(55)：包括编程、测试和试运行。(56)：系统的运行与数据库的日常维护。（分数：12.00）A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库的实施A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库的实施A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库的实施A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库的

9、实施A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库的实施A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库运行与维护The notion of NP-completeness has provided a(66)mathematical definition for(67)intractability of NP problems. But this measure applies only to worst-case complexity. Being NP-complete does not(68)that a problem is intr

10、actable on the average case. Indeed, some NP-complete problems are “(69)on average“, though some may not be. Levin initiated the study of average-case intractability, He showed that a bounded tiling problem under a simple distribution is average-case NP-complete. Since then, several additional avera

11、ge-case NP-complete problems have been shown within Levins(70). This paper is intended to provide a comprehensive survey of average-case NP-complete problems that have been published so far, and the techniques of obtaining these results.（分数：10.00）A.relaxedB.roughC.rigorousD.feasibleA.accessingB.calc

12、ulatingC.countingD.measuringA.directB.navigateC.indicateD.showA.difficultB.easyC.hardD.intractableA.frameworkB.problemC.basisD.foundationThe Turing machine is an abstract(71)of computer execution and storage introduced in 1936 by Alan Turing to give a mathematically precise definition of(72). or mec

13、hanical procedure. As such it is still widely used in theoretical computer science, especially in(73)theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as Turings the

14、sis. Every Turing machine computes a certain(74)partial function over the strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan luring already described, we can encode the action table of every Turing machine in a string. Thus we might try to cons

15、truct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed. As Turing showed, such a luring machine is indeed possible and since it is able to simul

16、ate any other Turing machine it is called a(75)Turing machine. A universal Turing machine is Turing complete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a univ

17、ersal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.（分数：10.00）A.implementB.patternC.toolD.modelA.operationB.calculatingC.algorithmD.mechanicsA.intricacyB.complexityC.complicacyD.difficultyA.fixed

18、B.steadyC.variationalD.changeableA.universalB.specialC.completeD.changeable软件水平考试（中级）软件设计师上午（基础知识）试题-试卷 35答案解析(总分：84.00，做题时间：90 分钟)一、选择题(总题数：21，分数：84.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_解析：2.在计算机系统中，表征系统运行状态的部件是(18)。（分数：2.00）A.程序计数器B.累加计数器C.中断计数器D.程序状态字 解析：解析：A 指示当前指令的

19、地址；B 是累加；C 是保存中断字；D 是保存系统运行状态。3.若项目集 IK含有 A.，则在状态 k时，仅当面临的输入符号 aFOLLOW(A)时，才采取“A.”动作的一定是(19)。（分数：2.00）A.LALR 文法B.LR(0)文法C.CLR(1)文法D.SLR(1)文法 解析：解析：当用产生式 A 归约时，LR(0)无论面临什么输入符号都进行归约；SLR(1)则仅当面临的输入符号 aFOLLOW(A)时进行归约；LR(1)则当在把 归约为 A的规范句型的前缀 A 前提下，当 后跟终结符 a时，才进行归约。4.在下列存储器中，访问速度最快的是(24)。（分数：2.00）A.硬盘存储器B

20、.软盘存储器C.磁带存储器D.半导体 RAM(内存储器) 解析：解析：内存储器的优点在于访问速度快，但是价格较贵，存储容量比外存储器小。外存储器单位存储容量的价格便宜，存储容量大，但是存取速度较慢。通常的外存储器包括硬盘存储器、软盘存储器和磁带存储器。半导体 RAM通常作为内存储器使用。5.基本块内的优化为(25)。（分数：2.00）A.代码外提，删除归纳变量B.删除多余变量，删除无用赋值 C.强度削弱，代码外提D.循环展开，循环合并解析：解析：基本块优化包括：合并已知量，删除无用赋值及删除多余运算。6.线性表采用链式存储时，其地址(31)。（分数：2.00）A.必须是连续的B.部分地址必须是

21、连续的C.一定是不连续的D.连续与否均可以 解析：解析：链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这组存储单元可以是连续的，也可以是不连续的。根据这个定义，正确答案应该选 D。7.要使下表中描述的状态安全，可用资源的最小数目应为(32)。 （分数：2.00）A.2B.3 C.4D.5解析：解析：如果 R1有一个资源可用，能保证进程 P2运行完。然后，P2 释放它现在使用的资源，使得 R1类型的两个资源可用。这将允许 P1运行完，把 R1类型的可用资源的数目增加到 3。只有 3个 R1类型的资源，如果 P3、P4 请求分配最大数目的资源，P3 和 P4仍然处于死锁状态。如果一开

22、始就有 3个 R1类型资源而不是 1个，P1 就可以获得 5个 R1的可用资源并运行完。再加上 P4原来占用的 2个 R1的资源，就可以让 P3运行。所以使该状态安全的所需可用资源的最小个数为 3。8.下列程序段执行后 s值为：(38)int i=1, s=0; do if(!(i%2)continue; s+ =i; while(+ +i10);（分数：2.00）A.1B.45C.25 D.以上均不是解析：解析：do if(!(i%2)continue; s+ =i;9.以文档作为驱动，适合于软件需求很明确的软件项目的生存周期模型是(49)。（分数：2.00）A.喷泉模型B.增量模型C.瀑布

23、模型 D.螺旋模型解析：解析：瀑布模型为软件开发提供了一种有效的管理模式。根据这一模式制定开发计划，进行成本预算，组织开发力量，以项目的阶段评审和文档控制为手段有效地对整个开发过程进行指导，所以它是以文档为驱动、适合于软件需求很明确的软件项目的模型。10.设有以下程序段 int x=0，s=0； while(!x!=0)s+=+x； printf(“%d”，s)；则(50)。（分数：2.00）A.运行程序段后输出 0B.运行程序段后输出 1 C.程序段中的控制表达式是非法的D.程序段执行无限次解析：解析：当 x=0时，!x=1，1 !=0，s=1；当 x=1时，!x=0，0=0，循环结束。11

24、.面向对象分析阶段建立的三个模型中，核心的模型是(62)。（分数：2.00）A.对象模型 B.动态模型C.功能模型D.分析模型解析：解析：对象模型是分析阶段三个模型的核心，也是其他两个模型的框架。在建立对象模型时，确定了类、关联、结构和属性，还没有确定操作。只有建立了动态模型和功能模型之后，才可能最后确定类的操作。功能模型指出了发生厂什么，动态模型确定什么时候发生，而对象模型确定发生的客体。12.优化可生成(62)的目标代码。（分数：2.00）A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小 解析：解析：优化的目的是使目标程序运行时间短、占用存储

25、空间小。所以答案选 D。软件是一种逻辑产品，它的开发主要是(1)。软件工程和计算机科学性质不同，软件工程着重于(2)。（分数：4.00）A.研制 B.拷贝C.再生产D.复制解析：A.原理的理论B.理论研究C.原理讨论D.建造软件系统 解析：解析：软件产品是一种逻辑产品，它的生产主要是研制，软件产品的成本主要体现在软件的研制和开发上，软件开发研制完成后，通过复制就产生了大量软件产品。计算机科学中的研究成果均可用于软什工程，但计算机科学着重于原理和理论，而软件工程着重于如何建造一个软件系统。某趾 M芯片，其存储容量为 16K8位，则该芯片引出线的最小数目应为(3)。存储器芯片的地址范围是(4)。（

26、分数：4.00）A.8B.14C.16D.26 解析：A.0000H00FFHB.0000HOFFFHC.000FH00FFHD.0000H3FFFH 解析：解析：RAM 存储器芯片地址线的引脚数与存储芯片的单元数有关，数据线的引脚数与存储芯片的字长有关。16K=214，所以地址线 14根；字长 8位，所以数据线 8，加上芯片的片选信号，读/写信号，电源线，地线，该芯片引出线的最小数目是 26。存储器芯片的地址范围为 0000H3FFFH。某机主存的读写周期为 1s，今采用增设 Cache 方案和多体交叉存取方案来使其有效访问周期减少到0.2s，设 Cache的命中率为 90%，则 Cache

27、的读写周期应为(42)才能满足要求。设在多体交叉存取访问时，产生存储体访问冲突的概率为 10%，则应由(43)存储体并行工作才能满足要求。（分数：4.00）A.0.05B.0.1 C.0.2D.0.4解析：A.6B.8C.9 D.10解析：解析：设 Cache的读写周期为 Tc，则： Tc+0.11=0.2 得 Tc=0.1s。 设需要 m个存储体才能满足要求，则有： 1/m0.9+0.11=0.2 得到 m=9。考虑一个具有等距间隔的站点的基带总线 LAN，数据输率为 10Mbps；总线长度为 1000m，传播速度为200m/s，发送一个 1000bit的帧给另一个站，从发送开始到接收结束的

28、平均时间是(49)；如果两个站严格地在同一时刻开始发送，它们的帧将会彼此干扰，如果每个发送站在发送期间监听总线，(50)可发现干扰。（分数：4.00）A.100B.105C.102.5 D.110解析：A.2B.2.5C.5 D.5.5解析：解析：帧的发送时间 td=1000b/ 10Mbps=100s，最大传播延时 =1000m/200m/s= 5s。平均传播延时 b=5s/2=2.5ps，从发送开始到接收结束的最长时间为 t=td+=105s，从发送开始到接收结束的平均时间为 t=td+=102.5s，发现干扰的最长时间为 =5s。在微型计算机中，下列设备属于输出设备的是(52)。下列设备

29、属于输入设备的是(53)。（分数：4.00）A.硬盘B.键盘C.鼠标D.打印机 解析：A.硬盘B.键盘 C.鼠标D.打印机解析：解析：硬盘是一种存储介质，连同驱动器和适配卡共同组成外存储器；键盘与鼠标均属于输入设备3打印机将计算机中的文件输出至纸上供用户阅读，是输出设备。打印机和显示器均属于输出设备，只有键盘属于常用的输入设备，硬盘为存储器的存储介质。一棵深度为 1的满 k叉树有如下性质：第 1层上的结点都是叶子结点，其余各层上每个结点都有 k 棵非空子树，如果按层次顺序从 1开始对全部结点编号，则各层的结点数目是(42)；编号为 n 的双亲结点(若存在)的编号是(43)；编号为 n的结点的第

30、 i个孩子结点(若存在)的编号是(44)；编号为 n的结点有右兄弟的条件是(45)，其右兄弟的编号是(46)。（分数：10.00）A.K i-1 B.k i -1C.k iD.K i+1解析：A.B.C.D. 解析：A.n*k+iB.n*k+i+1C.(n-1)*k+iD.(n-1)*k+i+1 解析：A.(n-1)MOD k=OB.(n-1)MOD k0 C.n MOD k=0D.n MOD k0解析：A.n-1B.nC.n+1 D.n+2解析：解析：这道题可以仿照二叉树的性质推导得出。按层次顺序将棵有 n个结点的完全二叉树的所有结点从 1到 n编号，就得到结点的一个线性序列。完全二叉树除最

31、下面一层外，各层都被结点充满了，每一层结点个数恰是上一层结点个数的二倍。因此，从一个结点的编号就可以推知它的双亲及左右子女结点的编号。当 时，结点 i的左子女是结点 2i，否则结点没有左子女。当 时，结点 i的右子女是结点 2i+1，否则结点 i以没有右子女。当 i1 时，结点 i的双亲是结点按照规范的设计方法，一个完整的数据库设计一般分为以下 6个阶段：(51)：分析用户的需求，包括数据、功能和性能需求。(52)：主要采用 ER模型进行设计，包括画 ER图。(53)：通过将 ER图转换成表，实现从 ER模型到关系模型的转换。(54)：主要是为所设计的数据库选择合适的存储结构和存取路径。(55

32、)：包括编程、测试和试运行。(56)：系统的运行与数据库的日常维护。（分数：12.00）A.需求分析 B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库的实施解析：解析：数据库设计是建立数据库及其应用系统的技术，是信息系统开发和建设中的核心技术。具体说，数据库设计是指对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能够有效地存储数据，满足各种用户的应用需求(信息要求和处理要求)。这个问题是数据库在应用领域的主要研究课题。数据库设计既是一项涉及多学科的综合性技术，又是一项庞大的工程项目。有人讲“三分技术，七分管理，十二分基础数据”是数据库建设的基本规律，这是有

33、一定道理的。技术与管理的界面(称之为“干件”)十分重要。数据库建设是硬件、软件和干件的结合。这是数据库设计的特点之一。数据库的设计应该和应用系统设计相结合，也就是说，整个设计过程中要把结构(数据)设计和行为(处理)设计紧密结合起来。这是数据库设计的特点之二。按照规范的设计方法，一个完整的数据库设计一般分为以下6个阶段： 1需求分析：分析用户的需求，包括数据、功能和性能需求。 2概念结构设计：主要采用E-R模型进行设计，包括画 E-R图。 3逻辑结构设计：通过将 E-R图转换成表，实现从 E-R模型到关系模型的转换。 4数据库物理设计：主要是为所设计的数据库选择合适的存储结构和存取路径。 5数据

34、库的实施：包括编程、测试和试运行。 6数据库运行与维护：系统的运行与数据库的日常维护。A.需求分析B.概念结构设计 C.逻辑结构设计D.数据库物理设计E.数据库的实施解析：A.需求分析B.概念结构设计C.逻辑结构设计 D.数据库物理设计E.数据库的实施解析：A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计 E.数据库的实施解析：A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库的实施 解析：A.需求分析B.概念结构设计C.逻辑结构设计D.数据库物理设计E.数据库运行与维护 解析：The notion of NP-completeness has provid

35、ed a(66)mathematical definition for(67)intractability of NP problems. But this measure applies only to worst-case complexity. Being NP-complete does not(68)that a problem is intractable on the average case. Indeed, some NP-complete problems are “(69)on average“, though some may not be. Levin initiat

36、ed the study of average-case intractability, He showed that a bounded tiling problem under a simple distribution is average-case NP-complete. Since then, several additional average-case NP-complete problems have been shown within Levins(70). This paper is intended to provide a comprehensive survey o

37、f average-case NP-complete problems that have been published so far, and the techniques of obtaining these results.（分数：10.00）A.relaxedB.roughC.rigorous D.feasible解析：A.accessingB.calculatingC.countingD.measuring 解析：A.directB.navigateC.indicate D.show解析：A.difficultB.easy C.hardD.intractable解析：A.framew

38、ork B.problemC.basisD.foundation解析：The Turing machine is an abstract(71)of computer execution and storage introduced in 1936 by Alan Turing to give a mathematically precise definition of(72). or mechanical procedure. As such it is still widely used in theoretical computer science, especially in(73)t

39、heory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as Turings thesis. Every Turing machine computes a certain(74)partial function over the strings over its alphabet. I

40、n that sense it behaves like a computer with a fixed program. However, as Alan luring already described, we can encode the action table of every Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a stri

41、ng describing the input tape, and then computes the tape that the encoded Turing machine would have computed. As Turing showed, such a luring machine is indeed possible and since it is able to simulate any other Turing machine it is called a(75)Turing machine. A universal Turing machine is Turing co

42、mplete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.（分数：10.00）A.implementB.patternC.toolD.model 解析：A.operationB.calculatingC.algorithm D.mechanics解析：A.intricacyB.complexity C.complicacyD.difficulty解析：A.fixed B.steadyC.variationalD.changeable解析：A.universal B.specialC.completeD.changeable解析：