1、软件水平考试（中级）软件设计师上午（基础知识）试题-试卷 23及答案解析(总分：148.00，做题时间：90 分钟)一、选择题(总题数：48，分数：148.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_2.计算机中的并行性是指在数据处理过程中，存在可同时进行运算和操作的各部分间的关系。并行性主要包括同时性和并发性两种。前者指同一时刻发生的两个或多个事件，后者指(9)发生的两个或多个事件。（分数：2.00）A.同一时间间隔B.同一时间C.同一时刻D.程序运行期间3.一个计算机系统的性能，不仅受 CPU的限制，
2、还与存储器和 FO设备的性能有关，不仅受硬件影响，还受软件质量的制约。计算机性能评价方法中的基准法是使用(10)作为计算机的负载，通过在不同计算机系统上运行建立起不同系统间相对性能比较的参数。（分数：2.00）A.各种应用程序B.复杂的程序计算程序C.基准测试程序D.操作系统4.白盒测试属于(13)。（分数：2.00）A.人工测试B.机器测试C.组装测试D.Alpha测试5.结构化设计(SD)方法的基本思想是(14)。（分数：2.00）A.将可能引起变化的因素隐藏在某个有关的模块内部B.根据输入输出数据结构到程序的结构C.模块要相对独立、功能单一D.自顶向下，逐步细化6.新系统试运行成功之后，
3、就可以在新系统和旧系统之间互相转换。新旧系统之间的转换方式有(17)。（分数：2.00）A.并行转换、串行转换、交叉转换B.同步转换、异步转换、交叉转换C.直接转换、并行转换、分段转换D.对比转换、分时转换、测试转换7.(20)是关于质量管理体系的一系列标准，有助于企业交付符合用户质量要求的产品。（分数：2.00）A.ISO 9000B.CMMC.ISO 1400D.SW-CMM8.软件通常具有商业秘密的法律特征，属于中华人民共和国反不正当竞争法保护的内容。对软件商业秘密的保护包括(21)两项基本内容。（分数：2.00）A.软件的方法和方案B.软件的技术秘密和经营秘密C.软件的表达形式和构思D
4、.软件的品牌和信誉9.在我国颁布实施的计算机软件保护条例中，对于法人或者其他组织享有著作权的软件，保护期限是50年，截止到软件(22)第 50年的 12月 31日，但软件自开发完成之日起 50年内未发表的，计算机软件保护条例不再对软件保护。（分数：2.00）A.法人或者其他组织成立之后B.软件首次发表后C.软件开发完成后D.法人或者其他组织变更、终止之后10.进程 P不断地从外部设备输入数据后通过缓冲区 K向进程 Q成批(以缓冲区大小为单位)传送，进程 Q接到数据并做进一步处理后通过缓冲区 T向进程 S成批传送，进程 R接到数据后将它们打印出来，K 和 T大小一样。要求打印数据的次序与进程 P
5、接收数据的次序一样。 （分数：2.00）A.两个信号量，初值分别为 0，1B.3个信号量，初值分别为 1，1，0C.4个信号量，初值分别为 1，0，1，0D.5个信号量，初值分别为 1，0，1，1，011.有一活动头的磁盘系统，磁盘块地址用一个三元组x，y，z来表示，其中，x 代表柱面号，y 代表磁盘面号，z 代表扇区号。磁盘调度采用最短查找时间优先(SSTF)算法。现有一组使用磁盘的申请，其磁盘访问地址依次为100,12,6，35,18,4，204,10， 45，8，6，120，4，12。当前磁头位置在 30号柱面处，这一组磁盘访问申请的执行次序为(26)。（分数：2.00）A.20，4，1
6、0， 35,18，4， 100,12,6， 45，8，6， 120,4,12B.20，4，10，35，18，4，45，8，6，100，12，6，120，4，12C.120，4，12，100，12，6，45，8，6，35，18，4，0，4，10D.35，18，4，45，8，6，20，4，10，100，12，6，120，4，1212.已知=0,1上的正规表达式 0*1(0|10*1)*，它和下列哪个图的 NFA等价，(27)。（分数：2.00）A.B.C.D.13.已知文法 G1=(V T =a,b,d，V N =S，A，B，S,P)，其中 P为， SdAB AaA|a BbB| 该文法生成的语言
7、是(28)。（分数：2.00）A.da m b n |m0，nOB.da m b n |m1，n0C.da m b n |m0，n1D.da m b n |m1，n114.已知文法 G2=(V T =a，(,)，V N =S，L)，S,P)，其中 P为 S(L)|a L-L，s|s 与 G2等价的不含左递归规则的文法是(29)。（分数：2.00）A.G21=(V T =a，(,)，V N =S，L，S，P)，其中 P为 S(L)|a LS，S|SB.G22=(V T a，(,)，V N =S，L，L，S，P)，其中 P为 S(L)|a LSL LSL|C.G23=(V T a，(,)，V N
8、=S，L，L，S，P)，其中 P为 S(L)|a LSL U,SL|D.G24=(V T =(a，(,)，V N =S，L，L，S，P)，其中 P为 S(L)|a LSL LSL|S15.一个程序的控制流图是一个有向图，它的结点是程序中的(30)。（分数：2.00）A.语句B.循环C.基本块D.函数16.在一棵完全二叉树中，其根的序号为 1，(31)可判定序号为 p和 q的两个结点是否在同一层。（分数：2.00）A.log 2 p=log 2 pB.log 2 p=log 2 qC.log 2 p+1=log 2 pD.log 2 p=log 2 p+117.堆是一种数据结构，(32)是堆。（
9、分数：2.00）A.(10，50，80，30，60，20，15，18)B.(10，18，15，20，50，80，30，60)C.(10，15，18，50，80，30，60，20)D.(10，30，60，20，15，18，50，80)18.(33)从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。（分数：2.00）A.二叉排序树B.大顶堆C.小顶堆D.平衡二叉树19.若有广义表 L=(1，2，3)，则 L的 K度和深度分别为(34)。（分数：2.00）A.1和 1B.1和 2C.1和 3D.2和 220.若对 27个元素只进行 3趟多路归并排序，则选取的归并路数为(35)
10、。（分数：2.00）A.2B.3C.4D.521.算术编码是(36)。（分数：2.00）A.有损数据压缩编码B.无损数据压缩编码C.不压缩数据的编码D.通道(或称信道)编码22.为适应网络带宽和降低存储器存储容量的要求，科技工作者开发了许多算法，用于压缩各种各样的数据。假设处理系统的计算精度足够高，由此造成的数据损失可忽略。其中，正向离散小波变换(FDWT)(37)。（分数：2.00）A.对重构图像的质量有损失B.对重构图像的质量没有损失C.变换前后数据项的数目不相等D.变换前后的系数具有相同含义23.CD-DA在多媒体的发展史上立下了不朽的功勋，20 世纪 80年代初就确定了声音采样频率为
11、44.1kHz，并且成为标准。问录制 74分钟的 CD-DA声音需要多少 MB的存储空间(按 1MB=10241024字节计算，不计文件格式本身所占用的空间。四舍五入取整数)，所需存储容量为(38)。（分数：2.00）A.747MBB.374MBC.783MBD.其他数值24.假设有一台摄像机，它的扫描速率为 450行/帧520 像素/行25 帧/秒，图像子采样格式为 4:2:0。为节省存储空间，如果每个 Y信号量化为 8位每样本，而 Cr和 Cb信号量化为 6位每样本。存储 10分钟这样的视像(video)至少需要多少(39)的磁盘容量(1GB=102410241024 字节)。（分数：2.
12、00）A.9.8GBB.4.9GBC.4.5GBD.其他数值25.关系模型是用(42)来表示和实现实体之间的关系。（分数：2.00）A.层次结构B.网状结构C.指针链D.表格的数据26.一个具有单属性键和 n(n0)元组的关系，如果对这个关系的键属性做一个投影，那么投影关系的基数是(43)。（分数：2.00）A.1B.C.nD.n 227.关系模式 R(A，B，C)和 S(C，D，E)进行关系代数运算，下列关系表达式中成立的是(44)。（分数：2.00）A.B.C.D.28.采用动态规划策略解决问题的显著特征是满足最优性原理，其含义是(50)。（分数：2.00）A.当前所做出的决策不会影响后面
13、的决策B.原问题的最优解包含其子问题的最优解C.问题可以找到最优解，但利用贪心法不能找到最优解D.每次决策必须是当前看来最优的决策才可以找到最优解29.下面函数中渐进时间最小的是(51)。（分数：2.00）A.T1(n)=n+nlognB.T2(n)=2 nC.T3(n)=n 2 -lognD.T4(n)=n+100logn30.下面的程序段违反了算法的(52)原则。 void sam() int n=2： while (!odd (n) n+=2； printf (n)； （分数：2.00）A.有穷性B.确定性C.可行性D.健壮性31.拉斯维加斯(Las Vegas)算法是一种常用的(53)
14、算法。（分数：2.00）A.确定性B.近似C.概率D.加密32.在分支一限界算法设计策略中，通常采用(54)搜索问题的解空间。（分数：2.00）A.深度优先B.广度优先C.自底向上D.拓扑序列33.传输延迟时间最小的交换方法是(59)。（分数：2.00）A.线路交换B.报文交换C.分组交换D.信元交换34.ATM采用的信元多路复用传输方式是(60)。（分数：2.00）A.异步时分复用B.统计时分复用C.同步时分复用D.波分复用35.Internet上常用简单的网络管理协议是(65)。（分数：2.00）A.CMISB.CMIPC.SNMPD.Open View实践证明这并不是提高计算机性能的最好
15、方法，因为其中 80%的指令在程序中使用频度很低。因而提出了另一种方案：简化指令的种类和格式，增加通用寄存器数目，使用 RR型指令格式，要求多数指令功能在一个机器周期内完成等，这种指令的计算机称为(2)。（分数：4.00）A.RISCB.CISCC.MIMDD.MIMDA.RISCB.CISCC.SISDD.SIMD计算机对存储器的要求是速度快、容量大、价格低，主存储器是 CPU按照地址进行随机读写的存储器，主存的特点是(3)，主有的最大容量与主存的地址位数有关，64MB 的主存，地址需要(4)位(二进制数)。（分数：4.00）A.CPU访问不同单元需要的时间不同B.CPU访问任何单元的速度相
16、同C.CPU访问地址小的单元，速度较快D.访问时间不固定A.16B.24C.26D.34计算机浮点数的表示中，可分为阶码和尾数两部分，如果某机阶码为 8位 (含 1位符号位)定点整数，用移码表示，其阶码最大正数是(8)，最小负数是(9)。（分数：4.00）A.1111111B.11111111C.10000000D.1A.10000000B.0C.1111111D.11111111设计模式使人们可以更加简单方便地复用成功的设计和体系结构。将已证实的技术表述成设计模式也会使新系统开发者更加容易理解其设计思路。一个模式有 4个基本要素，它们是(48)，设计模式中的 Factory属于(49)。（分
17、数：4.00）A.模式名称、问题、解决方案、效果B.模式名称、来源、目的、实现方式C.模式名称、结构、目的、实现方式D.模式名称、问题、实现方式、备注A.结构模式B.创建模式C.行为模式D.抽象模式消息摘要算法 MD5(Message Digest)是一种常用的(57)。MD5 算法以一个任意长数据块作为输入，其输出为一个(58)比特的消息摘要。（分数：4.00）A.索引算法B.Hash函数C.递归函数D.倒排算法A.128B.160C.256D.512传统的交换机作为第二层设备，只能识别并转发(59)地址，要支持 VLAN 间的通信只能借助于具有(60)功能的网络设备。（分数：4.00）A.
18、IPB.网络C.协议D.MACA.三层交换B.通信交换C.信元交换D.线路交换一个主机的 IP地址是 172.20.50.17对应的子网掩码是 255.255.255.240，则所在的子网号是(61)，子网的广播地址是(62)。（分数：4.00）A.172.20.50.16B.172.20.50.32C.172.20.50.17D.172.20.50.31A.172.20.50.31B.172.20.50.16C.172.20.50.255D.172.20.50.252设学生 S、课程 C、学生选课 SC的关系模式分别为： S(Sno，Sname，Sage，Saddr)、C(Cno，Cname
19、，Pcno)以及 SC(Sno，Cno，Grade)与关系代数表达式 Sno,Sname,Gr(Sname=数据库(S|SC|C)等价的元组演算表达式为： (35)S(u)SC(v)C(w)(36)(37)（分数：6.00）A.B.C.D.A.u1=v1v1=w1w1=数据库B.u1=v2v2=w1w3=数据库C.u1=v1v2=w1w2=数据库D.u2=v2v1=w2w2=数据库A.t1=u1t2=u2t3=v3B.t1=u1t2=u2t3=v2C.t1=u1t2=w1t3=v2D.t1=u1t2=w2t3=v3在设计算法时，通常应考虑以下原则：首先所设计的算法必须是(23)，其次应有很好的
20、(24)，还必须具有(25)，最后应考虑所设计的算法具有(26)。（分数：8.00）A.正确的B.有穷性C.有输入D.用户需求A.有穷性B.可读性C.确定性D.高效率与低存储量A.有输入B.确定性C.健壮性D.可读性A.可读性B.有输入C.健壮性D.高效率与低存储量开发软件时对提高软件开发人员工作效率至关重要的是(44)。软件工程中描述生存周期的瀑布模型一般包括计划、(45)、设计、编码、测试、维护等几个阶段，其中设计阶段在管理上又可以依次分成(46)和(47)两步。（分数：8.00）A.程序开发环境B.操作系统的资源管理功能C.程序人员数量，D.计算机的并行处理能力A.需求分析B.需求调查C
21、.可行性分析D.问题定义A.方案设计B.代码设计C.概要设计D.数据设计A.运行设计B.详细设计C.故障处理设计D.软件体系结构设计设有关系模式只(C，P，S，G，T，W)，各属性含义为：C 课程，P 老师，S 学生，G 成绩，T 时间，W 教室，其函数依赖集为： F=CP,(S，C)G，(T，W)C，(T，P)W，(T，S)W 则关系模式的关键字为(35)，R的规范化程度最高可达到(36)。若将 R分解为关系模式组 R1(C，P)，R2(S，C，G)，R3(S，T，W，C)，则 R1，R2，R3 的规范化程度最高分别可达到(37),(38),(39)。（分数：10.00）A.(T，R)B.(
22、J，C)C.(T，W)D.DA.2NFB.3NFC.BCNFD.4NFA.2NFB.3NFC.BCNFD.4NFA.2NFB.3NFC.BCNFD.4NFA.2NFB.3NFC.BCNFD.4NFThe CPU does not have to look(66)all of RAM to find the spot it needs. But RAM only(67)the data temporarily. As soon as you switch the computer(68), all that information disappears from the RAM. When yo
23、u switch the computer on again, the RAM is(69), and ready(70)a new program and new data.（分数：10.00）A.onB.throughC.forD.down uponA.takesB.operatesC.erasesD.holdsA.offB.onC.upD.downA.fullB.emptyC.zeroD.blankA.receiveB.be receivedC.receivingD.receivedWe know a computer is a machine that processes data(s
24、tored in main memory)into information, under control of a stored program. We also know that, internally, a computer is a binary machine; thus the data and the program instruictions must be stored in binary form. Characters are represented in(71). Numbers are stored as binary numbers, with each bits
25、positional value significant. A computers main memory is divided into bytes, words or both(depending on the system), and each of these basic storage units is assigned an(72). Using this address, the processor can read or write selected bytes or words. The processor consists of a clock, an instructio
26、n control unit, an arithmetic and logic unit, and registers. Once a program is stored in main memory, the processor can begin to execute it. During(73), the instruction control unit fetches an instruction from main memory; during(74), the arithmetic and logic unit executes it. Precisely timed electr
27、onic pulses generated by the clock drive this basic(75)（分数：10.00）A.a binary codeB.wordsC.registersD.positional valuesA.addressB.valueC.contentD.registerA.E-timeB.I-timeC.cycle timeD.run timeA.E-timeB.I-timeC.cycle timeD.run timeA.clock pulseB.instructionC.memory accessD.machine cycle软件水平考试（中级）软件设计师上
28、午（基础知识）试题-试卷 23答案解析(总分：148.00，做题时间：90 分钟)一、选择题(总题数：48，分数：148.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_解析：2.计算机中的并行性是指在数据处理过程中，存在可同时进行运算和操作的各部分间的关系。并行性主要包括同时性和并发性两种。前者指同一时刻发生的两个或多个事件，后者指(9)发生的两个或多个事件。（分数：2.00）A.同一时间间隔 B.同一时间C.同一时刻D.程序运行期间解析：解析：计算机中的并行性是指在数值计算、数据处理过程中存在可同时进行运
29、算或操作的各部分间的关系。并行性包括同时性和并发性两类，同时性指同一时刻发生的两个或多个事件，并发性指在同一时间间隔内发生的两个或多个事件，这些事件不一定是在同一时刻同时发生的。3.一个计算机系统的性能，不仅受 CPU的限制，还与存储器和 FO设备的性能有关，不仅受硬件影响，还受软件质量的制约。计算机性能评价方法中的基准法是使用(10)作为计算机的负载，通过在不同计算机系统上运行建立起不同系统间相对性能比较的参数。（分数：2.00）A.各种应用程序B.复杂的程序计算程序C.基准测试程序 D.操作系统解析：解析：计算机性能评价方法的基准法是使用基准测试程序(Bench Mark)在各种计算机系统
30、上运行，根据其运行结果及所用时间等，建立起各系统间相对性能比较的参数，作为衡量计算机系统性能的指标。4.白盒测试属于(13)。（分数：2.00）A.人工测试B.机器测试 C.组装测试D.Alpha测试解析：解析：软件测试方法分人工测试和机器测试。人工测试又称代码审查，主要有 3种方法：个人审查、抽查、会审。机器测试分为白盒测试和黑盒测试。白盒测试又称为功能测试，黑盒测试又称为结构测试。软件测试可分为 4步进行：(1)单元测试。(2)组装测试 (3)确认测试。(4)系统测试。其中，确认测试常用的有 Alpha测试和 Beta测试。5.结构化设计(SD)方法的基本思想是(14)。（分数：2.00）
31、A.将可能引起变化的因素隐藏在某个有关的模块内部B.根据输入输出数据结构到程序的结构C.模块要相对独立、功能单一 D.自顶向下，逐步细化解析：解析：结构化设计方法是一种面向数据流的设计方法，它可以与 SA方法衔接。结构化设计方法的基本思想是将系统设计成由相对独立、功能单一的模块组成的结构。6.新系统试运行成功之后，就可以在新系统和旧系统之间互相转换。新旧系统之间的转换方式有(17)。（分数：2.00）A.并行转换、串行转换、交叉转换B.同步转换、异步转换、交叉转换C.直接转换、并行转换、分段转换 D.对比转换、分时转换、测试转换解析：解析：在进行新旧系统转换以前，首先要进行新系统的试运行。在系
32、统测试、调试中，人们使用的是系统测试数据，有些实际运行中可能出现的问题，很难通过这些数据被发现。所以，一个系统开发后，让它实际运行一段时间，是对系统最好的检验和测试方法。新系统试运行成功之后，就可以在新系统和旧系统之间互相转换。新旧系统之间的转换方式有直接转换、并行转换和分段转换。(1)直接转换。直接转换就是在确定新系统运行无误时，立刻启用新系统，终止旧系统运行。这种方式对人员、设备费用很节省。这种方式一般适用于一些处理过程不太复杂、数据不很重要的场合。(2)并行转换。这种转换方式是新旧系统并行工作一段时间，经过一段时间的考验以后，新系统正式替代旧系统。对于较复杂的大型系统，它提供了一个与旧系
33、统运行结果进行比较的机会，可以对新旧两个系统的时间要求、出错次数和工作效率给以公正的评价。当然由于与旧系统并行工作，消除了尚未认识新系统之前的紧张和不安。在银行、财务和一些企业的核心系统中，这是一种经常使用的转换方式。它的主要特点是安全、可靠，但费用和工作量都很大，因为在相当长时间内系统要两套班子并行工作。(3)分段转换。分段转换又称逐步转换、向导转换、试点过渡法等，这种转换方式实际上是以上两种转换方式的结合。7.(20)是关于质量管理体系的一系列标准，有助于企业交付符合用户质量要求的产品。（分数：2.00）A.ISO 9000 B.CMMC.ISO 1400D.SW-CMM解析：解析：ISI
34、 9000 簇标准是国际标准化组织(ISO)颁布的在全世界范围内通用的关于质量管理和质量保证方面的系列标准，目前已被 80多个国家等同或等效采用，该系列标准在全球具有广泛深刻的影响，有人称之为 ISO 9000现象。ISO 1400 是国际标准化组织第 207技术委员会(TC 207)从 1993年开始制定的系列环境管理国际标准的总称，它同以往各国自定的环境排放标准和产品的技术标准不同，它是一个国际性标准，对全世界工业、商业、政府等所有组织针对改善环境管理行为具有统一标准的功能。它由环境管理体系(EMS)、环境行为评价(EPE)、生命周期评估(LCA)、环境管理(EM)、产品标准中的环境因素(
35、EAPS)等7个部分组成。CMM 是软件开发能力的成熟度模型(SW-CMM)的简称，包括 5个成熟等级，开发的能力越强，开发组织的成熟度越高，等级越高。8.软件通常具有商业秘密的法律特征，属于中华人民共和国反不正当竞争法保护的内容。对软件商业秘密的保护包括(21)两项基本内容。（分数：2.00）A.软件的方法和方案B.软件的技术秘密和经营秘密 C.软件的表达形式和构思D.软件的品牌和信誉解析：解析：中华人民共和国反不正当竞争法中所称的商业秘密，是指不为公众所知悉、能为权利人带来经济利益。具有实用性并经权利人采取保密措施的技术信息和经营信息。据此，软件商业秘密的保护包括软件的技术秘密和经营秘密两
36、项基本内容。9.在我国颁布实施的计算机软件保护条例中，对于法人或者其他组织享有著作权的软件，保护期限是50年，截止到软件(22)第 50年的 12月 31日，但软件自开发完成之日起 50年内未发表的，计算机软件保护条例不再对软件保护。（分数：2.00）A.法人或者其他组织成立之后B.软件首次发表后 C.软件开发完成后D.法人或者其他组织变更、终止之后解析：解析：根据计算机软件保护条例第十四条第一款规定：软件著作权自软件开发完成之日起产生。同时，计算机软件保护条例第十四条第三款规定：法人或者其他组织享有软件的著作权，保护期限是50年，截止到软件首次发表后第 50年的 12月 31日，但软件自开发
37、完成之日起 50年内未发表的，本条例不再保护。这是对法人或者其他组织所享有软件的著作权的限制，需要引起重视。10.进程 P不断地从外部设备输入数据后通过缓冲区 K向进程 Q成批(以缓冲区大小为单位)传送，进程 Q接到数据并做进一步处理后通过缓冲区 T向进程 S成批传送，进程 R接到数据后将它们打印出来，K 和 T大小一样。要求打印数据的次序与进程 P接收数据的次序一样。 （分数：2.00）A.两个信号量，初值分别为 0，1B.3个信号量，初值分别为 1，1，0C.4个信号量，初值分别为 1，0，1，0 D.5个信号量，初值分别为 1，0，1，1，0解析：解析：本题是考查信号量概念与 P、V 操
38、作的实际运用，解决进程之间的同步与互斥问题。这个问题看起来是两对生产者与消费者组合的问题。由于进程 P、Q、R 存在着供给与消费的关系，这种关系体现了一种次序依赖关系。一方面，进程 Q必须等待进程 P接收到一批数据并将其放入缓冲区 K后才可以取来加工，进程 R必须等待进程 Q将一批数据加工完成并放入缓冲区 T以后才可以取来打印；另一方面，进程P必须等待进程 Q取走缓冲区 K的数据后才能将下一批数据放入 K中，进程 Q必须等进程 R将缓冲区 T的数据取走进行打印后才可以将加工好了的下一批数据放入 T中。但是，进程 P和 Q之间并没有直接的依赖关系。因此，系统呈现这样一种工作流程： 因此，进程 P
39、和 Q之间存在两个同步条件，需要有两个信号量 S1和 S2来保证进程 P和 Q的同步关系，它们的初值分别为 1和 0；进程 Q和 R之间也一样，需要有两个信号量 S1 和 S2来保证它们的同步关系，初值也分别是 1和 0。 下图表示这 3个进程的工作流程。11.有一活动头的磁盘系统，磁盘块地址用一个三元组x，y，z来表示，其中，x 代表柱面号，y 代表磁盘面号，z 代表扇区号。磁盘调度采用最短查找时间优先(SSTF)算法。现有一组使用磁盘的申请，其磁盘访问地址依次为100,12,6，35,18,4，204,10， 45，8，6，120，4，12。当前磁头位置在 30号柱面处，这一组磁盘访问申请
40、的执行次序为(26)。（分数：2.00）A.20，4，10， 35,18，4， 100,12,6， 45，8，6， 120,4,12B.20，4，10，35，18，4，45，8，6，100，12，6，120，4，12C.120，4，12，100，12，6，45，8，6，35，18，4，0，4，10D.35，18，4，45，8，6，20，4，10，100，12，6，120，4，12 解析：解析：本题考查的内容包括磁盘的组成与地址、工作方式以及最短查找时间优先的磁盘调度算法及其应用。磁盘由一叠其中心固定在一个旋转轴上的盘片和一组读写头(磁头)组成。每个磁盘片表面刻有呈同心圆状的磁道，磁道上涂有磁性
41、物质，因此可以记录数据；磁道沿半径方向顺序编号，不同盘片上相同编号的磁道组成一个虚拟的圆柱面，所以磁道编号又称为柱面号。给定柱面号就唯一确定了磁道。每个磁道被均匀地分为若干段(中间可以有一定的空隙)，这些段沿圆周方向顺序编号，沿半径方向，相同编号的磁段组成一个扇形，所有这些段又称为扇区。给定扇区号就唯一确定了磁道上的磁段。一个磁盘有若干个盘片，现在的盘片都是双面的，即上下两面都可以记录数据，一般而言，顶上盘片的正面和最底盘片的背面不能记录数据。这些记录数据的盘片面沿一个方向编号，所以给定了盘面号就唯一确定了要访问的磁盘面。三元组小于柱面号，磁面号。扇区号大于唯一确定了磁盘的某个记录数据的磁段。
42、所有盘片的圆心固定在一个旋转轴上，所有盘片随着轴的旋转而高速旋转。为了读写数据，磁盘还有磁头，每个磁面对应一个磁头。当磁头对准磁道并接近它时，才能读写数据。磁盘分活动头磁盘和固定头磁盘两类。活动头磁盘的磁头数目与盘面数量一样，它们分别固定在一根杆(称为磁头臂)的一头，磁头臂的数量与磁头数量相等，它的长度比盘片的半径略大。磁头臂的另一头固定在一根与旋转轴平行的轴上，该轴可以沿半径方向来回移动，以对准某个柱面，这个动作称为“引臂”。磁盘片高速旋转，但磁头的移动速度较慢。当访问某个磁盘块时，需要给定柱面号、磁面号(有时也叫磁道号)和扇区号。第 1步要进行磁头引臂，使磁头对准给定的柱面号；然后将与磁面
43、号相同的磁头接近磁道，当磁盘片旋转到给定扇区时进行读写。整个过程中，磁头引臂最费时间。最短查找时间优先(SSTF)算法适用于活动头磁盘，目标在于尽可能缩短引臂时间。算法的实质是根据磁头的当前位置(柱面号)，调整磁盘访问申请序列，首先响应序列中柱面号最接近磁头当前位置的申请，以避免顺序响应时磁头可能不断地来回大幅度移动。但是，这种算法有可能引起某些申请无限等待：当接近磁头当前位置的申请源源不断地到来时，较远的申请有可能长时间得不到响应。本题中，离当前磁头位置最近的申请是35，18，4，首先获得响应：此时，磁头位置变为 35，下一个响应的便是45，8，6；接下去是20，4，10；然后向上，响应10
44、0，12，6和 120，4，12。12.已知=0,1上的正规表达式 0*1(0|10*1)*，它和下列哪个图的 NFA等价，(27)。（分数：2.00）A.B. C.D.解析：解析：对于任一正规表达式 R，可按如下方法构造出与之等价的非确定的有限自动机。 对于正规式 R，可用下图所示的拓广状态图表示。 通过对正规式 R进行分裂并加入新的结点，逐步把图转变成每条弧上的标记是上的一个字符或 ，转换规则如下图所示。 最后所得的图即为一个 NFA M，x 为初态结点，y 为终态结点。显然，L(M)=L(R)。按照上述方法构造正规表达式 0*1(0|10*1)*的非确定的有限自动机的过程如下所示。13.
45、已知文法 G1=(V T =a,b,d，V N =S，A，B，S,P)，其中 P为， SdAB AaA|a BbB| 该文法生成的语言是(28)。（分数：2.00）A.da m b n |m0，nOB.da m b n |m1，n0 C.da m b n |m0，n1D.da m b n |m1，n1解析：解析：已知文法 G=(V T ，V N ，S，P)，它所产生的语言定义如下：若有 S(11)w，则称 w 是文法G的一个句型。仅含终结符的句型是一个句子。语言 L(G)是由文法 G产生的所有句子组成的集合： L(G)=w|S w且 wV T * 推导的定义如下： 设文法 G=(V T ，V
46、N ，S，P)，AP，V*，则稀 A 直接推导出 ，表示成 这个定义告诉我们，若知道 AV*，根据 A，可求出 V*，方法是用 A 的右部 替换 A 中的 A得到 ；相反，若知道V*，根据 AP，可求出 AV*，方法是用 Ap 的左部 A替换 中的 得到A。 若存在一个推导序列： ，则称从 a0经 n步推导出 an，表示成 14.已知文法 G2=(V T =a，(,)，V N =S，L)，S,P)，其中 P为 S(L)|a L-L，s|s 与 G2等价的不含左递归规则的文法是(29)。（分数：2.00）A.G21=(V T =a，(,)，V N =S，L，S，P)，其中 P为 S(L)|a LS，S|SB.G22=(V T a，(,)，V N =S，L，L，S，P)，其中 P为 S(L)|a LSL LSL|C.G23=(V T a，(,)，V N =S，L，L，S，P)，其中 P为 S(L)|a LSL U,SL| D.G24=(V T =(a，(,)，V N =S，L，L，S，P)，其中 P为 S(L)|a LSL LSL|S解析：解析：采用自顶向下的预测分析法首先是等价改写给定的文法，消除文法的左递归和提取产生式的公共左因子。 消除直接左递归的方法如下： 若
