[计算机类试卷]软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷3及答案与解析.doc

1、软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 3及答案与解析 1 高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是_。 （ A）语句 （ B）语义 （ C）语用 （ D）语法 2 下面的 C程序代码段在运行中会出现 _ 错误。 int i=0； while(i 10)； i=i+1； （ A）语法 （ B）类型不匹配 （ C）变量定义 （ D）动态语义 3 程序设计语言提供了基本类型及其相关的操作，而 _ 则允许开发者自定义一种新的类型 及其相关的操作。 （ A）对象 （ B）实例 （ C）类 （ D）引用 4 对于下面的文法 GS， _ 是其句子 (从 S

2、出发开始推导 )。 GS: SM (S， M)MP MP Pa b c . x x z （ A） (a， f) （ B） (fac,bb)， g （ C） (abc) （ D） c,(da) 5 与逆波兰式 ab+-c*d-对应的中缀表达式是 _。 （ A） a-b-c*d （ B） -(a+b)*c-d （ C） -a+b*c-d （ D） (a+b)*(-c-d) 6 编译程序进行词法分析时不能 _。 （ A）过滤源程序中的注释 （ B）扫描源程序并识别记号 （ C）指出出错行号 （ D）查出拼错的保留字 (关键字 ) 7 对于以下编号为 、 、 的正规式，正确的说法是 _。 (aa* a

3、b)*b (a b)*b (a b)* aa*b （ A）正规式 等价 （ B）正规式 等价 （ C）正规式 等价 （ D）正规式 互不等价 8 编译的优化工作对于下面程序段构造的控制流程图有 _个基本块 。（ A） 1 （ B） 2 （ C） 3 （ D） 4 9 文法 GS： SxSx y所描述的语言是 _ (n0)。 （ A） (xux)n （ B） xyxn （ C） xynx （ D） xnyxn 10 与正规式 (a b)*等价的正规式为 _。 （ A） a* b* （ B） a*b* （ C） (a*b*)* （ D） (ab)* 11 以下不属于算法的基本特征的是 (7)。穷举

4、法的适用范围是 (8)。 （ A）有确切定义的 （ B）可行的 （ C）可描述的 （ D）不能有二义性 （ A） 一切问题 （ B）解的个数极多的问题 （ C）解的个数不太多的问题 （ D）不适合设计算法 13 设求解某问题的递归算法如下： F(int n) if n=1 Move(1) else F(n-1)； Move(n)； F(n-1)； 求解该算法的计算时间时，仅考虑算法 Move所做的计算为主要计算，且 Move为常数级算法。则算法 F的计算时间 T(n)的递推关系式为 (9)；设算法 Move的计算时间为 k，当 n=4时，算法 F的计算时间为 (10)。 （ A） T(n)=T

5、(n-1)+1 （ B） T(n)=2T(n-1) （ C） T(n)=2T(n-1)+1 （ D） T(n)=2T(n+1)+1 （ A） 14k （ B） 15k （ C） 16k （ D） 17k 15 递归算法的执行过程，一般来说，可先后分成 (12)和 (13)两个阶段。 （ A）试探 （ B）递推 （ C）枚举 （ D）分析 （ A）回溯 （ B）回归 （ C）返回 （ D）合成 17 若一个问题的求解既可以用递归算法，也可 以用递推算法，则往往用 (14)算法，因为 (15)。 （ A）先递归后递推 （ B）先递推后递归 （ C）递归 （ D）递推 （ A）递推的效率比递归高 （

6、 B）递归宜于问题分解 （ C）递归的效率比递推高 （ D）递推宜于问题分解 19 在下列算法设计方法中， (16)在求解问题的过程中并不从整体最优上加以考虑，而是作出在当前看来是最好的选择。利用该设计方法可以解决 (17)问题。 （ A）分治法 （ B）贪心法 （ C）动态规划法 （ D）回溯法 （ A）排序 （ B）检索 （ C）背包 （ D） 0/1背 包 21 在数据压缩编码的应用中，哈夫曼 (Huffman)算法可以用来构造具有 (18)的二叉树，这是一种采用了 (19)的算法。 （ A）前缀码 （ B）最优前缀码 （ C）后缀码 （ D）最优后缀码 （ A）贪心 （ B）分治 （

