1、软件水平考试（中级）软件设计师上午（基础知识）试题模拟试卷 4及答案与解析 1 计算机中的并行性是指在数据处理过程中，存在可同时进行运算和操作的各部分间的关系。并行性主要包括同时性和并发性两种。前者指同一时刻发生的两个或多个事件，后者指 (9)发生的两个或多个事件。 （ A）同一时间间隔 （ B）同一时间 （ C）同一时刻 （ D）程序运行期间 2 一个计算机系统的性能，不仅受 CPU的限制，还与存储器和 FO 设备的性能有关，不仅受硬件影响，还受软件质量的制约。计算机性能评价方法中的基准法是使用 (10)作为 计算机的负载，通过在不同计算机系统上运行建立起不同系统间相对性能比较的参数。 （
2、A）各种应用程序 （ B）复杂的程序计算程序 （ C）基准测试程序 （ D）操作系统 3 白盒测试属于 (13)。 （ A）人工测试 （ B）机器测试 （ C）组装测试 （ D） Alpha测试 4 结构化设计 (SD)方法的基本思想是 (14)。 （ A）将可能引起变化的因素隐藏在某个有关的模块内部 （ B）根据输入输出数据结构到程序的结构 （ C）模块要相对独立、功能单一 （ D）自顶向下，逐步细化 5 新系统试运行成 功之后，就可以在新系统和旧系统之间互相转换。新旧系统之间的转换方式有 (17)。 （ A）并行转换、串行转换、交叉转换 （ B）同步转换、异步转换、交叉转换 （ C）直接转
3、换、并行转换、分段转换 （ D）对比转换、分时转换、测试转换 6 (20)是关于质量管理体系的一系列标准，有助于企业交付符合用户质量要求的产品。 （ A） ISO 9000 （ B） CMM （ C） ISO 1400 （ D） SW-CMM 7 软件通常具有商业秘密的法律特征，属于中华人民共和国反不正当竞争法保护的内容。对软件商业秘密 的保护包括 (21)两项基本内容。 （ A）软件的方法和方案 （ B）软件的技术秘密和经营秘密 （ C）软件的表达形式和构思 （ D）软件的品牌和信誉 8 在我国颁布实施的计算机软件保护条例中，对于法人或者其他组织享有著作权的软件，保护期限是 50年，截止到软
4、件 (22)第 50年的 12月 31日，但软件自开发完成之日起 50年内未发表的，计算机软件保护条例不再对软件保护。 （ A）法人或者其他组织成立之后 （ B）软件首次发表后 （ C）软件开发完成后 （ D）法人或者其他组织变更、终止之后 9 进程 P不断地从外部设备输入数据后通过缓冲区 K向进程 Q成批 (以缓冲区大小为单位 )传送，进程 Q接到数据并做进一步处理后通过缓冲区 T向进程 S成批传送，进程 R接到数据后将它们打印出来， K和 T大小一样。要求打印数据的次序与进程 P接收数据的次序一样。为了在保证结果正确性的前提下尽可能并行工作，需要设置 (23)。 （ A）两个信号量，初值分
5、别为 0， 1 （ B） 3个信号量，初值分别为 1， 1， 0 （ C） 4个信号量，初值分别为 1， 0， 1， 0 （ D） 5个信号量，初值分别为 1， 0， 1， 1， 0 10 有一活动头的磁盘系统，磁盘块 地址用一个三元组 x， y， z来表示，其中，x代表柱面号， y代表磁盘面号， z代表扇区号。磁盘调度采用最短查找时间优先(SSTF)算法。现有一组使用磁盘的申请，其磁盘访问地址依次为 100,12,6，35,18,4， 20 4,10， 45， 8， 6， 120， 4， 12。当前磁头位置在 30号柱面处，这一组磁盘访问申请的执行次序为 (26)。 （ A） 20， 4，
6、10， 35,18， 4， 100,12,6， 45， 8， 6， 120,4,12 （ B） 20， 4， 10， 35， 18， 4， 45， 8， 6， 100， 12， 6，120， 4， 12 （ C） 120， 4， 12， 100， 12， 6， 45， 8， 6， 35， 18， 4， 0，4， 10 （ D） 35， 18， 4， 45， 8， 6， 20， 4， 10， 100， 12， 6，120， 4， 12 11 已知 =0,1上的正规表达式 0*1(0|10*1)*，它和下列哪个图的 NFA等价，(27)。 （ A） （ B） （ C） （ D） 12 已知文法 G
7、1=(VT=a,b,d， VN=S， A， B， S,P)，其中 P为， SdAB AaA|a BbB| 该文法生成的语言是 (28)。 （ A） dambn|m0， nO （ B） dambn|m1， n0 （ C） dambn|m0， n1 （ D） dambn|m1， n1 13 已知文法 G2=(VT=a， ， ， (,)， VN=S， L)， S,P)，其中 P为 S(L)|a L -L， s|s 与 G2等价的不含左递归规则的文法是 (29)。 （ A） G21=(VT=a， ， ， (,)， VN=S， L， S， P)，其中 P为 S(L)|a LS ， S|S （ B） G2
8、2=(VT a， ， ， (,)， VN=S， L， L， S， P)，其中 P为 S(L)|a LSL LSL| （ C） G23=(VTa， ， ， (,)， VN=S， L， L， S， P)，其中 P为 S(L)|a LSL U,SL| （ D） G24=(VT=(a， ， ， (,)， VN= S， L， L， S， P)，其中 P为 S(L)|a LSL LSL|S 14 一个程序的控制流图是一个有向图，它的结点是程序中的 (30)。 （ A）语句 （ B）循环 （ C）基本块 （ D）函数 15 在一棵完全二叉树中，其根的序号为 1， (31)可判定序号为 p和 q的两个结点是否
9、在同一层。 （ A） log2p=log2p （ B） log2p=log2q （ C） log2p+1=log2p （ D） log2p=log2p+1 16 堆是一种数据结构， (32)是堆。 （ 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) 17 (33)从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。 （ A）
10、二叉排序树 （ B）大顶堆 （ C）小顶堆 （ D）平衡二叉树 18 若有广义表 L=(1， 2， 3)，则 L的 K度和深度分别为 (34)。 （ A） 1和 1 （ B） 1和 2 （ C） 1和 3 （ D） 2和 2 19 若对 27个元素只进行 3趟多路归并排序，则选 取的归并路数为 (35)。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 20 算术编码是 (36)。 （ A）有损数据压缩编码 （ B）无损数据压缩编码 （ C）不压缩数据的编码 （ D）通道 (或称信道 )编码 21 为适应网络带宽和降低存储器存储容量的要求，科技工作者开发了许多算法，用于压缩各种各样的数
11、据。假设处理系统的计算精度足够高，由此造成的数据损失可忽略。其中，正向离散小波变换 (FDWT)(37)。 （ A）对重构图像的质量有损失 （ B）对重构图像的质量没有损失 （ C）变换前后数据项的数目 不相等 （ D）变换前后的系数具有相同含义 22 CD-DA在多媒体的发展史上立下了不朽的功勋， 20世纪 80年代初就确定了声音采样频率为 44.1kHz，并且成为标准。问录制 74分钟的 CD-DA声音需要多少MB的存储空间 (按 1MB=10241024字节计算，不计文件格式本身所占用的空间。四舍五入取整数 )，所需存储容量为 (38)。 （ A） 747MB （ B） 374MB （
12、C） 783MB （ D）其他数值 23 假设有一台摄像机，它的扫描速率为 450行 /帧 520像素 /行 25帧 /秒，图像子采样格式 为 4:2:0。为节省存储空间，如果每个 Y信号量化为 8位每样本，而 Cr和Cb信号量化为 6位每样本。存储 10分钟这样的视像 (video)至少需要多少 (39)的磁盘容量 (1GB=102410241024字节 )。 （ A） 9.8GB （ B） 4.9GB （ C） 4.5GB （ D）其他数值 24 关系模型是用 (42)来表示和实现实体之间的关系。 （ A）层次结构 （ B）网状结构 （ C）指针链 （ D）表格的数据 25 一个具有单属性
13、键和 n(n 0)元组的关系，如果对这个关系的键属性做一个投影，那么投 影关系的基数是 (43)。 （ A） 1 （ B） （ C） n （ D） n2 26 关系模式 R(A， B， C)和 S(C， D， E)进行关系代数运算，下列关系表达式中成立的是 (44)。 （ A） （ B） （ C） （ D） 27 采用动态规划策略解决问题的显著特征是满足最优性原理，其含义是 (50)。 （ A）当前所做出的决策不会影响后面的决策 （ B）原问题的最优解包含其子问题的最优解 （ C）问题可以找到最优解，但利用贪心法不能找到最优解 （ D）每次决策必须是当前看来最优的决策才可以找到最优解 28 下
14、面函数中渐进时间最小的是 (51)。 （ A） T1(n)=n+nlogn （ B） T2(n)=2n/sup+nlogn （ C） T3(n)=n2-logn （ D） T4(n)=n+100logn 29 下面的程序段违反了算法的 (52)原则。 void sam() int n=2： while (!odd (n) n+=2； printf (n)； （ A）有穷 性 （ B）确定性 （ C）可行性 （ D）健壮性 30 拉斯维加斯 (Las Vegas)算法是一种常用的 (53)算法。 （ A）确定性 （ B）近似 （ C）概率 （ D）加密 31 在分支一限界算法设计策略中，通常采用
15、 (54)搜索问题的解空间。 （ A）深度优先 （ B）广度优先 （ C）自底向上 （ D）拓扑序列 32 传输延迟时间最小的交换方法是 (59)。 （ A）线路交换 （ B）报文交换 （ C）分组交换 （ D）信元交换 33 ATM采用的信元多路复用传输方式是 (60)。 （ A）异步时分复用 （ B）统计时分复用 （ C）同步时分复用 （ D）波分复用 34 Internet上常用简单的网络管理协议是 (65)。 （ A） CMIS （ B） CMIP （ C） SNMP （ D） Open View 35 实践证明这并不是提高计算机性能的最好方法，因为其中 80%的指令在程序中使用频度很
16、低。因而提出了另一种方案：简化指令的种类和格式，增加通用寄存器数目，使用 RR型指令格式，要求多数指令功能在一个机器周期内完成等，这种指令的计算机称为 (2)。 （ A） RISC （ B） CISC （ C） MIMD （ D） MIMD （ A） RISC （ B） CISC （ C） SISD （ D） SIMD 37 计算机对存储器的要求是速度快、容量大、价格低，主存储器是 CPU按照地址进行随机读写的存储器，主存的特点是 (3)，主有的最大容量与主存的地址位数有关， 64MB的主存，地址需要 (4)位 (二进制数 )。 （ A） CPU访问不同单元需要的时间不同 （ B） CPU访问
17、任何单元的速度相同 （ C） CPU访问地址小的单元，速度较快 （ D）访问时间不固定 （ A） 16 （ B） 24 （ C） 26 （ D） 34 39 计算机浮点数的表示中，可分为阶码和尾数两部分，如果某机阶码为 8位 (含1位符号位 )定点整数，用移码表示，其阶码最大正数是 (8)，最小负数是 (9)。 （ A） 1111111 （ B） 11111111 （ C） 10000000 （ D） 1 （ A） 10000000 （ B） 0 （ C） 1111111 （ D） 11111111 41 设计模式使人们可以更加简单方便地复用成功的设计和体系结构。将已证实的技术表述成设计模式也
18、会使新系统开发者更加容易理解其设计思路。一个模式有 4个基本要素，它们是 (48)，设计模式中的 Factory属于 (49)。 （ A）模式名称、问题、解决方案、效果 （ B）模式名称、来源、目的、实现方式 （ C）模式名称、结构、目的、实现方式 （ D）模式名称、问题、实现方式、备注 （ A）结构模式 （ B）创建模式 （ C）行为模式 （ D）抽象模式 43 消息摘要算法 MD5(Message Digest)是一种常用的 (57)。 MD5算法以一个任意长数据块作为输入，其输出为一个 (58)比特的消息摘要。 （ A）索引算法 （ B） Hash函数 （ C）递归函数 （ D）倒排算法
19、 （ A） 128 （ B） 160 （ C） 256 （ D） 512 45 传统的交换机作为第二层设备，只能识别并转发 (59)地址，要支持 VLAN间的通信只能借助于具有 (60)功能的网络设备。 （ A） IP （ B）网络 （ C）协议 （ D） MAC （ A）三层交换 （ B）通信交换 （ C）信元交换 （ D）线路交换 47 一个主机的 IP 地址是 172.20.50.17对应的子网掩码是 255.255.255.240，则所在的子网号是 (61)，子网的广播地址是 (62)。 （ A） 172.20.50.16 （ B） 172.20.50.32 （ C） 172.20.5
20、0.17 （ D） 172.20.50.31 （ A） 172.20.50.31 （ B） 172.20.50.16 （ C） 172.20.50.255 （ D） 172.20.50.252 49 设学生 S、课程 C、学生选课 SC的关系模式分别为： S(Sno， Sname， Sage， Saddr)、 C(Cno， Cname， Pcno)以及 SC(Sno， Cno， Grade)与关系代数表达式 Sno,Sname,Gr(Sname=数据库 (S|SC|C)等价的元组演算表达式为： (35)S(u) SC(v) C(w) (36) (37) （ A） （ B） （ C） （ D）
21、（ A） u1=v1 v1=w1 w1=数据库 （ B） u1=v2 v2=w1 w3=数据库 （ C） u1=v1 v2=w1 w2=数据库 （ D） u2=v2 v1=w2 w2=数据库 （ A） t1=u1 t2=u2 t3=v3 （ B） t1=u1 t2=u2 t3=v2 （ C） t1=u1 t2=w1 t3=v2 （ D） t1=u1 t2=w2 t3=v3 52 在设计算法时，通常应考虑以下原则：首先所设计的算法必须是 (23)，其次应有很好的 (24)，还必须具有 (25)，最后应考虑所设计的算法具有 (26)。 （ A）正确的 （ B）有穷性 （ C）有输入 （ D）用户需
22、求 （ A）有穷性 （ B）可读性 （ C）确定性 （ D）高效率与低存储量 （ A）有输入 （ B）确定性 （ C）健壮性 （ D）可读性 （ A）可读性 （ B）有输入 （ C）健壮性 （ D）高效率与低存储量 56 开发软件时对提高软件开发人员工作效率至关重要的是 (44)。软件工程中描述生存周期的瀑布模型一般包括计划、 (45)、设计、编码、测试、维护等几个阶段，其中设计阶段在管理上又可以依次分成 (46)和 (47)两步。 （ A）程序开发环境 （ B）操作系统的资源管理功能 （ C）程序人员数量， （ D）计算机的并行处理能力 （ A）需求分析 （ B）需求调查 （ C）可行性分析
23、 （ D）问题 定义 （ A）方案设计 （ B）代码设计 （ C）概要设计 （ D）数据设计 （ A）运行设计 （ B）详细设计 （ C）故障处理设计 （ D）软件体系结构设计 60 设有关系模式只 (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，
24、 R2， R3的规范化程度最高分别可达到 (37),(38),(39)。 （ A） (T， R) （ B） (J， C) （ C） (T， W) （ E） D （ A） 2NF （ B） 3NF （ C） BCNF （ D） 4NF （ A） 2NF （ B） 3NF （ C） BCNF （ D） 4NF （ A） 2NF （ B） 3NF （ C） BCNF （ D） 4NF （ A） 2NF （ B） 3NF （ C） BCNF （ D） 4NF 65 The CPU does not have to look(66)all of RAM to find the spot it needs
25、. But RAM only(67)the data temporarily. As soon as you switch the computer(68), all that information disappears from the RAM. When you switch the computer on again, the RAM is(69), and ready(70)a new program and new data. （ A） on （ B） through （ C） for （ D） down upon （ A） takes （ B） operates （ C） era
26、ses （ D） holds （ A） off （ B） on （ C） up （ D） down （ A） full （ B） empty （ C） zero （ D） blank （ A） receive （ B） be received （ C） receiving （ D） received 70 We know a computer is a machine that processes data(stored in main memory)into information, under control of a stored program. We also know that,
27、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 positional value significant. A computers main memory is divided into bytes, words or both(de
28、pending 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 instruction control unit, an arithmetic and logic unit, and registers. Once a program is stored in main
29、 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 electronic pulses generated by the clock drive this basic(75) （ A） a binary code （ B） words （ C） re
30、gisters （ D） positional values （ A） address （ B） value （ C） content （ D） register （ A） E-time （ B） I-time （ C） cycle time （ D） run time （ A） E-time （ B） I-time （ C） cycle time （ D） run time （ A） clock pulse （ B） instruction （ C） memory access （ D） machine cycle 软件水平考试（中级）软件设计师上午（基础知识）试 题模拟试卷 4答案与解析
31、1 【正确答案】 A 【试题解析】 计算机中的并行性是指在数值计算、数据处理过程中存在可同时进行运算或操作的各部分间的关系。并行性包括同时性和并发性两类，同时性指同一时刻发生的两个或多个事件，并发性指在同一时间间隔内发生的两个或多个事件，这些事件不一定是在同一时刻同时发生的。 2 【正确答案】 C 【试题解析】 计算机性能评价方法的基准法是使用基准测试程序 (Bench Mark)在各种计算机系统上运行，根据其运行结果及所用时间等，建立起各系统间相对性能比较的参数，作 为衡量计算机系统性能的指标。 3 【正确答案】 B 【试题解析】 软件测试方法分人工测试和机器测试。人工测试又称代码审查，主要
32、有 3种方法：个人审查、抽查、会审。机器测试分为白盒测试和黑盒测试。白盒测试又称为功能测试，黑盒测试又称为结构测试。软件测试可分为 4 步进行： (1)单元测试。 (2)组装测试 (3)确认测试。 (4)系统测试。其中，确认测试常用的有Alpha测试和 Beta测试。 4 【正确答案】 C 【试题解析】 结构化设计方法是一种面向数据流的设计方法，它可以与 SA方法衔接。结构化设计 方法的基本思想是将系统设计成由相对独立、功能单一的模块组成的结构。 5 【正确答案】 C 【试题解析】 在进行新旧系统转换以前，首先要进行新系统的试运行。在系统测试、调试中，人们使用的是系统测试数据，有些实际运行中可
33、能出现的问题，很难通过这些数据被发现。所以，一个系统开发后，让它实际运行一段时间，是对系统最好的检验和测试方法。新系统试运行成功之后，就可以在新系统和旧系统之间互相转换。新旧系统之间的转换方式有直接转换、并行转换和分段转换。 (1)直接转换。直接转换就是在确定新系统运行无误时，立刻启用新 系统，终止旧系统运行。这种方式对人员、设备费用很节省。这种方式一般适用于一些处理过程不太复杂、数据不很重要的场合。 (2)并行转换。这种转换方式是新旧系统并行工作一段时间，经过一段时间的考验以后，新系统正式替代旧系统。对于较复杂的大型系统，它提供了一个与旧系统运行结果进行比较的机会，可以对新旧两个系统的时间要
34、求、出错次数和工作效率给以公正的评价。当然由于与旧系统并行工作，消除了尚未认识新系统之前的紧张和不安。在银行、财务和一些企业的核心系统中，这是一种经常使用的转换方式。它的主要特点是安全、可靠，但费用和工作 量都很大，因为在相当长时间内系统要两套班子并行工作。 (3)分段转换。分段转换又称逐步转换、向导转换、试点过渡法等，这种转换方式实际上是以上两种转换方式的结合。 6 【正确答案】 A 【试题解析】 ISI 9000簇标准是国际标准化组织 (ISO)颁布的在全世界范围内通用的关于质量管理和质量保证方面的系列标准，目前已被 80多个国家等同或等效采用，该系列标准在全球具有广泛深刻的影响，有人称之
35、为 ISO 9000现象。ISO 1400是国际标准化组织第 207技术委员会 (TC 207)从 1993 年开始制定的系 列环境管理国际标准的总称，它同以往各国自定的环境排放标准和产品的技术标准不同，它是一个国际性标准，对全世界工业、商业、政府等所有组织针对改善环境管理行为具有统一标准的功能。它由环境管理体系 (EMS)、环境行为评价(EPE)、生命周期评估 (LCA)、环境管理 (EM)、产品标准中的环境因素 (EAPS)等 7个部分组成。 CMM是软件开发能力的成熟度模型 (SW-CMM)的简称，包括 5个成熟等级，开发的能力越强，开发组织的成熟度越高，等级越高。 7 【正确答案】 B
36、 【试题解析】 中华人民共和国反不正当竞争法中所称的商业秘密，是指不为公众所知悉、能为权利人带来经济利益。具有实用性并经权利人采取保密措施的技术信息和经营信息。据此，软件商业秘密的保护包括软件的技术秘密和经营秘密两项基本内容。 8 【正确答案】 B 【试题解析】 根据计算机软件保护条例第十四条第一款规定：软件著作权自软件开发完成之日起产生。同时，计算机软件保护条例第十四条第三款规定：法人或者其他组织享有软件的著作权，保护期限是 50年，截止到软件首次发表后第 50年的 12月 31 日，但软件 自开发完成之日起 50年内未发表的，本条例不再保护。这是对法人或者其他组织所享有软件的著作权的限制，
37、需要引起重视。 9 【正确答案】 C 【试题解析】 本题是考查信号量概念与 P、 V操作的实际运用，解决进程之间的同步与互斥问题。这个问题看起来是两对生产者与消费者组合的问题。由于进程P、 Q、 R存在着供给与消费的关系，这种关系体现了一种次序依赖关系。一方面，进程 Q必须等待进程 P接收到一批数据并将其放入缓冲区 K后才可以取来加工，进程 R必须等待进程 Q将一批数据加工完成并放入缓冲区 T 以后才可以取来打印；另一方面，进 程 P必须等待进程 Q取走缓冲区 K的数据后才能将下一批数据放入 K中，进程 Q必须等进程 R将缓冲区 T 的数据取走进行打印后才可以将加工好了的下一批数据放入 T 中
38、。但是，进程 P和 Q之间并没有直接的依赖关系。因此，系统呈现这样一种工作流程： 因此，进程 P和 Q之间存在两个同步条件，需要有两个信号量 S1和 S2来保证进程 P和Q的同步关系，它们的初值分别为 1和 0；进程 Q和 R之间也一样，需要有两个信号量 S1和 S2来保证它们的同步关系，初值也分别是 1和 0。 下图表示这 3个进程的工作流程。10 【正确答案】 D 【试题 解析】 本题考查的内容包括磁盘的组成与地址、工作方式以及最短查找时间优先的磁盘调度算法及其应用。磁盘由一叠其中心固定在一个旋转轴上的盘片和一组读写头 (磁头 )组成。每个磁盘片表面刻有呈同心圆状的磁道，磁道上涂有磁性物质
39、，因此可以记录数据；磁道沿半径方向顺序编号，不同盘片上相同编号的磁道组成一个虚拟的圆柱面，所以磁道编号又称为柱面号。给定柱面号就唯一确定了磁道。每个磁道被均匀地分为若干段 (中间可以有一定的空隙 )，这些段沿圆周方向顺序编号，沿半径方向，相同编号的磁段组成一个扇形，所有这些段又称为扇区。给定扇区号就 唯一确定了磁道上的磁段。一个磁盘有若干个盘片，现在的盘片都是双面的，即上下两面都可以记录数据，一般而言，顶上盘片的正面和最底盘片的背面不能记录数据。这些记录数据的盘片面沿一个方向编号，所以给定了盘面号就唯一确定了要访问的磁盘面。三元组小于柱面号，磁面号。扇区号大于唯一确定了磁盘的某个记录数据的磁段
40、。所有盘片的圆心固定在一个旋转轴上，所有盘片随着轴的旋转而高速旋转。为了读写数据，磁盘还有磁头，每个磁面对应一个磁头。当磁头对准磁道并接近它时，才能读写数据。磁盘分活动头磁盘和固定头磁盘两类。活动头磁盘的磁头数目与 盘面数量一样，它们分别固定在一根杆 (称为磁头臂 )的一头，磁头臂的数量与磁头数量相等，它的长度比盘片的半径略大。磁头臂的另一头固定在一根与旋转轴平行的轴上，该轴可以沿半径方向来回移动，以对准某个柱面，这个动作称为 “引臂 ”。磁盘片高速旋转，但磁头的移动速度较慢。当访问某个磁盘块时，需要给定柱面号、磁面号 (有时也叫磁道号 )和扇区号。第 1步要进行磁头引臂，使磁头对准给定的柱面
41、号；然后将与磁面号相同的磁头接近磁道，当磁盘片旋转到给定扇区时进行读写。整个过程中，磁头引臂最费时间。最短查找时间优先 (SSTF)算法适用于活 动头磁盘，目标在于尽可能缩短引臂时间。算法的实质是根据磁头的当前位置 (柱面号 )，调整磁盘访问申请序列，首先响应序列中柱面号最接近磁头当前位置的申请，以避免顺序响应时磁头可能不断地来回大幅度移动。但是，这种算法有可能引起某些申请无限等待：当接近磁头当前位置的申请源源不断地到来时，较远的申请有可能长时间得不到响应。本题中，离当前磁头位置最近的申请是 35， 18， 4，首先获得响应：此时，磁头位置变为 35，下一个响应的便是 45， 8， 6；接下去
42、是 20， 4， 10；然后向上，响应 100， 12， 6和 120， 4， 12。 11 【正确答案】 B 【试题解析】 对于任一正规表达式 R，可按如下方法构造出与之等价的非确定的有限自动机。 对于正规式 R，可用下图所示的拓广状态图表示。 通过对正规式 R进行分裂并加入新的结点，逐步把图转变成每条弧上的标记是 上的一个字符或 ，转换规则如下图所示。 最后所得的图即为一个 NFA M， x为初态结点， y为终态结点。显然， L(M)=L(R)。按照上述方法构造正规表达式 0*1(0|10*1)*的非确定的有限自动机的过程如下所示。12 【正确答案】 B 【试题解析 】 已知文法 G=(V
43、T， VN， S， P)，它所产生的语言定义如下：若有S(11)w，则称 w 是文法 G的一个句型。仅含终结符的句型是一个句子。语言 L(G)是由文法 G产生的所有句子组成的集合： L(G)=w|S w 且 w VT* 推导的定义如下： 设文法 G=(VT， VN， S， P)， A P， ， V*，则稀 A直接推导出，表示成 这个定义告诉我们，若知道 A V*，根据 A ，可求出 V*，方法是用 A 的右部 替换 A中的 A得到 ；相反，若知道 V*，根据 A P，可求出 A V*，方法是用 Ap 的左部 A替换 中的 得到 A。 若存在一个推导序列： ，则称从 a0经n 步推导出 an，表
44、示成 根据文法 G1 的第 1条规则 SdAB 知道，文法 G1 产生的句子的第 1个字符是 d，后跟着由 A产生的终结字符串，再后边跟着由 B 产生的终结字符串。根据文法 G1 的第 2条规则AaA|a 知道，由 A产生的终结字符串是 am|m1；根据 B的规则 BbB| 知道，由 B 产生的终结字符串是 bn|0。因此， L(G1)=dambn|m1， n0。 13 【正确答案】 C 【试题解析】 采用自顶向下的预测分析法首先是等价改写给定的文法，消除文法的左递归和提取产生式的公共左因子。 消除直接左递归的方法如下： 若AA| ，其中 ， (VT VN)*， 不以 A开始，则关于 A的这种
45、形式的产生式可改写成 AA AA| 一般而言，假设 A的产生式为 AA 1|A 2|A n|1|2|m 其中 I(i=1， 2， ， n)不等于 ， j(j=1， 2， ， m)不以 A开始，那么上述产生式可改成 A1 A|2 A|mA A1 A|2A| n A| 消除文法 G2 中规则的左递归后，其规则变成 S(L)|a LSL L ， SL| 14 【正确答案】 C 【试题解析】 优化是对中间代码进行优化，为了能进行优化，首先要分析清楚程序中的控制流程和数据流程。对于中间代码来说，基本块是控制流程简单的基本元素，它是一个顺序执行的语句 (四元式 )序列，其中只有一个入口和一个出口。控制流程
46、图能很好地表示程序中基本块之间的关系，对程序的控制流和数据流分析是在程序的控制流图上进行的，所以，构建中间代码的控制流图是编译程序对中间代码进行优化的第一步 。对编译生成的中间代码，首先划分成基本块，然后，对于程序中的两个基本块 Bi和 Bj，若 Bj紧接着 Bi被执行，则从 Bi引一条有向边到 Bj，称 Bi是 Bj的直接前驱，而 Bj是 Bi的直接后继。所以，一个程序的控制流图是个有向图，其结点是程序中的基本块，它有唯一的首结点。 15 【正确答案】 A 【试题解析】 同一层的结点都是 2的同一倍数。 16 【正确答案】 B 【试题解析】 可以自己恢复成堆： 10 18 15 20 50
47、80 30 60 17 【正确答案】 C 【试题解析】 小顶堆任何一部分的顶元素都是这部分的最小值。 18 【正确答案】 B 【试题解析】 显然 K度是 1，深度是 2。 19 【正确答案】 B 【试题解析】 33=27。 20 【正确答案】 B 【试题解析】 算术编码是给已知统计信息的符号分配代码的数据压缩方法，它使用 0和 1之间的实数的间隔长度表示信息，可获得接近于熵的平均码长，编码时对数据不会造成损失。通道编码 (channel coding)是将用户数据转换成适合存储或传输的代码。在物理存储器上存储数据或者在物理线路上传输数字信号时都需要对用户数据进行通道编码。采用通道编码的主要目的有两个：第一是为了改善信号质量，使得读出信号的频带变窄；第二是为了在接收端能够从信号本身提取自同步信号。 21 【正确答案】 B 【试题解析】 在图像数据压缩的计算中，假设处理系统的计算精度足够高，由此造成的数据损失可忽略的情况下，凡是数学变换 (Mathem