7、C）递推 （ D）回溯 23 以关键字比较为基础的排序算法在最坏情况下的计算时间下界为 O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到 O(nlogn)的是 (21)，该算法采用的设计方法是 (22)。 （ A）归并排序 （ B）插入排序 （ C）选择排序 （ D）冒泡排序 （ A）分治法 （ B）贪心法 （ C）动态规划方法 （ D）回溯法 25 对于求取两个长度为 n的字符串的最长公共子序列 (LCS)问题，利用 (24)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为 O(n2)的正确算法。串 1， 0， 0， 1， O， 1， 0， 1和 0， 1， 0

8、， 1， 1,0,1， 1的最长公共子序列的长度为 (25)。 （ A）分治 （ B）贪心 （ C）动态规划 （ D）分支 限界 （ A） 3 （ B） 4 （ C） 5 （ D） 6 27 利用贪心法求解 0/1背包问题时， (26)能够确保获得最优解。用动态规划方求解O/1背包问题时，将 “用前 i个物品来装容量是 x的背包 ”的 0/1背包问题记为KNAP(1， i， X)设 fi(X)是 KNAP(1， i， X)最优解的效益值，第 j个物品的重量和放入背包后取得效益值分别为 W和 p(j=1 n)，则依次求解 f0(X)， f1(X)， ， fn(X)的过程中使用的递推关系式为 (2

9、7)。 （ A）优先选取重量最小的物品 （ B）优先选取效益最大的物品 （ C）优先选取单位重量效益最大的物品 （ D）没有任何准则 （ A） fi(X)=minfi-1(X),fi-1(X)+Pi （ B） fi(X)=maxfi-1(X),fi-1(X-Wi)+Pi （ C） fi(X)=minfi-1(X-Wi),fi-1(X-Wi)+Pi) （ D） fi(X)=maxfi-1(x-Wi),fi-1(X)+Pi 29 在某超市里有一个收银员，且同时最多允许有 n个顾客购物，我们可以将顾客和收银员看成是两类不同的进程，且工作流程如图 3-7所示。为了利用 PV操作正确地协调这两类进程之间

10、的工作，设置了三个信号量 S1， S2和 Sn，且初值分别为0， 0和 n。这样在图中的 a处应填 写 (13)，在图中的 b1， b2处应分别填写 (14)，在图中的 c1、 c2处应分别填写 (15)。 （ A） P(S1) （ B） P(S2) （ C） P(Sn) （ D） P(Sn)， P(S1) （ A） P(Sn)， V(S2) （ B） P(Sn)， V(S1) （ C） P(S2)， V(S1) （ D） V(S1)， P(S2) （ A） P(S1)， V(S2) （ B） P(Sn)， V(S1) （ C） P(S2)， V(S1) （ D） V(S1)， P(S2) 3

11、2 一台 PC计算机系统启动时，首先执行的是 (30)，然后加载 (31)。在设备管理中，虚拟设备的引入和实现是为了充分利用设备，提高系统效率，采用 (32)来模拟低速设备 (输入机或打印机 )的工作。 （ A）主引导记录 （ B）分区引导记录 （ C） BIOS引导程序 （ D）引导扇区 （ A）主引导记录和引导驱动器的分区表，并执行主引导记录 （ B）分区引导记录、配置系统，并执行分区引导记录 （ C）操作系统，如 Windows98/NT/2000/XP、 UNIX等 （ D）相关支撑软件 （ A） Spooling技术，利用磁带设备 （ B） Spooling技术，利用磁盘设备 （ C

12、）脱机批处理系统 （ D）移臂调度和旋转调度技术，利用磁盘设备 35 如图 3-12所示的树型文件中，方框表示目录，圆圈表示文件， “/”表示路径的分隔符， “/”在路径之首表示根目录。在图 3-12中， (34)。 假设当前目录是 D1，进程A以如下两种方式打开文件 f1。 方式 fd1=open(“(35)/f1“， o_ RDONLY)； 方式 fd1： =open(“/D1/W1/f1“， o_ RDONLY)； 其中，方式 的工作效率比方式 的工作效率高，因为采用方式 的文件系统 (36)。 （ A）子目录 W2中文件 f2和子目录 D2中文件 f2是完全相同的 （ B）子目录 W2

13、中文件 f2和了目录 D2中文件 f2是不相同的 （ C）子目录 W2中文件 f2和子目录 D2中文件 f2是可能相同也可能不相同的 （ D）树型文件系统中不允许出现相同名字的文件 （ A） /D1/W1 （ B） D1/W1 （ C） W1 （ D） f1 （ A）可以直接访问根目录下的文件 f1 （ B）可以从当前路径开始查找需要访问的文件 f1 （ C）只需要访问一次磁盘，就可以读取文件 f1，而方式 需要两次 （ D）只需要访问一次磁盘，就可以读取文件 f1，而方式 需要三次 38 被操作数的最高位移入 “进位 ”位，其余所有位接收其相邻低位值，最低位移入。的操作是 (17)指令。被操

14、作数的最高位保持不变，其余所有位接收其相邻高位值，最低位移到 “进位 ”位中的操作是 (18)指令。在程序执行过程中改变按程序计数器顺序读出指令的指令属于 (19)。相对寻址方式的实际地址是 (20)。特权指令在多用户、多任务的计算机系统中必不可少，它主要用于 (21)。 （ A）逻辑左移 （ B）算术左移 （ C）乘 2运算 （ D）除 2运算 （ A）逻辑左移 （ B）算术左移 （ C）乘 2运算 （ D）除 2运算 （ A）特权指令 （ B）传送指令 （ C）输入 /输出指令 （ D）转移指令 （ A）程序计数器的内容加上指令中形式地址值 （ B）基址寄存器的内容加上指令中形式地址值 （

15、 C）指令中形式地址中的内容 （ D）栈顶内容 （ A）检查用户的权限 （ B）系统硬件自检和配置 （ C）用户写汇编程序时调用 （ D）系统资源的分配和管理 43 直接存储器访问 (DMA)是一种快速传递大量数据常用的技术。工作过程大致如下。 (1)向 CPU申请 DMA传送。 (2)获 CPU允许后， DMA控制器接管 (22)的控制权。 (3)在 DMA控制器的控制下，在存储器和 (23)之间直接进行数据传送，在传送过程中不需要 (24)的参与。开始时需提供要传送的数据的 (25)和 (26)。 (4)传送结束后，向 CPU返回 DMA操作完成信号。 （ A）系统控制台 （ B）系统总线

16、 （ C） I/O控制器 （ D）中央处理器 （ A）外部设备 （ B）运算器 （ C）缓存 （ D）中央处理器 （ A）外部设备 （ B）系统时钟 （ C）系统总线 （ D）中央处理器 （ A）结束地址 （ B）起始地址 （ C）设备类型 （ D）数据 速率 （ A）结束地址 （ B）设备类型 （ C）数据长度 （ D）数据速率 48 计算机中常用的一种检错码是 CRC，即 (27)码。在进行编码的过程中要使用 (28)运算。假设使用的生成多项式是 G(13=X4/X3/X+1，原始报文为 11001010101，则编码后的报文为 (29)。 CRC码 (30)的说法是正确的。在无线电通信中

17、常采用 7中取3定比码，它规定码字长为 7位，并且其中总有且仅有 3个 “1”。这种码的编码效率为 (31)。 （ A）水平垂直奇偶校验 （ B）循环求和 （ C）循环冗余 （ D）正比率 （ A）模 2除法 （ B）定点二进制数除法 （ C）二一十进制数除法 （ D）循环移位法 （ A） 1100101010111 （ B） 110010101010011 （ C） 110010101011100 （ D） 110010101010101 （ A）可纠正一位差错 （ B）可检测所有偶数位错 （ C）可检测所有小于校验位长度的突发错 （ D）可检测所有小于、等于校验位长度的突发错 （ A） 3

18、/7 （ B） 4/7 （ C） log23/log27 （ D） (log235)/7 53 利用并行处理技术可以 缩短计算机的处理时间，所谓并行性是指 (48)。可以采用多种措施来提高计算机系统的并行性，它们可分成三类，即 (49)。提供专门用途的一类并行处理机 (亦称阵列处理机 )以 (50)方式工作，它适用于 (51)。多处理机是目前较高性能计算机的基本结构，它的并行任务的派生是 (52)。 （ A）多道程序工作 （ B）多用户工作 （ C）非单指令流单数据流方式工作 （ D）在同一时间完成两种或两种以上工作 （ A）多处理机，多级存储器和互联网络 （ B）流水结构，高速缓存和精简指令

19、集 （ C）微指令，虚拟存储和 I/O通道 （ D）资源重复，资源共享和时间重叠 （ A） SISD （ B） SIMD （ C） MISD （ D） MB4D （ A）事务处理 （ B）工业控制 （ C）矩阵运算 （ D）大量浮点计算 （ A）需要专门的指令来表示程序中并发关系和控制并发执行 （ B）靠指令本身就可以启动多个处理单元并行工作 （ C）只执行没有并发约束关系的程序 （ D）先并行执行，事后再用专门程序去解决并发约束 58 现采用四级流水线结构分别完成一条指令的取指、指令译码和取数、运算，以及送回运算结果四个基本操作，每步操作时间依次为 60ns， 100ns， 50ns和 70

20、ns，该流水线的操作周期应为 (53)。若有一小段程序需要用 20条基本指令完成 (这些指令完全适合于在流水线上执行 )，则得到第一条指令结果需 (54)ns，完成该段程序需(55)ns。在流水线结构的计算机中，频繁执行 (56)指令时会严重影响机器的效率。当有中断请求发生时，采用不精确断点法，则将 (57)。 （ A） 50 （ B） 70 （ C） 100 （ D） 280 （ A） 100 （ B） 200 （ C） 280 （ D） 400 （ A） 1400 （ B） 2000 （ C） 2300 （ D） 2600 （ A）条件转移 （ B）无条件转移 （ C）算术运算 （ D）访

21、问存储器 （ A）仅影响中断反应时间，不影响程序的正确执行 （ B）不仅影响中断反应时间，还影响程序的正确执行 （ C）不影响中断反应时间，但影响程序的正确执行 （ D）不影响中断反应时间，也不影响程序的正确执行 63 计算机执行程序所需的时间 P，可用 P=ICPIT来估计，其中 I是程序经编译后的机器指令数， CPI是执行每条指令所需的平均机器周期数， T为每个机器周期的时间。 RISC计算机采用 (58)来提高机器的速度。它的指 令系统具有 (59)的特点。指令控制部件的构建， (60)。 RISC机器又通过采用 (61)来加快处理器的数据处理速度。 RISC的指令集使编译优化工作 (6

22、2)。 （ A）虽增加 CPI，但更减少 T （ B）虽增加 T，但更减少 CPI （ C）虽增加 T，但更减少 CPI （ D）虽增加 I，但更减少 CPI （ A）指令种类少 （ B）指令种类多 （ C）指令寻址方式多 （ D）指令功能复杂 （ A） CISC更适于采用硬布线控制逻辑，而 RISC更适于采用微程序控制 （ B） CISC更适于采用微程序控制，而 RISC更适于采用 硬布线控制逻辑 （ C） CISC和 RISC都只采用微程序控制 （ D） CISC和 RISC都只采用硬布线控制逻辑 （ A）多寻址方式 （ B）大容量内存 （ C）大量的寄存器 （ D）更宽的数据总线 （ A

23、）更简单 （ B）更复杂 （ C）不需要 （ D）不可能 68 当存储器采用段页式管理时，主存被划分为定长的 (81)，程序按逻辑模块分成(82)。在某机器的多道程序环境下，每道程序还需要一个 (83)作为用户标识号，每道程序都有对应的 (84)。一个逻辑地址包括 (83)x、段号 s、页号 p和页内地址 d四个部分。 设逻辑地址长度分配如下，其中 x， s， p， d均以二进制数表示。其转换后的物理地址为 (86)。 （ A）段 （ B）页 （ C）区域 （ D）块 （ A）区域 （ B）页 （ C）块 （ D）段 （ A）模块号 （ B）区域号 （ C）基号 （ D）区域 （ A）一个段表

24、和一个页表 （ B）一个段表和一组页表 （ C）一组段表和一个页表 （ D）一组段表和一组页表 （ A） x220+s214+p211+d （ B） (x)+s+p+d （ C） (x)+s+p211+(d) （ D） (x)+s+p211+d 73 假设某计算机具有 1MB的内存 (目前使用的计算机往往具有 64MB以上的内存 )，并按字节编址，为了能存取该内存各地址的内容，其地址寄存器至少需要二进制 (86)位。为使 4字节组成的字能从存储器中一次读出，要求存放在存储器中的字边界对齐，一个字的地址码应 (87)。若存储周期为 200ns，且每个周期可访问 4字节，则该存储器带宽为 (88)

25、b/s。假如程序员可用的存储空间为 4MB，则程序员所用的地址为 (89)，而真正访问内存的地址称为 (90)。 （ A） 10 （ B） 16 （ C） 20 （ D） 32 （ A）最低两位为 00 （ B）最低两位为 10 （ C）最高两位为 00 （ D）最高两位为 10 （ A） 20M （ B） 40M （ C） 80M （ D） 160M （ A）有效地址 （ B）程序地址 （ C）逻辑地址 （ D）物理地址 （ A）指令 （ B）物理地址 （ C）内存地址 （ D）数据地址 78 用作存储器的芯片有不同的类型。 可随机读写，且只要不断电则其中存储的信息就可一直保存的，称为 (9

26、1)。 可随机读写，但即使在不断电的情况下其存储的信息也要定时刷新才不致 丢失的，称为 (92)。 所存信息由生产厂家用掩膜技术写好后就无法再改变的，称为 (93)。 通过紫外线照射后可擦除所有信息，然后重新写入新的信息并可多次进行的，称为 (94)。 通过电信号可在数秒钟内快速删除全部信息，但不能进行字节级别删除操作的，称为 (95)。 （ A） RAM （ B） VRAM （ C） DRAM （ D） SRAM （ A） RAM （ B） VRAM （ C） DRAM （ D） SRAM （ A） EPROM （ B） PROM （ C） ROM （ D） CDROM （ A） EPROM

27、 （ B） PROM （ C） ROM （ D） CDROM （ A） E2PROM （ B） Flash Memory （ C） EPROM （ D） Virtual Memory 83 虚拟存储器的作用是允许 (96)。它通常使用 (97)作为它的一个主要组成部分。对它的调度方法与 (98)基本相似，即把要经常访问的数据驻留在高速存储器中。因为使用了虚拟存储器，指令执行时 (99)。在虚拟存储系统中常使用相连存储器进行管理，它是 (100)寻址的。 （ A）直接使用外存代替内存 （ B）添加比地址字长允许的更多内存容量 （ C）程序直接访问比内存更大的地址空间 （ D）提高内存的访问速度

28、（ A） CDROM （ B）硬盘 （ C）软盘 （ D）寄存器 （ A） Cache （ B） DMA （ C） I/O （ D）中断 （ A）所需的数据一定能在内存中找到 （ B）必须先进行 “虚、实 ”地址转换 （ C）必须事先使用覆盖技术 （ D）必须将常用程序先调入内存 （ A）按地址 （ B）按内容 （ C）寄存器 （ D）计算 88 数字签名是一种网络安全技术，利用这种技术，接收者可以确定发送者的身份是否真实，同时发送者不能 (117)发 送的消息，接收者也不能 (118)接收的消息。Kerberos是一种分布式环境下的 (119)系统。为了防止重放攻击 (Replay)，它使用

29、了一次性的 (120)和时间戳。在公钥加密的情况下，用户必须警惕用于加密的公钥是否属于真正的接收者，为此必须使用数字证书。常用的数字证书格式有 (121)证书和 X.509证书。 （ A）泄露 （ B）隐藏 （ C）篡改 （ D）否认 （ A）泄露 （ B）否认 （ C）篡改 （ D）隐藏 （ A）数字签名 （ B）身份认证 （ C）数字证书 （ D）公钥加密 （ A） Key （ B） Certs （ C） MAC （ D） Ticket （ A） PGP （ B） SSL （ C） SHTTP （ D） SOCKS 93 发展容错技术可提高计算机系统的可靠性。利用元件冗余可保证在局部有故障

30、的情况下系统的正常工作。带有热备份的系统称为 (122)系统。它是 (123)，因此只要有一个子系统能正常工作，整个系统仍能正常工作。当子系统只能处于正常工作和不工作两种状态时，我们可以采用图 A的并联模型 (见图 1-21)，若单个子系统的可靠性都为 0.8，图示的三个子系统并联后的系统的可靠性为 (124)。当子系 统能处于正常和不正常状态时，我们可以采用图 B所示的表决模型 (见图 1-21)，若图中有任何二个或三个子系统输出相同，则选择该相同的输出作为系统输出。设单个子系统的可靠性为 0.8时，整个系统的可靠性为 (125)；若单个子系统的可靠性为0.5，整个系统的可靠性为 (126)

31、。（ A）并发 （ B）双工 （ C）双重 （ D）并行 （ A）两子系统同时同步运行，当联机子系统出错时，它退出服务，由备份系统接替 （ B）备份系统处于电源开机状态，一旦联机子系统出错，立即切换到备份系统 （ C）两子系统交替处于工作和自 检状态，当发现一子系统出错时，它不再交替到工作状态 （ D）两子系统并行工作，提高机器速度，一旦一个子系统出错，放弃并行工作 （ A） 0.9 （ B） 0.94 （ C） 0.992 （ D） 0.996 （ A） 0.882 （ B） 0.896 （ C） 0.925 （ D） 0.94 （ A） 0.5 （ B） 0.54 （ C） 0.62 （

32、D） 0.65 98 为提高数据传输的可靠性，可采用 “冗余校验 ”的方法；海明码是常用的方法之一。在此方法中，若要求能检测出所有的双位错，并能校正单位错，则合法码字集中的码距至少为 (127)。若原始数据的字长为 5位，则采用海明码时其校验位至少为 (128)位。对图 1-22的图 (a)所示系统，仅当部件 1，部件 2和部件 3，全部正常工作时，系统才能正常工作。图中数字为各部件的可靠性，整个系统的可靠性近似为 (129)。如果将部件 2和部件 3改成由两个器件构成，如图 (b)所示，只要器件 a和 b中有一个正常就能使部件 2正常工作，只要器件 c和 d中有一个正常就能使部件 3正常工作

33、。图中数字是各器件的可靠性，则部件 2的可靠性是 (130)，整个系统的可靠性近似为 (131)。（ A） 1 （ B） 2 （ C） 3 （ D） 4 （ A） 1 （ B） 2 （ C） 3 （ D） 4 （ A） 0.68 （ B） 0.72 （ C） 0.8 （ D） 0.92 （ A） 0.64 （ B） 0.88 （ C） 0.96 （ D） 0.99 （ A） 0.82 （ B） 0.9 （ C） 0.94 （ D） 0.96 103 Originally introduced by Netscape Communications,(1)are a general mechani

34、sm which HTFP Server side applications, such as CGI(2), can use to both store and retrieve information on the HTTP(3)side of the connection. Basically, Cookies can be used to compensate for the(4)nature of HTTP. The addition of a simple, persistent, client-side state significantly extends the capabi

35、lities of WWW-based(5). （ A） Browsers （ B） Cookies （ C） Connections （ D） Scripts （ A） graphics （ B） processes （ C） scripts （ D） texts （ A） Client （ B） Editor （ C） Creator （ D） Server （ A） fixed （ B） flexible （ C） stable （ D） stateless （ A） programs （ B） applications （ C） frameworks （ D） constraints

36、108 WebSQL is a SQL-like(6)language for extracting information from the web. Its capabilities for performing navigation of web(7)makes it a useful tool for automating several web-related tasks that require the systematic processing of either all the links in a(8), all the pages that can be reached from a given URL through(9)that match a pattern, or a combination of both. WebSQL also provides transparent access to index servers that can be queried via the Common(10)Interface. （ A） query （ B） transaction （ C） communication （ D） programming